diff options
Diffstat (limited to 'libexec/bootpd/hash.c')
-rw-r--r-- | libexec/bootpd/hash.c | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/libexec/bootpd/hash.c b/libexec/bootpd/hash.c new file mode 100644 index 0000000..2ecda63 --- /dev/null +++ b/libexec/bootpd/hash.c @@ -0,0 +1,425 @@ +/************************************************************************ + Copyright 1988, 1991 by Carnegie Mellon University + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, provided +that the above copyright notice appear in all copies and that both that +copyright notice and this permission notice appear in supporting +documentation, and that the name of Carnegie Mellon University not be used +in advertising or publicity pertaining to distribution of the software +without specific, written prior permission. + +CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS +SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. +IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL +DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +SOFTWARE. +************************************************************************/ + +#ifndef lint +static char rcsid[] = "$Id: hash.c,v 1.1.1.1 1994/09/10 14:44:55 csgr Exp $"; +#endif + + +/* + * Generalized hash table ADT + * + * Provides multiple, dynamically-allocated, variable-sized hash tables on + * various data and keys. + * + * This package attempts to follow some of the coding conventions suggested + * by Bob Sidebotham and the AFS Clean Code Committee of the + * Information Technology Center at Carnegie Mellon. + */ + + +#include <sys/types.h> +#include <stdlib.h> + +#ifndef USE_BFUNCS +#include <memory.h> +/* Yes, memcpy is OK here (no overlapped copies). */ +#define bcopy(a,b,c) memcpy(b,a,c) +#define bzero(p,l) memset(p,0,l) +#define bcmp(a,b,c) memcmp(a,b,c) +#endif + +#include "hash.h" + +#define TRUE 1 +#define FALSE 0 +#ifndef NULL +#define NULL 0 +#endif + +/* + * This can be changed to make internal routines visible to debuggers, etc. + */ +#ifndef PRIVATE +#define PRIVATE static +#endif + +#ifdef __STDC__ +#define P(args) args +#else +#define P(args) () +#endif + +PRIVATE void hashi_FreeMembers P((hash_member *, hash_freefp)); + +#undef P + + + +/* + * Hash table initialization routine. + * + * This routine creates and intializes a hash table of size "tablesize" + * entries. Successful calls return a pointer to the hash table (which must + * be passed to other hash routines to identify the hash table). Failed + * calls return NULL. + */ + +hash_tbl * +hash_Init(tablesize) + unsigned tablesize; +{ + register hash_tbl *hashtblptr; + register unsigned totalsize; + + if (tablesize > 0) { + totalsize = sizeof(hash_tbl) + + sizeof(hash_member *) * (tablesize - 1); + hashtblptr = (hash_tbl *) malloc(totalsize); + if (hashtblptr) { + bzero((char *) hashtblptr, totalsize); + hashtblptr->size = tablesize; /* Success! */ + hashtblptr->bucketnum = 0; + hashtblptr->member = (hashtblptr->table)[0]; + } + } else { + hashtblptr = NULL; /* Disallow zero-length tables */ + } + return hashtblptr; /* NULL if failure */ +} + + + +/* + * Frees an entire linked list of bucket members (used in the open + * hashing scheme). Does nothing if the passed pointer is NULL. + */ + +PRIVATE void +hashi_FreeMembers(bucketptr, free_data) + hash_member *bucketptr; + hash_freefp free_data; +{ + hash_member *nextbucket; + while (bucketptr) { + nextbucket = bucketptr->next; + (*free_data) (bucketptr->data); + free((char *) bucketptr); + bucketptr = nextbucket; + } +} + + + + +/* + * This routine re-initializes the hash table. It frees all the allocated + * memory and resets all bucket pointers to NULL. + */ + +void +hash_Reset(hashtable, free_data) + hash_tbl *hashtable; + hash_freefp free_data; +{ + hash_member **bucketptr; + unsigned i; + + bucketptr = hashtable->table; + for (i = 0; i < hashtable->size; i++) { + hashi_FreeMembers(*bucketptr, free_data); + *bucketptr++ = NULL; + } + hashtable->bucketnum = 0; + hashtable->member = (hashtable->table)[0]; +} + + + +/* + * Generic hash function to calculate a hash code from the given string. + * + * For each byte of the string, this function left-shifts the value in an + * accumulator and then adds the byte into the accumulator. The contents of + * the accumulator is returned after the entire string has been processed. + * It is assumed that this result will be used as the "hashcode" parameter in + * calls to other functions in this package. These functions automatically + * adjust the hashcode for the size of each hashtable. + * + * This algorithm probably works best when the hash table size is a prime + * number. + * + * Hopefully, this function is better than the previous one which returned + * the sum of the squares of all the bytes. I'm still open to other + * suggestions for a default hash function. The programmer is more than + * welcome to supply his/her own hash function as that is one of the design + * features of this package. + */ + +unsigned +hash_HashFunction(string, len) + unsigned char *string; + register unsigned len; +{ + register unsigned accum; + + accum = 0; + for (; len > 0; len--) { + accum <<= 1; + accum += (unsigned) (*string++ & 0xFF); + } + return accum; +} + + + +/* + * Returns TRUE if at least one entry for the given key exists; FALSE + * otherwise. + */ + +int +hash_Exists(hashtable, hashcode, compare, key) + hash_tbl *hashtable; + unsigned hashcode; + hash_cmpfp compare; + hash_datum *key; +{ + register hash_member *memberptr; + + memberptr = (hashtable->table)[hashcode % (hashtable->size)]; + while (memberptr) { + if ((*compare) (key, memberptr->data)) { + return TRUE; /* Entry does exist */ + } + memberptr = memberptr->next; + } + return FALSE; /* Entry does not exist */ +} + + + +/* + * Insert the data item "element" into the hash table using "hashcode" + * to determine the bucket number, and "compare" and "key" to determine + * its uniqueness. + * + * If the insertion is successful 0 is returned. If a matching entry + * already exists in the given bucket of the hash table, or some other error + * occurs, -1 is returned and the insertion is not done. + */ + +int +hash_Insert(hashtable, hashcode, compare, key, element) + hash_tbl *hashtable; + unsigned hashcode; + hash_cmpfp compare; + hash_datum *key, *element; +{ + hash_member *temp; + + hashcode %= hashtable->size; + if (hash_Exists(hashtable, hashcode, compare, key)) { + return -1; /* At least one entry already exists */ + } + temp = (hash_member *) malloc(sizeof(hash_member)); + if (!temp) + return -1; /* malloc failed! */ + + temp->data = element; + temp->next = (hashtable->table)[hashcode]; + (hashtable->table)[hashcode] = temp; + return 0; /* Success */ +} + + + +/* + * Delete all data elements which match the given key. If at least one + * element is found and the deletion is successful, 0 is returned. + * If no matching elements can be found in the hash table, -1 is returned. + */ + +int +hash_Delete(hashtable, hashcode, compare, key, free_data) + hash_tbl *hashtable; + unsigned hashcode; + hash_cmpfp compare; + hash_datum *key; + hash_freefp free_data; +{ + hash_member *memberptr, *tempptr; + hash_member *previous = NULL; + int retval; + + retval = -1; + hashcode %= hashtable->size; + + /* + * Delete the first member of the list if it matches. Since this moves + * the second member into the first position we have to keep doing this + * over and over until it no longer matches. + */ + memberptr = (hashtable->table)[hashcode]; + while (memberptr && (*compare) (key, memberptr->data)) { + (hashtable->table)[hashcode] = memberptr->next; + /* + * Stop hashi_FreeMembers() from deleting the whole list! + */ + memberptr->next = NULL; + hashi_FreeMembers(memberptr, free_data); + memberptr = (hashtable->table)[hashcode]; + retval = 0; + } + + /* + * Now traverse the rest of the list + */ + if (memberptr) { + previous = memberptr; + memberptr = memberptr->next; + } + while (memberptr) { + if ((*compare) (key, memberptr->data)) { + tempptr = memberptr; + previous->next = memberptr = memberptr->next; + /* + * Put the brakes on hashi_FreeMembers(). . . . + */ + tempptr->next = NULL; + hashi_FreeMembers(tempptr, free_data); + retval = 0; + } else { + previous = memberptr; + memberptr = memberptr->next; + } + } + return retval; +} + + + +/* + * Locate and return the data entry associated with the given key. + * + * If the data entry is found, a pointer to it is returned. Otherwise, + * NULL is returned. + */ + +hash_datum * +hash_Lookup(hashtable, hashcode, compare, key) + hash_tbl *hashtable; + unsigned hashcode; + hash_cmpfp compare; + hash_datum *key; +{ + hash_member *memberptr; + + memberptr = (hashtable->table)[hashcode % (hashtable->size)]; + while (memberptr) { + if ((*compare) (key, memberptr->data)) { + return (memberptr->data); + } + memberptr = memberptr->next; + } + return NULL; +} + + + +/* + * Return the next available entry in the hashtable for a linear search + */ + +hash_datum * +hash_NextEntry(hashtable) + hash_tbl *hashtable; +{ + register unsigned bucket; + register hash_member *memberptr; + + /* + * First try to pick up where we left off. + */ + memberptr = hashtable->member; + if (memberptr) { + hashtable->member = memberptr->next; /* Set up for next call */ + return memberptr->data; /* Return the data */ + } + /* + * We hit the end of a chain, so look through the array of buckets + * until we find a new chain (non-empty bucket) or run out of buckets. + */ + bucket = hashtable->bucketnum + 1; + while ((bucket < hashtable->size) && + !(memberptr = (hashtable->table)[bucket])) { + bucket++; + } + + /* + * Check to see if we ran out of buckets. + */ + if (bucket >= hashtable->size) { + /* + * Reset to top of table for next call. + */ + hashtable->bucketnum = 0; + hashtable->member = (hashtable->table)[0]; + /* + * But return end-of-table indication to the caller this time. + */ + return NULL; + } + /* + * Must have found a non-empty bucket. + */ + hashtable->bucketnum = bucket; + hashtable->member = memberptr->next; /* Set up for next call */ + return memberptr->data; /* Return the data */ +} + + + +/* + * Return the first entry in a hash table for a linear search + */ + +hash_datum * +hash_FirstEntry(hashtable) + hash_tbl *hashtable; +{ + hashtable->bucketnum = 0; + hashtable->member = (hashtable->table)[0]; + return hash_NextEntry(hashtable); +} + +/* + * Local Variables: + * tab-width: 4 + * c-indent-level: 4 + * c-argdecl-indent: 4 + * c-continued-statement-offset: 4 + * c-continued-brace-offset: -4 + * c-label-offset: -4 + * c-brace-offset: 0 + * End: + */ |