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