]>
Commit | Line | Data |
---|---|---|
d614a753 | 1 | /* Copyright (C) 2000-2020 Free Software Foundation, Inc. |
04ea3b0f UD |
2 | This file is part of the GNU C Library. |
3 | Contributed by Bruno Haible <haible@clisp.cons.org>, 2000. | |
4 | ||
43bc8ac6 | 5 | This program is free software; you can redistribute it and/or modify |
2e2efe65 RM |
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. | |
04ea3b0f | 9 | |
43bc8ac6 | 10 | This program is distributed in the hope that it will be useful, |
04ea3b0f | 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
43bc8ac6 UD |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | GNU General Public License for more details. | |
04ea3b0f | 14 | |
43bc8ac6 | 15 | You should have received a copy of the GNU General Public License |
5a82c748 | 16 | along with this program; if not, see <https://www.gnu.org/licenses/>. */ |
04ea3b0f | 17 | |
e054f494 RA |
18 | #include <stdint.h> |
19 | ||
04ea3b0f UD |
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 | |
1ecbb381 RS |
29 | NO_ADD_LOCALE if you don't want the add_locale_TABLE function |
30 | to be defined | |
04ea3b0f UD |
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)); | |
1ecbb381 | 40 | void add_locale_TABLE (struct locale_file *file, struct TABLE *t); |
04ea3b0f UD |
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; | |
1ecbb381 | 61 | /* Size of compressed representation. */ |
04ea3b0f | 62 | size_t result_size; |
04ea3b0f UD |
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 | { | |
ab52d206 | 69 | t->level1 = NULL; |
04ea3b0f | 70 | t->level1_alloc = t->level1_size = 0; |
ab52d206 | 71 | t->level2 = NULL; |
04ea3b0f | 72 | t->level2_alloc = t->level2_size = 0; |
ab52d206 | 73 | t->level3 = NULL; |
04ea3b0f UD |
74 | t->level3_alloc = t->level3_size = 0; |
75 | } | |
76 | ||
48ddeb0b UD |
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 | ||
04ea3b0f UD |
81 | /* Retrieve an entry. */ |
82 | static inline ELEMENT | |
25337753 | 83 | __attribute ((always_inline)) |
04ea3b0f UD |
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]; | |
48ddeb0b | 90 | if (lookup1 != EMPTY) |
04ea3b0f UD |
91 | { |
92 | uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1)) | |
93 | + (lookup1 << t->q); | |
94 | uint32_t lookup2 = t->level2[index2]; | |
48ddeb0b | 95 | if (lookup2 != EMPTY) |
04ea3b0f UD |
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; | |
ab52d206 UD |
127 | t->level1 = (uint32_t *) xrealloc ((char *) t->level1, |
128 | alloc * sizeof (uint32_t)); | |
04ea3b0f UD |
129 | t->level1_alloc = alloc; |
130 | } | |
131 | while (index1 >= t->level1_size) | |
48ddeb0b | 132 | t->level1[t->level1_size++] = EMPTY; |
04ea3b0f UD |
133 | } |
134 | ||
48ddeb0b | 135 | if (t->level1[index1] == EMPTY) |
04ea3b0f UD |
136 | { |
137 | if (t->level2_size == t->level2_alloc) | |
138 | { | |
139 | size_t alloc = 2 * t->level2_alloc + 1; | |
ab52d206 UD |
140 | t->level2 = (uint32_t *) xrealloc ((char *) t->level2, |
141 | (alloc << t->q) * sizeof (uint32_t)); | |
04ea3b0f UD |
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++) | |
48ddeb0b | 147 | t->level2[i] = EMPTY; |
04ea3b0f UD |
148 | t->level1[index1] = t->level2_size++; |
149 | } | |
150 | ||
151 | index2 += t->level1[index1] << t->q; | |
152 | ||
48ddeb0b | 153 | if (t->level2[index2] == EMPTY) |
04ea3b0f UD |
154 | { |
155 | if (t->level3_size == t->level3_alloc) | |
156 | { | |
157 | size_t alloc = 2 * t->level3_alloc + 1; | |
ab52d206 UD |
158 | t->level3 = (ELEMENT *) xrealloc ((char *) t->level3, |
159 | (alloc << t->p) * sizeof (ELEMENT)); | |
04ea3b0f UD |
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]; | |
48ddeb0b | 184 | if (lookup1 != EMPTY) |
04ea3b0f UD |
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]; | |
48ddeb0b | 191 | if (lookup2 != EMPTY) |
04ea3b0f UD |
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 | ||
1ecbb381 | 209 | #ifndef NO_ADD_LOCALE |
04ea3b0f UD |
210 | /* Finalize and shrink. */ |
211 | static void | |
1ecbb381 | 212 | CONCAT(add_locale_,TABLE) (struct locale_file *file, struct TABLE *t) |
04ea3b0f UD |
213 | { |
214 | size_t i, j, k; | |
215 | uint32_t reorder3[t->level3_size]; | |
216 | uint32_t reorder2[t->level2_size]; | |
1ecbb381 | 217 | uint32_t level2_offset, level3_offset, last_offset; |
04ea3b0f UD |
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++) | |
48ddeb0b | 240 | if (t->level2[i] != EMPTY) |
04ea3b0f UD |
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++) | |
48ddeb0b | 264 | if (t->level1[i] != EMPTY) |
04ea3b0f UD |
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); | |
7602d070 | 273 | t->result_size = LOCFILE_ALIGN_UP (last_offset); |
04ea3b0f | 274 | |
04ea3b0f UD |
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 | ||
1ecbb381 RS |
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); | |
04ea3b0f UD |
289 | |
290 | for (i = 0; i < t->level1_size; i++) | |
1ecbb381 RS |
291 | add_locale_uint32 |
292 | (file, | |
293 | t->level1[i] == EMPTY | |
04ea3b0f UD |
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++) | |
1ecbb381 RS |
298 | add_locale_uint32 |
299 | (file, | |
300 | t->level2[i] == EMPTY | |
04ea3b0f UD |
301 | ? 0 |
302 | : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset); | |
303 | ||
1ecbb381 RS |
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 (); | |
7602d070 | 311 | align_locale_data (file, LOCFILE_ALIGN); |
1ecbb381 | 312 | end_locale_structure (file); |
04ea3b0f UD |
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 | ||
48ddeb0b | 323 | #undef EMPTY |
04ea3b0f UD |
324 | #undef TABLE |
325 | #undef ELEMENT | |
326 | #undef DEFAULT | |
327 | #undef ITERATE | |
1ecbb381 | 328 | #undef NO_ADD_LOCALE |