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 }