locale/weight.h

   1 /* Copyright (C) 1996, 1997 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 not,
  17    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 values in the
  45    collate locale file that do not depend on byte order.  */
  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   ((u_int32_t *) _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_hash_size) * (collate_nrules + 1);
  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           *str += idx;
 131           idx += slot + 3;
 132           for (cnt = 0; cnt < collate_nrules; ++cnt)
 133             {
 134               result->data[cnt].number = __collate_extra[idx++];
 135               result->data[cnt].value = &__collate_extra[idx];
 136               idx += result->data[cnt].number;
 137             }
 138           return 0;
 139         }
 140
 141       /* To next entry in list.  */
 142       slot += __collate_extra[slot];
 143     }
 144   /* NOTREACHED */
 145   return 0;     /* To calm down gcc.  */
 146 }
 147
 148
 149 /* To process a string efficiently we retrieve all information about
 150    the string at once.  The following macro constructs a double linked
 151    list of this information.  It is a macro because we use `alloca'
 152    and we use a double linked list because of the backward collation
 153    order.  */
 154 #define get_string(str, forw, backw)                                          \
 155   do                                                                          \
 156     {                                                                         \
 157       weight_t *newp;                                                         \
 158       do                                                                      \
 159         {                                                                     \
 160           newp = (weight_t *) alloca (sizeof (weight_t)                       \
 161                                       + (collate_nrules                       \
 162                                          * sizeof (struct data_pair)));       \
 163                                                                               \
 164           newp->prev = backw;                                                 \
 165           if (backw == NULL)                                                  \
 166             forw = newp;                                                      \
 167           else                                                                \
 168             backw->next = newp;                                               \
 169           newp->next = NULL;                                                  \
 170           backw = newp;                                                       \
 171         }                                                                     \
 172       while (get_weight (&str, newp) == 0);                                   \
 173     }                                                                         \
 174   while (0)