1 /* -*- mode: c; c-file-style: "k&r" -*-
2
3 Modified for PHP by Andrei Zmievski <andrei@ispi.net>
4
5 strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
6 Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
7
8 This software is provided 'as-is', without any express or implied
9 warranty. In no event will the authors be held liable for any damages
10 arising from the use of this software.
11
12 Permission is granted to anyone to use this software for any purpose,
13 including commercial applications, and to alter it and redistribute it
14 freely, subject to the following restrictions:
15
16 1. The origin of this software must not be misrepresented; you must not
17 claim that you wrote the original software. If you use this software
18 in a product, an acknowledgment in the product documentation would be
19 appreciated but is not required.
20 2. Altered source versions must be plainly marked as such, and must not be
21 misrepresented as being the original software.
22 3. This notice may not be removed or altered from any source distribution.
23 */
24
25 #include <ctype.h>
26 #include <string.h>
27 #include <assert.h>
28 #include <stdio.h>
29
30 #include "php.h"
31 #include "php_string.h"
32
33 #if defined(__GNUC__)
34 # define UNUSED __attribute__((__unused__))
35 #else
36 # define UNUSED
37 #endif
38
39 #if 0
40 static char const *version UNUSED =
41 "$Id$";
42 #endif
43 /* {{{ compare_right
44 */
45 static int
compare_right(char const ** a,char const * aend,char const ** b,char const * bend)46 compare_right(char const **a, char const *aend, char const **b, char const *bend)
47 {
48 int bias = 0;
49
50 /* The longest run of digits wins. That aside, the greatest
51 value wins, but we can't know that it will until we've scanned
52 both numbers to know that they have the same magnitude, so we
53 remember it in BIAS. */
54 for(;; (*a)++, (*b)++) {
55 if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
56 (*b == bend || !isdigit((int)(unsigned char)**b)))
57 return bias;
58 else if (*a == aend || !isdigit((int)(unsigned char)**a))
59 return -1;
60 else if (*b == bend || !isdigit((int)(unsigned char)**b))
61 return +1;
62 else if (**a < **b) {
63 if (!bias)
64 bias = -1;
65 } else if (**a > **b) {
66 if (!bias)
67 bias = +1;
68 }
69 }
70
71 return 0;
72 }
73 /* }}} */
74
75 /* {{{ compare_left
76 */
77 static int
compare_left(char const ** a,char const * aend,char const ** b,char const * bend)78 compare_left(char const **a, char const *aend, char const **b, char const *bend)
79 {
80 /* Compare two left-aligned numbers: the first to have a
81 different value wins. */
82 for(;; (*a)++, (*b)++) {
83 if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
84 (*b == bend || !isdigit((int)(unsigned char)**b)))
85 return 0;
86 else if (*a == aend || !isdigit((int)(unsigned char)**a))
87 return -1;
88 else if (*b == bend || !isdigit((int)(unsigned char)**b))
89 return +1;
90 else if (**a < **b)
91 return -1;
92 else if (**a > **b)
93 return +1;
94 }
95
96 return 0;
97 }
98 /* }}} */
99
100 /* {{{ strnatcmp_ex
101 */
strnatcmp_ex(char const * a,size_t a_len,char const * b,size_t b_len,int fold_case)102 PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case)
103 {
104 unsigned char ca, cb;
105 char const *ap, *bp;
106 char const *aend = a + a_len,
107 *bend = b + b_len;
108 int fractional, result;
109 short leading = 1;
110
111 if (a_len == 0 || b_len == 0) {
112 return (a_len == b_len ? 0 : (a_len > b_len ? 1 : -1));
113 }
114
115 ap = a;
116 bp = b;
117 while (1) {
118 ca = *ap; cb = *bp;
119
120 /* skip over leading zeros */
121 while (leading && ca == '0' && (ap+1 < aend) && isdigit((int)(unsigned char)*(ap+1))) {
122 ca = *++ap;
123 }
124
125 while (leading && cb == '0' && (bp+1 < bend) && isdigit((int)(unsigned char)*(bp+1))) {
126 cb = *++bp;
127 }
128
129 leading = 0;
130
131 /* Skip consecutive whitespace */
132 while (isspace((int)(unsigned char)ca)) {
133 ca = *++ap;
134 }
135
136 while (isspace((int)(unsigned char)cb)) {
137 cb = *++bp;
138 }
139
140 /* process run of digits */
141 if (isdigit((int)(unsigned char)ca) && isdigit((int)(unsigned char)cb)) {
142 fractional = (ca == '0' || cb == '0');
143
144 if (fractional)
145 result = compare_left(&ap, aend, &bp, bend);
146 else
147 result = compare_right(&ap, aend, &bp, bend);
148
149 if (result != 0)
150 return result;
151 else if (ap == aend && bp == bend)
152 /* End of the strings. Let caller sort them out. */
153 return 0;
154 else {
155 /* Keep on comparing from the current point. */
156 ca = *ap; cb = *bp;
157 }
158 }
159
160 if (fold_case) {
161 ca = toupper((int)(unsigned char)ca);
162 cb = toupper((int)(unsigned char)cb);
163 }
164
165 if (ca < cb)
166 return -1;
167 else if (ca > cb)
168 return +1;
169
170 ++ap; ++bp;
171 if (ap >= aend && bp >= bend)
172 /* The strings compare the same. Perhaps the caller
173 will want to call strcmp to break the tie. */
174 return 0;
175 else if (ap >= aend)
176 return -1;
177 else if (bp >= bend)
178 return 1;
179 }
180 }
181 /* }}} */
182
183 /*
184 * Local variables:
185 * tab-width: 4
186 * c-basic-offset: 4
187 * End:
188 * vim600: sw=4 ts=4 fdm=marker
189 * vim<600: sw=4 ts=4
190 */
191
