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