1 /* Copyright (C) 1995, 1996 Tom Lord
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)
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.
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.
21 * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
31 static struct rx_hash *
32 default_hash_alloc (struct rx_hash_rules * rules)
34 static struct rx_hash *
35 default_hash_alloc (rules)
36 struct rx_hash_rules * rules;
39 return (struct rx_hash *)malloc (sizeof (struct rx_hash));
44 static struct rx_hash_item *
45 default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
47 static struct rx_hash_item *
48 default_hash_item_alloc (rules, value)
49 struct rx_hash_rules * rules;
53 struct rx_hash_item * it;
54 it = (struct rx_hash_item *)malloc (sizeof (*it));
66 default_free_hash (struct rx_hash * tab,
67 struct rx_hash_rules * rules)
70 default_free_hash (tab, rules)
72 struct rx_hash_rules * rules;
81 default_free_hash_item (struct rx_hash_item * item,
82 struct rx_hash_rules * rules)
85 default_free_hash_item (item, rules)
86 struct rx_hash_item * item;
87 struct rx_hash_rules * rules;
95 default_eq (void * va, void * vb)
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)
115 static unsigned long rx_hash_masks[4] =
124 #define JOIN_BYTE(H, B) (((H) + ((H) << 3) + (B)) & 0xf)
126 #define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))
132 struct rx_hash_item *
133 rx_hash_find (struct rx_hash * table,
136 struct rx_hash_rules * rules)
138 struct rx_hash_item *
139 rx_hash_find (table, hash, value, rules)
140 struct rx_hash * table;
143 struct rx_hash_rules * rules;
146 rx_hash_eq eq = EQ (rules);
148 long mask = rx_hash_masks [0];
149 int bucket = H2B(hash & mask);
151 while (RX_bitset_member (&table->nested_p, bucket))
153 table = (struct rx_hash *)(table->children [bucket]);
155 mask = rx_hash_masks[maskc];
156 bucket = H2B (hash & mask);
160 struct rx_hash_item * it;
161 it = (struct rx_hash_item *)(table->children[bucket]);
163 if (eq (it->data, value))
166 it = it->next_same_hash;
175 listlen (struct rx_hash_item * bucket)
179 struct rx_hash_item * bucket;
183 for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
190 overflows (struct rx_hash_item * bucket)
194 struct rx_hash_item * 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);
205 struct rx_hash_item *
206 rx_hash_store (struct rx_hash * table,
209 struct rx_hash_rules * rules)
211 struct rx_hash_item *
212 rx_hash_store (table, hash, value, rules)
213 struct rx_hash * table;
216 struct rx_hash_rules * rules;
219 rx_hash_eq eq = EQ (rules);
221 long mask = rx_hash_masks [0];
222 int bucket = H2B(hash & mask);
225 while (RX_bitset_member (&table->nested_p, bucket))
227 table = (struct rx_hash *)(table->children [bucket]);
229 mask = rx_hash_masks[maskc];
230 bucket = H2B(hash & mask);
235 struct rx_hash_item * it;
236 it = (struct rx_hash_item *)(table->children[bucket]);
238 if (eq (it->data, value))
241 it = it->next_same_hash;
246 && (overflows ((struct rx_hash_item *)table->children [bucket])))
248 struct rx_hash * newtab;
249 newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
252 rx_bzero ((char *)newtab, sizeof (*newtab));
253 newtab->parent = table;
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];
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;
271 ((struct rx_hash **)table->children)[bucket] = newtab;
272 RX_bitset_enjoin (&table->nested_p, bucket);
275 bucket = H2B(hash & newmask);
281 struct rx_hash_item * it = ((struct rx_hash_item *)
282 ITEM_ALLOC(rules) (rules, value));
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;
298 rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
301 rx_hash_free (it, rules)
302 struct rx_hash_item * it;
303 struct rx_hash_rules * rules;
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
317 int bucket = H2B (hash & rx_hash_masks [depth]);
318 struct rx_hash_item ** pos
319 = (struct rx_hash_item **)&table->children [bucket];
322 pos = &(*pos)->next_same_hash;
323 *pos = it->next_same_hash;
324 FREE_HASH_ITEM(rules) (it, rules);
326 while (!table->refs && depth)
328 struct rx_hash * save = table;
329 table = table->parent;
331 bucket = H2B(hash & rx_hash_masks [depth]);
333 table->children[bucket] = 0;
334 RX_bitset_remove (&table->nested_p, bucket);
335 FREE_HASH (rules) (save, rules);
342 rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
343 struct rx_hash_rules * rules)
346 rx_free_hash_table (tab, freefn, rules)
347 struct rx_hash * tab;
348 rx_hash_freefn freefn;
349 struct rx_hash_rules * rules;
354 for (x = 0; x < BKTS; ++x)
355 if (RX_bitset_member (&tab->nested_p, x))
357 rx_free_hash_table ((struct rx_hash *)tab->children[x],
359 FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules);
363 struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x];
366 struct rx_hash_item * that = them;
367 them = that->next_same_hash;
369 FREE_HASH_ITEM (rules) (that, rules);
378 rx_count_hash_nodes (struct rx_hash * st)
381 rx_count_hash_nodes (st)
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])));