3 Routines for manipulating hash tables... */
6 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
7 * Copyright (c) 1995-2003 by Internet Software Consortium
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
19 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * Internet Systems Consortium, Inc.
23 * Redwood City, CA 94063
27 * This software has been written for Internet Systems Consortium
28 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
29 * To learn more about Internet Systems Consortium, see
30 * ``http://www.isc.org/''. To learn more about Vixie Enterprises,
31 * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
32 * ``http://www.nominum.com''.
36 static char copyright[] =
37 "$Id: hash.c,v 1.1.2.6 2004/06/10 17:59:47 dhankins Exp $ Copyright (c) 2004 Internet Systems Consortium. All rights reserved.\n";
40 #include <omapip/omapip_p.h>
43 static int do_hash (const unsigned char *, unsigned, unsigned);
44 static int do_case_hash (const unsigned char *, unsigned, unsigned);
46 int new_hash_table (tp, count, file, line)
47 struct hash_table **tp;
52 struct hash_table *rval;
55 log_error ("%s(%d): new_hash_table called with null pointer.",
57 #if defined (POINTER_DEBUG)
63 log_error ("%s(%d): non-null target for new_hash_table.",
65 #if defined (POINTER_DEBUG)
69 rval = dmalloc (sizeof (struct hash_table) -
70 (DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *)) +
71 (count * sizeof (struct hash_bucket *)), file, line);
74 rval -> hash_count = count;
79 void free_hash_table (tp, file, line)
80 struct hash_table **tp;
85 struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
86 struct hash_table *ptr = *tp;
88 #if defined (DEBUG_MEMORY_LEAKAGE) || \
89 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
90 for (i = 0; i < ptr -> hash_count; i++) {
91 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
93 if (ptr -> dereferencer && hbc -> value)
94 (*ptr -> dereferencer) (&hbc -> value, MDL);
96 for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
98 free_hash_bucket (hbc, MDL);
100 ptr -> buckets [i] = (struct hash_bucket *)0;
104 dfree ((VOIDPTR)ptr, MDL);
105 *tp = (struct hash_table *)0;
108 struct hash_bucket *free_hash_buckets;
110 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
111 struct hash_bucket *hash_bucket_hunks;
113 void relinquish_hash_bucket_hunks ()
115 struct hash_bucket *c, *n, **p;
117 /* Account for all the hash buckets on the free list. */
118 p = &free_hash_buckets;
119 for (c = free_hash_buckets; c; c = c -> next) {
120 for (n = hash_bucket_hunks; n; n = n -> next) {
121 if (c > n && c < n + 127) {
127 /* If we didn't delete the hash bucket from the free list,
128 advance the pointer. */
133 for (c = hash_bucket_hunks; c; c = n) {
135 if (c -> len != 126) {
136 log_info ("hashbucket %lx hash_buckets %d free %u",
137 (unsigned long)c, 127, c -> len);
144 struct hash_bucket *new_hash_bucket (file, line)
148 struct hash_bucket *rval;
150 if (!free_hash_buckets) {
151 rval = dmalloc (127 * sizeof (struct hash_bucket),
155 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
156 rval -> next = hash_bucket_hunks;
157 hash_bucket_hunks = rval;
158 hash_bucket_hunks -> len = 0;
162 for (; i < 127; i++) {
163 rval -> next = free_hash_buckets;
164 free_hash_buckets = rval;
168 rval = free_hash_buckets;
169 free_hash_buckets = rval -> next;
173 void free_hash_bucket (ptr, file, line)
174 struct hash_bucket *ptr;
178 struct hash_bucket *hp;
179 #if defined (DEBUG_MALLOC_POOL)
180 for (hp = free_hash_buckets; hp; hp = hp -> next) {
182 log_error ("hash bucket freed twice!");
187 ptr -> next = free_hash_buckets;
188 free_hash_buckets = ptr;
191 int new_hash (struct hash_table **rp,
192 hash_reference referencer,
193 hash_dereference dereferencer,
194 int casep, const char *file, int line)
196 if (!new_hash_table (rp, DEFAULT_HASH_SIZE, file, line))
198 memset (&(*rp) -> buckets [0], 0,
199 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
200 (*rp) -> referencer = referencer;
201 (*rp) -> dereferencer = dereferencer;
203 (*rp) -> cmp = casecmp;
204 (*rp) -> do_hash = do_case_hash;
206 (*rp) -> cmp = (hash_comparator_t)memcmp;
207 (*rp) -> do_hash = do_hash;
212 static int do_case_hash (name, len, size)
213 const unsigned char *name;
217 register int accum = 0;
218 register const unsigned char *s = (const unsigned char *)name;
223 /* Make the hash case-insensitive. */
225 if (isascii (c) && isupper (c))
228 /* Add the character in... */
229 accum = (accum << 1) + c;
231 /* Add carry back in... */
232 while (accum > 65535) {
233 accum = (accum & 65535) + (accum >> 16);
239 static int do_hash (name, len, size)
240 const unsigned char *name;
244 register int accum = 0;
245 register const unsigned char *s = (const unsigned char *)name;
249 /* Add the character in... */
250 accum = (accum << 1) + *s++;
252 /* Add carry back in... */
253 while (accum > 65535) {
254 accum = (accum & 65535) + (accum >> 16);
260 void add_hash (table, name, len, pointer, file, line)
261 struct hash_table *table;
263 const unsigned char *name;
264 hashed_object_t *pointer;
269 struct hash_bucket *bp;
276 len = strlen ((const char *)name);
278 hashno = (*table -> do_hash) (name, len, table -> hash_count);
279 bp = new_hash_bucket (file, line);
282 log_error ("Can't add %s to hash table.", name);
286 if (table -> referencer) {
288 (*(table -> referencer)) (foo, pointer, file, line);
290 bp -> value = pointer;
291 bp -> next = table -> buckets [hashno];
293 table -> buckets [hashno] = bp;
296 void delete_hash_entry (table, name, len, file, line)
297 struct hash_table *table;
299 const unsigned char *name;
304 struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
311 len = strlen ((const char *)name);
313 hashno = (*table -> do_hash) (name, len, table -> hash_count);
315 /* Go through the list looking for an entry that matches;
316 if we find it, delete it. */
317 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
319 !strcmp ((const char *)bp -> name, (const char *)name)) ||
321 !(*table -> cmp) (bp -> name, name, len))) {
323 pbp -> next = bp -> next;
325 table -> buckets [hashno] = bp -> next;
327 if (bp -> value && table -> dereferencer) {
329 (*(table -> dereferencer)) (foo, file, line);
331 free_hash_bucket (bp, file, line);
334 pbp = bp; /* jwg, 9/6/96 - nice catch! */
338 int hash_lookup (vp, table, name, len, file, line)
339 hashed_object_t **vp;
340 struct hash_table *table;
341 const unsigned char *name;
347 struct hash_bucket *bp;
352 len = strlen ((const char *)name);
354 hashno = (*table -> do_hash) (name, len, table -> hash_count);
356 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
358 && !(*table -> cmp) (bp -> name, name, len)) {
359 if (table -> referencer)
360 (*table -> referencer) (vp, bp -> value,
370 int hash_foreach (struct hash_table *table, hash_foreach_func func)
373 struct hash_bucket *bp, *next;
379 for (i = 0; i < table -> hash_count; i++) {
380 bp = table -> buckets [i];
383 (*func) (bp -> name, bp -> len, bp -> value);
391 int casecmp (const void *v1, const void *v2, unsigned long len)
397 for (i = 0; i < len; i++)
400 if (isascii (s [i]) && isupper (s [i]))
401 c1 = tolower (s [i]);
405 if (isascii (t [i]) && isupper (t [i]))
406 c2 = tolower (t [i]);