Line data Source code
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 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
75 0 : fraccompare (char const *a, char const *b, char decimal_point)
76 : {
77 0 : if (*a == decimal_point && *b == decimal_point)
78 : {
79 0 : while (*++a == *++b)
80 0 : if (! ISDIGIT (*a))
81 0 : return 0;
82 0 : if (ISDIGIT (*a) && ISDIGIT (*b))
83 0 : return *a - *b;
84 0 : if (ISDIGIT (*a))
85 0 : goto a_trailing_nonzero;
86 0 : if (ISDIGIT (*b))
87 0 : goto b_trailing_nonzero;
88 0 : return 0;
89 : }
90 0 : else if (*a++ == decimal_point)
91 : {
92 0 : a_trailing_nonzero:
93 0 : while (*a == NUMERIC_ZERO)
94 0 : a++;
95 0 : return ISDIGIT (*a);
96 : }
97 0 : else if (*b++ == decimal_point)
98 : {
99 0 : b_trailing_nonzero:
100 0 : while (*b == NUMERIC_ZERO)
101 0 : b++;
102 0 : return - ISDIGIT (*b);
103 : }
104 0 : 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
115 0 : numcompare (char const *a, char const *b,
116 : int decimal_point, int thousands_sep)
117 : {
118 0 : unsigned char tmpa = *a;
119 0 : unsigned char tmpb = *b;
120 : int tmp;
121 : size_t log_a;
122 : size_t log_b;
123 :
124 0 : if (tmpa == NEGATION_SIGN)
125 : {
126 : do
127 0 : tmpa = *++a;
128 0 : while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep);
129 0 : if (tmpb != NEGATION_SIGN)
130 : {
131 0 : if (tmpa == decimal_point)
132 : do
133 0 : tmpa = *++a;
134 0 : while (tmpa == NUMERIC_ZERO);
135 0 : if (ISDIGIT (tmpa))
136 0 : return -1;
137 0 : while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
138 0 : tmpb = *++b;
139 0 : if (tmpb == decimal_point)
140 : do
141 0 : tmpb = *++b;
142 0 : while (tmpb == NUMERIC_ZERO);
143 0 : return - ISDIGIT (tmpb);
144 : }
145 : do
146 0 : tmpb = *++b;
147 0 : while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
148 :
149 0 : while (tmpa == tmpb && ISDIGIT (tmpa))
150 : {
151 : do
152 0 : tmpa = *++a;
153 0 : while (tmpa == thousands_sep);
154 : do
155 0 : tmpb = *++b;
156 0 : while (tmpb == thousands_sep);
157 : }
158 :
159 0 : if ((tmpa == decimal_point && !ISDIGIT (tmpb))
160 0 : || (tmpb == decimal_point && !ISDIGIT (tmpa)))
161 0 : return fraccompare (b, a, decimal_point);
162 :
163 0 : tmp = tmpb - tmpa;
164 :
165 0 : for (log_a = 0; ISDIGIT (tmpa); ++log_a)
166 : do
167 0 : tmpa = *++a;
168 0 : while (tmpa == thousands_sep);
169 :
170 0 : for (log_b = 0; ISDIGIT (tmpb); ++log_b)
171 : do
172 0 : tmpb = *++b;
173 0 : while (tmpb == thousands_sep);
174 :
175 0 : if (log_a != log_b)
176 0 : return log_a < log_b ? 1 : -1;
177 :
178 0 : if (!log_a)
179 0 : return 0;
180 :
181 0 : return tmp;
182 : }
183 0 : else if (tmpb == NEGATION_SIGN)
184 : {
185 : do
186 0 : tmpb = *++b;
187 0 : while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep);
188 0 : if (tmpb == decimal_point)
189 : do
190 0 : tmpb = *++b;
191 0 : while (tmpb == NUMERIC_ZERO);
192 0 : if (ISDIGIT (tmpb))
193 0 : return 1;
194 0 : while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
195 0 : tmpa = *++a;
196 0 : if (tmpa == decimal_point)
197 : do
198 0 : tmpa = *++a;
199 0 : while (tmpa == NUMERIC_ZERO);
200 0 : return ISDIGIT (tmpa);
201 : }
202 : else
203 : {
204 0 : while (tmpa == NUMERIC_ZERO || tmpa == thousands_sep)
205 0 : tmpa = *++a;
206 0 : while (tmpb == NUMERIC_ZERO || tmpb == thousands_sep)
207 0 : tmpb = *++b;
208 :
209 0 : while (tmpa == tmpb && ISDIGIT (tmpa))
210 : {
211 : do
212 0 : tmpa = *++a;
213 0 : while (tmpa == thousands_sep);
214 : do
215 0 : tmpb = *++b;
216 0 : while (tmpb == thousands_sep);
217 : }
218 :
219 0 : if ((tmpa == decimal_point && !ISDIGIT (tmpb))
220 0 : || (tmpb == decimal_point && !ISDIGIT (tmpa)))
221 0 : return fraccompare (a, b, decimal_point);
222 :
223 0 : tmp = tmpa - tmpb;
224 :
225 0 : for (log_a = 0; ISDIGIT (tmpa); ++log_a)
226 : do
227 0 : tmpa = *++a;
228 0 : while (tmpa == thousands_sep);
229 :
230 0 : for (log_b = 0; ISDIGIT (tmpb); ++log_b)
231 : do
232 0 : tmpb = *++b;
233 0 : while (tmpb == thousands_sep);
234 :
235 0 : if (log_a != log_b)
236 0 : return log_a < log_b ? -1 : 1;
237 :
238 0 : if (!log_a)
239 0 : return 0;
240 :
241 0 : return tmp;
242 : }
243 : }
244 :
245 : #endif
|
