string/strcoll.c

   1 /* Copyright (C) 1995, 96, 97, 98, 99, 2000 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Written by Ulrich Drepper <drepper@cygnus.com>, 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 <assert.h>
  21 #include <langinfo.h>
  22 #include <stddef.h>
  23 #include <stdint.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #ifndef STRING_TYPE
  28 # define STRING_TYPE char
  29 # define USTRING_TYPE unsigned char
  30 # ifdef USE_IN_EXTENDED_LOCALE_MODEL
  31 #  define STRCOLL __strcoll_l
  32 # else
  33 #  define STRCOLL strcoll
  34 # endif
  35 # define STRCMP strcmp
  36 # define STRLEN strlen
  37 # define WEIGHT_H "../locale/weight.h"
  38 # define SUFFIX MB
  39 # define L(arg) arg
  40 #endif
  41
  42 #define CONCAT(a,b) CONCAT1(a,b)
  43 #define CONCAT1(a,b) a##b
  44
  45 #include "../locale/localeinfo.h"
  46
  47 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
  48 int
  49 STRCOLL (s1, s2)
  50      const STRING_TYPE *s1;
  51      const STRING_TYPE *s2;
  52 #else
  53 int
  54 STRCOLL (s1, s2, l)
  55      const STRING_TYPE *s1;
  56      const STRING_TYPE *s2;
  57      __locale_t l;
  58 #endif
  59 {
  60 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
  61   struct locale_data *current = l->__locales[LC_COLLATE];
  62   uint_fast32_t nrules = *((const uint32_t *) current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].string);
  63 #else
  64   uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
  65 #endif
  66   /* We don't assign the following values right away since it might be
  67      unnecessary in case there are no rules.  */
  68   const unsigned char *rulesets;
  69   const int32_t *table;
  70   const USTRING_TYPE *weights;
  71   const USTRING_TYPE *extra;
  72   const int32_t *indirect;
  73   uint_fast32_t pass;
  74   int result = 0;
  75   const USTRING_TYPE *us1;
  76   const USTRING_TYPE *us2;
  77   size_t s1len;
  78   size_t s2len;
  79   int32_t *idx1arr;
  80   int32_t *idx2arr;
  81   unsigned char *rule1arr;
  82   unsigned char *rule2arr;
  83   size_t idx1max;
  84   size_t idx2max;
  85   size_t idx1cnt;
  86   size_t idx2cnt;
  87   size_t idx1now;
  88   size_t idx2now;
  89   size_t backw1_stop;
  90   size_t backw2_stop;
  91   size_t backw1;
  92   size_t backw2;
  93   int val1;
  94   int val2;
  95   int position;
  96   int seq1len;
  97   int seq2len;
  98   int use_malloc;
  99
 100 #include WEIGHT_H
 101
 102   if (nrules == 0)
 103     return STRCMP (s1, s2);
 104
 105 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
 106   rulesets = (const unsigned char *)
 107     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
 108   table = (const int32_t *)
 109     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
 110   weights = (const USTRING_TYPE *)
 111     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
 112   extra = (const USTRING_TYPE *)
 113     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
 114   indirect = (const int32_t *)
 115     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
 116 #else
 117   rulesets = (const unsigned char *)
 118     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_RULESETS);
 119   table = (const int32_t *)
 120     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_TABLE,SUFFIX));
 121   weights = (const USTRING_TYPE *)
 122     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_WEIGHT,SUFFIX));
 123   extra = (const USTRING_TYPE *)
 124     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_EXTRA,SUFFIX));
 125   indirect = (const int32_t *)
 126     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_INDIRECT,SUFFIX));
 127 #endif
 128   use_malloc = 0;
 129
 130   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
 131   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
 132   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
 133   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
 134
 135   /* We need this a few times.  */
 136   s1len = STRLEN (s1);
 137   s2len = STRLEN (s2);
 138
 139   /* We need the elements of the strings as unsigned values since they
 140      are used as indeces.  */
 141   us1 = (const USTRING_TYPE *) s1;
 142   us2 = (const USTRING_TYPE *) s2;
 143
 144   /* Perform the first pass over the string and while doing this find
 145      and store the weights for each character.  Since we want this to
 146      be as fast as possible we are using `alloca' to store the temporary
 147      values.  But since there is no limit on the length of the string
 148      we have to use `malloc' if the string is too long.  We should be
 149      very conservative here.
 150
 151      Please note that the localedef programs makes sure that `position'
 152      is not used at the first level.  */
 153   if (s1len + s2len >= 16384)
 154     {
 155       idx1arr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
 156       idx2arr = &idx1arr[s2len];
 157       rule1arr = (unsigned char *) &idx2arr[s2len];
 158       rule2arr = &rule1arr[s1len];
 159
 160       if (idx1arr == NULL)
 161         /* No memory.  Well, go with the stack then.
 162
 163            XXX Once this implementation is stable we will handle this
 164            differently.  Instead of precomputing the indeces we will
 165            do this in time.  This means, though, that this happens for
 166            every pass again.  */
 167         goto try_stack;
 168       use_malloc = 1;
 169     }
 170   else
 171     {
 172     try_stack:
 173       idx1arr = (int32_t *) alloca (s1len * sizeof (int32_t));
 174       idx2arr = (int32_t *) alloca (s2len * sizeof (int32_t));
 175       rule1arr = (unsigned char *) alloca (s2len);
 176       rule2arr = (unsigned char *) alloca (s2len);
 177     }
 178
 179   idx1cnt = 0;
 180   idx2cnt = 0;
 181   idx1max = 0;
 182   idx2max = 0;
 183   idx1now = 0;
 184   idx2now = 0;
 185   backw1_stop = ~0ul;
 186   backw2_stop = ~0ul;
 187   backw1 = ~0ul;
 188   backw2 = ~0ul;
 189   seq1len = 0;
 190   seq2len = 0;
 191   position = rulesets[0] & sort_position;
 192   while (1)
 193     {
 194       val1 = 0;
 195       val2 = 0;
 196
 197       /* Get the next non-IGNOREd element for string `s1'.  */
 198       if (seq1len == 0)
 199         do
 200           {
 201             ++val1;
 202
 203             if (backw1_stop != ~0ul)
 204               {
 205                 /* The is something pushed.  */
 206                 if (backw1 == backw1_stop)
 207                   {
 208                     /* The last pushed character was handled.  Continue
 209                        with forward characters.  */
 210                     if (idx1cnt < idx1max)
 211                       idx1now = idx1cnt;
 212                     else
 213                       /* Nothing anymore.  The backward sequence ended with
 214                          the last sequence in the string.  Note that seq1len
 215                          is still zero.  */
 216                       break;
 217                   }
 218                 else
 219                   idx1now = --backw1;
 220               }
 221             else
 222               {
 223                 backw1_stop = idx1max;
 224
 225                 while (*us1 != L('\0'))
 226                   {
 227                     int32_t tmp = findidx (&us1);
 228                     rule1arr[idx1max] = tmp >> 24;
 229                     idx1arr[idx1max] = tmp & 0xffffff;
 230                     idx1cnt = idx1max++;
 231
 232                     if ((rulesets[rule1arr[idx1cnt] * nrules]
 233                          & sort_backward) == 0)
 234                       /* No more backward characters to push.  */
 235                       break;
 236                     ++idx1cnt;
 237                   }
 238
 239                 if (backw1_stop >= idx1cnt)
 240                   {
 241                     /* No sequence at all or just one.  */
 242                     if (idx1cnt == idx1max || backw1_stop > idx1cnt)
 243                       /* Note that seq1len is still zero.  */
 244                       break;
 245
 246                     backw1_stop = ~0ul;
 247                     idx1now = idx1cnt;
 248                   }
 249                 else
 250                   /* We pushed backward sequences.  */
 251                   idx1now = backw1 = idx1cnt - 1;
 252               }
 253           }
 254         while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
 255
 256       /* And the same for string `s2'.  */
 257       if (seq2len == 0)
 258         do
 259           {
 260             ++val2;
 261
 262             if (backw2_stop != ~0ul)
 263               {
 264                 /* The is something pushed.  */
 265                 if (backw2 == backw2_stop)
 266                   {
 267                     /* The last pushed character was handled.  Continue
 268                        with forward characters.  */
 269                     if (idx2cnt < idx2max)
 270                       idx2now = idx2cnt;
 271                     else
 272                       /* Nothing anymore.  The backward sequence ended with
 273                          the last sequence in the string.  Note that seq2len
 274                          is still zero.  */
 275                       break;
 276                   }
 277                 else
 278                   idx2now = --backw2;
 279               }
 280             else
 281               {
 282                 backw2_stop = idx2max;
 283
 284                 while (*us2 != L('\0'))
 285                   {
 286                     int32_t tmp = findidx (&us2);
 287                     rule2arr[idx2max] = tmp >> 24;
 288                     idx2arr[idx2max] = tmp & 0xffffff;
 289                     idx2cnt = idx2max++;
 290
 291                     if ((rulesets[rule2arr[idx2cnt] * nrules]
 292                          & sort_backward) == 0)
 293                       /* No more backward characters to push.  */
 294                       break;
 295                     ++idx2cnt;
 296                   }
 297
 298                 if (backw2_stop >= idx2cnt)
 299                   {
 300                     /* No sequence at all or just one.  */
 301                     if (idx2cnt == idx2max || backw2_stop > idx2cnt)
 302                       /* Note that seq1len is still zero.  */
 303                       break;
 304
 305                     backw2_stop = ~0ul;
 306                     idx2now = idx2cnt;
 307                   }
 308                 else
 309                   /* We pushed backward sequences.  */
 310                   idx2now = backw2 = idx2cnt - 1;
 311               }
 312           }
 313         while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
 314
 315       /* See whether any or both strings are empty.  */
 316       if (seq1len == 0 || seq2len == 0)
 317         {
 318           if (seq1len == seq2len)
 319             /* Both ended.  So far so good, both strings are equal at the
 320                first level.  */
 321             break;
 322
 323           /* This means one string is shorter than the other.  Find out
 324              which one and return an appropriate value.  */
 325           result = seq1len == 0 ? -1 : 1;
 326           goto free_and_return;
 327         }
 328
 329       /* Test for position if necessary.  */
 330       if (position && val1 != val2)
 331         {
 332           result = val1 - val2;
 333           goto free_and_return;
 334         }
 335
 336       /* Compare the two sequences.  */
 337       do
 338         {
 339           if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
 340             {
 341               /* The sequences differ.  */
 342               result = weights[idx1arr[idx1now]] - weights[idx2arr[idx2now]];
 343               goto free_and_return;
 344             }
 345
 346           /* Increment the offsets.  */
 347           ++idx1arr[idx1now];
 348           ++idx2arr[idx2now];
 349
 350           --seq1len;
 351           --seq2len;
 352         }
 353       while (seq1len > 0 && seq2len > 0);
 354
 355       if (position && seq1len != seq2len)
 356         {
 357           result = seq1len - seq2len;
 358           goto free_and_return;
 359         }
 360     }
 361
 362   /* Now the remaining passes over the weights.  We now use the
 363      indeces we found before.  */
 364   for (pass = 1; pass < nrules; ++pass)
 365     {
 366       /* We assume that if a rule has defined `position' in one section
 367          this is true for all of them.  */
 368       idx1cnt = 0;
 369       idx2cnt = 0;
 370       backw1_stop = ~0ul;
 371       backw2_stop = ~0ul;
 372       backw1 = ~0ul;
 373       backw2 = ~0ul;
 374       position = rulesets[rule1arr[0] * nrules + pass] & sort_position;
 375
 376       while (1)
 377         {
 378           val1 = 0;
 379           val2 = 0;
 380
 381           /* Get the next non-IGNOREd element for string `s1'.  */
 382           if (seq1len == 0)
 383             do
 384               {
 385                 ++val1;
 386
 387                 if (backw1_stop != ~0ul)
 388                   {
 389                     /* The is something pushed.  */
 390                     if (backw1 == backw1_stop)
 391                       {
 392                         /* The last pushed character was handled.  Continue
 393                            with forward characters.  */
 394                         if (idx1cnt < idx1max)
 395                           idx1now = idx1cnt;
 396                         else
 397                           {
 398                             /* Nothing anymore.  The backward sequence
 399                                ended with the last sequence in the string.  */
 400                             idx1now = ~0ul;
 401                             break;
 402                           }
 403                       }
 404                     else
 405                       idx1now = --backw1;
 406                   }
 407                 else
 408                   {
 409                     backw1_stop = idx1cnt;
 410
 411                     while (idx1cnt < idx1max)
 412                       {
 413                         if ((rulesets[rule1arr[idx1cnt] * nrules + pass]
 414                              & sort_backward) == 0)
 415                           /* No more backward characters to push.  */
 416                           break;
 417                         ++idx1cnt;
 418                       }
 419
 420                     if (backw1_stop == idx1cnt)
 421                       {
 422                         /* No sequence at all or just one.  */
 423                         if (idx1cnt == idx1max)
 424                           /* Note that seq2len is still zero.  */
 425                           break;
 426
 427                         backw1_stop = ~0ul;
 428                         idx1now = idx1cnt++;
 429                       }
 430                     else
 431                       /* We pushed backward sequences.  */
 432                       idx1now = backw1 = idx1cnt - 1;
 433                   }
 434               }
 435             while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
 436
 437           /* And the same for string `s2'.  */
 438           if (seq2len == 0)
 439             do
 440               {
 441                 ++val2;
 442
 443                 if (backw2_stop != ~0ul)
 444                   {
 445                     /* The is something pushed.  */
 446                     if (backw2 == backw2_stop)
 447                       {
 448                         /* The last pushed character was handled.  Continue
 449                            with forward characters.  */
 450                         if (idx2cnt < idx2max)
 451                           idx2now = idx2cnt;
 452                         else
 453                           {
 454                             /* Nothing anymore.  The backward sequence
 455                                ended with the last sequence in the string.  */
 456                             idx2now = ~0ul;
 457                             break;
 458                           }
 459                       }
 460                     else
 461                       idx2now = --backw2;
 462                   }
 463                 else
 464                   {
 465                     backw2_stop = idx2cnt;
 466
 467                     while (idx2cnt < idx2max)
 468                       {
 469                         if ((rulesets[rule2arr[idx2cnt] * nrules + pass]
 470                              & sort_backward) == 0)
 471                           /* No more backward characters to push.  */
 472                           break;
 473                         ++idx2cnt;
 474                       }
 475
 476                     if (backw2_stop == idx2cnt)
 477                       {
 478                         /* No sequence at all or just one.  */
 479                         if (idx2cnt == idx2max)
 480                           /* Note that seq2len is still zero.  */
 481                           break;
 482
 483                         backw2_stop = ~0ul;
 484                         idx2now = idx2cnt++;
 485                       }
 486                     else
 487                       /* We pushed backward sequences.  */
 488                       idx2now = backw2 = idx2cnt - 1;
 489                   }
 490               }
 491             while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
 492
 493           /* See whether any or both strings are empty.  */
 494           if (seq1len == 0 || seq2len == 0)
 495             {
 496               if (seq1len == seq2len)
 497                 /* Both ended.  So far so good, both strings are equal
 498                    at this level.  */
 499                 break;
 500
 501               /* This means one string is shorter than the other.  Find out
 502                  which one and return an appropriate value.  */
 503               result = seq1len == 0 ? -1 : 1;
 504               goto free_and_return;
 505             }
 506
 507           /* Test for position if necessary.  */
 508           if (position && val1 != val2)
 509             {
 510               result = val1 - val2;
 511               goto free_and_return;
 512             }
 513
 514           /* Compare the two sequences.  */
 515           do
 516             {
 517               if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
 518                 {
 519                   /* The sequences differ.  */
 520                   result = (weights[idx1arr[idx1now]]
 521                             - weights[idx2arr[idx2now]]);
 522                   goto free_and_return;
 523                 }
 524
 525               /* Increment the offsets.  */
 526               ++idx1arr[idx1now];
 527               ++idx2arr[idx2now];
 528
 529               --seq1len;
 530               --seq2len;
 531             }
 532           while (seq1len > 0 && seq2len > 0);
 533
 534           if (position && seq1len != seq2len)
 535             {
 536               result = seq1len - seq2len;
 537               goto free_and_return;
 538             }
 539         }
 540     }
 541
 542   /* Free the memory if needed.  */
 543  free_and_return:
 544   if (use_malloc)
 545     free (idx1arr);
 546
 547   return result;
 548 }