1: /* hash.c
2:
3: Routines for manipulating hash tables... */
4:
5: /*
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
9: *
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.
13: *
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.
21: *
22: * Internet Systems Consortium, Inc.
23: * 950 Charter Street
24: * Redwood City, CA 94063
25: * <info@isc.org>
26: * https://www.isc.org/
27: *
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''.
34: */
35:
36: #include "dhcpd.h"
37:
38: #include <omapip/omapip_p.h>
39: #include <limits.h>
40: #include <ctype.h>
41:
42: static unsigned
43: find_length(const void *key,
44: unsigned (*do_hash)(const void *, unsigned, unsigned))
45: {
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)
51: return 4;
52:
53: log_debug("Unexpected hash function at %s:%d.", MDL);
54: /*
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.
58: */
59: return 0;
60: }
61:
62: int new_hash_table (tp, count, file, line)
63: struct hash_table **tp;
64: unsigned count;
65: const char *file;
66: int line;
67: {
68: struct hash_table *rval;
69: unsigned extra;
70:
71: if (!tp) {
72: log_error ("%s(%d): new_hash_table called with null pointer.",
73: file, line);
74: #if defined (POINTER_DEBUG)
75: abort ();
76: #endif
77: return 0;
78: }
79: if (*tp) {
80: log_error ("%s(%d): non-null target for new_hash_table.",
81: file, line);
82: #if defined (POINTER_DEBUG)
83: abort ();
84: #endif
85: }
86:
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.
90: */
91: if (count <= 1)
92: extra = 0;
93: else
94: extra = count - 1;
95:
96: rval = dmalloc(sizeof(struct hash_table) +
97: (extra * sizeof(struct hash_bucket *)), file, line);
98: if (!rval)
99: return 0;
100: rval -> hash_count = count;
101: *tp = rval;
102: return 1;
103: }
104:
105: void free_hash_table (tp, file, line)
106: struct hash_table **tp;
107: const char *file;
108: int line;
109: {
110: struct hash_table *ptr = *tp;
111:
112: #if defined (DEBUG_MEMORY_LEAKAGE) || \
113: defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
114: int i;
115: struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
116:
117: for (i = 0; i < ptr -> hash_count; i++) {
118: for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
119: hbn = hbc -> next;
120: if (ptr -> dereferencer && hbc -> value)
121: (*ptr -> dereferencer) (&hbc -> value, MDL);
122: }
123: for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
124: hbn = hbc -> next;
125: free_hash_bucket (hbc, MDL);
126: }
127: ptr -> buckets [i] = (struct hash_bucket *)0;
128: }
129: #endif
130:
131: dfree((void *)ptr, MDL);
132: *tp = (struct hash_table *)0;
133: }
134:
135: struct hash_bucket *free_hash_buckets;
136:
137: #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
138: struct hash_bucket *hash_bucket_hunks;
139:
140: void relinquish_hash_bucket_hunks ()
141: {
142: struct hash_bucket *c, *n, **p;
143:
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) {
149: *p = c -> next;
150: n -> len++;
151: break;
152: }
153: }
154: /* If we didn't delete the hash bucket from the free list,
155: advance the pointer. */
156: if (!n)
157: p = &c -> next;
158: }
159:
160: for (c = hash_bucket_hunks; c; c = n) {
161: n = c -> next;
162: if (c -> len != 126) {
163: log_info ("hashbucket %lx hash_buckets %d free %u",
164: (unsigned long)c, 127, c -> len);
165: }
166: dfree (c, MDL);
167: }
168: }
169: #endif
170:
171: struct hash_bucket *new_hash_bucket (file, line)
172: const char *file;
173: int line;
174: {
175: struct hash_bucket *rval;
176: int i = 0;
177: if (!free_hash_buckets) {
178: rval = dmalloc (127 * sizeof (struct hash_bucket),
179: file, line);
180: if (!rval)
181: return rval;
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;
186: i++;
187: rval++;
188: #endif
189: for (; i < 127; i++) {
190: rval -> next = free_hash_buckets;
191: free_hash_buckets = rval;
192: rval++;
193: }
194: }
195: rval = free_hash_buckets;
196: free_hash_buckets = rval -> next;
197: return rval;
198: }
199:
200: void free_hash_bucket (ptr, file, line)
201: struct hash_bucket *ptr;
202: const char *file;
203: int line;
204: {
205: #if defined (DEBUG_MALLOC_POOL)
206: struct hash_bucket *hp;
207:
208: for (hp = free_hash_buckets; hp; hp = hp -> next) {
209: if (hp == ptr) {
210: log_error ("hash bucket freed twice!");
211: abort ();
212: }
213: }
214: #endif
215: ptr -> next = free_hash_buckets;
216: free_hash_buckets = ptr;
217: }
218:
219: int new_hash(struct hash_table **rp,
220: hash_reference referencer,
221: hash_dereference dereferencer,
222: unsigned hsize,
223: unsigned (*hasher)(const void *, unsigned, unsigned),
224: const char *file, int line)
225: {
226: if (hsize == 0)
227: hsize = DEFAULT_HASH_SIZE;
228:
229: if (!new_hash_table (rp, hsize, file, line))
230: return 0;
231:
232: memset ((*rp)->buckets, 0, hsize * sizeof(struct hash_bucket *));
233:
234: (*rp)->referencer = referencer;
235: (*rp)->dereferencer = dereferencer;
236: (*rp)->do_hash = hasher;
237:
238: if (hasher == do_case_hash)
239: (*rp)->cmp = casecmp;
240: else
241: (*rp)->cmp = memcmp;
242:
243: return 1;
244: }
245:
246: unsigned
247: do_case_hash(const void *name, unsigned len, unsigned size)
248: {
249: register unsigned accum = 0;
250: register const unsigned char *s = name;
251: int i = len;
252: register unsigned c;
253:
254: while (i--) {
255: /* Make the hash case-insensitive. */
256: c = *s++;
257: if (isascii(c))
258: c = tolower(c);
259:
260: /* Add the character in... */
261: accum = (accum << 1) + c;
262:
263: /* Add carry back in... */
264: while (accum > 65535) {
265: accum = (accum & 65535) + (accum >> 16);
266: }
267:
268: }
269: return accum % size;
270: }
271:
272: unsigned
273: do_string_hash(const void *name, unsigned len, unsigned size)
274: {
275: register unsigned accum = 0;
276: register const unsigned char *s = (const unsigned char *)name;
277: int i = len;
278:
279: while (i--) {
280: /* Add the character in... */
281: accum = (accum << 1) + *s++;
282:
283: /* Add carry back in... */
284: while (accum > 65535) {
285: accum = (accum & 65535) + (accum >> 16);
286: }
287: }
288: return accum % size;
289: }
290:
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.
295: */
296: unsigned
297: do_id_hash(const void *name, unsigned len, unsigned size)
298: {
299: register unsigned accum = 0;
300: register const unsigned char *s = (const unsigned char *)name;
301: const unsigned char *end = s + len;
302:
303: if (len == 0)
304: return 0;
305:
306: /*
307: * The switch handles our starting conditions, then we hash the
308: * remaining bytes in groups of 3
309: */
310:
311: switch (len % 3) {
312: case 0:
313: break;
314: case 2:
315: accum ^= *s++ << 8;
316: case 1:
317: accum ^= *s++;
318: break;
319: }
320:
321: while (s < end) {
322: accum ^= *s++ << 16;
323: accum ^= *s++ << 8;
324: accum ^= *s++;
325: }
326:
327: return accum % size;
328: }
329:
330: unsigned
331: do_number_hash(const void *key, unsigned len, unsigned size)
332: {
333: register unsigned number = *((const unsigned *)key);
334:
335: return number % size;
336: }
337:
338: unsigned
339: do_ip4_hash(const void *key, unsigned len, unsigned size)
340: {
341: u_int32_t number;
342:
343: memcpy(&number, key, 4);
344:
345: number = ntohl(number);
346:
347: return number % size;
348: }
349:
350: unsigned char *
351: hash_report(struct hash_table *table)
352: {
353: static unsigned char retbuf[sizeof("Contents/Size (%): "
354: "2147483647/2147483647 "
355: "(2147483647%). "
356: "Min/max: 2147483647/2147483647")];
357: unsigned curlen, pct, contents=0, minlen=UINT_MAX, maxlen=0;
358: unsigned i;
359: struct hash_bucket *bp;
360:
361: if (table == NULL)
362: return (unsigned char *) "No table.";
363:
364: if (table->hash_count == 0)
365: return (unsigned char *) "Invalid hash table.";
366:
367: for (i = 0 ; i < table->hash_count ; i++) {
368: curlen = 0;
369:
370: bp = table->buckets[i];
371: while (bp != NULL) {
372: curlen++;
373: bp = bp->next;
374: }
375:
376: if (curlen < minlen)
377: minlen = curlen;
378: if (curlen > maxlen)
379: maxlen = curlen;
380:
381: contents += curlen;
382: }
383:
384: if (contents >= (UINT_MAX / 100))
385: pct = contents / ((table->hash_count / 100) + 1);
386: else
387: pct = (contents * 100) / table->hash_count;
388:
389: if (contents > 2147483647 ||
390: table->hash_count > 2147483647 ||
391: pct > 2147483647 ||
392: minlen > 2147483647 ||
393: maxlen > 2147483647)
394: return (unsigned char *) "Report out of range for display.";
395:
396: sprintf((char *)retbuf,
397: "Contents/Size (%%): %u/%u (%u%%). Min/max: %u/%u",
398: contents, table->hash_count, pct, minlen, maxlen);
399:
400: return retbuf;
401: }
402:
403: void add_hash (table, key, len, pointer, file, line)
404: struct hash_table *table;
405: unsigned len;
406: const void *key;
407: hashed_object_t *pointer;
408: const char *file;
409: int line;
410: {
411: int hashno;
412: struct hash_bucket *bp;
413: void *foo;
414:
415: if (!table)
416: return;
417:
418: if (!len)
419: len = find_length(key, table->do_hash);
420:
421: hashno = (*table->do_hash)(key, len, table->hash_count);
422: bp = new_hash_bucket (file, line);
423:
424: if (!bp) {
425: log_error ("Can't add entry to hash table: no memory.");
426: return;
427: }
428: bp -> name = key;
429: if (table -> referencer) {
430: foo = &bp -> value;
431: (*(table -> referencer)) (foo, pointer, file, line);
432: } else
433: bp -> value = pointer;
434: bp -> next = table -> buckets [hashno];
435: bp -> len = len;
436: table -> buckets [hashno] = bp;
437: }
438:
439: void delete_hash_entry (table, key, len, file, line)
440: struct hash_table *table;
441: unsigned len;
442: const void *key;
443: const char *file;
444: int line;
445: {
446: int hashno;
447: struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
448: void *foo;
449:
450: if (!table)
451: return;
452:
453: if (!len)
454: len = find_length(key, table->do_hash);
455:
456: hashno = (*table->do_hash)(key, len, table->hash_count);
457:
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) {
461: if ((!bp -> len &&
462: !strcmp ((const char *)bp->name, key)) ||
463: (bp -> len == len &&
464: !(table -> cmp)(bp->name, key, len))) {
465: if (pbp) {
466: pbp -> next = bp -> next;
467: } else {
468: table -> buckets [hashno] = bp -> next;
469: }
470: if (bp -> value && table -> dereferencer) {
471: foo = &bp -> value;
472: (*(table -> dereferencer)) (foo, file, line);
473: }
474: free_hash_bucket (bp, file, line);
475: break;
476: }
477: pbp = bp; /* jwg, 9/6/96 - nice catch! */
478: }
479: }
480:
481: int hash_lookup (vp, table, key, len, file, line)
482: hashed_object_t **vp;
483: struct hash_table *table;
484: const void *key;
485: unsigned len;
486: const char *file;
487: int line;
488: {
489: int hashno;
490: struct hash_bucket *bp;
491:
492: if (!table)
493: return 0;
494: if (!len)
495: len = find_length(key, table->do_hash);
496:
497: if (*vp != NULL) {
498: log_fatal("Internal inconsistency: storage value has not been "
499: "initialized to zero (from %s:%d).", file, line);
500: }
501:
502: hashno = (*table->do_hash)(key, len, table->hash_count);
503:
504: for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
505: if (len == bp -> len
506: && !(*table->cmp)(bp->name, key, len)) {
507: if (table -> referencer)
508: (*table -> referencer) (vp, bp -> value,
509: file, line);
510: else
511: *vp = bp -> value;
512: return 1;
513: }
514: }
515: return 0;
516: }
517:
518: int hash_foreach (struct hash_table *table, hash_foreach_func func)
519: {
520: int i;
521: struct hash_bucket *bp, *next;
522: int count = 0;
523:
524: if (!table)
525: return 0;
526:
527: for (i = 0; i < table -> hash_count; i++) {
528: bp = table -> buckets [i];
529: while (bp) {
530: next = bp -> next;
531: if ((*func)(bp->name, bp->len, bp->value)
532: != ISC_R_SUCCESS)
533: return count;
534: bp = next;
535: count++;
536: }
537: }
538: return count;
539: }
540:
541: int casecmp (const void *v1, const void *v2, size_t len)
542: {
543: size_t i;
544: const unsigned char *s = v1;
545: const unsigned char *t = v2;
546:
547: for (i = 0; i < len; i++)
548: {
549: int c1, c2;
550: if (isascii(s[i]))
551: c1 = tolower(s[i]);
552: else
553: c1 = s[i];
554:
555: if (isascii(t[i]))
556: c2 = tolower(t[i]);
557: else
558: c2 = t[i];
559:
560: if (c1 < c2)
561: return -1;
562: if (c1 > c2)
563: return 1;
564: }
565: return 0;
566: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / dhcp / omapip