xref: /PHP-5.3/ext/standard/strnatcmp.c (revision b3de24c9)
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;
113 
114 	ap = a;
115 	bp = b;
116 	while (1) {
117 		ca = *ap; cb = *bp;
118 
119 		/* skip over leading zeros */
120 		while (leading && ca == '0' && (ap+1 < aend) && isdigit(*(ap+1))) {
121 			ca = *++ap;
122 		}
123 
124 		while (leading && cb == '0' && (bp+1 < bend) && isdigit(*(bp+1))) {
125 			cb = *++bp;
126 		}
127 
128 		leading = 0;
129 
130 		/* Skip consecutive whitespace */
131 		while (isspace((int)(unsigned char)ca)) {
132 			ca = *++ap;
133 		}
134 
135 		while (isspace((int)(unsigned char)cb)) {
136 			cb = *++bp;
137 		}
138 
139 		/* process run of digits */
140 		if (isdigit((int)(unsigned char)ca)  &&  isdigit((int)(unsigned char)cb)) {
141 			fractional = (ca == '0' || cb == '0');
142 
143 			if (fractional)
144 				result = compare_left(&ap, aend, &bp, bend);
145 			else
146 				result = compare_right(&ap, aend, &bp, bend);
147 
148 			if (result != 0)
149 				return result;
150 			else if (ap == aend && bp == bend)
151 				/* End of the strings. Let caller sort them out. */
152 				return 0;
153 			else {
154 				/* Keep on comparing from the current point. */
155 				ca = *ap; cb = *bp;
156 			}
157 		}
158 
159 		if (fold_case) {
160 			ca = toupper((int)(unsigned char)ca);
161 			cb = toupper((int)(unsigned char)cb);
162 		}
163 
164 		if (ca < cb)
165 			return -1;
166 		else if (ca > cb)
167 			return +1;
168 
169 		++ap; ++bp;
170 		if (ap >= aend && bp >= bend)
171 			/* The strings compare the same.  Perhaps the caller
172 			   will want to call strcmp to break the tie. */
173 			return 0;
174 		else if (ap >= aend)
175 			return -1;
176 		else if (bp >= bend)
177 			return 1;
178 	}
179 }
180 /* }}} */
181 
182 /*
183  * Local variables:
184  * tab-width: 4
185  * c-basic-offset: 4
186  * End:
187  * vim600: sw=4 ts=4 fdm=marker
188  * vim<600: sw=4 ts=4
189  */
190