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   SPDX-License-Identifier: Zlib
   9  */
  10
  11
  12 /* partial change history:
  13  *
  14  * 2004-10-10 mbp: Lift out character type dependencies into macros.
  15  *
  16  * Eric Sosman pointed out that ctype functions take a parameter whose
  17  * value must be that of an unsigned int, even on platforms that have
  18  * negative chars in their default char type.
  19  */
  20
  21 /*
  22  * Modified 2014-10-29 to use the g_ascii_XXX() routines; this avoids
  23  * locale-dependent behavior.  The routine names were changed to
  24  * ws_ascii_XXX() to reflect this.
  25  */
  26
  27 #include "strnatcmp.h"
  28
  29 #include <glib.h>
  30
  31 /* These are defined as macros to make it easier to adapt this code to
  32  * different characters types or comparison functions. */
  33 static int
  34 nat_isdigit(nat_char a)
  35 {
  36     return g_ascii_isdigit(a);
  37 }
  38
  39
  40 static int
  41 nat_isspace(nat_char a)
  42 {
  43     return g_ascii_isspace(a);
  44 }
  45
  46
  47 static nat_char
  48 nat_toupper(nat_char a)
  49 {
  50     return g_ascii_toupper(a);
  51 }
  52
  53
  54 static int
  55 compare_right(nat_char const *a, nat_char const *b)
  56 {
  57     int bias = 0;
  58
  59     /* The longest run of digits wins.  That aside, the greatest
  60        value wins, but we can't know that it will until we've scanned
  61        both numbers to know that they have the same magnitude, so we
  62        remember it in BIAS. */
  63     for (;; a++, b++) {
  64         if (!nat_isdigit(*a)  &&  !nat_isdigit(*b))
  65             return bias;
  66         else if (!nat_isdigit(*a))
  67             return -1;
  68         else if (!nat_isdigit(*b))
  69             return +1;
  70         else if (*a < *b) {
  71             if (!bias)
  72                 bias = -1;
  73         } else if (*a > *b) {
  74             if (!bias)
  75                 bias = +1;
  76         } else if (!*a  &&  !*b)
  77             return bias;
  78     }
  79
  80     return 0;
  81 }
  82
  83
  84 static int
  85 compare_left(nat_char const *a, nat_char const *b)
  86 {
  87     /* Compare two left-aligned numbers: the first to have a
  88        different value wins. */
  89     for (;; a++, b++) {
  90         if (!nat_isdigit(*a)  &&  !nat_isdigit(*b))
  91             return 0;
  92         else if (!nat_isdigit(*a))
  93             return -1;
  94         else if (!nat_isdigit(*b))
  95             return +1;
  96         else if (*a < *b)
  97             return -1;
  98         else if (*a > *b)
  99             return +1;
 100     }
 101
 102     return 0;
 103 }
 104
 105
 106 static int strnatcmp0(nat_char const *a, nat_char const *b, int fold_case)
 107 {
 108     int ai, bi;
 109     nat_char ca, cb;
 110     int fractional, result;
 111
 112     if (!a || !b) {
 113         if (!a && !b)
 114             return 0;
 115         if (!a)
 116             return -1;
 117         return +1;
 118     }
 119     ai = bi = 0;
 120     while (1) {
 121         ca = a[ai]; cb = b[bi];
 122
 123         /* skip over leading spaces or zeros */
 124         while (nat_isspace(ca))
 125             ca = a[++ai];
 126
 127         while (nat_isspace(cb))
 128             cb = b[++bi];
 129
 130         /* process run of digits */
 131         if (nat_isdigit(ca)  &&  nat_isdigit(cb)) {
 132             fractional = (ca == '0' || cb == '0');
 133
 134             if (fractional) {
 135                 if ((result = compare_left(a+ai, b+bi)) != 0)
 136                     return result;
 137             } else {
 138                 if ((result = compare_right(a+ai, b+bi)) != 0)
 139                     return result;
 140             }
 141         }
 142
 143         if (!ca && !cb) {
 144             /* The strings compare the same.  Perhaps the caller
 145                will want to call strcmp to break the tie. */
 146             return 0;
 147         }
 148
 149         if (fold_case) {
 150             ca = nat_toupper(ca);
 151             cb = nat_toupper(cb);
 152         }
 153
 154         if (ca < cb)
 155             return -1;
 156         else if (ca > cb)
 157             return +1;
 158
 159         ++ai; ++bi;
 160     }
 161 }
 162
 163
 164 int ws_ascii_strnatcmp(nat_char const *a, nat_char const *b)
 165 {
 166     return strnatcmp0(a, b, 0);
 167 }
 168
 169
 170 /* Compare, recognizing numeric string and ignoring case. */
 171 int ws_ascii_strnatcasecmp(nat_char const *a, nat_char const *b)
 172 {
 173     return strnatcmp0(a, b, 1);
 174 }
 175
 176
 177 /*
 178  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 179  *
 180  * Local variables:
 181  * c-basic-offset: 4
 182  * tab-width: 8
 183  * indent-tabs-mode: nil
 184  * End:
 185  *
 186  * vi: set shiftwidth=4 tabstop=8 expandtab:
 187  * :indentSize=4:tabSize=8:noTabs=true:
 188  */
 189