87a91c2fcd366abf0bd9dde32861bf79433f75ef
[dragonfly.git] / lib / libc / string / wcscoll.c
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
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
78                 /* special pass for UNDEFINED */
79                 if (pass == table->info->directive_count) {
80                         direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
81                 } else {
82                         direc = table->info->directive[pass];
83                 }
84
85                 if (direc & DIRECTIVE_BACKWARD) {
86                         wchar_t *bp, *fp, c;
87                         if ((tr1 = wcsdup(w1)) == NULL)
88                                 goto fail;
89                         bp = tr1;
90                         fp = tr1 + wcslen(tr1) - 1;
91                         while (bp < fp) {
92                                 c = *bp;
93                                 *bp++ = *fp;
94                                 *fp-- = c;
95                         }
96                         if ((tr2 = wcsdup(w2)) == NULL)
97                                 goto fail;
98                         bp = tr2;
99                         fp = tr2 + wcslen(tr2) - 1;
100                         while (bp < fp) {
101                                 c = *bp;
102                                 *bp++ = *fp;
103                                 *fp-- = c;
104                         }
105                         w1 = tr1;
106                         w2 = tr2;
107                 }
108
109                 if (direc & DIRECTIVE_POSITION) {
110                         while ((*w1 || st1) && (*w2 || st2)) {
111                                 pri1 = pri2 = 0;
112                                 _collate_lookup(table, w1, &len1, &pri1, pass,
113                                     &st1);
114                                 if (pri1 <= 0) {
115                                         if (pri1 < 0) {
116                                                 errno = EINVAL;
117                                                 goto fail;
118                                         }
119                                         pri1 = COLLATE_MAX_PRIORITY;
120                                 }
121                                 _collate_lookup(table, w2, &len2, &pri2, pass,
122                                     &st2);
123                                 if (pri2 <= 0) {
124                                         if (pri2 < 0) {
125                                                 errno = EINVAL;
126                                                 goto fail;
127                                         }
128                                         pri2 = COLLATE_MAX_PRIORITY;
129                                 }
130                                 if (pri1 != pri2) {
131                                         ret = pri1 - pri2;
132                                         goto end;
133                                 }
134                                 w1 += len1;
135                                 w2 += len2;
136                         }
137                 } else {
138                         while ((*w1 || st1) && (*w2 || st2)) {
139                                 pri1 = pri2 = 0;
140                                 while (*w1) {
141                                         _collate_lookup(table, w1, &len1,
142                                             &pri1, pass, &st1);
143                                         if (pri1 > 0)
144                                                 break;
145                                         if (pri1 < 0) {
146                                                 errno = EINVAL;
147                                                 goto fail;
148                                         }
149                                         w1 += len1;
150                                 }
151                                 while (*w2) {
152                                         _collate_lookup(table, w2, &len2,
153                                             &pri2, pass, &st2);
154                                         if (pri2 > 0)
155                                                 break;
156                                         if (pri2 < 0) {
157                                                 errno = EINVAL;
158                                                 goto fail;
159                                         }
160                                         w2 += len2;
161                                 }
162                                 if (!pri1 || !pri2)
163                                         break;
164                                 if (pri1 != pri2) {
165                                         ret = pri1 - pri2;
166                                         goto end;
167                                 }
168                                 w1 += len1;
169                                 w2 += len2;
170                         }
171                 }
172                 if (!*w1) {
173                         if (*w2) {
174                                 ret = -(int)*w2;
175                                 goto end;
176                         }
177                 } else {
178                         ret = *w1;
179                         goto end;
180                 }
181         }
182         ret = 0;
183
184 end:
185         if (tr1)
186                 free(tr1);
187         if (tr2)
188                 free(tr2);
189
190         return (ret);
191
192 fail:
193         ret = wcscmp(ws1, ws2);
194         goto end;
195 }
196
197 int
198 wcscoll(const wchar_t *ws1, const wchar_t *ws2)
199 {
200         return wcscoll_l(ws1, ws2, __get_locale());
201 }