1 /*
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 <stdio.h>
28
29 #include "php.h"
30 #include "php_string.h"
31
32 /* {{{ compare_right
33 */
34 static int
compare_right(char const ** a,char const * aend,char const ** b,char const * bend)35 compare_right(char const **a, char const *aend, char const **b, char const *bend)
36 {
37 int bias = 0;
38
39 /* The longest run of digits wins. That aside, the greatest
40 value wins, but we can't know that it will until we've scanned
41 both numbers to know that they have the same magnitude, so we
42 remember it in BIAS. */
43 for(;; (*a)++, (*b)++) {
44 if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
45 (*b == bend || !isdigit((int)(unsigned char)**b)))
46 return bias;
47 else if (*a == aend || !isdigit((int)(unsigned char)**a))
48 return -1;
49 else if (*b == bend || !isdigit((int)(unsigned char)**b))
50 return +1;
51 else if (**a < **b) {
52 if (!bias)
53 bias = -1;
54 } else if (**a > **b) {
55 if (!bias)
56 bias = +1;
57 }
58 }
59
60 return 0;
61 }
62 /* }}} */
63
64 /* {{{ compare_left
65 */
66 static int
compare_left(char const ** a,char const * aend,char const ** b,char const * bend)67 compare_left(char const **a, char const *aend, char const **b, char const *bend)
68 {
69 /* Compare two left-aligned numbers: the first to have a
70 different value wins. */
71 for(;; (*a)++, (*b)++) {
72 if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
73 (*b == bend || !isdigit((int)(unsigned char)**b)))
74 return 0;
75 else if (*a == aend || !isdigit((int)(unsigned char)**a))
76 return -1;
77 else if (*b == bend || !isdigit((int)(unsigned char)**b))
78 return +1;
79 else if (**a < **b)
80 return -1;
81 else if (**a > **b)
82 return +1;
83 }
84
85 return 0;
86 }
87 /* }}} */
88
89 /* {{{ strnatcmp_ex
90 */
strnatcmp_ex(char const * a,size_t a_len,char const * b,size_t b_len,int fold_case)91 PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case)
92 {
93 unsigned char ca, cb;
94 char const *ap, *bp;
95 char const *aend = a + a_len,
96 *bend = b + b_len;
97 int fractional, result;
98 short leading = 1;
99
100 if (a_len == 0 || b_len == 0) {
101 return (a_len == b_len ? 0 : (a_len > b_len ? 1 : -1));
102 }
103
104 ap = a;
105 bp = b;
106 while (1) {
107 ca = *ap; cb = *bp;
108
109 /* skip over leading zeros */
110 while (leading && ca == '0' && (ap+1 < aend) && isdigit((int)(unsigned char)*(ap+1))) {
111 ca = *++ap;
112 }
113
114 while (leading && cb == '0' && (bp+1 < bend) && isdigit((int)(unsigned char)*(bp+1))) {
115 cb = *++bp;
116 }
117
118 leading = 0;
119
120 /* Skip consecutive whitespace */
121 while (isspace((int)(unsigned char)ca)) {
122 ca = *++ap;
123 }
124
125 while (isspace((int)(unsigned char)cb)) {
126 cb = *++bp;
127 }
128
129 /* process run of digits */
130 if (isdigit((int)(unsigned char)ca) && isdigit((int)(unsigned char)cb)) {
131 fractional = (ca == '0' || cb == '0');
132
133 if (fractional)
134 result = compare_left(&ap, aend, &bp, bend);
135 else
136 result = compare_right(&ap, aend, &bp, bend);
137
138 if (result != 0)
139 return result;
140 else if (ap == aend && bp == bend)
141 /* End of the strings. Let caller sort them out. */
142 return 0;
143 else if (ap == aend)
144 return -1;
145 else if (bp == bend)
146 return 1;
147 else {
148 /* Keep on comparing from the current point. */
149 ca = *ap; cb = *bp;
150 }
151 }
152
153 if (fold_case) {
154 ca = toupper((int)(unsigned char)ca);
155 cb = toupper((int)(unsigned char)cb);
156 }
157
158 if (ca < cb)
159 return -1;
160 else if (ca > cb)
161 return +1;
162
163 ++ap; ++bp;
164 if (ap >= aend && bp >= bend)
165 /* The strings compare the same. Perhaps the caller
166 will want to call strcmp to break the tie. */
167 return 0;
168 else if (ap >= aend)
169 return -1;
170 else if (bp >= bend)
171 return 1;
172 }
173 }
174 /* }}} */
175
