]>
Commit | Line | Data |
---|---|---|
a334319f | 1 | /* Copyright (C) 2000-2001, 2003 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 | ||
a334319f UD |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
04ea3b0f | 9 | |
a334319f | 10 | The GNU C Library is distributed in the hope that it will be useful, |
04ea3b0f | 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
a334319f UD |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. | |
04ea3b0f | 14 | |
a334319f UD |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, write to the Free | |
17 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA | |
18 | 02111-1307 USA. */ | |
04ea3b0f UD |
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_FINALIZE if you don't want the TABLE_finalize function to be defined | |
30 | ||
31 | This will define | |
32 | ||
33 | struct TABLE; | |
34 | void TABLE_init (struct TABLE *t); | |
35 | ELEMENT TABLE_get (struct TABLE *t, uint32_t wc); | |
36 | void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value); | |
37 | void TABLE_iterate (struct TABLE *t, | |
38 | void (*fn) (uint32_t wc, ELEMENT value)); | |
39 | void TABLE_finalize (struct TABLE *t); | |
40 | */ | |
41 | ||
42 | #define CONCAT(a,b) CONCAT1(a,b) | |
43 | #define CONCAT1(a,b) a##b | |
44 | ||
45 | struct TABLE | |
46 | { | |
47 | /* Parameters. */ | |
48 | unsigned int p; | |
49 | unsigned int q; | |
50 | /* Working representation. */ | |
51 | size_t level1_alloc; | |
52 | size_t level1_size; | |
53 | uint32_t *level1; | |
54 | size_t level2_alloc; | |
55 | size_t level2_size; | |
56 | uint32_t *level2; | |
57 | size_t level3_alloc; | |
58 | size_t level3_size; | |
59 | ELEMENT *level3; | |
60 | /* Compressed representation. */ | |
61 | size_t result_size; | |
62 | char *result; | |
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 | ||
209 | #ifndef NO_FINALIZE | |
210 | /* Finalize and shrink. */ | |
211 | static void | |
212 | CONCAT(TABLE,_finalize) (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 level1_offset, 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++) | |
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); | |
273 | t->result_size = (last_offset + 3) & ~3ul; | |
274 | t->result = (char *) xmalloc (t->result_size); | |
275 | ||
276 | level1_offset = | |
277 | 5 * sizeof (uint32_t); | |
278 | level2_offset = | |
279 | 5 * sizeof (uint32_t) | |
280 | + t->level1_size * sizeof (uint32_t); | |
281 | level3_offset = | |
282 | 5 * sizeof (uint32_t) | |
283 | + t->level1_size * sizeof (uint32_t) | |
284 | + (t->level2_size << t->q) * sizeof (uint32_t); | |
285 | ||
286 | ((uint32_t *) t->result)[0] = t->q + t->p; | |
287 | ((uint32_t *) t->result)[1] = t->level1_size; | |
288 | ((uint32_t *) t->result)[2] = t->p; | |
289 | ((uint32_t *) t->result)[3] = (1 << t->q) - 1; | |
290 | ((uint32_t *) t->result)[4] = (1 << t->p) - 1; | |
291 | ||
292 | for (i = 0; i < t->level1_size; i++) | |
293 | ((uint32_t *) (t->result + level1_offset))[i] = | |
48ddeb0b | 294 | (t->level1[i] == EMPTY |
04ea3b0f UD |
295 | ? 0 |
296 | : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset); | |
297 | ||
298 | for (i = 0; i < (t->level2_size << t->q); i++) | |
299 | ((uint32_t *) (t->result + level2_offset))[i] = | |
48ddeb0b | 300 | (t->level2[i] == EMPTY |
04ea3b0f UD |
301 | ? 0 |
302 | : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset); | |
303 | ||
304 | for (i = 0; i < (t->level3_size << t->p); i++) | |
305 | ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i]; | |
306 | ||
307 | if (last_offset < t->result_size) | |
308 | memset (t->result + last_offset, 0, t->result_size - last_offset); | |
309 | ||
310 | if (t->level1_alloc > 0) | |
311 | free (t->level1); | |
312 | if (t->level2_alloc > 0) | |
313 | free (t->level2); | |
314 | if (t->level3_alloc > 0) | |
315 | free (t->level3); | |
316 | } | |
317 | #endif | |
318 | ||
48ddeb0b | 319 | #undef EMPTY |
04ea3b0f UD |
320 | #undef TABLE |
321 | #undef ELEMENT | |
322 | #undef DEFAULT | |
323 | #undef ITERATE | |
324 | #undef NO_FINALIZE |