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$ Copyright (c) 2004 Internet Systems Consortium. All rights reserved.\n";
40 #include <omapip/omapip_p.h>
44 static int do_hash (const unsigned char *, unsigned, unsigned);
45 static int do_case_hash (const unsigned char *, unsigned, unsigned);
47 int new_hash_table (tp
, count
, file
, line
)
48 struct hash_table
**tp
;
53 struct hash_table
*rval
;
56 log_error ("%s(%d): new_hash_table called with null pointer.",
58 #if defined (POINTER_DEBUG)
64 log_error ("%s(%d): non-null target for new_hash_table.",
66 #if defined (POINTER_DEBUG)
70 rval
= dmalloc (sizeof (struct hash_table
) -
71 (DEFAULT_HASH_SIZE
* sizeof (struct hash_bucket
*)) +
72 (count
* sizeof (struct hash_bucket
*)), file
, line
);
75 rval
-> hash_count
= count
;
80 void free_hash_table (tp
, file
, line
)
81 struct hash_table
**tp
;
86 __unused
struct hash_bucket
*hbc
, *hbn
= (struct hash_bucket
*)0;
87 struct hash_table
*ptr
= *tp
;
89 #if defined (DEBUG_MEMORY_LEAKAGE) || \
90 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
91 for (i
= 0; i
< ptr
-> hash_count
; i
++) {
92 for (hbc
= ptr
-> buckets
[i
]; hbc
; hbc
= hbn
) {
94 if (ptr
-> dereferencer
&& hbc
-> value
)
95 (*ptr
-> dereferencer
) (&hbc
-> value
, MDL
);
97 for (hbc
= ptr
-> buckets
[i
]; hbc
; hbc
= hbn
) {
99 free_hash_bucket (hbc
, MDL
);
101 ptr
-> buckets
[i
] = (struct hash_bucket
*)0;
105 dfree ((VOIDPTR
)ptr
, MDL
);
106 *tp
= (struct hash_table
*)0;
109 struct hash_bucket
*free_hash_buckets
;
111 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
112 struct hash_bucket
*hash_bucket_hunks
;
114 void relinquish_hash_bucket_hunks ()
116 struct hash_bucket
*c
, *n
, **p
;
118 /* Account for all the hash buckets on the free list. */
119 p
= &free_hash_buckets
;
120 for (c
= free_hash_buckets
; c
; c
= c
-> next
) {
121 for (n
= hash_bucket_hunks
; n
; n
= n
-> next
) {
122 if (c
> n
&& c
< n
+ 127) {
128 /* If we didn't delete the hash bucket from the free list,
129 advance the pointer. */
134 for (c
= hash_bucket_hunks
; c
; c
= n
) {
136 if (c
-> len
!= 126) {
137 log_info ("hashbucket %lx hash_buckets %d free %u",
138 (unsigned long)c
, 127, c
-> len
);
145 struct hash_bucket
*new_hash_bucket (file
, line
)
149 struct hash_bucket
*rval
;
151 if (!free_hash_buckets
) {
152 rval
= dmalloc (127 * sizeof (struct hash_bucket
),
156 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
157 rval
-> next
= hash_bucket_hunks
;
158 hash_bucket_hunks
= rval
;
159 hash_bucket_hunks
-> len
= 0;
163 for (; i
< 127; i
++) {
164 rval
-> next
= free_hash_buckets
;
165 free_hash_buckets
= rval
;
169 rval
= free_hash_buckets
;
170 free_hash_buckets
= rval
-> next
;
174 void free_hash_bucket (ptr
, file
, line
)
175 struct hash_bucket
*ptr
;
179 __unused
struct hash_bucket
*hp
;
180 #if defined (DEBUG_MALLOC_POOL)
181 for (hp
= free_hash_buckets
; hp
; hp
= hp
-> next
) {
183 log_error ("hash bucket freed twice!");
188 ptr
-> next
= free_hash_buckets
;
189 free_hash_buckets
= ptr
;
192 int new_hash (struct hash_table
**rp
,
193 hash_reference referencer
,
194 hash_dereference dereferencer
,
195 int casep
, const char *file
, int line
)
197 if (!new_hash_table (rp
, DEFAULT_HASH_SIZE
, file
, line
))
199 memset (&(*rp
) -> buckets
[0], 0,
200 DEFAULT_HASH_SIZE
* sizeof (struct hash_bucket
*));
201 (*rp
) -> referencer
= referencer
;
202 (*rp
) -> dereferencer
= dereferencer
;
204 (*rp
) -> cmp
= casecmp
;
205 (*rp
) -> do_hash
= do_case_hash
;
207 (*rp
) -> cmp
= (hash_comparator_t
)memcmp
;
208 (*rp
) -> do_hash
= do_hash
;
213 static int do_case_hash (name
, len
, size
)
214 const unsigned char *name
;
218 register int accum
= 0;
219 register const unsigned char *s
= (const unsigned char *)name
;
224 /* Make the hash case-insensitive. */
226 if (isascii (c
) && isupper (c
))
229 /* Add the character in... */
230 accum
= (accum
<< 1) + c
;
232 /* Add carry back in... */
233 while (accum
> 65535) {
234 accum
= (accum
& 65535) + (accum
>> 16);
240 static int do_hash (name
, len
, size
)
241 const unsigned char *name
;
245 register int accum
= 0;
246 register const unsigned char *s
= (const unsigned char *)name
;
250 /* Add the character in... */
251 accum
= (accum
<< 1) + *s
++;
253 /* Add carry back in... */
254 while (accum
> 65535) {
255 accum
= (accum
& 65535) + (accum
>> 16);
261 void add_hash (table
, name
, len
, pointer
, file
, line
)
262 struct hash_table
*table
;
264 const unsigned char *name
;
265 hashed_object_t
*pointer
;
270 struct hash_bucket
*bp
;
277 len
= strlen ((const char *)name
);
279 hashno
= (*table
-> do_hash
) (name
, len
, table
-> hash_count
);
280 bp
= new_hash_bucket (file
, line
);
283 log_error ("Can't add %s to hash table.", name
);
287 if (table
-> referencer
) {
289 (*(table
-> referencer
)) (foo
, pointer
, file
, line
);
291 bp
-> value
= pointer
;
292 bp
-> next
= table
-> buckets
[hashno
];
294 table
-> buckets
[hashno
] = bp
;
297 void delete_hash_entry (table
, name
, len
, file
, line
)
298 struct hash_table
*table
;
300 const unsigned char *name
;
305 struct hash_bucket
*bp
, *pbp
= (struct hash_bucket
*)0;
312 len
= strlen ((const char *)name
);
314 hashno
= (*table
-> do_hash
) (name
, len
, table
-> hash_count
);
316 /* Go through the list looking for an entry that matches;
317 if we find it, delete it. */
318 for (bp
= table
-> buckets
[hashno
]; bp
; bp
= bp
-> next
) {
320 !strcmp ((const char *)bp
-> name
, (const char *)name
)) ||
322 !(*table
-> cmp
) (bp
-> name
, name
, len
))) {
324 pbp
-> next
= bp
-> next
;
326 table
-> buckets
[hashno
] = bp
-> next
;
328 if (bp
-> value
&& table
-> dereferencer
) {
330 (*(table
-> dereferencer
)) (foo
, file
, line
);
332 free_hash_bucket (bp
, file
, line
);
335 pbp
= bp
; /* jwg, 9/6/96 - nice catch! */
339 int hash_lookup (vp
, table
, name
, len
, file
, line
)
340 hashed_object_t
**vp
;
341 struct hash_table
*table
;
342 const unsigned char *name
;
348 struct hash_bucket
*bp
;
353 len
= strlen ((const char *)name
);
355 hashno
= (*table
-> do_hash
) (name
, len
, table
-> hash_count
);
357 for (bp
= table
-> buckets
[hashno
]; bp
; bp
= bp
-> next
) {
359 && !(*table
-> cmp
) (bp
-> name
, name
, len
)) {
360 if (table
-> referencer
)
361 (*table
-> referencer
) (vp
, bp
-> value
,
371 int hash_foreach (struct hash_table
*table
, hash_foreach_func func
)
374 struct hash_bucket
*bp
, *next
;
380 for (i
= 0; i
< table
-> hash_count
; i
++) {
381 bp
= table
-> buckets
[i
];
384 (*func
) (bp
-> name
, bp
-> len
, bp
-> value
);
392 int casecmp (const void *v1
, const void *v2
, unsigned long len
)
398 for (i
= 0; i
< len
; i
++)
401 if (isascii (s
[i
]) && isupper (s
[i
]))
402 c1
= tolower (s
[i
]);
406 if (isascii (t
[i
]) && isupper (t
[i
]))
407 c2
= tolower (t
[i
]);