hash.c revision 3229
1/************************************************************************ 2 Copyright 1988, 1991 by Carnegie Mellon University 3 4 All Rights Reserved 5 6Permission to use, copy, modify, and distribute this software and its 7documentation for any purpose and without fee is hereby granted, provided 8that the above copyright notice appear in all copies and that both that 9copyright notice and this permission notice appear in supporting 10documentation, and that the name of Carnegie Mellon University not be used 11in advertising or publicity pertaining to distribution of the software 12without specific, written prior permission. 13 14CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 15SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 16IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 17DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 18PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 19ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 20SOFTWARE. 21************************************************************************/ 22 23#ifndef lint 24static char rcsid[] = "$Id: hash.c,v 1.1.1.1 1994/09/10 14:44:55 csgr Exp $"; 25#endif 26 27 28/* 29 * Generalized hash table ADT 30 * 31 * Provides multiple, dynamically-allocated, variable-sized hash tables on 32 * various data and keys. 33 * 34 * This package attempts to follow some of the coding conventions suggested 35 * by Bob Sidebotham and the AFS Clean Code Committee of the 36 * Information Technology Center at Carnegie Mellon. 37 */ 38 39 40#include <sys/types.h> 41#include <stdlib.h> 42 43#ifndef USE_BFUNCS 44#include <memory.h> 45/* Yes, memcpy is OK here (no overlapped copies). */ 46#define bcopy(a,b,c) memcpy(b,a,c) 47#define bzero(p,l) memset(p,0,l) 48#define bcmp(a,b,c) memcmp(a,b,c) 49#endif 50 51#include "hash.h" 52 53#define TRUE 1 54#define FALSE 0 55#ifndef NULL 56#define NULL 0 57#endif 58 59/* 60 * This can be changed to make internal routines visible to debuggers, etc. 61 */ 62#ifndef PRIVATE 63#define PRIVATE static 64#endif 65 66#ifdef __STDC__ 67#define P(args) args 68#else 69#define P(args) () 70#endif 71 72PRIVATE void hashi_FreeMembers P((hash_member *, hash_freefp)); 73 74#undef P 75 76 77 78/* 79 * Hash table initialization routine. 80 * 81 * This routine creates and intializes a hash table of size "tablesize" 82 * entries. Successful calls return a pointer to the hash table (which must 83 * be passed to other hash routines to identify the hash table). Failed 84 * calls return NULL. 85 */ 86 87hash_tbl * 88hash_Init(tablesize) 89 unsigned tablesize; 90{ 91 register hash_tbl *hashtblptr; 92 register unsigned totalsize; 93 94 if (tablesize > 0) { 95 totalsize = sizeof(hash_tbl) 96 + sizeof(hash_member *) * (tablesize - 1); 97 hashtblptr = (hash_tbl *) malloc(totalsize); 98 if (hashtblptr) { 99 bzero((char *) hashtblptr, totalsize); 100 hashtblptr->size = tablesize; /* Success! */ 101 hashtblptr->bucketnum = 0; 102 hashtblptr->member = (hashtblptr->table)[0]; 103 } 104 } else { 105 hashtblptr = NULL; /* Disallow zero-length tables */ 106 } 107 return hashtblptr; /* NULL if failure */ 108} 109 110 111 112/* 113 * Frees an entire linked list of bucket members (used in the open 114 * hashing scheme). Does nothing if the passed pointer is NULL. 115 */ 116 117PRIVATE void 118hashi_FreeMembers(bucketptr, free_data) 119 hash_member *bucketptr; 120 hash_freefp free_data; 121{ 122 hash_member *nextbucket; 123 while (bucketptr) { 124 nextbucket = bucketptr->next; 125 (*free_data) (bucketptr->data); 126 free((char *) bucketptr); 127 bucketptr = nextbucket; 128 } 129} 130 131 132 133 134/* 135 * This routine re-initializes the hash table. It frees all the allocated 136 * memory and resets all bucket pointers to NULL. 137 */ 138 139void 140hash_Reset(hashtable, free_data) 141 hash_tbl *hashtable; 142 hash_freefp free_data; 143{ 144 hash_member **bucketptr; 145 unsigned i; 146 147 bucketptr = hashtable->table; 148 for (i = 0; i < hashtable->size; i++) { 149 hashi_FreeMembers(*bucketptr, free_data); 150 *bucketptr++ = NULL; 151 } 152 hashtable->bucketnum = 0; 153 hashtable->member = (hashtable->table)[0]; 154} 155 156 157 158/* 159 * Generic hash function to calculate a hash code from the given string. 160 * 161 * For each byte of the string, this function left-shifts the value in an 162 * accumulator and then adds the byte into the accumulator. The contents of 163 * the accumulator is returned after the entire string has been processed. 164 * It is assumed that this result will be used as the "hashcode" parameter in 165 * calls to other functions in this package. These functions automatically 166 * adjust the hashcode for the size of each hashtable. 167 * 168 * This algorithm probably works best when the hash table size is a prime 169 * number. 170 * 171 * Hopefully, this function is better than the previous one which returned 172 * the sum of the squares of all the bytes. I'm still open to other 173 * suggestions for a default hash function. The programmer is more than 174 * welcome to supply his/her own hash function as that is one of the design 175 * features of this package. 176 */ 177 178unsigned 179hash_HashFunction(string, len) 180 unsigned char *string; 181 register unsigned len; 182{ 183 register unsigned accum; 184 185 accum = 0; 186 for (; len > 0; len--) { 187 accum <<= 1; 188 accum += (unsigned) (*string++ & 0xFF); 189 } 190 return accum; 191} 192 193 194 195/* 196 * Returns TRUE if at least one entry for the given key exists; FALSE 197 * otherwise. 198 */ 199 200int 201hash_Exists(hashtable, hashcode, compare, key) 202 hash_tbl *hashtable; 203 unsigned hashcode; 204 hash_cmpfp compare; 205 hash_datum *key; 206{ 207 register hash_member *memberptr; 208 209 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 210 while (memberptr) { 211 if ((*compare) (key, memberptr->data)) { 212 return TRUE; /* Entry does exist */ 213 } 214 memberptr = memberptr->next; 215 } 216 return FALSE; /* Entry does not exist */ 217} 218 219 220 221/* 222 * Insert the data item "element" into the hash table using "hashcode" 223 * to determine the bucket number, and "compare" and "key" to determine 224 * its uniqueness. 225 * 226 * If the insertion is successful 0 is returned. If a matching entry 227 * already exists in the given bucket of the hash table, or some other error 228 * occurs, -1 is returned and the insertion is not done. 229 */ 230 231int 232hash_Insert(hashtable, hashcode, compare, key, element) 233 hash_tbl *hashtable; 234 unsigned hashcode; 235 hash_cmpfp compare; 236 hash_datum *key, *element; 237{ 238 hash_member *temp; 239 240 hashcode %= hashtable->size; 241 if (hash_Exists(hashtable, hashcode, compare, key)) { 242 return -1; /* At least one entry already exists */ 243 } 244 temp = (hash_member *) malloc(sizeof(hash_member)); 245 if (!temp) 246 return -1; /* malloc failed! */ 247 248 temp->data = element; 249 temp->next = (hashtable->table)[hashcode]; 250 (hashtable->table)[hashcode] = temp; 251 return 0; /* Success */ 252} 253 254 255 256/* 257 * Delete all data elements which match the given key. If at least one 258 * element is found and the deletion is successful, 0 is returned. 259 * If no matching elements can be found in the hash table, -1 is returned. 260 */ 261 262int 263hash_Delete(hashtable, hashcode, compare, key, free_data) 264 hash_tbl *hashtable; 265 unsigned hashcode; 266 hash_cmpfp compare; 267 hash_datum *key; 268 hash_freefp free_data; 269{ 270 hash_member *memberptr, *tempptr; 271 hash_member *previous = NULL; 272 int retval; 273 274 retval = -1; 275 hashcode %= hashtable->size; 276 277 /* 278 * Delete the first member of the list if it matches. Since this moves 279 * the second member into the first position we have to keep doing this 280 * over and over until it no longer matches. 281 */ 282 memberptr = (hashtable->table)[hashcode]; 283 while (memberptr && (*compare) (key, memberptr->data)) { 284 (hashtable->table)[hashcode] = memberptr->next; 285 /* 286 * Stop hashi_FreeMembers() from deleting the whole list! 287 */ 288 memberptr->next = NULL; 289 hashi_FreeMembers(memberptr, free_data); 290 memberptr = (hashtable->table)[hashcode]; 291 retval = 0; 292 } 293 294 /* 295 * Now traverse the rest of the list 296 */ 297 if (memberptr) { 298 previous = memberptr; 299 memberptr = memberptr->next; 300 } 301 while (memberptr) { 302 if ((*compare) (key, memberptr->data)) { 303 tempptr = memberptr; 304 previous->next = memberptr = memberptr->next; 305 /* 306 * Put the brakes on hashi_FreeMembers(). . . . 307 */ 308 tempptr->next = NULL; 309 hashi_FreeMembers(tempptr, free_data); 310 retval = 0; 311 } else { 312 previous = memberptr; 313 memberptr = memberptr->next; 314 } 315 } 316 return retval; 317} 318 319 320 321/* 322 * Locate and return the data entry associated with the given key. 323 * 324 * If the data entry is found, a pointer to it is returned. Otherwise, 325 * NULL is returned. 326 */ 327 328hash_datum * 329hash_Lookup(hashtable, hashcode, compare, key) 330 hash_tbl *hashtable; 331 unsigned hashcode; 332 hash_cmpfp compare; 333 hash_datum *key; 334{ 335 hash_member *memberptr; 336 337 memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 338 while (memberptr) { 339 if ((*compare) (key, memberptr->data)) { 340 return (memberptr->data); 341 } 342 memberptr = memberptr->next; 343 } 344 return NULL; 345} 346 347 348 349/* 350 * Return the next available entry in the hashtable for a linear search 351 */ 352 353hash_datum * 354hash_NextEntry(hashtable) 355 hash_tbl *hashtable; 356{ 357 register unsigned bucket; 358 register hash_member *memberptr; 359 360 /* 361 * First try to pick up where we left off. 362 */ 363 memberptr = hashtable->member; 364 if (memberptr) { 365 hashtable->member = memberptr->next; /* Set up for next call */ 366 return memberptr->data; /* Return the data */ 367 } 368 /* 369 * We hit the end of a chain, so look through the array of buckets 370 * until we find a new chain (non-empty bucket) or run out of buckets. 371 */ 372 bucket = hashtable->bucketnum + 1; 373 while ((bucket < hashtable->size) && 374 !(memberptr = (hashtable->table)[bucket])) { 375 bucket++; 376 } 377 378 /* 379 * Check to see if we ran out of buckets. 380 */ 381 if (bucket >= hashtable->size) { 382 /* 383 * Reset to top of table for next call. 384 */ 385 hashtable->bucketnum = 0; 386 hashtable->member = (hashtable->table)[0]; 387 /* 388 * But return end-of-table indication to the caller this time. 389 */ 390 return NULL; 391 } 392 /* 393 * Must have found a non-empty bucket. 394 */ 395 hashtable->bucketnum = bucket; 396 hashtable->member = memberptr->next; /* Set up for next call */ 397 return memberptr->data; /* Return the data */ 398} 399 400 401 402/* 403 * Return the first entry in a hash table for a linear search 404 */ 405 406hash_datum * 407hash_FirstEntry(hashtable) 408 hash_tbl *hashtable; 409{ 410 hashtable->bucketnum = 0; 411 hashtable->member = (hashtable->table)[0]; 412 return hash_NextEntry(hashtable); 413} 414 415/* 416 * Local Variables: 417 * tab-width: 4 418 * c-indent-level: 4 419 * c-argdecl-indent: 4 420 * c-continued-statement-offset: 4 421 * c-continued-brace-offset: -4 422 * c-label-offset: -4 423 * c-brace-offset: 0 424 * End: 425 */ 426