1 /*
2 * Copyright 2010 Nexenta Systems, Inc. All rights reserved.
3 * Copyright (c) 2002 Tim J. Robbins
4 * All rights reserved.
5 *
6 * Copyright (c) 2011 The FreeBSD Foundation
7 * All rights reserved.
8 * Portions of this software were developed by David Chisnall
9 * under sponsorship from the FreeBSD Foundation.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33 #include <errno.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <wchar.h>
37 #include "collate.h"
38
39 int
wcscoll_l(const wchar_t * ws1,const wchar_t * ws2,locale_t locale)40 wcscoll_l(const wchar_t *ws1, const wchar_t *ws2, locale_t locale)
41 {
42 int len1, len2, pri1, pri2, ret;
43 wchar_t *tr1 = NULL, *tr2 = NULL;
44 int direc, pass;
45
46 FIX_LOCALE(locale);
47 struct xlocale_collate *table =
48 (struct xlocale_collate*)locale->components[XLC_COLLATE];
49
50 if (table->__collate_load_error)
51 /*
52 * Locale has no special collating order or could not be
53 * loaded, do a fast binary comparison.
54 */
55 return (wcscmp(ws1, ws2));
56
57 ret = 0;
58
59 /*
60 * Once upon a time we had code to try to optimize this, but
61 * it turns out that you really can't make many assumptions
62 * safely. You absolutely have to run this pass by pass,
63 * because some passes will be ignored for a given character,
64 * while others will not. Simpler locales will benefit from
65 * having fewer passes, and most comparisions should resolve
66 * during the primary pass anyway.
67 *
68 * Note that we do one final extra pass at the end to pick
69 * up UNDEFINED elements. There is special handling for them.
70 */
71 for (pass = 0; pass <= table->info->directive_count; pass++) {
72
73 const int32_t *st1 = NULL;
74 const int32_t *st2 = NULL;
75 const wchar_t *w1 = ws1;
76 const wchar_t *w2 = ws2;
77 int check1, check2;
78
79 /* special pass for UNDEFINED */
80 if (pass == table->info->directive_count) {
81 direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
82 } else {
83 direc = table->info->directive[pass];
84 }
85
86 if (direc & DIRECTIVE_BACKWARD) {
87 wchar_t *bp, *fp, c;
88 if ((tr1 = wcsdup(w1)) == NULL)
89 goto fail;
90 bp = tr1;
91 fp = tr1 + wcslen(tr1) - 1;
92 while (bp < fp) {
93 c = *bp;
94 *bp++ = *fp;
95 *fp-- = c;
96 }
97 if ((tr2 = wcsdup(w2)) == NULL)
98 goto fail;
99 bp = tr2;
100 fp = tr2 + wcslen(tr2) - 1;
101 while (bp < fp) {
102 c = *bp;
103 *bp++ = *fp;
104 *fp-- = c;
105 }
106 w1 = tr1;
107 w2 = tr2;
108 }
109
110 if (direc & DIRECTIVE_POSITION) {
111 while (*w1 && *w2) {
112 pri1 = pri2 = 0;
113 check1 = check2 = 1;
114 while ((pri1 == pri2) && (check1 || check2)) {
115 if (check1) {
116 _collate_lookup(table, w1, &len1,
117 &pri1, pass, &st1);
118 if (pri1 < 0) {
119 errno = EINVAL;
120 goto fail;
121 }
122 if (!pri1) {
123 pri1 = COLLATE_MAX_PRIORITY;
124 st1 = NULL;
125 }
126 check1 = (st1 != NULL);
127 }
128 if (check2) {
129 _collate_lookup(table, w2, &len2,
130 &pri2, pass, &st2);
131 if (pri2 < 0) {
132 errno = EINVAL;
133 goto fail;
134 }
135 if (!pri2) {
136 pri2 = COLLATE_MAX_PRIORITY;
137 st2 = NULL;
138 }
139 check2 = (st2 != NULL);
140 }
141 }
142 if (pri1 != pri2) {
143 ret = pri1 - pri2;
144 goto end;
145 }
146 w1 += len1;
147 w2 += len2;
148 }
149 } else {
150 while (*w1 && *w2) {
151 pri1 = pri2 = 0;
152 check1 = check2 = 1;
153 while ((pri1 == pri2) && (check1 || check2)) {
154 while (check1 && *w1) {
155 _collate_lookup(table, w1,
156 &len1, &pri1, pass, &st1);
157 if (pri1 > 0)
158 break;
159 if (pri1 < 0) {
160 errno = EINVAL;
161 goto fail;
162 }
163 st1 = NULL;
164 w1 += 1;
165 }
166 check1 = (st1 != NULL);
167 while (check2 && *w2) {
168 _collate_lookup(table, w2,
169 &len2, &pri2, pass, &st2);
170 if (pri2 > 0)
171 break;
172 if (pri2 < 0) {
173 errno = EINVAL;
174 goto fail;
175 }
176 st2 = NULL;
177 w2 += 1;
178 }
179 check2 = (st2 != NULL);
180 if (!pri1 || !pri2)
181 break;
182 }
183 if (!pri1 || !pri2)
184 break;
185 if (pri1 != pri2) {
186 ret = pri1 - pri2;
187 goto end;
188 }
189 w1 += len1;
190 w2 += len2;
191 }
192 }
193 if (!*w1) {
194 if (*w2) {
195 ret = -(int)*w2;
196 goto end;
197 }
198 } else {
199 ret = *w1;
200 goto end;
201 }
202 }
203 ret = 0;
204
205 end:
206 free(tr1);
207 free(tr2);
208
209 return (ret);
210
211 fail:
212 ret = wcscmp(ws1, ws2);
213 goto end;
214 }
215
216 int
wcscoll(const wchar_t * ws1,const wchar_t * ws2)217 wcscoll(const wchar_t *ws1, const wchar_t *ws2)
218 {
219 return wcscoll_l(ws1, ws2, __get_locale());
220 }
221