1 /* Copyright (C) 2000-2001, 2003, 2005 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License version 2 as
7 published by the Free Software Foundation.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software Foundation,
16 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
18 /* Construction of sparse 3-level tables.
19 See wchar-lookup.h or coll-lookup.h for their structure and the
22 Before including this file, set
23 TABLE to the name of the structure to be defined
24 ELEMENT to the type of every entry
25 DEFAULT to the default value for empty entries
26 ITERATE if you want the TABLE_iterate function to be defined
27 NO_FINALIZE if you don't want the TABLE_finalize function to be defined
32 void TABLE_init (struct TABLE *t);
33 ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
34 void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
35 void TABLE_iterate (struct TABLE *t,
36 void (*fn) (uint32_t wc, ELEMENT value));
37 void TABLE_finalize (struct TABLE *t);
40 #define CONCAT(a,b) CONCAT1(a,b)
41 #define CONCAT1(a,b) a##b
48 /* Working representation. */
58 /* Compressed representation. */
63 /* Initialize. Assumes t->p and t->q have already been set. */
65 CONCAT(TABLE
,_init
) (struct TABLE
*t
)
68 t
->level1_alloc
= t
->level1_size
= 0;
70 t
->level2_alloc
= t
->level2_size
= 0;
72 t
->level3_alloc
= t
->level3_size
= 0;
75 /* Marker for an empty slot. This has the value 0xFFFFFFFF, regardless
76 whether 'int' is 16 bit, 32 bit, or 64 bit. */
77 #define EMPTY ((uint32_t) ~0)
79 /* Retrieve an entry. */
81 __attribute ((always_inline
))
82 CONCAT(TABLE
,_get
) (struct TABLE
*t
, uint32_t wc
)
84 uint32_t index1
= wc
>> (t
->q
+ t
->p
);
85 if (index1
< t
->level1_size
)
87 uint32_t lookup1
= t
->level1
[index1
];
90 uint32_t index2
= ((wc
>> t
->p
) & ((1 << t
->q
) - 1))
92 uint32_t lookup2
= t
->level2
[index2
];
95 uint32_t index3
= (wc
& ((1 << t
->p
) - 1))
97 ELEMENT lookup3
= t
->level3
[index3
];
108 CONCAT(TABLE
,_add
) (struct TABLE
*t
, uint32_t wc
, ELEMENT value
)
110 uint32_t index1
= wc
>> (t
->q
+ t
->p
);
111 uint32_t index2
= (wc
>> t
->p
) & ((1 << t
->q
) - 1);
112 uint32_t index3
= wc
& ((1 << t
->p
) - 1);
115 if (value
== CONCAT(TABLE
,_get
) (t
, wc
))
118 if (index1
>= t
->level1_size
)
120 if (index1
>= t
->level1_alloc
)
122 size_t alloc
= 2 * t
->level1_alloc
;
125 t
->level1
= (uint32_t *) xrealloc ((char *) t
->level1
,
126 alloc
* sizeof (uint32_t));
127 t
->level1_alloc
= alloc
;
129 while (index1
>= t
->level1_size
)
130 t
->level1
[t
->level1_size
++] = EMPTY
;
133 if (t
->level1
[index1
] == EMPTY
)
135 if (t
->level2_size
== t
->level2_alloc
)
137 size_t alloc
= 2 * t
->level2_alloc
+ 1;
138 t
->level2
= (uint32_t *) xrealloc ((char *) t
->level2
,
139 (alloc
<< t
->q
) * sizeof (uint32_t));
140 t
->level2_alloc
= alloc
;
142 i1
= t
->level2_size
<< t
->q
;
143 i2
= (t
->level2_size
+ 1) << t
->q
;
144 for (i
= i1
; i
< i2
; i
++)
145 t
->level2
[i
] = EMPTY
;
146 t
->level1
[index1
] = t
->level2_size
++;
149 index2
+= t
->level1
[index1
] << t
->q
;
151 if (t
->level2
[index2
] == EMPTY
)
153 if (t
->level3_size
== t
->level3_alloc
)
155 size_t alloc
= 2 * t
->level3_alloc
+ 1;
156 t
->level3
= (ELEMENT
*) xrealloc ((char *) t
->level3
,
157 (alloc
<< t
->p
) * sizeof (ELEMENT
));
158 t
->level3_alloc
= alloc
;
160 i1
= t
->level3_size
<< t
->p
;
161 i2
= (t
->level3_size
+ 1) << t
->p
;
162 for (i
= i1
; i
< i2
; i
++)
163 t
->level3
[i
] = DEFAULT
;
164 t
->level2
[index2
] = t
->level3_size
++;
167 index3
+= t
->level2
[index2
] << t
->p
;
169 t
->level3
[index3
] = value
;
173 /* Apply a function to all entries in the table. */
175 CONCAT(TABLE
,_iterate
) (struct TABLE
*t
,
176 void (*fn
) (uint32_t wc
, ELEMENT value
))
179 for (index1
= 0; index1
< t
->level1_size
; index1
++)
181 uint32_t lookup1
= t
->level1
[index1
];
182 if (lookup1
!= EMPTY
)
184 uint32_t lookup1_shifted
= lookup1
<< t
->q
;
186 for (index2
= 0; index2
< (1 << t
->q
); index2
++)
188 uint32_t lookup2
= t
->level2
[index2
+ lookup1_shifted
];
189 if (lookup2
!= EMPTY
)
191 uint32_t lookup2_shifted
= lookup2
<< t
->p
;
193 for (index3
= 0; index3
< (1 << t
->p
); index3
++)
195 ELEMENT lookup3
= t
->level3
[index3
+ lookup2_shifted
];
196 if (lookup3
!= DEFAULT
)
197 fn ((((index1
<< t
->q
) + index2
) << t
->p
) + index3
,
206 /* GCC ATM seems to do a poor job with pointers to nested functions passed
207 to inlined functions. Help it a little bit with this hack. */
208 #define wchead_table_iterate(tp, fn) \
211 struct wchead_table *t = (tp); \
213 for (index1 = 0; index1 < t->level1_size; index1++) \
215 uint32_t lookup1 = t->level1[index1]; \
216 if (lookup1 != ((uint32_t) ~0)) \
218 uint32_t lookup1_shifted = lookup1 << t->q; \
220 for (index2 = 0; index2 < (1 << t->q); index2++) \
222 uint32_t lookup2 = t->level2[index2 + lookup1_shifted]; \
223 if (lookup2 != ((uint32_t) ~0)) \
225 uint32_t lookup2_shifted = lookup2 << t->p; \
227 for (index3 = 0; index3 < (1 << t->p); index3++) \
229 struct element_t *lookup3 \
230 = t->level3[index3 + lookup2_shifted]; \
231 if (lookup3 != NULL) \
232 fn ((((index1 << t->q) + index2) << t->p) + index3, \
244 /* Finalize and shrink. */
246 CONCAT(TABLE
,_finalize
) (struct TABLE
*t
)
249 uint32_t reorder3
[t
->level3_size
];
250 uint32_t reorder2
[t
->level2_size
];
251 uint32_t level1_offset
, level2_offset
, level3_offset
, last_offset
;
253 /* Uniquify level3 blocks. */
255 for (j
= 0; j
< t
->level3_size
; j
++)
257 for (i
= 0; i
< k
; i
++)
258 if (memcmp (&t
->level3
[i
<< t
->p
], &t
->level3
[j
<< t
->p
],
259 (1 << t
->p
) * sizeof (ELEMENT
)) == 0)
261 /* Relocate block j to block i. */
266 memcpy (&t
->level3
[i
<< t
->p
], &t
->level3
[j
<< t
->p
],
267 (1 << t
->p
) * sizeof (ELEMENT
));
273 for (i
= 0; i
< (t
->level2_size
<< t
->q
); i
++)
274 if (t
->level2
[i
] != EMPTY
)
275 t
->level2
[i
] = reorder3
[t
->level2
[i
]];
277 /* Uniquify level2 blocks. */
279 for (j
= 0; j
< t
->level2_size
; j
++)
281 for (i
= 0; i
< k
; i
++)
282 if (memcmp (&t
->level2
[i
<< t
->q
], &t
->level2
[j
<< t
->q
],
283 (1 << t
->q
) * sizeof (uint32_t)) == 0)
285 /* Relocate block j to block i. */
290 memcpy (&t
->level2
[i
<< t
->q
], &t
->level2
[j
<< t
->q
],
291 (1 << t
->q
) * sizeof (uint32_t));
297 for (i
= 0; i
< t
->level1_size
; i
++)
298 if (t
->level1
[i
] != EMPTY
)
299 t
->level1
[i
] = reorder2
[t
->level1
[i
]];
301 /* Create and fill the resulting compressed representation. */
303 5 * sizeof (uint32_t)
304 + t
->level1_size
* sizeof (uint32_t)
305 + (t
->level2_size
<< t
->q
) * sizeof (uint32_t)
306 + (t
->level3_size
<< t
->p
) * sizeof (ELEMENT
);
307 t
->result_size
= (last_offset
+ 3) & ~3ul;
308 t
->result
= (char *) xmalloc (t
->result_size
);
311 5 * sizeof (uint32_t);
313 5 * sizeof (uint32_t)
314 + t
->level1_size
* sizeof (uint32_t);
316 5 * sizeof (uint32_t)
317 + t
->level1_size
* sizeof (uint32_t)
318 + (t
->level2_size
<< t
->q
) * sizeof (uint32_t);
320 ((uint32_t *) t
->result
)[0] = t
->q
+ t
->p
;
321 ((uint32_t *) t
->result
)[1] = t
->level1_size
;
322 ((uint32_t *) t
->result
)[2] = t
->p
;
323 ((uint32_t *) t
->result
)[3] = (1 << t
->q
) - 1;
324 ((uint32_t *) t
->result
)[4] = (1 << t
->p
) - 1;
326 for (i
= 0; i
< t
->level1_size
; i
++)
327 ((uint32_t *) (t
->result
+ level1_offset
))[i
] =
328 (t
->level1
[i
] == EMPTY
330 : (t
->level1
[i
] << t
->q
) * sizeof (uint32_t) + level2_offset
);
332 for (i
= 0; i
< (t
->level2_size
<< t
->q
); i
++)
333 ((uint32_t *) (t
->result
+ level2_offset
))[i
] =
334 (t
->level2
[i
] == EMPTY
336 : (t
->level2
[i
] << t
->p
) * sizeof (ELEMENT
) + level3_offset
);
338 for (i
= 0; i
< (t
->level3_size
<< t
->p
); i
++)
339 ((ELEMENT
*) (t
->result
+ level3_offset
))[i
] = t
->level3
[i
];
341 if (last_offset
< t
->result_size
)
342 memset (t
->result
+ last_offset
, 0, t
->result_size
- last_offset
);
344 if (t
->level1_alloc
> 0)
346 if (t
->level2_alloc
> 0)
348 if (t
->level3_alloc
> 0)