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 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   - It's guaranteed to evaluate its argument exactly once.
35   - It's typically faster.
36   POSIX says that only '0' through '9' are digits.  Prefer ISDIGIT to
37   ISDIGIT_LOCALE 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
75static inline int
76fraccompare (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
115static inline int
116numcompare (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
247