1 /* Copyright (C) 2000-2023 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; version 2 of the License, or
8 (at your option) any later version.
9
10 This program 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
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, see <https://www.gnu.org/licenses/>. */
17
18 #include <stdint.h>
19
20 /* Construction of sparse 3-level tables.
21 See wchar-lookup.h or coll-lookup.h for their structure and the
22 meaning of p and q.
23
24 Before including this file, set
25 TABLE to the name of the structure to be defined
26 ELEMENT to the type of every entry
27 DEFAULT to the default value for empty entries
28 ITERATE if you want the TABLE_iterate function to be defined
29 NO_ADD_LOCALE if you don't want the add_locale_TABLE function
30 to be defined
31
32 This will define
33
34 struct TABLE;
35 void TABLE_init (struct TABLE *t);
36 ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
37 void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
38 void TABLE_iterate (struct TABLE *t,
39 void (*fn) (uint32_t wc, ELEMENT value));
40 void add_locale_TABLE (struct locale_file *file, struct TABLE *t);
41 */
42
43 #define CONCAT(a,b) CONCAT1(a,b)
44 #define CONCAT1(a,b) a##b
45
46 struct TABLE
47 {
48 /* Parameters. */
49 unsigned int p;
50 unsigned int q;
51 /* Working representation. */
52 size_t level1_alloc;
53 size_t level1_size;
54 uint32_t *level1;
55 size_t level2_alloc;
56 size_t level2_size;
57 uint32_t *level2;
58 size_t level3_alloc;
59 size_t level3_size;
60 ELEMENT *level3;
61 /* Size of compressed representation. */
62 size_t result_size;
63 };
64
65 /* Initialize. Assumes t->p and t->q have already been set. */
66 static inline void
67 CONCAT(TABLE,_init) (struct TABLE *t)
68 {
69 t->level1 = NULL;
70 t->level1_alloc = t->level1_size = 0;
71 t->level2 = NULL;
72 t->level2_alloc = t->level2_size = 0;
73 t->level3 = NULL;
74 t->level3_alloc = t->level3_size = 0;
75 }
76
77 /* Marker for an empty slot. This has the value 0xFFFFFFFF, regardless
78 whether 'int' is 16 bit, 32 bit, or 64 bit. */
79 #define EMPTY ((uint32_t) ~0)
80
81 /* Retrieve an entry. */
82 static inline ELEMENT
83 __attribute ((always_inline))
84 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
85 {
86 uint32_t index1 = wc >> (t->q + t->p);
87 if (index1 < t->level1_size)
88 {
89 uint32_t lookup1 = t->level1[index1];
90 if (lookup1 != EMPTY)
91 {
92 uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
93 + (lookup1 << t->q);
94 uint32_t lookup2 = t->level2[index2];
95 if (lookup2 != EMPTY)
96 {
97 uint32_t index3 = (wc & ((1 << t->p) - 1))
98 + (lookup2 << t->p);
99 ELEMENT lookup3 = t->level3[index3];
100
101 return lookup3;
102 }
103 }
104 }
105 return DEFAULT;
106 }
107
108 /* Add one entry. */
109 static void
110 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
111 {
112 uint32_t index1 = wc >> (t->q + t->p);
113 uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
114 uint32_t index3 = wc & ((1 << t->p) - 1);
115 size_t i, i1, i2;
116
117 if (value == CONCAT(TABLE,_get) (t, wc))
118 return;
119
120 if (index1 >= t->level1_size)
121 {
122 if (index1 >= t->level1_alloc)
123 {
124 size_t alloc = 2 * t->level1_alloc;
125 if (alloc <= index1)
126 alloc = index1 + 1;
127 t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
128 alloc * sizeof (uint32_t));
129 t->level1_alloc = alloc;
130 }
131 while (index1 >= t->level1_size)
132 t->level1[t->level1_size++] = EMPTY;
133 }
134
135 if (t->level1[index1] == EMPTY)
136 {
137 if (t->level2_size == t->level2_alloc)
138 {
139 size_t alloc = 2 * t->level2_alloc + 1;
140 t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
141 (alloc << t->q) * sizeof (uint32_t));
142 t->level2_alloc = alloc;
143 }
144 i1 = t->level2_size << t->q;
145 i2 = (t->level2_size + 1) << t->q;
146 for (i = i1; i < i2; i++)
147 t->level2[i] = EMPTY;
148 t->level1[index1] = t->level2_size++;
149 }
150
151 index2 += t->level1[index1] << t->q;
152
153 if (t->level2[index2] == EMPTY)
154 {
155 if (t->level3_size == t->level3_alloc)
156 {
157 size_t alloc = 2 * t->level3_alloc + 1;
158 t->level3 = (ELEMENT *) xrealloc ((char *) t->level3,
159 (alloc << t->p) * sizeof (ELEMENT));
160 t->level3_alloc = alloc;
161 }
162 i1 = t->level3_size << t->p;
163 i2 = (t->level3_size + 1) << t->p;
164 for (i = i1; i < i2; i++)
165 t->level3[i] = DEFAULT;
166 t->level2[index2] = t->level3_size++;
167 }
168
169 index3 += t->level2[index2] << t->p;
170
171 t->level3[index3] = value;
172 }
173
174 #ifdef ITERATE
175 /* Apply a function to all entries in the table. */
176 static void
177 CONCAT(TABLE,_iterate) (struct TABLE *t,
178 void (*fn) (uint32_t wc, ELEMENT value))
179 {
180 uint32_t index1;
181 for (index1 = 0; index1 < t->level1_size; index1++)
182 {
183 uint32_t lookup1 = t->level1[index1];
184 if (lookup1 != EMPTY)
185 {
186 uint32_t lookup1_shifted = lookup1 << t->q;
187 uint32_t index2;
188 for (index2 = 0; index2 < (1 << t->q); index2++)
189 {
190 uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
191 if (lookup2 != EMPTY)
192 {
193 uint32_t lookup2_shifted = lookup2 << t->p;
194 uint32_t index3;
195 for (index3 = 0; index3 < (1 << t->p); index3++)
196 {
197 ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
198 if (lookup3 != DEFAULT)
199 fn ((((index1 << t->q) + index2) << t->p) + index3,
200 lookup3);
201 }
202 }
203 }
204 }
205 }
206 }
207 #endif
208
209 #ifndef NO_ADD_LOCALE
210 /* Finalize and shrink. */
211 static void
212 CONCAT(add_locale_,TABLE) (struct locale_file *file, struct TABLE *t)
213 {
214 size_t i, j, k;
215 uint32_t reorder3[t->level3_size];
216 uint32_t reorder2[t->level2_size];
217 uint32_t level2_offset, level3_offset, last_offset;
218
219 /* Uniquify level3 blocks. */
220 k = 0;
221 for (j = 0; j < t->level3_size; j++)
222 {
223 for (i = 0; i < k; i++)
224 if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
225 (1 << t->p) * sizeof (ELEMENT)) == 0)
226 break;
227 /* Relocate block j to block i. */
228 reorder3[j] = i;
229 if (i == k)
230 {
231 if (i != j)
232 memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
233 (1 << t->p) * sizeof (ELEMENT));
234 k++;
235 }
236 }
237 t->level3_size = k;
238
239 for (i = 0; i < (t->level2_size << t->q); i++)
240 if (t->level2[i] != EMPTY)
241 t->level2[i] = reorder3[t->level2[i]];
242
243 /* Uniquify level2 blocks. */
244 k = 0;
245 for (j = 0; j < t->level2_size; j++)
246 {
247 for (i = 0; i < k; i++)
248 if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
249 (1 << t->q) * sizeof (uint32_t)) == 0)
250 break;
251 /* Relocate block j to block i. */
252 reorder2[j] = i;
253 if (i == k)
254 {
255 if (i != j)
256 memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
257 (1 << t->q) * sizeof (uint32_t));
258 k++;
259 }
260 }
261 t->level2_size = k;
262
263 for (i = 0; i < t->level1_size; i++)
264 if (t->level1[i] != EMPTY)
265 t->level1[i] = reorder2[t->level1[i]];
266
267 /* Create and fill the resulting compressed representation. */
268 last_offset =
269 5 * sizeof (uint32_t)
270 + t->level1_size * sizeof (uint32_t)
271 + (t->level2_size << t->q) * sizeof (uint32_t)
272 + (t->level3_size << t->p) * sizeof (ELEMENT);
273 t->result_size = LOCFILE_ALIGN_UP (last_offset);
274
275 level2_offset =
276 5 * sizeof (uint32_t)
277 + t->level1_size * sizeof (uint32_t);
278 level3_offset =
279 5 * sizeof (uint32_t)
280 + t->level1_size * sizeof (uint32_t)
281 + (t->level2_size << t->q) * sizeof (uint32_t);
282
283 start_locale_structure (file);
284 add_locale_uint32 (file, t->q + t->p);
285 add_locale_uint32 (file, t->level1_size);
286 add_locale_uint32 (file, t->p);
287 add_locale_uint32 (file, (1 << t->q) - 1);
288 add_locale_uint32 (file, (1 << t->p) - 1);
289
290 for (i = 0; i < t->level1_size; i++)
291 add_locale_uint32
292 (file,
293 t->level1[i] == EMPTY
294 ? 0
295 : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
296
297 for (i = 0; i < (t->level2_size << t->q); i++)
298 add_locale_uint32
299 (file,
300 t->level2[i] == EMPTY
301 ? 0
302 : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
303
304 if (sizeof (ELEMENT) == 1)
305 add_locale_raw_data (file, t->level3, t->level3_size << t->p);
306 else if (sizeof (ELEMENT) == sizeof (uint32_t))
307 add_locale_uint32_array (file, (uint32_t *) t->level3,
308 t->level3_size << t->p);
309 else
310 abort ();
311 align_locale_data (file, LOCFILE_ALIGN);
312 end_locale_structure (file);
313
314 if (t->level1_alloc > 0)
315 free (t->level1);
316 if (t->level2_alloc > 0)
317 free (t->level2);
318 if (t->level3_alloc > 0)
319 free (t->level3);
320 }
321 #endif
322
323 #undef EMPTY
324 #undef TABLE
325 #undef ELEMENT
326 #undef DEFAULT
327 #undef ITERATE
328 #undef NO_ADD_LOCALE