firmware/common/strnatcmp.c

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