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