]>
jfr.im git - irc/evilnet/x3.git/blob - rx/rxhash.c
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
])));