1 /* Copyright (C) 2000-2002 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
6 NOTE: The canonical source of this file is maintained with the GNU C Library.
7 See glibc/locale/programs/ld-ctype.c.
8 Bugs can be reported to bug-glibc@gnu.org.
10 This program is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 2, or (at your option) any
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
25 /* Construction of sparse 3-level tables.
26 See wchar-lookup.h for their structure and the meaning of p and q.
28 Before including this file, set
29 TABLE to the name of the structure to be defined
30 ITERATE if you want the TABLE_iterate function to be defined
31 NO_FINALIZE if you don't want the TABLE_finalize function to be defined
36 void TABLE_init (struct TABLE *t);
37 int TABLE_get (struct TABLE *t, uint32_t wc);
38 void TABLE_add (struct TABLE *t, uint32_t wc);
39 void TABLE_iterate (struct TABLE *t, void (*fn) (uint32_t wc));
40 void TABLE_finalize (struct TABLE *t);
43 #define CONCAT(a,b) CONCAT1(a,b)
44 #define CONCAT1(a,b) a##b
51 /* Working representation. */
61 /* Compressed representation. */
66 /* Initialize. Assumes t->p and t->q have already been set. */
68 CONCAT(TABLE,_init) (struct TABLE *t)
71 t->level1_alloc = t->level1_size = 0;
73 t->level2_alloc = t->level2_size = 0;
75 t->level3_alloc = t->level3_size = 0;
78 /* Marker for an empty slot. This has the value 0xFFFFFFFF, regardless
79 whether 'int' is 16 bit, 32 bit, or 64 bit. */
80 #define EMPTY ((uint32_t) ~0)
82 /* Retrieve an entry. */
84 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
86 uint32_t index1 = wc >> (t->q + t->p + 5);
87 if (index1 < t->level1_size)
89 uint32_t lookup1 = t->level1[index1];
92 uint32_t index2 = ((wc >> (t->p + 5)) & ((1 << t->q) - 1))
94 uint32_t lookup2 = t->level2[index2];
97 uint32_t index3 = ((wc >> 5) & ((1 << t->p) - 1))
99 uint32_t lookup3 = t->level3[index3];
100 uint32_t index4 = wc & 0x1f;
102 return (lookup3 >> index4) & 1;
111 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc)
113 uint32_t index1 = wc >> (t->q + t->p + 5);
114 uint32_t index2 = (wc >> (t->p + 5)) & ((1 << t->q) - 1);
115 uint32_t index3 = (wc >> 5) & ((1 << t->p) - 1);
116 uint32_t index4 = wc & 0x1f;
119 if (index1 >= t->level1_size)
121 if (index1 >= t->level1_alloc)
123 size_t alloc = 2 * t->level1_alloc;
126 t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
127 alloc * sizeof (uint32_t));
128 t->level1_alloc = alloc;
130 while (index1 >= t->level1_size)
131 t->level1[t->level1_size++] = EMPTY;
134 if (t->level1[index1] == EMPTY)
136 if (t->level2_size == t->level2_alloc)
138 size_t alloc = 2 * t->level2_alloc + 1;
139 t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
140 (alloc << t->q) * sizeof (uint32_t));
141 t->level2_alloc = alloc;
143 i1 = t->level2_size << t->q;
144 i2 = (t->level2_size + 1) << t->q;
145 for (i = i1; i < i2; i++)
146 t->level2[i] = EMPTY;
147 t->level1[index1] = t->level2_size++;
150 index2 += t->level1[index1] << t->q;
152 if (t->level2[index2] == EMPTY)
154 if (t->level3_size == t->level3_alloc)
156 size_t alloc = 2 * t->level3_alloc + 1;
157 t->level3 = (uint32_t *) xrealloc ((char *) t->level3,
158 (alloc << t->p) * sizeof (uint32_t));
159 t->level3_alloc = alloc;
161 i1 = t->level3_size << t->p;
162 i2 = (t->level3_size + 1) << t->p;
163 for (i = i1; i < i2; i++)
165 t->level2[index2] = t->level3_size++;
168 index3 += t->level2[index2] << t->p;
170 t->level3[index3] |= (uint32_t)1 << index4;
174 /* Apply a function to all entries in the table. */
176 CONCAT(TABLE,_iterate) (struct TABLE *t, void (*fn) (uint32_t wc))
179 for (index1 = 0; index1 < t->level1_size; index1++)
181 uint32_t lookup1 = t->level1[index1];
182 if (lookup1 != EMPTY)
184 uint32_t lookup1_shifted = lookup1 << t->q;
186 for (index2 = 0; index2 < (1 << t->q); index2++)
188 uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
189 if (lookup2 != EMPTY)
191 uint32_t lookup2_shifted = lookup2 << t->p;
193 for (index3 = 0; index3 < (1 << t->p); index3++)
195 uint32_t lookup3 = t->level3[index3 + lookup2_shifted];
197 for (index4 = 0; index4 < 32; index4++)
198 if ((lookup3 >> index4) & 1)
199 fn ((((((index1 << t->q) + index2) << t->p) + index3) << 5) + index4);
209 /* Finalize and shrink. */
211 CONCAT(TABLE,_finalize) (struct TABLE *t)
214 uint32_t reorder3[t->level3_size];
215 uint32_t reorder2[t->level2_size];
216 uint32_t level1_offset, level2_offset, level3_offset;
218 /* Uniquify level3 blocks. */
220 for (j = 0; j < t->level3_size; j++)
222 for (i = 0; i < k; i++)
223 if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
224 (1 << t->p) * sizeof (uint32_t)) == 0)
226 /* Relocate block j to block i. */
231 memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
232 (1 << t->p) * sizeof (uint32_t));
238 for (i = 0; i < (t->level2_size << t->q); i++)
239 if (t->level2[i] != EMPTY)
240 t->level2[i] = reorder3[t->level2[i]];
242 /* Uniquify level2 blocks. */
244 for (j = 0; j < t->level2_size; j++)
246 for (i = 0; i < k; i++)
247 if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
248 (1 << t->q) * sizeof (uint32_t)) == 0)
250 /* Relocate block j to block i. */
255 memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
256 (1 << t->q) * sizeof (uint32_t));
262 for (i = 0; i < t->level1_size; i++)
263 if (t->level1[i] != EMPTY)
264 t->level1[i] = reorder2[t->level1[i]];
266 /* Create and fill the resulting compressed representation. */
268 5 * sizeof (uint32_t)
269 + t->level1_size * sizeof (uint32_t)
270 + (t->level2_size << t->q) * sizeof (uint32_t)
271 + (t->level3_size << t->p) * sizeof (uint32_t);
272 t->result = (char *) xmalloc (t->result_size);
275 5 * sizeof (uint32_t);
277 5 * sizeof (uint32_t)
278 + t->level1_size * sizeof (uint32_t);
280 5 * sizeof (uint32_t)
281 + t->level1_size * sizeof (uint32_t)
282 + (t->level2_size << t->q) * sizeof (uint32_t);
284 ((uint32_t *) t->result)[0] = t->q + t->p + 5;
285 ((uint32_t *) t->result)[1] = t->level1_size;
286 ((uint32_t *) t->result)[2] = t->p + 5;
287 ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
288 ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
290 for (i = 0; i < t->level1_size; i++)
291 ((uint32_t *) (t->result + level1_offset))[i] =
292 (t->level1[i] == EMPTY
294 : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
296 for (i = 0; i < (t->level2_size << t->q); i++)
297 ((uint32_t *) (t->result + level2_offset))[i] =
298 (t->level2[i] == EMPTY
300 : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
302 for (i = 0; i < (t->level3_size << t->p); i++)
303 ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
305 if (t->level1_alloc > 0)
307 if (t->level2_alloc > 0)
309 if (t->level3_alloc > 0)