1 /* hash.c 2 3 Routines for manipulating hash tables... */ 4 5 /* 6 * Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium. 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of The Internet Software Consortium nor the names 19 * of its contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND 23 * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 24 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 25 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 26 * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR 27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 30 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 31 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * This software has been written for the Internet Software Consortium 37 * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie 38 * Enterprises. To learn more about the Internet Software Consortium, 39 * see ``http://www.vix.com/isc''. To learn more about Vixie 40 * Enterprises, see ``http://www.vix.com''. 41 */ 42 43 #define lint 44 #ifndef lint 45 static char copyright[] = 46 "$Id: hash.c,v 1.9.2.3 1999/04/09 17:39:41 mellon Exp $ Copyright (c) 1995, 1996, 1997, 1998 The Internet Software Consortium. All rights reserved.\n"; 47 #endif /* not lint */ 48 49 #include <rosdhcp.h> 50 51 static __inline int do_hash PROTO ((unsigned char *, int, int)); 52 53 struct hash_table *new_hash () 54 { 55 struct hash_table *rv = new_hash_table (DEFAULT_HASH_SIZE); 56 if (!rv) 57 return rv; 58 memset (&rv -> buckets [0], 0, 59 DEFAULT_HASH_SIZE * sizeof (struct hash_bucket *)); 60 return rv; 61 } 62 63 static __inline int do_hash (name, len, size) 64 unsigned char *name; 65 int len; 66 int size; 67 { 68 register int accum = 0; 69 register unsigned char *s = name; 70 int i = len; 71 while (i--) { 72 /* Add the character in... */ 73 accum += *s++; 74 /* Add carry back in... */ 75 while (accum > 255) { 76 accum = (accum & 255) + (accum >> 8); 77 } 78 } 79 return accum % size; 80 } 81 82 void add_hash (table, name, len, pointer) 83 struct hash_table *table; 84 int len; 85 unsigned char *name; 86 unsigned char *pointer; 87 { 88 int hashno; 89 struct hash_bucket *bp; 90 91 if (!table) 92 return; 93 if (!len) 94 len = strlen ((char *)name); 95 96 hashno = do_hash (name, len, table -> hash_count); 97 bp = new_hash_bucket (); 98 99 if (!bp) { 100 warn ("Can't add %s to hash table.", name); 101 return; 102 } 103 bp -> name = name; 104 bp -> value = pointer; 105 bp -> next = table -> buckets [hashno]; 106 bp -> len = len; 107 table -> buckets [hashno] = bp; 108 } 109 110 void delete_hash_entry (table, name, len) 111 struct hash_table *table; 112 int len; 113 unsigned char *name; 114 { 115 int hashno; 116 struct hash_bucket *bp, *pbp = (struct hash_bucket *)0; 117 118 if (!table) 119 return; 120 if (!len) 121 len = strlen ((char *)name); 122 123 hashno = do_hash (name, len, table -> hash_count); 124 125 /* Go through the list looking for an entry that matches; 126 if we find it, delete it. */ 127 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) { 128 if ((!bp -> len && 129 !strcmp ((char *)bp -> name, (char *)name)) || 130 (bp -> len == len && 131 !memcmp (bp -> name, name, len))) { 132 if (pbp) { 133 pbp -> next = bp -> next; 134 } else { 135 table -> buckets [hashno] = bp -> next; 136 } 137 free_hash_bucket (bp, "delete_hash_entry"); 138 break; 139 } 140 pbp = bp; /* jwg, 9/6/96 - nice catch! */ 141 } 142 } 143 144 unsigned char *hash_lookup (table, name, len) 145 struct hash_table *table; 146 unsigned char *name; 147 int len; 148 { 149 int hashno; 150 struct hash_bucket *bp; 151 152 if (!table) 153 return (unsigned char *)0; 154 155 if (!len) 156 len = strlen ((char *)name); 157 158 hashno = do_hash (name, len, table -> hash_count); 159 160 for (bp = table -> buckets [hashno]; bp; bp = bp -> next) { 161 if (len == bp -> len && !memcmp (bp -> name, name, len)) 162 return bp -> value; 163 } 164 return (unsigned char *)0; 165 } 166