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