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