wsutil/strnatcmp.c

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