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 static inline int
  62 nat_unify_case(int a)
  63 {
  64      /* We use 'tolower' and not 'toupper' so that '_' gets sorted
  65         before the letters */
  66      return tolower(a);
  67 }
  68
  69
  70
  71 static int
  72 compare_right(char const *a, char const *b)
  73 {
  74      int bias = 0;
  75      int ca, cb;
  76
  77      /* The longest run of digits wins.  That aside, the greatest
  78         value wins, but we can't know that it will until we've scanned
  79         both numbers to know that they have the same magnitude, so we
  80         remember it in BIAS. */
  81      for (;; a++, b++) {
  82       ca = to_int(*a);
  83       cb = to_int(*b);
  84           if (!nat_isdigit(ca)  &&  !nat_isdigit(cb))
  85                return bias;
  86           else if (!nat_isdigit(ca))
  87                return -1;
  88           else if (!nat_isdigit(cb))
  89                return +1;
  90           else if (ca < cb) {
  91                if (!bias)
  92                     bias = -1;
  93           } else if (ca > cb) {
  94                if (!bias)
  95                     bias = +1;
  96           } else if (!ca  &&  !cb)
  97                return bias;
  98      }
  99
 100      return 0;
 101 }
 102
 103
 104 static int
 105 compare_left(char const *a, char const *b)
 106 {
 107      /* Compare two left-aligned numbers: the first to have a
 108         different value wins. */
 109      for (;; a++, b++) {
 110           if (!nat_isdigit(*a)  &&  !nat_isdigit(*b))
 111                return 0;
 112           else if (!nat_isdigit(*a))
 113                return -1;
 114           else if (!nat_isdigit(*b))
 115                return +1;
 116           else if (*a < *b)
 117                return -1;
 118           else if (*a > *b)
 119                return +1;
 120      }
 121
 122      return 0;
 123 }
 124
 125 static int strnatcmp0(char const *a, char const *b, int fold_case)
 126 {
 127      int ai, bi;
 128      int ca, cb;
 129      int fractional, result;
 130
 131      assert(a && b);
 132      ai = bi = 0;
 133      while (1) {
 134       ca = to_int(a[ai]);
 135       cb = to_int(b[bi]);
 136
 137           /* process run of digits */
 138           if (nat_isdigit(ca)  &&  nat_isdigit(cb)) {
 139                fractional = (ca == '0' || cb == '0');
 140
 141                if (fractional) {
 142                     if ((result = compare_left(a+ai, b+bi)) != 0)
 143                          return result;
 144                } else {
 145                     if ((result = compare_right(a+ai, b+bi)) != 0)
 146                          return result;
 147                }
 148           }
 149
 150           if (!ca && !cb) {
 151                /* The strings compare the same.  Call str[case]cmp() to ensure
 152                   consistent results. */
 153                if(fold_case)
 154                    return strcasecmp(a,b);
 155                else
 156                    return strcmp(a,b);
 157           }
 158
 159           if (fold_case) {
 160                ca = nat_unify_case(ca);
 161                cb = nat_unify_case(cb);
 162           }
 163
 164           if (ca < cb)
 165                return -1;
 166           else if (ca > cb)
 167                return +1;
 168
 169           ++ai; ++bi;
 170      }
 171 }
 172
 173
 174
 175 int strnatcmp(const char *a, const char *b) {
 176      return strnatcmp0(a, b, 0);
 177 }
 178
 179
 180 /* Compare, recognizing numeric string and ignoring case. */
 181 int strnatcasecmp(const char *a, const char *b) {
 182      return strnatcmp0(a, b, 1);
 183 }