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