lib/strnumcmp-in.h

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