Merge from vendor branch HEIMDAL:
[dragonfly.git] / contrib / dhcp-3.0 / omapip / hash.c
1 /* hash.c
2
3    Routines for manipulating hash tables... */
4
5 /*
6  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
7  * Copyright (c) 1995-2003 by Internet Software Consortium
8  *
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.
12  *
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.
20  *
21  *   Internet Systems Consortium, Inc.
22  *   950 Charter Street
23  *   Redwood City, CA 94063
24  *   <info@isc.org>
25  *   http://www.isc.org/
26  *
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''.
33  */
34
35 #ifndef lint
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";
38 #endif /* not lint */
39
40 #include <omapip/omapip_p.h>
41 #include <ctype.h>
42
43 static int do_hash (const unsigned char *, unsigned, unsigned);
44 static int do_case_hash (const unsigned char *, unsigned, unsigned);
45
46 int new_hash_table (tp, count, file, line)
47         struct hash_table **tp;
48         int count;
49         const char *file;
50         int line;
51 {
52         struct hash_table *rval;
53
54         if (!tp) {
55                 log_error ("%s(%d): new_hash_table called with null pointer.",
56                            file, line);
57 #if defined (POINTER_DEBUG)
58                 abort ();
59 #endif
60                 return 0;
61         }
62         if (*tp) {
63                 log_error ("%s(%d): non-null target for new_hash_table.",
64                            file, line);
65 #if defined (POINTER_DEBUG)
66                 abort ();
67 #endif
68         }
69         rval = dmalloc (sizeof (struct hash_table) -
70                         (DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *)) +
71                         (count * sizeof (struct hash_bucket *)), file, line);
72         if (!rval)
73                 return 0;
74         rval -> hash_count = count;
75         *tp = rval;
76         return 1;
77 }
78
79 void free_hash_table (tp, file, line)
80         struct hash_table **tp;
81         const char *file;
82         int line;
83 {
84         int i;
85         struct hash_bucket *hbc, *hbn = (struct hash_bucket *)0;
86         struct hash_table *ptr = *tp;
87
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) {
92                 hbn = hbc -> next;
93                 if (ptr -> dereferencer && hbc -> value)
94                     (*ptr -> dereferencer) (&hbc -> value, MDL);
95             }
96             for (hbc = ptr -> buckets [i]; hbc; hbc = hbn) {
97                 hbn = hbc -> next;
98                 free_hash_bucket (hbc, MDL);
99             }
100             ptr -> buckets [i] = (struct hash_bucket *)0;
101         }
102 #endif
103
104         dfree ((VOIDPTR)ptr, MDL);
105         *tp = (struct hash_table *)0;
106 }
107
108 struct hash_bucket *free_hash_buckets;
109
110 #if defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
111 struct hash_bucket *hash_bucket_hunks;
112
113 void relinquish_hash_bucket_hunks ()
114 {
115         struct hash_bucket *c, *n, **p;
116
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) {
122                                 *p = c -> next;
123                                 n -> len++;
124                                 break;
125                         }
126                 }
127                 /* If we didn't delete the hash bucket from the free list,
128                    advance the pointer. */
129                 if (!n)
130                         p = &c -> next;
131         }
132                 
133         for (c = hash_bucket_hunks; c; c = n) {
134                 n = c -> next;
135                 if (c -> len != 126) {
136                         log_info ("hashbucket %lx hash_buckets %d free %u",
137                                   (unsigned long)c, 127, c -> len);
138                 }
139                 dfree (c, MDL);
140         }
141 }
142 #endif
143
144 struct hash_bucket *new_hash_bucket (file, line)
145         const char *file;
146         int line;
147 {
148         struct hash_bucket *rval;
149         int i = 0;
150         if (!free_hash_buckets) {
151                 rval = dmalloc (127 * sizeof (struct hash_bucket),
152                                 file, line);
153                 if (!rval)
154                         return rval;
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;
159                 i++;
160                 rval++;
161 #endif
162                 for (; i < 127; i++) {
163                         rval -> next = free_hash_buckets;
164                         free_hash_buckets = rval;
165                         rval++;
166                 }
167         }
168         rval = free_hash_buckets;
169         free_hash_buckets = rval -> next;
170         return rval;
171 }
172
173 void free_hash_bucket (ptr, file, line)
174         struct hash_bucket *ptr;
175         const char *file;
176         int line;
177 {
178         struct hash_bucket *hp;
179 #if defined (DEBUG_MALLOC_POOL)
180         for (hp = free_hash_buckets; hp; hp = hp -> next) {
181                 if (hp == ptr) {
182                         log_error ("hash bucket freed twice!");
183                         abort ();
184                 }
185         }
186 #endif
187         ptr -> next = free_hash_buckets;
188         free_hash_buckets = ptr;
189 }
190
191 int new_hash (struct hash_table **rp,
192               hash_reference referencer,
193               hash_dereference dereferencer,
194               int casep, const char *file, int line)
195 {
196         if (!new_hash_table (rp, DEFAULT_HASH_SIZE, file, line))
197                 return 0;
198         memset (&(*rp) -> buckets [0], 0,
199                 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *));
200         (*rp) -> referencer = referencer;
201         (*rp) -> dereferencer = dereferencer;
202         if (casep) {
203                 (*rp) -> cmp = casecmp;
204                 (*rp) -> do_hash = do_case_hash;
205         } else {
206                 (*rp) -> cmp = (hash_comparator_t)memcmp;
207                 (*rp) -> do_hash = do_hash;
208         }
209         return 1;
210 }
211
212 static int do_case_hash (name, len, size)
213         const unsigned char *name;
214         unsigned len;
215         unsigned size;
216 {
217         register int accum = 0;
218         register const unsigned char *s = (const unsigned char *)name;
219         int i = len;
220         register unsigned c;
221
222         while (i--) {
223                 /* Make the hash case-insensitive. */
224                 c = *s++;
225                 if (isascii (c) && isupper (c))
226                         c = tolower (c);
227
228                 /* Add the character in... */
229                 accum = (accum << 1) + c;
230
231                 /* Add carry back in... */
232                 while (accum > 65535) {
233                         accum = (accum & 65535) + (accum >> 16);
234                 }
235         }
236         return accum % size;
237 }
238
239 static int do_hash (name, len, size)
240         const unsigned char *name;
241         unsigned len;
242         unsigned size;
243 {
244         register int accum = 0;
245         register const unsigned char *s = (const unsigned char *)name;
246         int i = len;
247
248         while (i--) {
249                 /* Add the character in... */
250                 accum = (accum << 1) + *s++;
251
252                 /* Add carry back in... */
253                 while (accum > 65535) {
254                         accum = (accum & 65535) + (accum >> 16);
255                 }
256         }
257         return accum % size;
258 }
259
260 void add_hash (table, name, len, pointer, file, line)
261         struct hash_table *table;
262         unsigned len;
263         const unsigned char *name;
264         hashed_object_t *pointer;
265         const char *file;
266         int line;
267 {
268         int hashno;
269         struct hash_bucket *bp;
270         void *foo;
271
272         if (!table)
273                 return;
274
275         if (!len)
276                 len = strlen ((const char *)name);
277
278         hashno = (*table -> do_hash) (name, len, table -> hash_count);
279         bp = new_hash_bucket (file, line);
280
281         if (!bp) {
282                 log_error ("Can't add %s to hash table.", name);
283                 return;
284         }
285         bp -> name = name;
286         if (table -> referencer) {
287                 foo = &bp -> value;
288                 (*(table -> referencer)) (foo, pointer, file, line);
289         } else
290                 bp -> value = pointer;
291         bp -> next = table -> buckets [hashno];
292         bp -> len = len;
293         table -> buckets [hashno] = bp;
294 }
295
296 void delete_hash_entry (table, name, len, file, line)
297         struct hash_table *table;
298         unsigned len;
299         const unsigned char *name;
300         const char *file;
301         int line;
302 {
303         int hashno;
304         struct hash_bucket *bp, *pbp = (struct hash_bucket *)0;
305         void *foo;
306
307         if (!table)
308                 return;
309
310         if (!len)
311                 len = strlen ((const char *)name);
312
313         hashno = (*table -> do_hash) (name, len, table -> hash_count);
314
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) {
318                 if ((!bp -> len &&
319                      !strcmp ((const char *)bp -> name, (const char *)name)) ||
320                     (bp -> len == len &&
321                      !(*table -> cmp) (bp -> name, name, len))) {
322                         if (pbp) {
323                                 pbp -> next = bp -> next;
324                         } else {
325                                 table -> buckets [hashno] = bp -> next;
326                         }
327                         if (bp -> value && table -> dereferencer) {
328                                 foo = &bp -> value;
329                                 (*(table -> dereferencer)) (foo, file, line);
330                         }
331                         free_hash_bucket (bp, file, line);
332                         break;
333                 }
334                 pbp = bp;       /* jwg, 9/6/96 - nice catch! */
335         }
336 }
337
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;
342         unsigned len;
343         const char *file;
344         int line;
345 {
346         int hashno;
347         struct hash_bucket *bp;
348
349         if (!table)
350                 return 0;
351         if (!len)
352                 len = strlen ((const char *)name);
353
354         hashno = (*table -> do_hash) (name, len, table -> hash_count);
355
356         for (bp = table -> buckets [hashno]; bp; bp = bp -> next) {
357                 if (len == bp -> len
358                     && !(*table -> cmp) (bp -> name, name, len)) {
359                         if (table -> referencer)
360                                 (*table -> referencer) (vp, bp -> value,
361                                                         file, line);
362                         else
363                                 *vp = bp -> value;
364                         return 1;
365                 }
366         }
367         return 0;
368 }
369
370 int hash_foreach (struct hash_table *table, hash_foreach_func func)
371 {
372         int i;
373         struct hash_bucket *bp, *next;
374         int count = 0;
375
376         if (!table)
377                 return 0;
378
379         for (i = 0; i < table -> hash_count; i++) {
380                 bp = table -> buckets [i];
381                 while (bp) {
382                         next = bp -> next;
383                         (*func) (bp -> name, bp -> len, bp -> value);
384                         bp = next;
385                         count++;
386                 }
387         }
388         return count;
389 }
390
391 int casecmp (const void *v1, const void *v2, unsigned long len)
392 {
393         unsigned i;
394         const char *s = v1;
395         const char *t = v2;
396         
397         for (i = 0; i < len; i++)
398         {
399                 int c1, c2;
400                 if (isascii (s [i]) && isupper (s [i]))
401                         c1 = tolower (s [i]);
402                 else
403                         c1 = s [i];
404                 
405                 if (isascii (t [i]) && isupper (t [i]))
406                         c2 = tolower (t [i]);
407                 else
408                         c2 = t [i];
409                 
410                 if (c1 < c2)
411                         return -1;
412                 if (c1 > c2)
413                         return 1;
414         }
415         return 0;
416 }