This source file includes following definitions.
- CONCAT
- CONCAT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 #define CONCAT(a,b) CONCAT1(a,b)
45 #define CONCAT1(a,b) a##b
46
47 struct TABLE
48 {
49
50 unsigned int p;
51 unsigned int q;
52
53 size_t level1_alloc;
54 size_t level1_size;
55 uint32_t *level1;
56 size_t level2_alloc;
57 size_t level2_size;
58 uint32_t *level2;
59 size_t level3_alloc;
60 size_t level3_size;
61 ELEMENT *level3;
62
63 size_t result_size;
64 char *result;
65 };
66
67
68 static inline void
69 CONCAT(TABLE,_init) (struct TABLE *t)
70 {
71 t->level1 = NULL;
72 t->level1_alloc = t->level1_size = 0;
73 t->level2 = NULL;
74 t->level2_alloc = t->level2_size = 0;
75 t->level3 = NULL;
76 t->level3_alloc = t->level3_size = 0;
77 }
78
79
80
81 #define EMPTY ((uint32_t) ~0)
82
83
84 static inline ELEMENT
85 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
86 {
87 uint32_t index1 = wc >> (t->q + t->p);
88 if (index1 < t->level1_size)
89 {
90 uint32_t lookup1 = t->level1[index1];
91 if (lookup1 != EMPTY)
92 {
93 uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
94 + (lookup1 << t->q);
95 uint32_t lookup2 = t->level2[index2];
96 if (lookup2 != EMPTY)
97 {
98 uint32_t index3 = (wc & ((1 << t->p) - 1))
99 + (lookup2 << t->p);
100 ELEMENT lookup3 = t->level3[index3];
101
102 return lookup3;
103 }
104 }
105 }
106 return DEFAULT;
107 }
108
109
110 static void
111 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
112 {
113 uint32_t index1 = wc >> (t->q + t->p);
114 uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
115 uint32_t index3 = wc & ((1 << t->p) - 1);
116 size_t i, i1, i2;
117
118 if (value == CONCAT(TABLE,_get) (t, wc))
119 return;
120
121 if (index1 >= t->level1_size)
122 {
123 if (index1 >= t->level1_alloc)
124 {
125 size_t alloc = 2 * t->level1_alloc;
126 if (alloc <= index1)
127 alloc = index1 + 1;
128 t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
129 alloc * sizeof (uint32_t));
130 t->level1_alloc = alloc;
131 }
132 while (index1 >= t->level1_size)
133 t->level1[t->level1_size++] = EMPTY;
134 }
135
136 if (t->level1[index1] == EMPTY)
137 {
138 if (t->level2_size == t->level2_alloc)
139 {
140 size_t alloc = 2 * t->level2_alloc + 1;
141 t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
142 (alloc << t->q) * sizeof (uint32_t));
143 t->level2_alloc = alloc;
144 }
145 i1 = t->level2_size << t->q;
146 i2 = (t->level2_size + 1) << t->q;
147 for (i = i1; i < i2; i++)
148 t->level2[i] = EMPTY;
149 t->level1[index1] = t->level2_size++;
150 }
151
152 index2 += t->level1[index1] << t->q;
153
154 if (t->level2[index2] == EMPTY)
155 {
156 if (t->level3_size == t->level3_alloc)
157 {
158 size_t alloc = 2 * t->level3_alloc + 1;
159 t->level3 = (ELEMENT *) xrealloc ((char *) t->level3,
160 (alloc << t->p) * sizeof (ELEMENT));
161 t->level3_alloc = alloc;
162 }
163 i1 = t->level3_size << t->p;
164 i2 = (t->level3_size + 1) << t->p;
165 for (i = i1; i < i2; i++)
166 t->level3[i] = DEFAULT;
167 t->level2[index2] = t->level3_size++;
168 }
169
170 index3 += t->level2[index2] << t->p;
171
172 t->level3[index3] = value;
173 }
174
175 #ifdef ITERATE
176
177 static void
178 CONCAT(TABLE,_iterate) (struct TABLE *t,
179 void (*fn) (uint32_t wc, ELEMENT value))
180 {
181 uint32_t index1;
182 for (index1 = 0; index1 < t->level1_size; index1++)
183 {
184 uint32_t lookup1 = t->level1[index1];
185 if (lookup1 != EMPTY)
186 {
187 uint32_t lookup1_shifted = lookup1 << t->q;
188 uint32_t index2;
189 for (index2 = 0; index2 < (1 << t->q); index2++)
190 {
191 uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
192 if (lookup2 != EMPTY)
193 {
194 uint32_t lookup2_shifted = lookup2 << t->p;
195 uint32_t index3;
196 for (index3 = 0; index3 < (1 << t->p); index3++)
197 {
198 ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
199 if (lookup3 != DEFAULT)
200 fn ((((index1 << t->q) + index2) << t->p) + index3,
201 lookup3);
202 }
203 }
204 }
205 }
206 }
207 }
208 #endif
209
210 #ifndef NO_FINALIZE
211
212 static void
213 CONCAT(TABLE,_finalize) (struct TABLE *t)
214 {
215 size_t i, j, k;
216 uint32_t reorder3[t->level3_size];
217 uint32_t reorder2[t->level2_size];
218 uint32_t level1_offset, level2_offset, level3_offset, last_offset;
219
220
221 k = 0;
222 for (j = 0; j < t->level3_size; j++)
223 {
224 for (i = 0; i < k; i++)
225 if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
226 (1 << t->p) * sizeof (ELEMENT)) == 0)
227 break;
228
229 reorder3[j] = i;
230 if (i == k)
231 {
232 if (i != j)
233 memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
234 (1 << t->p) * sizeof (ELEMENT));
235 k++;
236 }
237 }
238 t->level3_size = k;
239
240 for (i = 0; i < (t->level2_size << t->q); i++)
241 if (t->level2[i] != EMPTY)
242 t->level2[i] = reorder3[t->level2[i]];
243
244
245 k = 0;
246 for (j = 0; j < t->level2_size; j++)
247 {
248 for (i = 0; i < k; i++)
249 if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
250 (1 << t->q) * sizeof (uint32_t)) == 0)
251 break;
252
253 reorder2[j] = i;
254 if (i == k)
255 {
256 if (i != j)
257 memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
258 (1 << t->q) * sizeof (uint32_t));
259 k++;
260 }
261 }
262 t->level2_size = k;
263
264 for (i = 0; i < t->level1_size; i++)
265 if (t->level1[i] != EMPTY)
266 t->level1[i] = reorder2[t->level1[i]];
267
268
269 last_offset =
270 5 * sizeof (uint32_t)
271 + t->level1_size * sizeof (uint32_t)
272 + (t->level2_size << t->q) * sizeof (uint32_t)
273 + (t->level3_size << t->p) * sizeof (ELEMENT);
274 t->result_size = (last_offset + 3) & ~3ul;
275 t->result = (char *) xmalloc (t->result_size);
276
277 level1_offset =
278 5 * sizeof (uint32_t);
279 level2_offset =
280 5 * sizeof (uint32_t)
281 + t->level1_size * sizeof (uint32_t);
282 level3_offset =
283 5 * sizeof (uint32_t)
284 + t->level1_size * sizeof (uint32_t)
285 + (t->level2_size << t->q) * sizeof (uint32_t);
286
287 ((uint32_t *) t->result)[0] = t->q + t->p;
288 ((uint32_t *) t->result)[1] = t->level1_size;
289 ((uint32_t *) t->result)[2] = t->p;
290 ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
291 ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
292
293 for (i = 0; i < t->level1_size; i++)
294 ((uint32_t *) (t->result + level1_offset))[i] =
295 (t->level1[i] == EMPTY
296 ? 0
297 : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
298
299 for (i = 0; i < (t->level2_size << t->q); i++)
300 ((uint32_t *) (t->result + level2_offset))[i] =
301 (t->level2[i] == EMPTY
302 ? 0
303 : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
304
305 for (i = 0; i < (t->level3_size << t->p); i++)
306 ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i];
307
308 if (last_offset < t->result_size)
309 memset (t->result + last_offset, 0, t->result_size - last_offset);
310
311 if (t->level1_alloc > 0)
312 free (t->level1);
313 if (t->level2_alloc > 0)
314 free (t->level2);
315 if (t->level3_alloc > 0)
316 free (t->level3);
317 }
318 #endif
319
320 #undef EMPTY
321 #undef TABLE
322 #undef ELEMENT
323 #undef DEFAULT
324 #undef ITERATE
325 #undef NO_FINALIZE