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