1 : #define VSTR_CMP_C
2 : /*
3 : * Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 James Antill
4 : *
5 : * This library is free software; you can redistribute it and/or
6 : * modify it under the terms of the GNU Lesser General Public
7 : * License as published by the Free Software Foundation; either
8 : * version 2 of the License, or (at your option) any later version.
9 : *
10 : * This library 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 GNU
13 : * Lesser General Public License for more details.
14 : *
15 : * You should have received a copy of the GNU Lesser General Public
16 : * License along with this library; if not, write to the Free Software
17 : * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 : *
19 : * email: james@and.org
20 : */
21 : /* functions for comparing vstrs */
22 : #include "main.h"
23 :
24 : #define VSTR__CMP_DOUBLE_ITER_BEG(b1, p1, l1, i1, b2, p2, l2, i2) do { \
25 : int r1 = vstr_iter_fwd_beg(b1, p1, l1, i1); \
26 : int r2 = vstr_iter_fwd_beg(b2, p2, l2, i2); \
27 : if (!r1 && !r2) \
28 : return (0); \
29 : else if (!r1) \
30 : return (-1); \
31 : else if (!r2) \
32 : return (1); \
33 : \
34 : ASSERT((i1)->node && (i2)->node); \
35 : \
36 : } while (FALSE)
37 :
38 :
39 : /* compare 2 vector strings */
40 : int vstr_cmp(const Vstr_base *base_1, size_t pos_1, size_t len_1,
41 : const Vstr_base *base_2, size_t pos_2, size_t len_2)
42 844590 : {
43 844590 : Vstr_iter iter1[1];
44 844590 : Vstr_iter iter2[1];
45 :
46 844590 : VSTR__CMP_DOUBLE_ITER_BEG(base_1, pos_1, len_1, iter1,
47 : base_2, pos_2, len_2, iter2);
48 :
49 894075 : do
50 : {
51 894075 : size_t tmp = iter1->len;
52 894075 : if (tmp > iter2->len)
53 23330 : tmp = iter2->len;
54 :
55 894075 : assert(iter1->node && iter2->node);
56 :
57 894075 : if ((iter1->node->type != VSTR_TYPE_NODE_NON) &&
58 : (iter2->node->type != VSTR_TYPE_NODE_NON))
59 : {
60 893505 : int ret = vstr_wrap_memcmp(iter1->ptr, iter2->ptr, tmp);
61 893505 : if (ret)
62 825386 : return (ret);
63 68119 : iter1->ptr += tmp;
64 68119 : iter2->ptr += tmp;
65 : }
66 570 : else if (iter1->node->type != VSTR_TYPE_NODE_NON)
67 5 : return (1);
68 565 : else if (iter2->node->type != VSTR_TYPE_NODE_NON)
69 5 : return (-1);
70 :
71 68679 : iter1->len -= tmp;
72 68679 : iter2->len -= tmp;
73 :
74 68679 : assert(!iter1->len || !iter2->len);
75 :
76 68679 : } while ((iter1->len || vstr_iter_fwd_nxt(iter1)) &&
77 : (iter2->len || vstr_iter_fwd_nxt(iter2)) &&
78 : TRUE);
79 :
80 19138 : if (iter1->node)
81 60 : return (1);
82 19078 : if (vstr_iter_len(iter2))
83 60 : return (-1);
84 :
85 19018 : return (0);
86 : }
87 :
88 : /* compare with a "normal" C string */
89 : int vstr_cmp_buf(const Vstr_base *base, size_t pos, size_t len,
90 : const void *buf, size_t buf_len)
91 234118738 : {
92 234118738 : Vstr_iter iter[1];
93 :
94 234118738 : if (!vstr_iter_fwd_beg(base, pos, len, iter) && !buf_len)
95 430 : return (0);
96 234118308 : if (!iter->node)
97 15 : return (-1);
98 234118293 : if (!buf_len)
99 15 : return (1);
100 :
101 235490954 : do
102 : {
103 235490954 : int ret = 0;
104 :
105 235490954 : if (iter->len > buf_len)
106 : {
107 90 : iter->len = buf_len;
108 : /* make sure we know iter is bigger than buf */
109 90 : iter->remaining += 1;
110 : }
111 :
112 235490954 : if ((iter->node->type == VSTR_TYPE_NODE_NON) && buf)
113 37 : return (-1);
114 235490917 : if ((iter->node->type != VSTR_TYPE_NODE_NON) && !buf)
115 117 : return (1);
116 :
117 235490800 : if (buf)
118 : {
119 235314946 : if ((ret = vstr_wrap_memcmp(iter->ptr, buf, iter->len)))
120 229513250 : return (ret);
121 5801696 : buf = ((char *)buf) + iter->len;
122 : }
123 :
124 5977550 : buf_len -= iter->len;
125 5977550 : } while (buf_len && vstr_iter_fwd_nxt(iter));
126 :
127 4604874 : if (iter->remaining)
128 90 : return (1);
129 4604784 : if (buf_len)
130 90 : return (-1);
131 :
132 4604694 : return (0);
133 : }
134 :
135 : /* only do ASCII/binary case comparisons -- regardless of the OS/compiler
136 : * char set default */
137 : static int vstr__cmp_memcasecmp(const char *str1, const char *str2, size_t len)
138 141792 : {
139 470567 : while (len)
140 : {
141 428594 : unsigned char a = *str1;
142 428594 : unsigned char b = *str2;
143 :
144 428594 : if (VSTR__IS_ASCII_UPPER(a))
145 123491 : a = VSTR__TO_ASCII_LOWER(a);
146 428594 : if (VSTR__IS_ASCII_UPPER(b))
147 124184 : b = VSTR__TO_ASCII_LOWER(b);
148 :
149 428594 : if (a - b)
150 99819 : return (a - b);
151 :
152 328775 : ++str1;
153 328775 : ++str2;
154 328775 : --len;
155 : }
156 :
157 41973 : return (0);
158 : }
159 :
160 : /* don't include ASCII case when comparing */
161 : int vstr_cmp_case(const Vstr_base *base_1, size_t pos_1, size_t len_1,
162 : const Vstr_base *base_2, size_t pos_2, size_t len_2)
163 4779 : {
164 4779 : Vstr_iter iter1[1];
165 4779 : Vstr_iter iter2[1];
166 :
167 4779 : VSTR__CMP_DOUBLE_ITER_BEG(base_1, pos_1, len_1, iter1,
168 : base_2, pos_2, len_2, iter2);
169 :
170 5062 : do
171 : {
172 5062 : size_t tmp = iter1->len;
173 5062 : if (tmp > iter2->len)
174 3379 : tmp = iter2->len;
175 :
176 5062 : assert(iter1->node && iter2->node);
177 :
178 5062 : if ((iter1->node->type != VSTR_TYPE_NODE_NON) &&
179 : (iter2->node->type != VSTR_TYPE_NODE_NON))
180 : {
181 1527 : int ret = vstr__cmp_memcasecmp(iter1->ptr, iter2->ptr, tmp);
182 1527 : if (ret)
183 620 : return (ret);
184 907 : iter1->ptr += tmp;
185 907 : iter2->ptr += tmp;
186 : }
187 3535 : else if (iter1->node->type != VSTR_TYPE_NODE_NON)
188 3525 : return (1);
189 10 : else if (iter2->node->type != VSTR_TYPE_NODE_NON)
190 5 : return (-1);
191 :
192 912 : iter1->len -= tmp;
193 912 : iter2->len -= tmp;
194 :
195 912 : assert(!iter1->len || !iter2->len);
196 :
197 912 : } while ((iter1->len || vstr_iter_fwd_nxt(iter1)) &&
198 : (iter2->len || vstr_iter_fwd_nxt(iter2)) &&
199 : TRUE);
200 :
201 599 : if (iter1->node)
202 60 : return (1);
203 539 : if (vstr_iter_len(iter2))
204 60 : return (-1);
205 :
206 479 : return (0);
207 : }
208 :
209 : int vstr_cmp_case_buf(const Vstr_base *base, size_t pos, size_t len,
210 : const char *buf, size_t buf_len)
211 138902 : {
212 138902 : Vstr_iter iter[1];
213 :
214 138902 : if (!vstr_iter_fwd_beg(base, pos, len, iter) && !buf_len)
215 15 : return (0);
216 138887 : if (!iter->node)
217 15 : return (-1);
218 138872 : if (!buf_len)
219 15 : return (1);
220 :
221 140305 : do
222 : {
223 140305 : int ret = 0;
224 :
225 140305 : if (iter->len > buf_len)
226 : {
227 90 : iter->len = buf_len;
228 : /* make sure we know iter is bigger than buf */
229 90 : iter->remaining += 1;
230 : }
231 :
232 140305 : if ((iter->node->type == VSTR_TYPE_NODE_NON) && buf)
233 25 : return (-1);
234 140280 : if ((iter->node->type != VSTR_TYPE_NODE_NON) && !buf)
235 5 : return (1);
236 :
237 140275 : if (buf)
238 : {
239 140265 : if ((ret = vstr__cmp_memcasecmp(iter->ptr, buf, iter->len)))
240 99199 : return (ret);
241 41066 : buf += iter->len;
242 : }
243 :
244 41076 : buf_len -= iter->len;
245 41076 : } while (buf_len && vstr_iter_fwd_nxt(iter));
246 :
247 39628 : if (iter->remaining)
248 90 : return (1);
249 39538 : if (buf_len)
250 90 : return (-1);
251 :
252 39448 : return (0);
253 : }
254 :
255 : #define VSTR__CMP_BAD (-1)
256 :
257 : #define VSTR__CMP_NORM 0
258 : #define VSTR__CMP_NUMB 1
259 : #define VSTR__CMP_FRAC 2
260 :
261 : #define VSTR__CMP_NON_MAIN_LOOP 3
262 :
263 : #define VSTR__CMP_LEN_POS 4 /* return positive if scan_1 length is longer */
264 : #define VSTR__CMP_LEN_NEG 8 /* return negative if scan_1 length is longer */
265 : #define VSTR__CMP_DONE 9
266 :
267 : static int vstr__cmp_vers(const char *scan_str_1,
268 : const char *scan_str_2, size_t len,
269 : int state, int *difference)
270 1050 : {
271 1050 : int diff = 0;
272 :
273 6615 : while ((state < VSTR__CMP_NON_MAIN_LOOP) &&
274 : len && !(diff = *scan_str_1 - *scan_str_2))
275 : {
276 5565 : switch (state)
277 : {
278 : case VSTR__CMP_NORM:
279 4815 : if (VSTR__IS_ASCII_DIGIT(*scan_str_1))
280 725 : state = VSTR__CMP_NUMB;
281 4815 : if (*scan_str_1 == VSTR__ASCII_DIGIT_0())
282 : {
283 400 : assert(state == VSTR__CMP_NUMB);
284 400 : ++state;
285 400 : assert(state == VSTR__CMP_FRAC);
286 : }
287 370 : break;
288 : case VSTR__CMP_FRAC:
289 250 : if (VSTR__IS_ASCII_DIGIT(*scan_str_1) &&
290 : (*scan_str_1 != VSTR__ASCII_DIGIT_0()))
291 150 : state = VSTR__CMP_NUMB;
292 : case VSTR__CMP_NUMB:
293 750 : if (!VSTR__IS_ASCII_DIGIT(*scan_str_1))
294 50 : state = VSTR__CMP_NORM;
295 :
296 10 : ASSERT_NO_SWITCH_DEF();
297 : }
298 :
299 5565 : ++scan_str_1;
300 5565 : ++scan_str_2;
301 :
302 5565 : --len;
303 : }
304 :
305 1050 : if (diff)
306 : {
307 450 : int new_state = VSTR__CMP_BAD;
308 :
309 450 : assert(len);
310 :
311 450 : *difference = diff;
312 :
313 450 : switch (state)
314 : {
315 : case VSTR__CMP_NORM:
316 50 : if (VSTR__IS_ASCII_DIGIT(*scan_str_1) &&
317 : (*scan_str_1 != VSTR__ASCII_DIGIT_0()) &&
318 : VSTR__IS_ASCII_DIGIT(*scan_str_2) &&
319 : (*scan_str_2 != VSTR__ASCII_DIGIT_0()))
320 50 : state = VSTR__CMP_NUMB;
321 50 : break;
322 : case VSTR__CMP_FRAC:
323 : case VSTR__CMP_NUMB:
324 400 : if (!VSTR__IS_ASCII_DIGIT(*scan_str_1) &&
325 : !VSTR__IS_ASCII_DIGIT(*scan_str_2))
326 150 : state = VSTR__CMP_NORM;
327 :
328 30 : ASSERT_NO_SWITCH_DEF();
329 : }
330 :
331 450 : if (state == VSTR__CMP_NORM)
332 150 : return (VSTR__CMP_DONE);
333 :
334 300 : assert((state == VSTR__CMP_NUMB) ||
335 : (state == VSTR__CMP_FRAC));
336 :
337 : /* if a string is longer return positive or negative ignoring difference */
338 300 : new_state = state << 2;
339 :
340 300 : assert(((state == VSTR__CMP_NUMB) && (new_state == VSTR__CMP_LEN_POS)) ||
341 : ((state == VSTR__CMP_FRAC) && (new_state == VSTR__CMP_LEN_NEG)) ||
342 : FALSE);
343 :
344 300 : state = new_state;
345 : }
346 :
347 900 : if (state >= VSTR__CMP_NON_MAIN_LOOP)
348 : {
349 620 : assert((state == VSTR__CMP_LEN_POS) ||
350 : (state == VSTR__CMP_LEN_NEG));
351 :
352 700 : while (len &&
353 : VSTR__IS_ASCII_DIGIT(*scan_str_1) &&
354 : VSTR__IS_ASCII_DIGIT(*scan_str_2))
355 : {
356 400 : ++scan_str_1;
357 400 : ++scan_str_2;
358 :
359 400 : --len;
360 : }
361 :
362 300 : if (len)
363 : {
364 100 : assert((VSTR__CMP_LEN_POS + 1) < VSTR__CMP_LEN_NEG);
365 :
366 100 : if (VSTR__IS_ASCII_DIGIT(*scan_str_1))
367 50 : *difference = ((-state) + VSTR__CMP_LEN_POS + 1);
368 100 : if (VSTR__IS_ASCII_DIGIT(*scan_str_2))
369 50 : *difference = (state - VSTR__CMP_LEN_POS - 1);
370 : /* if both are the same length then use the initial stored difference */
371 :
372 100 : return (VSTR__CMP_DONE);
373 : }
374 : }
375 :
376 800 : return (state);
377 : }
378 :
379 : /* Compare strings while treating digits characters numerically. *
380 : * However digits starting with a 0 are clasified as fractional (Ie. 0.x)
381 : */
382 : int vstr_cmp_vers(const Vstr_base *base_1, size_t pos_1, size_t len_1,
383 : const Vstr_base *base_2, size_t pos_2, size_t len_2)
384 460 : {
385 460 : Vstr_iter iter1[1];
386 460 : Vstr_iter iter2[1];
387 460 : int state = VSTR__CMP_NORM;
388 460 : int ret = 0;
389 :
390 460 : VSTR__CMP_DOUBLE_ITER_BEG(base_1, pos_1, len_1, iter1,
391 : base_2, pos_2, len_2, iter2);
392 :
393 440 : do
394 : {
395 440 : size_t tmp = iter1->len;
396 440 : if (tmp > iter2->len)
397 100 : tmp = iter2->len;
398 :
399 440 : assert(iter1->node && iter2->node);
400 :
401 440 : if ((iter1->node->type != VSTR_TYPE_NODE_NON) &&
402 : (iter2->node->type != VSTR_TYPE_NODE_NON))
403 : {
404 425 : state = vstr__cmp_vers(iter1->ptr, iter2->ptr, tmp, state, &ret);
405 425 : if (state == VSTR__CMP_DONE)
406 100 : return (ret);
407 325 : iter1->ptr += tmp;
408 325 : iter2->ptr += tmp;
409 : }
410 15 : else if (iter1->node->type != VSTR_TYPE_NODE_NON)
411 5 : goto scan_1_longer;
412 10 : else if (iter2->node->type != VSTR_TYPE_NODE_NON)
413 5 : goto scan_2_longer;
414 :
415 330 : iter1->len -= tmp;
416 330 : iter2->len -= tmp;
417 :
418 330 : assert(!iter1->len || !iter2->len);
419 330 : } while ((iter1->len || vstr_iter_fwd_nxt(iter1)) &&
420 : (iter2->len || vstr_iter_fwd_nxt(iter2)) &&
421 : TRUE);
422 :
423 320 : if (iter1->node)
424 80 : goto scan_1_longer;
425 240 : if (vstr_iter_len(iter2))
426 80 : goto scan_2_longer;
427 :
428 160 : return (ret); /* same length, might have been different at a previous point */
429 :
430 : scan_1_longer:
431 85 : if ((state == VSTR__CMP_FRAC) || (state == VSTR__CMP_LEN_NEG))
432 30 : return (-1);
433 :
434 55 : assert((state == VSTR__CMP_NORM) || (state == VSTR__CMP_NUMB) ||
435 : (state == VSTR__CMP_LEN_POS));
436 55 : return (1);
437 :
438 : scan_2_longer:
439 85 : if ((state == VSTR__CMP_FRAC) || (state == VSTR__CMP_LEN_NEG))
440 30 : return (1);
441 :
442 55 : assert((state == VSTR__CMP_NORM) || (state == VSTR__CMP_NUMB) ||
443 : (state == VSTR__CMP_LEN_POS));
444 55 : return (-1);
445 : }
446 :
447 : int vstr_cmp_vers_buf(const Vstr_base *base, size_t pos, size_t len,
448 : const char *buf, size_t buf_len)
449 705 : {
450 705 : Vstr_iter iter[1];
451 705 : int state = VSTR__CMP_NORM;
452 705 : int ret = 0;
453 :
454 705 : if (!vstr_iter_fwd_beg(base, pos, len, iter) && !buf_len)
455 15 : return (0);
456 690 : if (!iter->node)
457 15 : return (-1);
458 675 : if (!buf_len)
459 15 : return (1);
460 :
461 660 : do
462 : {
463 660 : if (iter->len > buf_len)
464 : {
465 150 : iter->len = buf_len;
466 : /* make sure we know iter is bigger than buf */
467 150 : iter->remaining += 1;
468 : }
469 :
470 660 : if ((iter->node->type == VSTR_TYPE_NODE_NON) && buf)
471 25 : goto scan_2_longer;
472 635 : if ((iter->node->type != VSTR_TYPE_NODE_NON) && !buf)
473 5 : goto scan_1_longer;
474 :
475 630 : if (buf)
476 : {
477 625 : state = vstr__cmp_vers(iter->ptr, buf, iter->len, state, &ret);
478 625 : if (state == VSTR__CMP_DONE)
479 150 : return (ret);
480 475 : buf += iter->len;
481 : }
482 :
483 480 : buf_len -= iter->len;
484 480 : } while (buf_len && vstr_iter_fwd_nxt(iter));
485 :
486 480 : if (iter->remaining)
487 120 : goto scan_1_longer;
488 360 : if (buf_len)
489 120 : goto scan_2_longer;
490 :
491 240 : return (ret);
492 :
493 : scan_1_longer:
494 125 : if ((state == VSTR__CMP_FRAC) || (state == VSTR__CMP_LEN_NEG))
495 45 : return (-1);
496 :
497 80 : assert((state == VSTR__CMP_NORM) || (state == VSTR__CMP_NUMB) ||
498 : (state == VSTR__CMP_LEN_POS));
499 80 : return (1);
500 :
501 : scan_2_longer:
502 145 : if ((state == VSTR__CMP_FRAC) || (state == VSTR__CMP_LEN_NEG))
503 45 : return (1);
504 :
505 100 : assert((state == VSTR__CMP_NORM) || (state == VSTR__CMP_NUMB) ||
506 : (state == VSTR__CMP_LEN_POS));
507 100 : return (-1);
508 : }
509 :
|