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.2 2003/06/17 04:27:07 dillon 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 #ifndef NULL 55 #define NULL 0 56 #endif 57 58 /* 59 * This can be changed to make internal routines visible to debuggers, etc. 60 */ 61 #ifndef PRIVATE 62 #define PRIVATE static 63 #endif 64 65 #ifdef __STDC__ 66 #define P(args) args 67 #else 68 #define P(args) () 69 #endif 70 71 PRIVATE void hashi_FreeMembers P((hash_member *, hash_freefp)); 72 73 #undef P 74 75 76 77 /* 78 * Hash table initialization routine. 79 * 80 * This routine creates and intializes a hash table of size "tablesize" 81 * entries. Successful calls return a pointer to the hash table (which must 82 * be passed to other hash routines to identify the hash table). Failed 83 * calls return NULL. 84 */ 85 86 hash_tbl * 87 hash_Init(tablesize) 88 unsigned tablesize; 89 { 90 register hash_tbl *hashtblptr; 91 register unsigned totalsize; 92 93 if (tablesize > 0) { 94 totalsize = sizeof(hash_tbl) 95 + sizeof(hash_member *) * (tablesize - 1); 96 hashtblptr = (hash_tbl *) malloc(totalsize); 97 if (hashtblptr) { 98 bzero((char *) hashtblptr, totalsize); 99 hashtblptr->size = tablesize; /* Success! */ 100 hashtblptr->bucketnum = 0; 101 hashtblptr->member = (hashtblptr->table)[0]; 102 } 103 } else { 104 hashtblptr = NULL; /* Disallow zero-length tables */ 105 } 106 return hashtblptr; /* NULL if failure */ 107 } 108 109 110 111 /* 112 * Frees an entire linked list of bucket members (used in the open 113 * hashing scheme). Does nothing if the passed pointer is NULL. 114 */ 115 116 PRIVATE void 117 hashi_FreeMembers(bucketptr, free_data) 118 hash_member *bucketptr; 119 hash_freefp free_data; 120 { 121 hash_member *nextbucket; 122 while (bucketptr) { 123 nextbucket = bucketptr->next; 124 (*free_data) (bucketptr->data); 125 free((char *) bucketptr); 126 bucketptr = nextbucket; 127 } 128 } 129 130 131 132 133 /* 134 * This routine re-initializes the hash table. It frees all the allocated 135 * memory and resets all bucket pointers to NULL. 136 */ 137 138 void 139 hash_Reset(hashtable, free_data) 140 hash_tbl *hashtable; 141 hash_freefp free_data; 142 { 143 hash_member **bucketptr; 144 unsigned i; 145 146 bucketptr = hashtable->table; 147 for (i = 0; i < hashtable->size; i++) { 148 hashi_FreeMembers(*bucketptr, free_data); 149 *bucketptr++ = NULL; 150 } 151 hashtable->bucketnum = 0; 152 hashtable->member = (hashtable->table)[0]; 153 } 154 155 156 157 /* 158 * Generic hash function to calculate a hash code from the given string. 159 * 160 * For each byte of the string, this function left-shifts the value in an 161 * accumulator and then adds the byte into the accumulator. The contents of 162 * the accumulator is returned after the entire string has been processed. 163 * It is assumed that this result will be used as the "hashcode" parameter in 164 * calls to other functions in this package. These functions automatically 165 * adjust the hashcode for the size of each hashtable. 166 * 167 * This algorithm probably works best when the hash table size is a prime 168 * number. 169 * 170 * Hopefully, this function is better than the previous one which returned 171 * the sum of the squares of all the bytes. I'm still open to other 172 * suggestions for a default hash function. The programmer is more than 173 * welcome to supply his/her own hash function as that is one of the design 174 * features of this package. 175 */ 176 177 unsigned 178 hash_HashFunction(string, len) 179 unsigned char *string; 180 register unsigned len; 181 { 182 register unsigned accum; 183 184 accum = 0; 185 for (; len > 0; len--) { 186 accum <<= 1; 187 accum += (unsigned) (*string++ & 0xFF); 188 } 189 return accum; 190 } 191 192 193 194 /* 195 * Returns TRUE if at least one entry for the given key exists; FALSE 196 * otherwise. 197 */ 198 199 int 200 hash_Exists(hashtable, hashcode, compare, key) 201 hash_tbl *hashtable; 202 unsigned hashcode; 203 hash_cmpfp compare; 204 hash_datum *key; 205 { 206 register hash_member *memberptr; 207 208 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 209 while (memberptr) { 210 if ((*compare) (key, memberptr->data)) { 211 return TRUE; /* Entry does exist */ 212 } 213 memberptr = memberptr->next; 214 } 215 return FALSE; /* Entry does not exist */ 216 } 217 218 219 220 /* 221 * Insert the data item "element" into the hash table using "hashcode" 222 * to determine the bucket number, and "compare" and "key" to determine 223 * its uniqueness. 224 * 225 * If the insertion is successful 0 is returned. If a matching entry 226 * already exists in the given bucket of the hash table, or some other error 227 * occurs, -1 is returned and the insertion is not done. 228 */ 229 230 int 231 hash_Insert(hashtable, hashcode, compare, key, element) 232 hash_tbl *hashtable; 233 unsigned hashcode; 234 hash_cmpfp compare; 235 hash_datum *key, *element; 236 { 237 hash_member *temp; 238 239 hashcode %= hashtable->size; 240 if (hash_Exists(hashtable, hashcode, compare, key)) { 241 return -1; /* At least one entry already exists */ 242 } 243 temp = (hash_member *) malloc(sizeof(hash_member)); 244 if (!temp) 245 return -1; /* malloc failed! */ 246 247 temp->data = element; 248 temp->next = (hashtable->table)[hashcode]; 249 (hashtable->table)[hashcode] = temp; 250 return 0; /* Success */ 251 } 252 253 254 255 /* 256 * Delete all data elements which match the given key. If at least one 257 * element is found and the deletion is successful, 0 is returned. 258 * If no matching elements can be found in the hash table, -1 is returned. 259 */ 260 261 int 262 hash_Delete(hashtable, hashcode, compare, key, free_data) 263 hash_tbl *hashtable; 264 unsigned hashcode; 265 hash_cmpfp compare; 266 hash_datum *key; 267 hash_freefp free_data; 268 { 269 hash_member *memberptr, *tempptr; 270 hash_member *previous = NULL; 271 int retval; 272 273 retval = -1; 274 hashcode %= hashtable->size; 275 276 /* 277 * Delete the first member of the list if it matches. Since this moves 278 * the second member into the first position we have to keep doing this 279 * over and over until it no longer matches. 280 */ 281 memberptr = (hashtable->table)[hashcode]; 282 while (memberptr && (*compare) (key, memberptr->data)) { 283 (hashtable->table)[hashcode] = memberptr->next; 284 /* 285 * Stop hashi_FreeMembers() from deleting the whole list! 286 */ 287 memberptr->next = NULL; 288 hashi_FreeMembers(memberptr, free_data); 289 memberptr = (hashtable->table)[hashcode]; 290 retval = 0; 291 } 292 293 /* 294 * Now traverse the rest of the list 295 */ 296 if (memberptr) { 297 previous = memberptr; 298 memberptr = memberptr->next; 299 } 300 while (memberptr) { 301 if ((*compare) (key, memberptr->data)) { 302 tempptr = memberptr; 303 previous->next = memberptr = memberptr->next; 304 /* 305 * Put the brakes on hashi_FreeMembers(). . . . 306 */ 307 tempptr->next = NULL; 308 hashi_FreeMembers(tempptr, free_data); 309 retval = 0; 310 } else { 311 previous = memberptr; 312 memberptr = memberptr->next; 313 } 314 } 315 return retval; 316 } 317 318 319 320 /* 321 * Locate and return the data entry associated with the given key. 322 * 323 * If the data entry is found, a pointer to it is returned. Otherwise, 324 * NULL is returned. 325 */ 326 327 hash_datum * 328 hash_Lookup(hashtable, hashcode, compare, key) 329 hash_tbl *hashtable; 330 unsigned hashcode; 331 hash_cmpfp compare; 332 hash_datum *key; 333 { 334 hash_member *memberptr; 335 336 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 337 while (memberptr) { 338 if ((*compare) (key, memberptr->data)) { 339 return (memberptr->data); 340 } 341 memberptr = memberptr->next; 342 } 343 return NULL; 344 } 345 346 347 348 /* 349 * Return the next available entry in the hashtable for a linear search 350 */ 351 352 hash_datum * 353 hash_NextEntry(hashtable) 354 hash_tbl *hashtable; 355 { 356 register unsigned bucket; 357 register hash_member *memberptr; 358 359 /* 360 * First try to pick up where we left off. 361 */ 362 memberptr = hashtable->member; 363 if (memberptr) { 364 hashtable->member = memberptr->next; /* Set up for next call */ 365 return memberptr->data; /* Return the data */ 366 } 367 /* 368 * We hit the end of a chain, so look through the array of buckets 369 * until we find a new chain (non-empty bucket) or run out of buckets. 370 */ 371 bucket = hashtable->bucketnum + 1; 372 while ((bucket < hashtable->size) && 373 !(memberptr = (hashtable->table)[bucket])) { 374 bucket++; 375 } 376 377 /* 378 * Check to see if we ran out of buckets. 379 */ 380 if (bucket >= hashtable->size) { 381 /* 382 * Reset to top of table for next call. 383 */ 384 hashtable->bucketnum = 0; 385 hashtable->member = (hashtable->table)[0]; 386 /* 387 * But return end-of-table indication to the caller this time. 388 */ 389 return NULL; 390 } 391 /* 392 * Must have found a non-empty bucket. 393 */ 394 hashtable->bucketnum = bucket; 395 hashtable->member = memberptr->next; /* Set up for next call */ 396 return memberptr->data; /* Return the data */ 397 } 398 399 400 401 /* 402 * Return the first entry in a hash table for a linear search 403 */ 404 405 hash_datum * 406 hash_FirstEntry(hashtable) 407 hash_tbl *hashtable; 408 { 409 hashtable->bucketnum = 0; 410 hashtable->member = (hashtable->table)[0]; 411 return hash_NextEntry(hashtable); 412 } 413 414 /* 415 * Local Variables: 416 * tab-width: 4 417 * c-indent-level: 4 418 * c-argdecl-indent: 4 419 * c-continued-statement-offset: 4 420 * c-continued-brace-offset: -4 421 * c-label-offset: -4 422 * c-brace-offset: 0 423 * End: 424 */ 425