1 /* Copyright (C) 2000-2002, 2009-2012 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, see <http://www.gnu.org/licenses/>. */
23 /* Construction of sparse 3-level tables.
24 See wchar-lookup.h for their structure and the meaning of p and q.
26 Before including this file, set
27 TABLE to the name of the structure to be defined
28 ITERATE if you want the TABLE_iterate function to be defined
29 NO_FINALIZE if you don't want the TABLE_finalize function to be defined
34 void TABLE_init (struct TABLE *t);
35 int TABLE_get (struct TABLE *t, uint32_t wc);
36 void TABLE_add (struct TABLE *t, uint32_t wc);
37 void TABLE_iterate (struct TABLE *t, void (*fn) (uint32_t wc));
38 void TABLE_finalize (struct TABLE *t);
41 #define CONCAT(a,b) CONCAT1(a,b)
42 #define CONCAT1(a,b) a##b
49 /* Working representation. */
59 /* Compressed representation. */
64 /* Initialize. Assumes t->p and t->q have already been set. */
66 CONCAT(TABLE,_init) (struct TABLE *t)
69 t->level1_alloc = t->level1_size = 0;
71 t->level2_alloc = t->level2_size = 0;
73 t->level3_alloc = t->level3_size = 0;
76 /* Marker for an empty slot. This has the value 0xFFFFFFFF, regardless
77 whether 'int' is 16 bit, 32 bit, or 64 bit. */
78 #define EMPTY ((uint32_t) ~0)
80 /* Retrieve an entry. */
82 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
84 uint32_t index1 = wc >> (t->q + t->p + 5);
85 if (index1 < t->level1_size)
87 uint32_t lookup1 = t->level1[index1];
90 uint32_t index2 = ((wc >> (t->p + 5)) & ((1 << t->q) - 1))
92 uint32_t lookup2 = t->level2[index2];
95 uint32_t index3 = ((wc >> 5) & ((1 << t->p) - 1))
97 uint32_t lookup3 = t->level3[index3];
98 uint32_t index4 = wc & 0x1f;
100 return (lookup3 >> index4) & 1;
109 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc)
111 uint32_t index1 = wc >> (t->q + t->p + 5);
112 uint32_t index2 = (wc >> (t->p + 5)) & ((1 << t->q) - 1);
113 uint32_t index3 = (wc >> 5) & ((1 << t->p) - 1);
114 uint32_t index4 = wc & 0x1f;
117 if (index1 >= t->level1_size)
119 if (index1 >= t->level1_alloc)
121 size_t alloc = 2 * t->level1_alloc;
124 t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
125 alloc * sizeof (uint32_t));
126 t->level1_alloc = alloc;
128 while (index1 >= t->level1_size)
129 t->level1[t->level1_size++] = EMPTY;
132 if (t->level1[index1] == EMPTY)
134 if (t->level2_size == t->level2_alloc)
136 size_t alloc = 2 * t->level2_alloc + 1;
137 t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
138 (alloc << t->q) * sizeof (uint32_t));
139 t->level2_alloc = alloc;
141 i1 = t->level2_size << t->q;
142 i2 = (t->level2_size + 1) << t->q;
143 for (i = i1; i < i2; i++)
144 t->level2[i] = EMPTY;
145 t->level1[index1] = t->level2_size++;
148 index2 += t->level1[index1] << t->q;
150 if (t->level2[index2] == EMPTY)
152 if (t->level3_size == t->level3_alloc)
154 size_t alloc = 2 * t->level3_alloc + 1;
155 t->level3 = (uint32_t *) xrealloc ((char *) t->level3,
156 (alloc << t->p) * sizeof (uint32_t));
157 t->level3_alloc = alloc;
159 i1 = t->level3_size << t->p;
160 i2 = (t->level3_size + 1) << t->p;
161 for (i = i1; i < i2; i++)
163 t->level2[index2] = t->level3_size++;
166 index3 += t->level2[index2] << t->p;
168 t->level3[index3] |= (uint32_t)1 << index4;
172 /* Apply a function to all entries in the table. */
174 CONCAT(TABLE,_iterate) (struct TABLE *t, void (*fn) (uint32_t wc))
177 for (index1 = 0; index1 < t->level1_size; index1++)
179 uint32_t lookup1 = t->level1[index1];
180 if (lookup1 != EMPTY)
182 uint32_t lookup1_shifted = lookup1 << t->q;
184 for (index2 = 0; index2 < (1 << t->q); index2++)
186 uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
187 if (lookup2 != EMPTY)
189 uint32_t lookup2_shifted = lookup2 << t->p;
191 for (index3 = 0; index3 < (1 << t->p); index3++)
193 uint32_t lookup3 = t->level3[index3 + lookup2_shifted];
195 for (index4 = 0; index4 < 32; index4++)
196 if ((lookup3 >> index4) & 1)
197 fn ((((((index1 << t->q) + index2) << t->p) + index3) << 5) + index4);
207 /* Finalize and shrink. */
209 CONCAT(TABLE,_finalize) (struct TABLE *t)
212 uint32_t reorder3[t->level3_size];
213 uint32_t reorder2[t->level2_size];
214 uint32_t level1_offset, level2_offset, level3_offset;
216 /* Uniquify level3 blocks. */
218 for (j = 0; j < t->level3_size; j++)
220 for (i = 0; i < k; i++)
221 if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
222 (1 << t->p) * sizeof (uint32_t)) == 0)
224 /* Relocate block j to block i. */
229 memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
230 (1 << t->p) * sizeof (uint32_t));
236 for (i = 0; i < (t->level2_size << t->q); i++)
237 if (t->level2[i] != EMPTY)
238 t->level2[i] = reorder3[t->level2[i]];
240 /* Uniquify level2 blocks. */
242 for (j = 0; j < t->level2_size; j++)
244 for (i = 0; i < k; i++)
245 if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
246 (1 << t->q) * sizeof (uint32_t)) == 0)
248 /* Relocate block j to block i. */
253 memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
254 (1 << t->q) * sizeof (uint32_t));
260 for (i = 0; i < t->level1_size; i++)
261 if (t->level1[i] != EMPTY)
262 t->level1[i] = reorder2[t->level1[i]];
264 /* Create and fill the resulting compressed representation. */
266 5 * sizeof (uint32_t)
267 + t->level1_size * sizeof (uint32_t)
268 + (t->level2_size << t->q) * sizeof (uint32_t)
269 + (t->level3_size << t->p) * sizeof (uint32_t);
270 t->result = (char *) xmalloc (t->result_size);
273 5 * sizeof (uint32_t);
275 5 * sizeof (uint32_t)
276 + t->level1_size * sizeof (uint32_t);
278 5 * sizeof (uint32_t)
279 + t->level1_size * sizeof (uint32_t)
280 + (t->level2_size << t->q) * sizeof (uint32_t);
282 ((uint32_t *) t->result)[0] = t->q + t->p + 5;
283 ((uint32_t *) t->result)[1] = t->level1_size;
284 ((uint32_t *) t->result)[2] = t->p + 5;
285 ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
286 ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
288 for (i = 0; i < t->level1_size; i++)
289 ((uint32_t *) (t->result + level1_offset))[i] =
290 (t->level1[i] == EMPTY
292 : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
294 for (i = 0; i < (t->level2_size << t->q); i++)
295 ((uint32_t *) (t->result + level2_offset))[i] =
296 (t->level2[i] == EMPTY
298 : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
300 for (i = 0; i < (t->level3_size << t->p); i++)
301 ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
303 if (t->level1_alloc > 0)
305 if (t->level2_alloc > 0)
307 if (t->level3_alloc > 0)