3 Routines for manipulating hash tables... */
6 * Copyright (c) 2004-2006 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.7 2006/02/24 23:16:30 dhankins Exp $ Copyright (c) 2004-2006 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 if ((*func
)(bp
->name
, bp
->len
, bp
->value
)
393 int casecmp (const void *v1
, const void *v2
, unsigned long len
)
399 for (i
= 0; i
< len
; i
++)
402 if (isascii (s
[i
]) && isupper (s
[i
]))
403 c1
= tolower (s
[i
]);
407 if (isascii (t
[i
]) && isupper (t
[i
]))
408 c2
= tolower (t
[i
]);