1 /* Compare numeric strings. This is an internal include file.
2
3 Copyright (C) 1988-2023 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 <https://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 outside
110 'char' range 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