wsutil/strnatcmp.c

   1 /* strnatcmp.c
   2  *
   3  * Original code downloaded from: http://sourcefrog.net/projects/natsort/
   4
   5   strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
   6   Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>
   7
   8   This software is provided 'as-is', without any express or implied
   9   warranty.  In no event will the authors be held liable for any damages
  10   arising from the use of this software.
  11
  12   Permission is granted to anyone to use this software for any purpose,
  13   including commercial applications, and to alter it and redistribute it
  14   freely, subject to the following restrictions:
  15
  16   1. The origin of this software must not be misrepresented; you must not
  17      claim that you wrote the original software. If you use this software
  18      in a product, an acknowledgment in the product documentation would be
  19      appreciated but is not required.
  20   2. Altered source versions must be plainly marked as such, and must not be
  21      misrepresented as being the original software.
  22   3. This notice may not be removed or altered from any source distribution.
  23 */
  24
  25
  26 /* partial change history:
  27  *
  28  * 2004-10-10 mbp: Lift out character type dependencies into macros.
  29  *
  30  * Eric Sosman pointed out that ctype functions take a parameter whose
  31  * value must be that of an unsigned int, even on platforms that have
  32  * negative chars in their default char type.
  33  */
  34
  35 /*
  36  * Modified 2014-10-29 to use the g_ascii_XXX() routines; this avoids
  37  * locale-dependent behavior.  The routine names were changed to
  38  * ws_ascii_XXX() to reflect this.
  39  */
  40
  41
  42 #include <glib.h>
  43
  44 #include "strnatcmp.h"
  45
  46
  47 /* These are defined as macros to make it easier to adapt this code to
  48  * different characters types or comparison functions. */
  49 static int
  50 nat_isdigit(nat_char a)
  51 {
  52     return g_ascii_isdigit(a);
  53 }
  54
  55
  56 static int
  57 nat_isspace(nat_char a)
  58 {
  59     return g_ascii_isspace(a);
  60 }
  61
  62
  63 static nat_char
  64 nat_toupper(nat_char a)
  65 {
  66     return g_ascii_toupper(a);
  67 }
  68
  69
  70 static int
  71 compare_right(nat_char const *a, nat_char const *b)
  72 {
  73     int bias = 0;
  74
  75     /* The longest run of digits wins.  That aside, the greatest
  76        value wins, but we can't know that it will until we've scanned
  77        both numbers to know that they have the same magnitude, so we
  78        remember it in BIAS. */
  79     for (;; a++, b++) {
  80         if (!nat_isdigit(*a)  &&  !nat_isdigit(*b))
  81             return bias;
  82         else if (!nat_isdigit(*a))
  83             return -1;
  84         else if (!nat_isdigit(*b))
  85             return +1;
  86         else if (*a < *b) {
  87             if (!bias)
  88                 bias = -1;
  89         } else if (*a > *b) {
  90             if (!bias)
  91                 bias = +1;
  92         } else if (!*a  &&  !*b)
  93             return bias;
  94     }
  95
  96     return 0;
  97 }
  98
  99
 100 static int
 101 compare_left(nat_char const *a, nat_char const *b)
 102 {
 103     /* Compare two left-aligned numbers: the first to have a
 104        different value wins. */
 105     for (;; a++, b++) {
 106         if (!nat_isdigit(*a)  &&  !nat_isdigit(*b))
 107             return 0;
 108         else if (!nat_isdigit(*a))
 109             return -1;
 110         else if (!nat_isdigit(*b))
 111             return +1;
 112         else if (*a < *b)
 113             return -1;
 114         else if (*a > *b)
 115             return +1;
 116     }
 117
 118     return 0;
 119 }
 120
 121
 122 static int strnatcmp0(nat_char const *a, nat_char const *b, int fold_case)
 123 {
 124     int ai, bi;
 125     nat_char ca, cb;
 126     int fractional, result;
 127
 128     if (!a || !b) {
 129         if (!a && !b)
 130             return 0;
 131         if (!a)
 132             return -1;
 133         return +1;
 134     }
 135     ai = bi = 0;
 136     while (1) {
 137         ca = a[ai]; cb = b[bi];
 138
 139         /* skip over leading spaces or zeros */
 140         while (nat_isspace(ca))
 141             ca = a[++ai];
 142
 143         while (nat_isspace(cb))
 144             cb = b[++bi];
 145
 146         /* process run of digits */
 147         if (nat_isdigit(ca)  &&  nat_isdigit(cb)) {
 148             fractional = (ca == '0' || cb == '0');
 149
 150             if (fractional) {
 151                 if ((result = compare_left(a+ai, b+bi)) != 0)
 152                     return result;
 153             } else {
 154                 if ((result = compare_right(a+ai, b+bi)) != 0)
 155                     return result;
 156             }
 157         }
 158
 159         if (!ca && !cb) {
 160             /* The strings compare the same.  Perhaps the caller
 161                will want to call strcmp to break the tie. */
 162             return 0;
 163         }
 164
 165         if (fold_case) {
 166             ca = nat_toupper(ca);
 167             cb = nat_toupper(cb);
 168         }
 169
 170         if (ca < cb)
 171             return -1;
 172         else if (ca > cb)
 173             return +1;
 174
 175         ++ai; ++bi;
 176     }
 177 }
 178
 179
 180 int ws_ascii_strnatcmp(nat_char const *a, nat_char const *b)
 181 {
 182     return strnatcmp0(a, b, 0);
 183 }
 184
 185
 186 /* Compare, recognizing numeric string and ignoring case. */
 187 int ws_ascii_strnatcasecmp(nat_char const *a, nat_char const *b)
 188 {
 189     return strnatcmp0(a, b, 1);
 190 }
 191
 192
 193 /*
 194  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 195  *
 196  * Local variables:
 197  * c-basic-offset: 4
 198  * tab-width: 8
 199  * indent-tabs-mode: nil
 200  * End:
 201  *
 202  * vi: set shiftwidth=4 tabstop=8 expandtab:
 203  * :indentSize=4:tabSize=8:noTabs=true:
 204  */
 205