lib/strnumcmp-in.h

   1 /* Compare numeric strings.  This is an internal include file.
   2
   3    Copyright (C) 1988, 1991-1993, 1995-1996, 1998-2000, 2003-2006, 2009-2011
   4    Free Software Foundation, Inc.
   5
   6    This program is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation, either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  18
  19 /* Written by Mike Haertel.  */
  20
  21 #ifndef STRNUMCMP_IN_H
  22 # define STRNUMCMP_IN_H 1
  23
  24 # include "strnumcmp.h"
  25
  26 # include <stddef.h>
  27
  28 # define NEGATION_SIGN   '-'
  29 # define NUMERIC_ZERO    '0'
  30
  31 /* ISDIGIT differs from isdigit, as follows:
  32    - Its arg may be any int or unsigned int; it need not be an unsigned char
  33      or EOF.
  34    - It's typically faster.
  35    POSIX says that only '0' through '9' are digits.  Prefer ISDIGIT to
  36    isdigit unless it's important to use the locale's definition
  37    of `digit' even when the host does not conform to POSIX.  */
  38 # define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9)
  39
  40
  41 /* Compare strings A and B containing decimal fractions < 1.
  42    DECIMAL_POINT is the decimal point.  Each string
  43    should begin with a decimal point followed immediately by the digits
  44    of the fraction.  Strings not of this form are treated as zero.  */
  45
  46 /* The goal here, is to take two numbers a and b... compare these
  47    in parallel.  Instead of converting each, and then comparing the
  48    outcome.  Most likely stopping the comparison before the conversion
  49    is complete.  The algorithm used, in the old "sort" utility:
  50
  51    Algorithm: fraccompare
  52    Action   : compare two decimal fractions
  53    accepts  : char *a, char *b
  54    returns  : -1 if a<b, 0 if a=b, 1 if a>b.
  55    implement:
  56
  57    if *a == decimal_point AND *b == decimal_point
  58      find first character different in a and b.
  59      if both are digits, return the difference *a - *b.
  60      if *a is a digit
  61        skip past zeros
  62        if digit return 1, else 0
  63      if *b is a digit
  64        skip past zeros
  65        if digit return -1, else 0
  66    if *a is a decimal_point
  67      skip past decimal_point and zeros
  68      if digit return 1, else 0
  69    if *b is a decimal_point
  70      skip past decimal_point and zeros
  71      if digit return -1, else 0
  72    return 0 */
  73
  74 static inline int _GL_ATTRIBUTE_PURE
  75 fraccompare (char const *a, char const *b, char decimal_point)
  76 {
  77   if (*a == decimal_point && *b == decimal_point)
  78     {
  79       while (*++a == *++b)
  80         if (! ISDIGIT (*a))
  81           return 0;
  82       if (ISDIGIT (*a) && ISDIGIT (*b))
  83         return *a - *b;
  84       if (ISDIGIT (*a))
  85         goto a_trailing_nonzero;
  86       if (ISDIGIT (*b))
  87         goto b_trailing_nonzero;
  88       return 0;
  89     }
  90   else if (*a++ == decimal_point)
  91     {
  92     a_trailing_nonzero:
  93       while (*a == NUMERIC_ZERO)
  94         a++;
  95       return ISDIGIT (*a);
  96     }
  97   else if (*b++ == decimal_point)
  98     {
  99     b_trailing_nonzero:
 100       while (*b == NUMERIC_ZERO)
 101         b++;
 102       return - ISDIGIT (*b);
 103     }
 104   return 0;
 105 }
 106
 107 /* Compare strings A and B as numbers without explicitly converting
 108    them to machine numbers, to avoid overflow problems and perhaps
 109    improve performance.  DECIMAL_POINT is the decimal point and
 110    THOUSANDS_SEP the thousands separator.  A DECIMAL_POINT of -1
 111    causes comparisons to act as if there is no decimal point
 112    character, and likewise for THOUSANDS_SEP.  */
 113
 114 static inline int _GL_ATTRIBUTE_PURE
 115 numcompare (char const *a, char const *b,
 116             int decimal_point, int thousands_sep)
 117 {
 118   unsigned char tmpa = *a;
 119   unsigned char tmpb = *b;
 120   int tmp;
 121   size_t log_a;
 122   size_t log_b;
 123
 124   if (tmpa == NEGATION_SIGN)
 125     {
 126       do
 127         tmpa = *++a;
 128       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep);
 129       if (tmpb != NEGATION_SIGN)
 130         {
 131           if (tmpa == decimal_point)
 132             do
 133               tmpa = *++a;
 134             while (tmpa == NUMERIC_ZERO);
 135           if (ISDIGIT (tmpa))
 136             return -1;
 137           while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
 138             tmpb = *++b;
 139           if (tmpb == decimal_point)
 140             do
 141               tmpb = *++b;
 142             while (tmpb == NUMERIC_ZERO);
 143           return - ISDIGIT (tmpb);
 144         }
 145       do
 146         tmpb = *++b;
 147       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
 148
 149       while (tmpa == tmpb && ISDIGIT (tmpa))
 150         {
 151           do
 152             tmpa = *++a;
 153           while (tmpa == thousands_sep);
 154           do
 155             tmpb = *++b;
 156           while (tmpb == thousands_sep);
 157         }
 158
 159       if ((tmpa == decimal_point && !ISDIGIT (tmpb))
 160           || (tmpb == decimal_point && !ISDIGIT (tmpa)))
 161         return fraccompare (b, a, decimal_point);
 162
 163       tmp = tmpb - tmpa;
 164
 165       for (log_a = 0; ISDIGIT (tmpa); ++log_a)
 166         do
 167           tmpa = *++a;
 168         while (tmpa == thousands_sep);
 169
 170       for (log_b = 0; ISDIGIT (tmpb); ++log_b)
 171         do
 172           tmpb = *++b;
 173         while (tmpb == thousands_sep);
 174
 175       if (log_a != log_b)
 176         return log_a < log_b ? 1 : -1;
 177
 178       if (!log_a)
 179         return 0;
 180
 181       return tmp;
 182     }
 183   else if (tmpb == NEGATION_SIGN)
 184     {
 185       do
 186         tmpb = *++b;
 187       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
 188       if (tmpb == decimal_point)
 189         do
 190           tmpb = *++b;
 191         while (tmpb == NUMERIC_ZERO);
 192       if (ISDIGIT (tmpb))
 193         return 1;
 194       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
 195         tmpa = *++a;
 196       if (tmpa == decimal_point)
 197         do
 198           tmpa = *++a;
 199         while (tmpa == NUMERIC_ZERO);
 200       return ISDIGIT (tmpa);
 201     }
 202   else
 203     {
 204       while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
 205         tmpa = *++a;
 206       while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
 207         tmpb = *++b;
 208
 209       while (tmpa == tmpb && ISDIGIT (tmpa))
 210         {
 211           do
 212             tmpa = *++a;
 213           while (tmpa == thousands_sep);
 214           do
 215             tmpb = *++b;
 216           while (tmpb == thousands_sep);
 217         }
 218
 219       if ((tmpa == decimal_point && !ISDIGIT (tmpb))
 220           || (tmpb == decimal_point && !ISDIGIT (tmpa)))
 221         return fraccompare (a, b, decimal_point);
 222
 223       tmp = tmpa - tmpb;
 224
 225       for (log_a = 0; ISDIGIT (tmpa); ++log_a)
 226         do
 227           tmpa = *++a;
 228         while (tmpa == thousands_sep);
 229
 230       for (log_b = 0; ISDIGIT (tmpb); ++log_b)
 231         do
 232           tmpb = *++b;
 233         while (tmpb == thousands_sep);
 234
 235       if (log_a != log_b)
 236         return log_a < log_b ? -1 : 1;
 237
 238       if (!log_a)
 239         return 0;
 240
 241       return tmp;
 242     }
 243 }
 244
 245 #endif