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