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 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 217 wcscoll(const wchar_t *ws1, const wchar_t *ws2) 218 { 219 return wcscoll_l(ws1, ws2, __get_locale()); 220 } 221