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