1 /************************************************************************ 2 Copyright 1988, 1991 by Carnegie Mellon University 3 4 All Rights Reserved 5 6 Permission to use, copy, modify, and distribute this software and its 7 documentation for any purpose and without fee is hereby granted, provided 8 that the above copyright notice appear in all copies and that both that 9 copyright notice and this permission notice appear in supporting 10 documentation, and that the name of Carnegie Mellon University not be used 11 in advertising or publicity pertaining to distribution of the software 12 without specific, written prior permission. 13 14 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 15 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 16 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 17 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 18 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 19 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 20 SOFTWARE. 21 22 $FreeBSD: src/libexec/bootpd/hash.c,v 1.5 1999/08/28 00:09:18 peter Exp $ 23 $DragonFly: src/libexec/bootpd/hash.c,v 1.3 2008/06/05 18:01:49 swildner Exp $ 24 25 ************************************************************************/ 26 27 /* 28 * Generalized hash table ADT 29 * 30 * Provides multiple, dynamically-allocated, variable-sized hash tables on 31 * various data and keys. 32 * 33 * This package attempts to follow some of the coding conventions suggested 34 * by Bob Sidebotham and the AFS Clean Code Committee of the 35 * Information Technology Center at Carnegie Mellon. 36 */ 37 38 39 #include <sys/types.h> 40 #include <stdlib.h> 41 42 #ifndef USE_BFUNCS 43 #include <memory.h> 44 /* Yes, memcpy is OK here (no overlapped copies). */ 45 #define bcopy(a,b,c) memcpy(b,a,c) 46 #define bzero(p,l) memset(p,0,l) 47 #define bcmp(a,b,c) memcmp(a,b,c) 48 #endif 49 50 #include "hash.h" 51 52 #define TRUE 1 53 #define FALSE 0 54 55 /* 56 * This can be changed to make internal routines visible to debuggers, etc. 57 */ 58 #ifndef PRIVATE 59 #define PRIVATE static 60 #endif 61 62 PRIVATE void hashi_FreeMembers(hash_member *, hash_freefp); 63 64 65 66 /* 67 * Hash table initialization routine. 68 * 69 * This routine creates and intializes a hash table of size "tablesize" 70 * entries. Successful calls return a pointer to the hash table (which must 71 * be passed to other hash routines to identify the hash table). Failed 72 * calls return NULL. 73 */ 74 75 hash_tbl * 76 hash_Init(unsigned tablesize) 77 { 78 hash_tbl *hashtblptr; 79 unsigned totalsize; 80 81 if (tablesize > 0) { 82 totalsize = sizeof(hash_tbl) 83 + sizeof(hash_member *) * (tablesize - 1); 84 hashtblptr = (hash_tbl *) malloc(totalsize); 85 if (hashtblptr) { 86 bzero((char *) hashtblptr, totalsize); 87 hashtblptr->size = tablesize; /* Success! */ 88 hashtblptr->bucketnum = 0; 89 hashtblptr->member = (hashtblptr->table)[0]; 90 } 91 } else { 92 hashtblptr = NULL; /* Disallow zero-length tables */ 93 } 94 return hashtblptr; /* NULL if failure */ 95 } 96 97 98 99 /* 100 * Frees an entire linked list of bucket members (used in the open 101 * hashing scheme). Does nothing if the passed pointer is NULL. 102 */ 103 104 PRIVATE void 105 hashi_FreeMembers(hash_member *bucketptr, hash_freefp free_data) 106 { 107 hash_member *nextbucket; 108 while (bucketptr) { 109 nextbucket = bucketptr->next; 110 (*free_data) (bucketptr->data); 111 free((char *) bucketptr); 112 bucketptr = nextbucket; 113 } 114 } 115 116 117 118 119 /* 120 * This routine re-initializes the hash table. It frees all the allocated 121 * memory and resets all bucket pointers to NULL. 122 */ 123 124 void 125 hash_Reset(hash_tbl *hashtable, hash_freefp free_data) 126 { 127 hash_member **bucketptr; 128 unsigned i; 129 130 bucketptr = hashtable->table; 131 for (i = 0; i < hashtable->size; i++) { 132 hashi_FreeMembers(*bucketptr, free_data); 133 *bucketptr++ = NULL; 134 } 135 hashtable->bucketnum = 0; 136 hashtable->member = (hashtable->table)[0]; 137 } 138 139 140 141 /* 142 * Generic hash function to calculate a hash code from the given string. 143 * 144 * For each byte of the string, this function left-shifts the value in an 145 * accumulator and then adds the byte into the accumulator. The contents of 146 * the accumulator is returned after the entire string has been processed. 147 * It is assumed that this result will be used as the "hashcode" parameter in 148 * calls to other functions in this package. These functions automatically 149 * adjust the hashcode for the size of each hashtable. 150 * 151 * This algorithm probably works best when the hash table size is a prime 152 * number. 153 * 154 * Hopefully, this function is better than the previous one which returned 155 * the sum of the squares of all the bytes. I'm still open to other 156 * suggestions for a default hash function. The programmer is more than 157 * welcome to supply his/her own hash function as that is one of the design 158 * features of this package. 159 */ 160 161 unsigned 162 hash_HashFunction(unsigned char *string, unsigned len) 163 { 164 unsigned accum; 165 166 accum = 0; 167 for (; len > 0; len--) { 168 accum <<= 1; 169 accum += (unsigned) (*string++ & 0xFF); 170 } 171 return accum; 172 } 173 174 175 176 /* 177 * Returns TRUE if at least one entry for the given key exists; FALSE 178 * otherwise. 179 */ 180 181 int 182 hash_Exists(hash_tbl *hashtable, unsigned hashcode, hash_cmpfp compare, 183 hash_datum *key) 184 { 185 hash_member *memberptr; 186 187 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 188 while (memberptr) { 189 if ((*compare) (key, memberptr->data)) { 190 return TRUE; /* Entry does exist */ 191 } 192 memberptr = memberptr->next; 193 } 194 return FALSE; /* Entry does not exist */ 195 } 196 197 198 199 /* 200 * Insert the data item "element" into the hash table using "hashcode" 201 * to determine the bucket number, and "compare" and "key" to determine 202 * its uniqueness. 203 * 204 * If the insertion is successful 0 is returned. If a matching entry 205 * already exists in the given bucket of the hash table, or some other error 206 * occurs, -1 is returned and the insertion is not done. 207 */ 208 209 int 210 hash_Insert(hash_tbl *hashtable, unsigned hashcode, hash_cmpfp compare, 211 hash_datum *key, hash_datum *element) 212 { 213 hash_member *temp; 214 215 hashcode %= hashtable->size; 216 if (hash_Exists(hashtable, hashcode, compare, key)) { 217 return -1; /* At least one entry already exists */ 218 } 219 temp = (hash_member *) malloc(sizeof(hash_member)); 220 if (!temp) 221 return -1; /* malloc failed! */ 222 223 temp->data = element; 224 temp->next = (hashtable->table)[hashcode]; 225 (hashtable->table)[hashcode] = temp; 226 return 0; /* Success */ 227 } 228 229 230 231 /* 232 * Delete all data elements which match the given key. If at least one 233 * element is found and the deletion is successful, 0 is returned. 234 * If no matching elements can be found in the hash table, -1 is returned. 235 */ 236 237 int 238 hash_Delete(hash_tbl *hashtable, unsigned hashcode, hash_cmpfp compare, 239 hash_datum *key, hash_freefp free_data) 240 { 241 hash_member *memberptr, *tempptr; 242 hash_member *previous = NULL; 243 int retval; 244 245 retval = -1; 246 hashcode %= hashtable->size; 247 248 /* 249 * Delete the first member of the list if it matches. Since this moves 250 * the second member into the first position we have to keep doing this 251 * over and over until it no longer matches. 252 */ 253 memberptr = (hashtable->table)[hashcode]; 254 while (memberptr && (*compare) (key, memberptr->data)) { 255 (hashtable->table)[hashcode] = memberptr->next; 256 /* 257 * Stop hashi_FreeMembers() from deleting the whole list! 258 */ 259 memberptr->next = NULL; 260 hashi_FreeMembers(memberptr, free_data); 261 memberptr = (hashtable->table)[hashcode]; 262 retval = 0; 263 } 264 265 /* 266 * Now traverse the rest of the list 267 */ 268 if (memberptr) { 269 previous = memberptr; 270 memberptr = memberptr->next; 271 } 272 while (memberptr) { 273 if ((*compare) (key, memberptr->data)) { 274 tempptr = memberptr; 275 previous->next = memberptr = memberptr->next; 276 /* 277 * Put the brakes on hashi_FreeMembers(). . . . 278 */ 279 tempptr->next = NULL; 280 hashi_FreeMembers(tempptr, free_data); 281 retval = 0; 282 } else { 283 previous = memberptr; 284 memberptr = memberptr->next; 285 } 286 } 287 return retval; 288 } 289 290 291 292 /* 293 * Locate and return the data entry associated with the given key. 294 * 295 * If the data entry is found, a pointer to it is returned. Otherwise, 296 * NULL is returned. 297 */ 298 299 hash_datum * 300 hash_Lookup(hash_tbl *hashtable, unsigned hashcode, hash_cmpfp compare, 301 hash_datum *key) 302 { 303 hash_member *memberptr; 304 305 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 306 while (memberptr) { 307 if ((*compare) (key, memberptr->data)) { 308 return (memberptr->data); 309 } 310 memberptr = memberptr->next; 311 } 312 return NULL; 313 } 314 315 316 317 /* 318 * Return the next available entry in the hashtable for a linear search 319 */ 320 321 hash_datum * 322 hash_NextEntry(hash_tbl *hashtable) 323 { 324 unsigned bucket; 325 hash_member *memberptr; 326 327 /* 328 * First try to pick up where we left off. 329 */ 330 memberptr = hashtable->member; 331 if (memberptr) { 332 hashtable->member = memberptr->next; /* Set up for next call */ 333 return memberptr->data; /* Return the data */ 334 } 335 /* 336 * We hit the end of a chain, so look through the array of buckets 337 * until we find a new chain (non-empty bucket) or run out of buckets. 338 */ 339 bucket = hashtable->bucketnum + 1; 340 while ((bucket < hashtable->size) && 341 !(memberptr = (hashtable->table)[bucket])) { 342 bucket++; 343 } 344 345 /* 346 * Check to see if we ran out of buckets. 347 */ 348 if (bucket >= hashtable->size) { 349 /* 350 * Reset to top of table for next call. 351 */ 352 hashtable->bucketnum = 0; 353 hashtable->member = (hashtable->table)[0]; 354 /* 355 * But return end-of-table indication to the caller this time. 356 */ 357 return NULL; 358 } 359 /* 360 * Must have found a non-empty bucket. 361 */ 362 hashtable->bucketnum = bucket; 363 hashtable->member = memberptr->next; /* Set up for next call */ 364 return memberptr->data; /* Return the data */ 365 } 366 367 368 369 /* 370 * Return the first entry in a hash table for a linear search 371 */ 372 373 hash_datum * 374 hash_FirstEntry(hash_tbl *hashtable) 375 { 376 hashtable->bucketnum = 0; 377 hashtable->member = (hashtable->table)[0]; 378 return hash_NextEntry(hashtable); 379 } 380 381 /* 382 * Local Variables: 383 * tab-width: 4 384 * c-indent-level: 4 385 * c-argdecl-indent: 4 386 * c-continued-statement-offset: 4 387 * c-continued-brace-offset: -4 388 * c-label-offset: -4 389 * c-brace-offset: 0 390 * End: 391 */ 392