3 Routines for manipulating hash tables... */
6 * Copyright (c) 2009-2010 by Internet Systems Consortium, Inc. ("ISC")
7 * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
8 * Copyright (c) 1995-2003 by Internet Software Consortium
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
14 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
20 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22 * Internet Systems Consortium, Inc.
24 * Redwood City, CA 94063
26 * https://www.isc.org/
28 * This software has been written for Internet Systems Consortium
29 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
30 * To learn more about Internet Systems Consortium, see
31 * ``https://www.isc.org/''. To learn more about Vixie Enterprises,
32 * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
33 * ``http://www.nominum.com''.
38 #include <omapip/omapip_p.h>
43 find_length(const void *key
,
44 unsigned (*do_hash
)(const void *, unsigned, unsigned))
46 if (do_hash
== do_case_hash
|| do_hash
== do_string_hash
)
47 return strlen((const char *)key
);
48 if (do_hash
== do_number_hash
)
49 return sizeof(unsigned);
50 if (do_hash
== do_ip4_hash
)
53 log_debug("Unexpected hash function at %s:%d.", MDL
);
55 * If we get a hash function we don't specifically expect
56 * return a length of 0, this covers the case where a client
57 * id has a length of 0.
62 int new_hash_table (tp
, count
, file
, line
)
63 struct hash_table
**tp
;
68 struct hash_table
*rval
;
72 log_error ("%s(%d): new_hash_table called with null pointer.",
74 #if defined (POINTER_DEBUG)
80 log_error ("%s(%d): non-null target for new_hash_table.",
82 #if defined (POINTER_DEBUG)
87 /* There is one hash bucket in the structure. Allocate extra
88 * memory beyond the end of the structure to fulfill the requested
89 * count ("count - 1"). Do not let there be less than one.
96 rval
= dmalloc(sizeof(struct hash_table
) +
97 (extra
* sizeof(struct hash_bucket
*)), file
, line
);
100 rval
-> hash_count
= count
;
105 void free_hash_table (tp
, file
, line
)
106 struct hash_table
**tp
;
110 struct hash_table
*ptr
= *tp
;
112 #if defined (DEBUG_MEMORY_LEAKAGE) || \
113 defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
115 struct hash_bucket
*hbc
, *hbn
= (struct hash_bucket
*)0;
117 for (i
= 0; i
< ptr
-> hash_count
; i
++) {
118 for (hbc
= ptr
-> buckets
[i
]; hbc
; hbc
= hbn
) {
120 if (ptr
-> dereferencer
&& hbc
-> value
)
121 (*ptr
-> dereferencer
) (&hbc
-> value
, MDL
);
123 for (hbc
= ptr
-> buckets
[i
]; hbc
; hbc
= hbn
) {
125 free_hash_bucket (hbc
, MDL
);
127 ptr
-> buckets
[i
] = (struct hash_bucket
*)0;
131 dfree((void *)ptr
, MDL
);
132 *tp
= (struct hash_table
*)0;
135 struct hash_bucket
*free_hash_buckets
;
137 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
138 struct hash_bucket
*hash_bucket_hunks
;
140 void relinquish_hash_bucket_hunks ()
142 struct hash_bucket
*c
, *n
, **p
;
144 /* Account for all the hash buckets on the free list. */
145 p
= &free_hash_buckets
;
146 for (c
= free_hash_buckets
; c
; c
= c
-> next
) {
147 for (n
= hash_bucket_hunks
; n
; n
= n
-> next
) {
148 if (c
> n
&& c
< n
+ 127) {
154 /* If we didn't delete the hash bucket from the free list,
155 advance the pointer. */
160 for (c
= hash_bucket_hunks
; c
; c
= n
) {
162 if (c
-> len
!= 126) {
163 log_info ("hashbucket %lx hash_buckets %d free %u",
164 (unsigned long)c
, 127, c
-> len
);
171 struct hash_bucket
*new_hash_bucket (file
, line
)
175 struct hash_bucket
*rval
;
177 if (!free_hash_buckets
) {
178 rval
= dmalloc (127 * sizeof (struct hash_bucket
),
182 # if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
183 rval
-> next
= hash_bucket_hunks
;
184 hash_bucket_hunks
= rval
;
185 hash_bucket_hunks
-> len
= 0;
189 for (; i
< 127; i
++) {
190 rval
-> next
= free_hash_buckets
;
191 free_hash_buckets
= rval
;
195 rval
= free_hash_buckets
;
196 free_hash_buckets
= rval
-> next
;
200 void free_hash_bucket (ptr
, file
, line
)
201 struct hash_bucket
*ptr
;
205 #if defined (DEBUG_MALLOC_POOL)
206 struct hash_bucket
*hp
;
208 for (hp
= free_hash_buckets
; hp
; hp
= hp
-> next
) {
210 log_error ("hash bucket freed twice!");
215 ptr
-> next
= free_hash_buckets
;
216 free_hash_buckets
= ptr
;
219 int new_hash(struct hash_table
**rp
,
220 hash_reference referencer
,
221 hash_dereference dereferencer
,
223 unsigned (*hasher
)(const void *, unsigned, unsigned),
224 const char *file
, int line
)
227 hsize
= DEFAULT_HASH_SIZE
;
229 if (!new_hash_table (rp
, hsize
, file
, line
))
232 memset ((*rp
)->buckets
, 0, hsize
* sizeof(struct hash_bucket
*));
234 (*rp
)->referencer
= referencer
;
235 (*rp
)->dereferencer
= dereferencer
;
236 (*rp
)->do_hash
= hasher
;
238 if (hasher
== do_case_hash
)
239 (*rp
)->cmp
= casecmp
;
247 do_case_hash(const void *name
, unsigned len
, unsigned size
)
249 register unsigned accum
= 0;
250 register const unsigned char *s
= name
;
255 /* Make the hash case-insensitive. */
260 /* Add the character in... */
261 accum
= (accum
<< 1) + c
;
263 /* Add carry back in... */
264 while (accum
> 65535) {
265 accum
= (accum
& 65535) + (accum
>> 16);
273 do_string_hash(const void *name
, unsigned len
, unsigned size
)
275 register unsigned accum
= 0;
276 register const unsigned char *s
= (const unsigned char *)name
;
280 /* Add the character in... */
281 accum
= (accum
<< 1) + *s
++;
283 /* Add carry back in... */
284 while (accum
> 65535) {
285 accum
= (accum
& 65535) + (accum
>> 16);
291 /* Client identifiers are generally 32-bits of ordinary
292 * non-randomness followed by 24-bits of unordinary randomness.
293 * So, end-align in 24-bit chunks, and xor any preceding data
294 * just to mix it up a little.
297 do_id_hash(const void *name
, unsigned len
, unsigned size
)
299 register unsigned accum
= 0;
300 register const unsigned char *s
= (const unsigned char *)name
;
301 const unsigned char *end
= s
+ len
;
307 * The switch handles our starting conditions, then we hash the
308 * remaining bytes in groups of 3
331 do_number_hash(const void *key
, unsigned len
, unsigned size
)
333 register unsigned number
= *((const unsigned *)key
);
335 return number
% size
;
339 do_ip4_hash(const void *key
, unsigned len
, unsigned size
)
343 memcpy(&number
, key
, 4);
345 number
= ntohl(number
);
347 return number
% size
;
351 hash_report(struct hash_table
*table
)
353 static unsigned char retbuf
[sizeof("Contents/Size (%): "
354 "2147483647/2147483647 "
356 "Min/max: 2147483647/2147483647")];
357 unsigned curlen
, pct
, contents
=0, minlen
=UINT_MAX
, maxlen
=0;
359 struct hash_bucket
*bp
;
362 return (unsigned char *) "No table.";
364 if (table
->hash_count
== 0)
365 return (unsigned char *) "Invalid hash table.";
367 for (i
= 0 ; i
< table
->hash_count
; i
++) {
370 bp
= table
->buckets
[i
];
384 if (contents
>= (UINT_MAX
/ 100))
385 pct
= contents
/ ((table
->hash_count
/ 100) + 1);
387 pct
= (contents
* 100) / table
->hash_count
;
389 if (contents
> 2147483647 ||
390 table
->hash_count
> 2147483647 ||
392 minlen
> 2147483647 ||
394 return (unsigned char *) "Report out of range for display.";
396 sprintf((char *)retbuf
,
397 "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
398 contents
, table
->hash_count
, pct
, minlen
, maxlen
);
403 void add_hash (table
, key
, len
, pointer
, file
, line
)
404 struct hash_table
*table
;
407 hashed_object_t
*pointer
;
412 struct hash_bucket
*bp
;
419 len
= find_length(key
, table
->do_hash
);
421 hashno
= (*table
->do_hash
)(key
, len
, table
->hash_count
);
422 bp
= new_hash_bucket (file
, line
);
425 log_error ("Can't add entry to hash table: no memory.");
429 if (table
-> referencer
) {
431 (*(table
-> referencer
)) (foo
, pointer
, file
, line
);
433 bp
-> value
= pointer
;
434 bp
-> next
= table
-> buckets
[hashno
];
436 table
-> buckets
[hashno
] = bp
;
439 void delete_hash_entry (table
, key
, len
, file
, line
)
440 struct hash_table
*table
;
447 struct hash_bucket
*bp
, *pbp
= (struct hash_bucket
*)0;
454 len
= find_length(key
, table
->do_hash
);
456 hashno
= (*table
->do_hash
)(key
, len
, table
->hash_count
);
458 /* Go through the list looking for an entry that matches;
459 if we find it, delete it. */
460 for (bp
= table
-> buckets
[hashno
]; bp
; bp
= bp
-> next
) {
462 !strcmp ((const char *)bp
->name
, key
)) ||
464 !(table
-> cmp
)(bp
->name
, key
, len
))) {
466 pbp
-> next
= bp
-> next
;
468 table
-> buckets
[hashno
] = bp
-> next
;
470 if (bp
-> value
&& table
-> dereferencer
) {
472 (*(table
-> dereferencer
)) (foo
, file
, line
);
474 free_hash_bucket (bp
, file
, line
);
477 pbp
= bp
; /* jwg, 9/6/96 - nice catch! */
481 int hash_lookup (vp
, table
, key
, len
, file
, line
)
482 hashed_object_t
**vp
;
483 struct hash_table
*table
;
490 struct hash_bucket
*bp
;
495 len
= find_length(key
, table
->do_hash
);
498 log_fatal("Internal inconsistency: storage value has not been "
499 "initialized to zero (from %s:%d).", file
, line
);
502 hashno
= (*table
->do_hash
)(key
, len
, table
->hash_count
);
504 for (bp
= table
-> buckets
[hashno
]; bp
; bp
= bp
-> next
) {
506 && !(*table
->cmp
)(bp
->name
, key
, len
)) {
507 if (table
-> referencer
)
508 (*table
-> referencer
) (vp
, bp
-> value
,
518 int hash_foreach (struct hash_table
*table
, hash_foreach_func func
)
521 struct hash_bucket
*bp
, *next
;
527 for (i
= 0; i
< table
-> hash_count
; i
++) {
528 bp
= table
-> buckets
[i
];
531 if ((*func
)(bp
->name
, bp
->len
, bp
->value
)
541 int casecmp (const void *v1
, const void *v2
, size_t len
)
544 const unsigned char *s
= v1
;
545 const unsigned char *t
= v2
;
547 for (i
= 0; i
< len
; i
++)