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  * This version is changed to ignore leading zeros, it does not equal to the
  33  * original software.
  34  */
  35
  36 #include <ctype.h>
  37 #include <string.h>
  38 #include <stdio.h>
  39
  40 #include "strnatcmp.h"
  41
  42 #define assert(x)   /* nothing */
  43
  44 /* Convert char to int regardless of whether char is signed or not */
  45 static inline int
  46 to_int(char c)
  47 {
  48     return (int) ((unsigned char) c);
  49 }
  50
  51 /* These are defined as macros to make it easier to adapt this code to
  52  * different characters types or comparison functions. */
  53 static inline int
  54 nat_isdigit(int a)
  55 {
  56      return isdigit(a);
  57 }
  58
  59
  60 static inline int
  61 nat_isspace(int a)
  62 {
  63      return a == '0' || isspace(a);
  64 }
  65
  66
  67 static inline int
  68 nat_toupper(int a)
  69 {
  70      return toupper(a);
  71 }
  72
  73
  74
  75 static int
  76 compare_right(char const *a, char const *b)
  77 {
  78      int bias = 0;
  79      int ca, cb;
  80
  81      /* The longest run of digits wins.  That aside, the greatest
  82         value wins, but we can't know that it will until we've scanned
  83         both numbers to know that they have the same magnitude, so we
  84         remember it in BIAS. */
  85      for (;; a++, b++) {
  86       ca = to_int(*a);
  87       cb = to_int(*b);
  88           if (!nat_isdigit(ca)  &&  !nat_isdigit(cb))
  89                return bias;
  90           else if (!nat_isdigit(ca))
  91                return -1;
  92           else if (!nat_isdigit(cb))
  93                return +1;
  94           else if (ca < cb) {
  95                if (!bias)
  96                     bias = -1;
  97           } else if (ca > cb) {
  98                if (!bias)
  99                     bias = +1;
 100           } else if (!ca  &&  !cb)
 101                return bias;
 102      }
 103
 104      return 0;
 105 }
 106
 107 static int strnatcmp0(char const *a, char const *b, int fold_case)
 108 {
 109      int ai, bi;
 110      int ca, cb;
 111      int result;
 112
 113      assert(a && b);
 114      ai = bi = 0;
 115      while (1) {
 116           ca = to_int(a[ai]);
 117       cb = to_int(b[bi]);
 118
 119           /* skip over leading spaces or zeros */
 120           while (nat_isspace(ca))
 121                ca = to_int(a[++ai]);
 122
 123           while (nat_isspace(cb))
 124                cb = to_int(b[++bi]);
 125
 126           /* process run of digits */
 127           if (nat_isdigit(ca)  &&  nat_isdigit(cb)) {
 128                 if ((result = compare_right(a+ai, b+bi)) != 0)
 129                         return result;
 130           }
 131
 132           if (!ca && !cb) {
 133                /* The strings compare the same.  Perhaps the caller
 134                   will want to call strcmp to break the tie. */
 135                return 0;
 136           }
 137
 138           if (fold_case) {
 139                ca = nat_toupper(ca);
 140                cb = nat_toupper(cb);
 141           }
 142
 143           if (ca < cb)
 144                return -1;
 145           else if (ca > cb)
 146                return +1;
 147
 148           ++ai; ++bi;
 149      }
 150 }
 151
 152
 153
 154 int strnatcmp(const char *a, const char *b) {
 155      return strnatcmp0(a, b, 0);
 156 }
 157
 158
 159 /* Compare, recognizing numeric string and ignoring case. */
 160 int strnatcasecmp(const char *a, const char *b) {
 161      return strnatcmp0(a, b, 1);
 162 }