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 } 202