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