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