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