locale/weight.h

   1 /* Copyright (C) 1996 Free Software Foundation, Inc.
   2 This file is part of the GNU C Library.
   3 Written by Ulrich Drepper, <drepper@gnu.ai.mit.edu>.
   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
  17 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18 Boston, MA 02111-1307, USA.  */
  19
  20 #include <alloca.h>
  21
  22
  23 #ifndef STRING_TYPE
  24 # error STRING_TYPE not defined
  25 #endif
  26
  27 #ifndef USTRING_TYPE
  28 # error USTRING_TYPE not defined
  29 #endif
  30
  31 typedef struct weight_t
  32 {
  33   struct weight_t *prev;
  34   struct weight_t *next;
  35   struct data_pair {
  36     size_t number;
  37     u32_t *value;
  38   } data[0];
  39 } weight_t;
  40
  41
  42 /* The following five macros grant access to the non-byte order
  43    dependend values in the collate locale file.  */
  44 #define collate_nrules \
  45   (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES))
  46 #define collate_hash_size \
  47   (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_HASH_SIZE))
  48 #define collate_hash_layers \
  49   (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_HASH_LAYERS))
  50 #define collate_undefined \
  51   (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_UNDEFINED))
  52 #define collate_rules \
  53   (_NL_CURRENT (LC_COLLATE, _NL_COLLATE_RULES))
  54
  55
  56 static __inline int get_weight (const STRING_TYPE **str, weight_t *result);
  57 static __inline int
  58 get_weight (const STRING_TYPE **str, weight_t *result)
  59 {
  60   unsigned int ch = *((USTRING_TYPE *) (*str))++;
  61   size_t slot;
  62
  63   if (sizeof (STRING_TYPE) == 1)
  64     slot = ch * (collate_nrules + 1);
  65   else
  66     {
  67       const size_t level_size = collate_hash_size * (collate_nrules + 1);
  68       size_t level;
  69
  70       slot = (ch * (collate_nrules + 1)) % collate_hash_size;
  71
  72       level = 0;
  73       while (__collate_table[slot] != (u32_t) ch)
  74         {
  75           if (__collate_table[slot + 1] == 0
  76               || ++level >= collate_hash_layers)
  77             {
  78               size_t idx = collate_undefined;
  79               size_t cnt;
  80
  81               for (cnt = 0; cnt < collate_nrules; ++cnt)
  82                 {
  83                   result->data[cnt].number = __collate_extra[idx++];
  84                   result->data[cnt].value = &__collate_extra[idx];
  85                   idx += result->data[cnt].number;
  86                 }
  87               return 0;
  88             }
  89           slot += level_size;
  90         }
  91     }
  92
  93   if (__collate_table[slot + 1] != FORWARD_CHAR)
  94     {
  95       /* We have a simple form.  One one value for each weight.  */
  96       size_t cnt;
  97
  98       for (cnt = 0; cnt < collate_nrules; ++cnt)
  99         {
 100           result->data[cnt].number = 1;
 101           result->data[cnt].value = &__collate_table[slot + 1 + cnt];
 102         }
 103       return ch == 0;
 104     }
 105
 106   /* We now look for any collation element which starts with CH.
 107      There might none, but the last list member is a catch-all case
 108      because it is simple the character CH.  The value of this entry
 109      might be the same as UNDEFINED.  */
 110   slot = __collate_table[slot + 2];
 111
 112   while (1)
 113     {
 114       size_t idx;
 115
 116       /* This is a comparison between a u32_t array (aka wchar_t) and
 117          an 8-bit string.  */
 118       for (idx = 0; __collate_extra[slot + 2 + idx] != 0; ++idx)
 119         if (__collate_extra[slot + 2 + idx] != (u32_t) str[idx])
 120           break;
 121
 122       /* When the loop finished with all character of the collation
 123          element used, we found the longest prefix.  */
 124       if (__collate_extra[slot + 2 + idx] == 0)
 125         {
 126           size_t cnt;
 127
 128           idx += slot + 3;
 129           for (cnt = 0; cnt < collate_nrules; ++cnt)
 130             {
 131               result->data[cnt].number = __collate_extra[idx++];
 132               result->data[cnt].value = &__collate_extra[idx];
 133               idx += result->data[cnt].number;
 134             }
 135           return 0;
 136         }
 137
 138       /* To next entry in list.  */
 139       slot += __collate_extra[slot];
 140     }
 141   /* NOTREACHED */
 142   return 0;     /* To calm down gcc.  */
 143 }
 144
 145
 146 /* To process a string efficiently we retrieve all information about
 147    the string at once.  The following macro constructs a double linked
 148    list of this information.  It is a macro because we use `alloca'
 149    and we use a double linked list because of the backward collation
 150    order.  */
 151 #define get_string(str, forw, backw)                                          \
 152   do                                                                          \
 153     {                                                                         \
 154       weight_t *newp;                                                         \
 155       do                                                                      \
 156         {                                                                     \
 157           newp = (weight_t *) alloca (sizeof (weight_t)                       \
 158                                       + (collate_nrules                       \
 159                                          * sizeof (struct data_pair)));       \
 160                                                                               \
 161           newp->prev = backw;                                                 \
 162           if (backw == NULL)                                                  \
 163             forw = newp;                                                      \
 164           else                                                                \
 165             backw->next = newp;                                               \
 166           newp->next = NULL;                                                  \
 167           backw = newp;                                                       \
 168         }                                                                     \
 169       while (get_weight (&str, newp) == 0);                                   \
 170     }                                                                         \
 171   while (0)