lib/strnumcmp-in.h

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