5a9bcd74864412fa2367cb3bfb02bc38fbbd768e
[kopensolaris-gnu/glibc.git] / 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)