xref: /PHP-7.0/ext/standard/strnatcmp.c (revision b7a7b1a6)
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