]>
Commit | Line | Data |
---|---|---|
d76ed9a9 AS |
1 | /* Copyright (C) 1995, 1996 Tom Lord |
2 | * | |
3 | * This program is free software; you can redistribute it and/or modify | |
4 | * it under the terms of the GNU Library General Public License as published by | |
5 | * the Free Software Foundation; either version 2, or (at your option) | |
6 | * any later version. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
11 | * GNU Library General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU Library General Public License | |
14 | * along with this software; see the file COPYING. If not, write to | |
15 | * the Free Software Foundation, 59 Temple Place - Suite 330, | |
16 | * Boston, MA 02111-1307, USA. | |
17 | */ | |
18 | ||
19 | \f | |
20 | /* | |
21 | * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu) | |
22 | */ | |
23 | \f | |
24 | ||
25 | #include "rxall.h" | |
26 | #include "rxhash.h" | |
27 | ||
28 | \f | |
29 | ||
30 | #ifdef __STDC__ | |
31 | static struct rx_hash * | |
32 | default_hash_alloc (struct rx_hash_rules * rules) | |
33 | #else | |
34 | static struct rx_hash * | |
35 | default_hash_alloc (rules) | |
36 | struct rx_hash_rules * rules; | |
37 | #endif | |
38 | { | |
39 | return (struct rx_hash *)malloc (sizeof (struct rx_hash)); | |
40 | } | |
41 | ||
42 | ||
43 | #ifdef __STDC__ | |
44 | static struct rx_hash_item * | |
45 | default_hash_item_alloc (struct rx_hash_rules * rules, void * value) | |
46 | #else | |
47 | static struct rx_hash_item * | |
48 | default_hash_item_alloc (rules, value) | |
49 | struct rx_hash_rules * rules; | |
50 | void * value; | |
51 | #endif | |
52 | { | |
53 | struct rx_hash_item * it; | |
54 | it = (struct rx_hash_item *)malloc (sizeof (*it)); | |
55 | if (it) | |
56 | { | |
57 | it->data = value; | |
58 | it->binding = 0; | |
59 | } | |
60 | return it; | |
61 | } | |
62 | ||
63 | ||
64 | #ifdef __STDC__ | |
65 | static void | |
66 | default_free_hash (struct rx_hash * tab, | |
67 | struct rx_hash_rules * rules) | |
68 | #else | |
69 | static void | |
70 | default_free_hash (tab, rules) | |
71 | struct rx_hash * tab; | |
72 | struct rx_hash_rules * rules; | |
73 | #endif | |
74 | { | |
75 | free ((char *)tab); | |
76 | } | |
77 | ||
78 | ||
79 | #ifdef __STDC__ | |
80 | static void | |
81 | default_free_hash_item (struct rx_hash_item * item, | |
82 | struct rx_hash_rules * rules) | |
83 | #else | |
84 | static void | |
85 | default_free_hash_item (item, rules) | |
86 | struct rx_hash_item * item; | |
87 | struct rx_hash_rules * rules; | |
88 | #endif | |
89 | { | |
90 | free ((char *)item); | |
91 | } | |
92 | ||
93 | #ifdef __STDC__ | |
94 | static int | |
95 | default_eq (void * va, void * vb) | |
96 | #else | |
97 | static int | |
98 | default_eq (va, vb) | |
99 | void * va; | |
100 | void * vb; | |
101 | #endif | |
102 | { | |
103 | return va == vb; | |
104 | } | |
105 | ||
106 | \f | |
107 | ||
108 | #define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq) | |
109 | #define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc) | |
110 | #define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash) | |
111 | #define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) ? rules->hash_item_alloc : default_hash_item_alloc) | |
112 | #define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) ? rules->free_hash_item : default_free_hash_item) | |
113 | ||
114 | \f | |
115 | static unsigned long rx_hash_masks[4] = | |
116 | { | |
117 | 0x12488421, | |
118 | 0x96699669, | |
119 | 0xbe7dd7eb, | |
120 | 0xffffffff | |
121 | }; | |
122 | ||
123 | /* hash to bucket */ | |
124 | #define JOIN_BYTE(H, B) (((H) + ((H) << 3) + (B)) & 0xf) | |
125 | ||
126 | #define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf)) | |
127 | ||
128 | #define BKTS 16 | |
129 | ||
130 | /* Hash tables */ | |
131 | #ifdef __STDC__ | |
132 | struct rx_hash_item * | |
133 | rx_hash_find (struct rx_hash * table, | |
134 | unsigned long hash, | |
135 | void * value, | |
136 | struct rx_hash_rules * rules) | |
137 | #else | |
138 | struct rx_hash_item * | |
139 | rx_hash_find (table, hash, value, rules) | |
140 | struct rx_hash * table; | |
141 | unsigned long hash; | |
142 | void * value; | |
143 | struct rx_hash_rules * rules; | |
144 | #endif | |
145 | { | |
146 | rx_hash_eq eq = EQ (rules); | |
147 | int maskc = 0; | |
148 | long mask = rx_hash_masks [0]; | |
149 | int bucket = H2B(hash & mask); | |
150 | ||
151 | while (RX_bitset_member (&table->nested_p, bucket)) | |
152 | { | |
153 | table = (struct rx_hash *)(table->children [bucket]); | |
154 | ++maskc; | |
155 | mask = rx_hash_masks[maskc]; | |
156 | bucket = H2B (hash & mask); | |
157 | } | |
158 | ||
159 | { | |
160 | struct rx_hash_item * it; | |
161 | it = (struct rx_hash_item *)(table->children[bucket]); | |
162 | while (it) | |
163 | if (eq (it->data, value)) | |
164 | return it; | |
165 | else | |
166 | it = it->next_same_hash; | |
167 | } | |
168 | ||
169 | return 0; | |
170 | } | |
171 | ||
172 | ||
173 | #ifdef __STDC__ | |
174 | static int | |
175 | listlen (struct rx_hash_item * bucket) | |
176 | #else | |
177 | static int | |
178 | listlen (bucket) | |
179 | struct rx_hash_item * bucket; | |
180 | #endif | |
181 | { | |
182 | int i; | |
183 | for (i = 0; bucket; ++i, bucket = bucket->next_same_hash) | |
184 | ; | |
185 | return i; | |
186 | } | |
187 | ||
188 | #ifdef __STDC__ | |
189 | static int | |
190 | overflows (struct rx_hash_item * bucket) | |
191 | #else | |
192 | static int | |
193 | overflows (bucket) | |
194 | struct rx_hash_item * bucket; | |
195 | #endif | |
196 | { | |
197 | return !( bucket | |
198 | && bucket->next_same_hash | |
199 | && bucket->next_same_hash->next_same_hash | |
200 | && bucket->next_same_hash->next_same_hash->next_same_hash); | |
201 | } | |
202 | ||
203 | ||
204 | #ifdef __STDC__ | |
205 | struct rx_hash_item * | |
206 | rx_hash_store (struct rx_hash * table, | |
207 | unsigned long hash, | |
208 | void * value, | |
209 | struct rx_hash_rules * rules) | |
210 | #else | |
211 | struct rx_hash_item * | |
212 | rx_hash_store (table, hash, value, rules) | |
213 | struct rx_hash * table; | |
214 | unsigned long hash; | |
215 | void * value; | |
216 | struct rx_hash_rules * rules; | |
217 | #endif | |
218 | { | |
219 | rx_hash_eq eq = EQ (rules); | |
220 | int maskc = 0; | |
221 | long mask = rx_hash_masks [0]; | |
222 | int bucket = H2B(hash & mask); | |
223 | int depth = 0; | |
224 | ||
225 | while (RX_bitset_member (&table->nested_p, bucket)) | |
226 | { | |
227 | table = (struct rx_hash *)(table->children [bucket]); | |
228 | ++maskc; | |
229 | mask = rx_hash_masks[maskc]; | |
230 | bucket = H2B(hash & mask); | |
231 | ++depth; | |
232 | } | |
233 | ||
234 | { | |
235 | struct rx_hash_item * it; | |
236 | it = (struct rx_hash_item *)(table->children[bucket]); | |
237 | while (it) | |
238 | if (eq (it->data, value)) | |
239 | return it; | |
240 | else | |
241 | it = it->next_same_hash; | |
242 | } | |
243 | ||
244 | { | |
245 | if ( (depth < 3) | |
246 | && (overflows ((struct rx_hash_item *)table->children [bucket]))) | |
247 | { | |
248 | struct rx_hash * newtab; | |
249 | newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules); | |
250 | if (!newtab) | |
251 | goto add_to_bucket; | |
252 | rx_bzero ((char *)newtab, sizeof (*newtab)); | |
253 | newtab->parent = table; | |
254 | { | |
255 | struct rx_hash_item * them; | |
256 | unsigned long newmask; | |
257 | them = (struct rx_hash_item *)table->children[bucket]; | |
258 | newmask = rx_hash_masks[maskc + 1]; | |
259 | while (them) | |
260 | { | |
261 | struct rx_hash_item * save = them->next_same_hash; | |
262 | int new_buck = H2B(them->hash & newmask); | |
263 | them->next_same_hash = ((struct rx_hash_item *) | |
264 | newtab->children[new_buck]); | |
265 | ((struct rx_hash_item **)newtab->children)[new_buck] = them; | |
266 | them->table = newtab; | |
267 | them = save; | |
268 | ++newtab->refs; | |
269 | --table->refs; | |
270 | } | |
271 | ((struct rx_hash **)table->children)[bucket] = newtab; | |
272 | RX_bitset_enjoin (&table->nested_p, bucket); | |
273 | ++table->refs; | |
274 | table = newtab; | |
275 | bucket = H2B(hash & newmask); | |
276 | } | |
277 | } | |
278 | } | |
279 | add_to_bucket: | |
280 | { | |
281 | struct rx_hash_item * it = ((struct rx_hash_item *) | |
282 | ITEM_ALLOC(rules) (rules, value)); | |
283 | if (!it) | |
284 | return 0; | |
285 | it->hash = hash; | |
286 | it->table = table; | |
287 | /* DATA and BINDING are to be set in hash_item_alloc */ | |
288 | it->next_same_hash = (struct rx_hash_item *)table->children [bucket]; | |
289 | ((struct rx_hash_item **)table->children)[bucket] = it; | |
290 | ++table->refs; | |
291 | return it; | |
292 | } | |
293 | } | |
294 | ||
295 | ||
296 | #ifdef __STDC__ | |
297 | void | |
298 | rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules) | |
299 | #else | |
300 | void | |
301 | rx_hash_free (it, rules) | |
302 | struct rx_hash_item * it; | |
303 | struct rx_hash_rules * rules; | |
304 | #endif | |
305 | { | |
306 | if (it) | |
307 | { | |
308 | struct rx_hash * table = it->table; | |
309 | unsigned long hash = it->hash; | |
310 | int depth = (table->parent | |
311 | ? (table->parent->parent | |
312 | ? (table->parent->parent->parent | |
313 | ? 3 | |
314 | : 2) | |
315 | : 1) | |
316 | : 0); | |
317 | int bucket = H2B (hash & rx_hash_masks [depth]); | |
318 | struct rx_hash_item ** pos | |
319 | = (struct rx_hash_item **)&table->children [bucket]; | |
320 | ||
321 | while (*pos != it) | |
322 | pos = &(*pos)->next_same_hash; | |
323 | *pos = it->next_same_hash; | |
324 | FREE_HASH_ITEM(rules) (it, rules); | |
325 | --table->refs; | |
326 | while (!table->refs && depth) | |
327 | { | |
328 | struct rx_hash * save = table; | |
329 | table = table->parent; | |
330 | --depth; | |
331 | bucket = H2B(hash & rx_hash_masks [depth]); | |
332 | --table->refs; | |
333 | table->children[bucket] = 0; | |
334 | RX_bitset_remove (&table->nested_p, bucket); | |
335 | FREE_HASH (rules) (save, rules); | |
336 | } | |
337 | } | |
338 | } | |
339 | ||
340 | #ifdef __STDC__ | |
341 | void | |
342 | rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn, | |
343 | struct rx_hash_rules * rules) | |
344 | #else | |
345 | void | |
346 | rx_free_hash_table (tab, freefn, rules) | |
347 | struct rx_hash * tab; | |
348 | rx_hash_freefn freefn; | |
349 | struct rx_hash_rules * rules; | |
350 | #endif | |
351 | { | |
352 | int x; | |
353 | ||
354 | for (x = 0; x < BKTS; ++x) | |
355 | if (RX_bitset_member (&tab->nested_p, x)) | |
356 | { | |
357 | rx_free_hash_table ((struct rx_hash *)tab->children[x], | |
358 | freefn, rules); | |
359 | FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules); | |
360 | } | |
361 | else | |
362 | { | |
363 | struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x]; | |
364 | while (them) | |
365 | { | |
366 | struct rx_hash_item * that = them; | |
367 | them = that->next_same_hash; | |
368 | freefn (that); | |
369 | FREE_HASH_ITEM (rules) (that, rules); | |
370 | } | |
371 | } | |
372 | } | |
373 | ||
374 | ||
375 | ||
376 | #ifdef __STDC__ | |
377 | int | |
378 | rx_count_hash_nodes (struct rx_hash * st) | |
379 | #else | |
380 | int | |
381 | rx_count_hash_nodes (st) | |
382 | struct rx_hash * st; | |
383 | #endif | |
384 | { | |
385 | int x; | |
386 | int count = 0; | |
387 | for (x = 0; x < BKTS; ++x) | |
388 | count += ((RX_bitset_member (&st->nested_p, x)) | |
389 | ? rx_count_hash_nodes ((struct rx_hash *)st->children[x]) | |
390 | : listlen ((struct rx_hash_item *)(st->children[x]))); | |
391 | ||
392 | return count; | |
393 | } | |
394 |