string/strcoll.c

   1 /* Copyright (C) 1995, 1996, 1997, 1998, 1999 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #include <endian.h>
  21 #include <stddef.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #ifndef STRING_TYPE
  27 # define STRING_TYPE char
  28 # define USTRING_TYPE unsigned char
  29 # ifdef USE_IN_EXTENDED_LOCALE_MODEL
  30 #  define STRCOLL __strcoll_l
  31 # else
  32 #  define STRCOLL strcoll
  33 # endif
  34 # define STRCMP strcmp
  35 #endif
  36
  37 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
  38 int
  39 STRCOLL (s1, s2)
  40      const STRING_TYPE *s1;
  41      const STRING_TYPE *s2;
  42 #else
  43 int
  44 STRCOLL (s1, s2, l)
  45      const STRING_TYPE *s1;
  46      const STRING_TYPE *s2;
  47      __locale_t l;
  48 #endif
  49 {
  50   return STRCMP (s1, s2);
  51 }
  52
  53 #if 0
  54 /* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
  55    these functions.  */
  56 #include "../locale/weight.h"
  57
  58
  59 /* Compare S1 and S2, returning less than, equal to or
  60    greater than zero if the collated form of S1 is lexicographically
  61    less than, equal to or greater than the collated form of S2.  */
  62 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
  63 int
  64 STRCOLL (s1, s2)
  65      const STRING_TYPE *s1;
  66      const STRING_TYPE *s2;
  67 #else
  68 int
  69 STRCOLL (s1, s2, l)
  70      const STRING_TYPE *s1;
  71      const STRING_TYPE *s2;
  72      __locale_t l;
  73 #endif
  74 {
  75 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
  76   struct locale_data *current = l->__locales[LC_COLLATE];
  77 # if BYTE_ORDER == BIG_ENDIAN
  78   const uint32_t *collate_table = (const uint32_t *)
  79     current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].string;
  80   const uint32_t *collate_extra = (const uint32_t *)
  81     current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].string;
  82 # elif BYTE_ORDER == LITTLE_ENDIAN
  83   const uint32_t *collate_table = (const uint32_t *)
  84     current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].string;
  85   const uint32_t *collate_extra = (const uint32_t *)
  86     current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].string;
  87 # else
  88 #  error bizarre byte order
  89 # endif
  90 #endif
  91   weight_t *s1forw = NULL;
  92   weight_t *s1backw = NULL;
  93   weight_t *s2forw = NULL;
  94   weight_t *s2backw = NULL;
  95   size_t pass;
  96
  97   /* If the current locale does not specify locale data we use normal
  98      8-bit string comparison.  */
  99   if (collate_nrules == 0)
 100     return STRCMP (s1, s2);
 101
 102   /* Handle empty strings as a special case.  */
 103   if (*s1 == '\0')
 104     return *s2 == '\0' ? 0 : -1;
 105   else if (*s2 == '\0')
 106     return 1;
 107
 108   /* Get full information about the strings.  This means we get
 109      information for all passes in a special data structure.  */
 110   get_string (s1, s1forw, s1backw);
 111   get_string (s2, s2forw, s2backw);
 112
 113   /* Now we have all the information.  In at most the given number of
 114      passes we can finally decide about the order.  */
 115   for (pass = 0; pass < collate_nrules; ++pass)
 116     {
 117       int forward = (collate_rules[pass] & sort_forward) != 0;
 118       const weight_t *s1run = forward ? s1forw : s1backw;
 119       const weight_t *s2run = forward ? s2forw : s2backw;
 120       int s1idx = forward ? 0 : s1run->data[pass].number - 1;
 121       int s2idx = forward ? 0 : s2run->data[pass].number - 1;
 122
 123       while (1)
 124         {
 125           int s1ignore = 0;
 126           int s2ignore = 0;
 127           uint32_t w1 = 0;
 128           uint32_t w2 = 0;
 129
 130           /* Here we have to check for IGNORE entries.  If these are
 131              found we count them and go on with the next value.  */
 132           while (s1run != NULL
 133                  && ((w1 = s1run->data[pass].value[s1idx])
 134                      == (uint32_t) IGNORE_CHAR))
 135             {
 136               ++s1ignore;
 137               if (forward
 138                   ? ++s1idx >= s1run->data[pass].number
 139                   : --s1idx < 0)
 140                 {
 141                   weight_t *nextp = forward ? s1run->next : s1run->prev;
 142                   if (nextp == NULL)
 143                     {
 144                       w1 = 0;
 145                       /* No more non-INGOREd elements means lowest
 146                          possible value.  */
 147                       s1ignore = -1;
 148                     }
 149                   else
 150                     s1idx = forward ? 0 : nextp->data[pass].number - 1;
 151                   s1run = nextp;
 152                 }
 153             }
 154
 155           while (s2run != NULL
 156                  && ((w2 = s2run->data[pass].value[s2idx])
 157                      == (uint32_t) IGNORE_CHAR))
 158             {
 159               ++s2ignore;
 160               if (forward
 161                   ? ++s2idx >= s2run->data[pass].number
 162                   : --s2idx < 0)
 163                 {
 164                   weight_t *nextp = forward ? s2run->next : s2run->prev;
 165                   if (nextp == NULL)
 166                     {
 167                       w2 = 0;
 168                       /* No more non-INGOREd elements means lowest
 169                          possible value.  */
 170                       s2ignore = -1;
 171                     }
 172                   else
 173                     s2idx = forward ? 0 : nextp->data[pass].number - 1;
 174                   s2run = nextp;
 175                 }
 176             }
 177
 178           /* If one string is completely processed stop.  */
 179           if (s1run == NULL || s2run == NULL)
 180             break;
 181
 182           /* Now we have information of the number of ignored
 183              weights and the value of the next weight.  */
 184           if ((collate_rules[pass] & sort_position) != 0
 185               && s1ignore != s2ignore && (w1 != 0 || w2 != 0))
 186             return s1ignore < s2ignore ? -1 : 1;
 187
 188           if (w1 != w2)
 189             return w1 < w2 ? -1 : 1;
 190
 191           /* We have to increment the index counters.  */
 192           if (forward)
 193             {
 194               if (++s1idx >= s1run->data[pass].number)
 195                 {
 196                   s1run = s1run->next;
 197                   s1idx = 0;
 198                 }
 199               if (++s2idx >= s2run->data[pass].number)
 200                 {
 201                   s2run = s2run->next;
 202                   s2idx = 0;
 203                 }
 204             }
 205           else
 206             {
 207               if (--s1idx < 0)
 208                 {
 209                   s1run = s1run->prev;
 210                   if (s1run != NULL)
 211                     s1idx = s1run->data[pass].number - 1;
 212                 }
 213               if (--s2idx < 0)
 214                 {
 215                   s2run = s2run->prev;
 216                   if (s2run != NULL)
 217                     s2idx = s2run->data[pass].number - 1;
 218                 }
 219             }
 220         }
 221
 222       if (s1run != s2run)
 223         return s1run != NULL ? 1 : -1;
 224     }
 225
 226   return 0;
 227 }
 228 #endif