string/strcoll.c

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