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 #define CONCAT(a,b) CONCAT1(a,b)
42 #define CONCAT1(a,b) a##b
43
44 struct TABLE
45 {
46
47 unsigned int p;
48 unsigned int q;
49
50 size_t level1_alloc;
51 size_t level1_size;
52 uint32_t *level1;
53 size_t level2_alloc;
54 size_t level2_size;
55 uint32_t *level2;
56 size_t level3_alloc;
57 size_t level3_size;
58 uint32_t *level3;
59
60 size_t result_size;
61 char *result;
62 };
63
64
65 static inline void
66 CONCAT(TABLE,_init) (struct TABLE *t)
67 {
68 t->level1 = NULL;
69 t->level1_alloc = t->level1_size = 0;
70 t->level2 = NULL;
71 t->level2_alloc = t->level2_size = 0;
72 t->level3 = NULL;
73 t->level3_alloc = t->level3_size = 0;
74 }
75
76
77
78 #define EMPTY ((uint32_t) ~0)
79
80
81 static inline int
82 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
83 {
84 uint32_t index1 = wc >> (t->q + t->p + 5);
85 if (index1 < t->level1_size)
86 {
87 uint32_t lookup1 = t->level1[index1];
88 if (lookup1 != EMPTY)
89 {
90 uint32_t index2 = ((wc >> (t->p + 5)) & ((1 << t->q) - 1))
91 + (lookup1 << t->q);
92 uint32_t lookup2 = t->level2[index2];
93 if (lookup2 != EMPTY)
94 {
95 uint32_t index3 = ((wc >> 5) & ((1 << t->p) - 1))
96 + (lookup2 << t->p);
97 uint32_t lookup3 = t->level3[index3];
98 uint32_t index4 = wc & 0x1f;
99
100 return (lookup3 >> index4) & 1;
101 }
102 }
103 }
104 return 0;
105 }
106
107
108 static void
109 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc)
110 {
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;
115 size_t i, i1, i2;
116
117 if (index1 >= t->level1_size)
118 {
119 if (index1 >= t->level1_alloc)
120 {
121 size_t alloc = 2 * t->level1_alloc;
122 if (alloc <= index1)
123 alloc = index1 + 1;
124 t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
125 alloc * sizeof (uint32_t));
126 t->level1_alloc = alloc;
127 }
128 while (index1 >= t->level1_size)
129 t->level1[t->level1_size++] = EMPTY;
130 }
131
132 if (t->level1[index1] == EMPTY)
133 {
134 if (t->level2_size == t->level2_alloc)
135 {
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;
140 }
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++;
146 }
147
148 index2 += t->level1[index1] << t->q;
149
150 if (t->level2[index2] == EMPTY)
151 {
152 if (t->level3_size == t->level3_alloc)
153 {
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;
158 }
159 i1 = t->level3_size << t->p;
160 i2 = (t->level3_size + 1) << t->p;
161 for (i = i1; i < i2; i++)
162 t->level3[i] = 0;
163 t->level2[index2] = t->level3_size++;
164 }
165
166 index3 += t->level2[index2] << t->p;
167
168 t->level3[index3] |= (uint32_t)1 << index4;
169 }
170
171 #ifdef ITERATE
172
173 static void
174 CONCAT(TABLE,_iterate) (struct TABLE *t, void (*fn) (uint32_t wc))
175 {
176 uint32_t index1;
177 for (index1 = 0; index1 < t->level1_size; index1++)
178 {
179 uint32_t lookup1 = t->level1[index1];
180 if (lookup1 != EMPTY)
181 {
182 uint32_t lookup1_shifted = lookup1 << t->q;
183 uint32_t index2;
184 for (index2 = 0; index2 < (1 << t->q); index2++)
185 {
186 uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
187 if (lookup2 != EMPTY)
188 {
189 uint32_t lookup2_shifted = lookup2 << t->p;
190 uint32_t index3;
191 for (index3 = 0; index3 < (1 << t->p); index3++)
192 {
193 uint32_t lookup3 = t->level3[index3 + lookup2_shifted];
194 uint32_t index4;
195 for (index4 = 0; index4 < 32; index4++)
196 if ((lookup3 >> index4) & 1)
197 fn ((((((index1 << t->q) + index2) << t->p) + index3) << 5) + index4);
198 }
199 }
200 }
201 }
202 }
203 }
204 #endif
205
206 #ifndef NO_FINALIZE
207
208 static void
209 CONCAT(TABLE,_finalize) (struct TABLE *t)
210 {
211 size_t i, j, k;
212 uint32_t reorder3[t->level3_size];
213 uint32_t reorder2[t->level2_size];
214 uint32_t level1_offset, level2_offset, level3_offset;
215
216
217 k = 0;
218 for (j = 0; j < t->level3_size; j++)
219 {
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)
223 break;
224
225 reorder3[j] = i;
226 if (i == k)
227 {
228 if (i != j)
229 memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
230 (1 << t->p) * sizeof (uint32_t));
231 k++;
232 }
233 }
234 t->level3_size = k;
235
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]];
239
240
241 k = 0;
242 for (j = 0; j < t->level2_size; j++)
243 {
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)
247 break;
248
249 reorder2[j] = i;
250 if (i == k)
251 {
252 if (i != j)
253 memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
254 (1 << t->q) * sizeof (uint32_t));
255 k++;
256 }
257 }
258 t->level2_size = k;
259
260 for (i = 0; i < t->level1_size; i++)
261 if (t->level1[i] != EMPTY)
262 t->level1[i] = reorder2[t->level1[i]];
263
264
265 t->result_size =
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);
271
272 level1_offset =
273 5 * sizeof (uint32_t);
274 level2_offset =
275 5 * sizeof (uint32_t)
276 + t->level1_size * sizeof (uint32_t);
277 level3_offset =
278 5 * sizeof (uint32_t)
279 + t->level1_size * sizeof (uint32_t)
280 + (t->level2_size << t->q) * sizeof (uint32_t);
281
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;
287
288 for (i = 0; i < t->level1_size; i++)
289 ((uint32_t *) (t->result + level1_offset))[i] =
290 (t->level1[i] == EMPTY
291 ? 0
292 : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
293
294 for (i = 0; i < (t->level2_size << t->q); i++)
295 ((uint32_t *) (t->result + level2_offset))[i] =
296 (t->level2[i] == EMPTY
297 ? 0
298 : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
299
300 for (i = 0; i < (t->level3_size << t->p); i++)
301 ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
302
303 if (t->level1_alloc > 0)
304 free (t->level1);
305 if (t->level2_alloc > 0)
306 free (t->level2);
307 if (t->level3_alloc > 0)
308 free (t->level3);
309 }
310 #endif
311
312 #undef EMPTY
313 #undef TABLE
314 #undef ITERATE
315 #undef NO_FINALIZE