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