hash.c revision 50476
13229Spst/************************************************************************ 23229Spst Copyright 1988, 1991 by Carnegie Mellon University 33229Spst 43229Spst All Rights Reserved 53229Spst 63229SpstPermission to use, copy, modify, and distribute this software and its 73229Spstdocumentation for any purpose and without fee is hereby granted, provided 83229Spstthat the above copyright notice appear in all copies and that both that 93229Spstcopyright notice and this permission notice appear in supporting 103229Spstdocumentation, and that the name of Carnegie Mellon University not be used 113229Spstin advertising or publicity pertaining to distribution of the software 123229Spstwithout specific, written prior permission. 133229Spst 143229SpstCARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 153229SpstSOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 163229SpstIN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 173229SpstDAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 183229SpstPROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 193229SpstACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 203229SpstSOFTWARE. 2118471Swosch 2250476Speter $FreeBSD: head/libexec/bootpd/hash.c 50476 1999-08-28 00:22:10Z peter $ 2318471Swosch 243229Spst************************************************************************/ 253229Spst 263229Spst/* 273229Spst * Generalized hash table ADT 283229Spst * 293229Spst * Provides multiple, dynamically-allocated, variable-sized hash tables on 303229Spst * various data and keys. 313229Spst * 323229Spst * This package attempts to follow some of the coding conventions suggested 333229Spst * by Bob Sidebotham and the AFS Clean Code Committee of the 343229Spst * Information Technology Center at Carnegie Mellon. 353229Spst */ 363229Spst 373229Spst 383229Spst#include <sys/types.h> 393229Spst#include <stdlib.h> 403229Spst 413229Spst#ifndef USE_BFUNCS 423229Spst#include <memory.h> 433229Spst/* Yes, memcpy is OK here (no overlapped copies). */ 443229Spst#define bcopy(a,b,c) memcpy(b,a,c) 453229Spst#define bzero(p,l) memset(p,0,l) 463229Spst#define bcmp(a,b,c) memcmp(a,b,c) 473229Spst#endif 483229Spst 493229Spst#include "hash.h" 503229Spst 513229Spst#define TRUE 1 523229Spst#define FALSE 0 533229Spst#ifndef NULL 543229Spst#define NULL 0 553229Spst#endif 563229Spst 573229Spst/* 583229Spst * This can be changed to make internal routines visible to debuggers, etc. 593229Spst */ 603229Spst#ifndef PRIVATE 613229Spst#define PRIVATE static 623229Spst#endif 633229Spst 643229Spst#ifdef __STDC__ 653229Spst#define P(args) args 663229Spst#else 673229Spst#define P(args) () 683229Spst#endif 693229Spst 703229SpstPRIVATE void hashi_FreeMembers P((hash_member *, hash_freefp)); 713229Spst 723229Spst#undef P 733229Spst 743229Spst 753229Spst 763229Spst/* 773229Spst * Hash table initialization routine. 783229Spst * 793229Spst * This routine creates and intializes a hash table of size "tablesize" 803229Spst * entries. Successful calls return a pointer to the hash table (which must 813229Spst * be passed to other hash routines to identify the hash table). Failed 823229Spst * calls return NULL. 833229Spst */ 843229Spst 853229Spsthash_tbl * 863229Spsthash_Init(tablesize) 873229Spst unsigned tablesize; 883229Spst{ 893229Spst register hash_tbl *hashtblptr; 903229Spst register unsigned totalsize; 913229Spst 923229Spst if (tablesize > 0) { 933229Spst totalsize = sizeof(hash_tbl) 943229Spst + sizeof(hash_member *) * (tablesize - 1); 953229Spst hashtblptr = (hash_tbl *) malloc(totalsize); 963229Spst if (hashtblptr) { 973229Spst bzero((char *) hashtblptr, totalsize); 983229Spst hashtblptr->size = tablesize; /* Success! */ 993229Spst hashtblptr->bucketnum = 0; 1003229Spst hashtblptr->member = (hashtblptr->table)[0]; 1013229Spst } 1023229Spst } else { 1033229Spst hashtblptr = NULL; /* Disallow zero-length tables */ 1043229Spst } 1053229Spst return hashtblptr; /* NULL if failure */ 1063229Spst} 1073229Spst 1083229Spst 1093229Spst 1103229Spst/* 1113229Spst * Frees an entire linked list of bucket members (used in the open 1123229Spst * hashing scheme). Does nothing if the passed pointer is NULL. 1133229Spst */ 1143229Spst 1153229SpstPRIVATE void 1163229Spsthashi_FreeMembers(bucketptr, free_data) 1173229Spst hash_member *bucketptr; 1183229Spst hash_freefp free_data; 1193229Spst{ 1203229Spst hash_member *nextbucket; 1213229Spst while (bucketptr) { 1223229Spst nextbucket = bucketptr->next; 1233229Spst (*free_data) (bucketptr->data); 1243229Spst free((char *) bucketptr); 1253229Spst bucketptr = nextbucket; 1263229Spst } 1273229Spst} 1283229Spst 1293229Spst 1303229Spst 1313229Spst 1323229Spst/* 1333229Spst * This routine re-initializes the hash table. It frees all the allocated 1343229Spst * memory and resets all bucket pointers to NULL. 1353229Spst */ 1363229Spst 1373229Spstvoid 1383229Spsthash_Reset(hashtable, free_data) 1393229Spst hash_tbl *hashtable; 1403229Spst hash_freefp free_data; 1413229Spst{ 1423229Spst hash_member **bucketptr; 1433229Spst unsigned i; 1443229Spst 1453229Spst bucketptr = hashtable->table; 1463229Spst for (i = 0; i < hashtable->size; i++) { 1473229Spst hashi_FreeMembers(*bucketptr, free_data); 1483229Spst *bucketptr++ = NULL; 1493229Spst } 1503229Spst hashtable->bucketnum = 0; 1513229Spst hashtable->member = (hashtable->table)[0]; 1523229Spst} 1533229Spst 1543229Spst 1553229Spst 1563229Spst/* 1573229Spst * Generic hash function to calculate a hash code from the given string. 1583229Spst * 1593229Spst * For each byte of the string, this function left-shifts the value in an 1603229Spst * accumulator and then adds the byte into the accumulator. The contents of 1613229Spst * the accumulator is returned after the entire string has been processed. 1623229Spst * It is assumed that this result will be used as the "hashcode" parameter in 1633229Spst * calls to other functions in this package. These functions automatically 1643229Spst * adjust the hashcode for the size of each hashtable. 1653229Spst * 1663229Spst * This algorithm probably works best when the hash table size is a prime 1673229Spst * number. 1683229Spst * 1693229Spst * Hopefully, this function is better than the previous one which returned 1703229Spst * the sum of the squares of all the bytes. I'm still open to other 1713229Spst * suggestions for a default hash function. The programmer is more than 1723229Spst * welcome to supply his/her own hash function as that is one of the design 1733229Spst * features of this package. 1743229Spst */ 1753229Spst 1763229Spstunsigned 1773229Spsthash_HashFunction(string, len) 1783229Spst unsigned char *string; 1793229Spst register unsigned len; 1803229Spst{ 1813229Spst register unsigned accum; 1823229Spst 1833229Spst accum = 0; 1843229Spst for (; len > 0; len--) { 1853229Spst accum <<= 1; 1863229Spst accum += (unsigned) (*string++ & 0xFF); 1873229Spst } 1883229Spst return accum; 1893229Spst} 1903229Spst 1913229Spst 1923229Spst 1933229Spst/* 1943229Spst * Returns TRUE if at least one entry for the given key exists; FALSE 1953229Spst * otherwise. 1963229Spst */ 1973229Spst 1983229Spstint 1993229Spsthash_Exists(hashtable, hashcode, compare, key) 2003229Spst hash_tbl *hashtable; 2013229Spst unsigned hashcode; 2023229Spst hash_cmpfp compare; 2033229Spst hash_datum *key; 2043229Spst{ 2053229Spst register hash_member *memberptr; 2063229Spst 2073229Spst memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 2083229Spst while (memberptr) { 2093229Spst if ((*compare) (key, memberptr->data)) { 2103229Spst return TRUE; /* Entry does exist */ 2113229Spst } 2123229Spst memberptr = memberptr->next; 2133229Spst } 2143229Spst return FALSE; /* Entry does not exist */ 2153229Spst} 2163229Spst 2173229Spst 2183229Spst 2193229Spst/* 2203229Spst * Insert the data item "element" into the hash table using "hashcode" 2213229Spst * to determine the bucket number, and "compare" and "key" to determine 2223229Spst * its uniqueness. 2233229Spst * 2243229Spst * If the insertion is successful 0 is returned. If a matching entry 2253229Spst * already exists in the given bucket of the hash table, or some other error 2263229Spst * occurs, -1 is returned and the insertion is not done. 2273229Spst */ 2283229Spst 2293229Spstint 2303229Spsthash_Insert(hashtable, hashcode, compare, key, element) 2313229Spst hash_tbl *hashtable; 2323229Spst unsigned hashcode; 2333229Spst hash_cmpfp compare; 2343229Spst hash_datum *key, *element; 2353229Spst{ 2363229Spst hash_member *temp; 2373229Spst 2383229Spst hashcode %= hashtable->size; 2393229Spst if (hash_Exists(hashtable, hashcode, compare, key)) { 2403229Spst return -1; /* At least one entry already exists */ 2413229Spst } 2423229Spst temp = (hash_member *) malloc(sizeof(hash_member)); 2433229Spst if (!temp) 2443229Spst return -1; /* malloc failed! */ 2453229Spst 2463229Spst temp->data = element; 2473229Spst temp->next = (hashtable->table)[hashcode]; 2483229Spst (hashtable->table)[hashcode] = temp; 2493229Spst return 0; /* Success */ 2503229Spst} 2513229Spst 2523229Spst 2533229Spst 2543229Spst/* 2553229Spst * Delete all data elements which match the given key. If at least one 2563229Spst * element is found and the deletion is successful, 0 is returned. 2573229Spst * If no matching elements can be found in the hash table, -1 is returned. 2583229Spst */ 2593229Spst 2603229Spstint 2613229Spsthash_Delete(hashtable, hashcode, compare, key, free_data) 2623229Spst hash_tbl *hashtable; 2633229Spst unsigned hashcode; 2643229Spst hash_cmpfp compare; 2653229Spst hash_datum *key; 2663229Spst hash_freefp free_data; 2673229Spst{ 2683229Spst hash_member *memberptr, *tempptr; 2693229Spst hash_member *previous = NULL; 2703229Spst int retval; 2713229Spst 2723229Spst retval = -1; 2733229Spst hashcode %= hashtable->size; 2743229Spst 2753229Spst /* 2763229Spst * Delete the first member of the list if it matches. Since this moves 2773229Spst * the second member into the first position we have to keep doing this 2783229Spst * over and over until it no longer matches. 2793229Spst */ 2803229Spst memberptr = (hashtable->table)[hashcode]; 2813229Spst while (memberptr && (*compare) (key, memberptr->data)) { 2823229Spst (hashtable->table)[hashcode] = memberptr->next; 2833229Spst /* 2843229Spst * Stop hashi_FreeMembers() from deleting the whole list! 2853229Spst */ 2863229Spst memberptr->next = NULL; 2873229Spst hashi_FreeMembers(memberptr, free_data); 2883229Spst memberptr = (hashtable->table)[hashcode]; 2893229Spst retval = 0; 2903229Spst } 2913229Spst 2923229Spst /* 2933229Spst * Now traverse the rest of the list 2943229Spst */ 2953229Spst if (memberptr) { 2963229Spst previous = memberptr; 2973229Spst memberptr = memberptr->next; 2983229Spst } 2993229Spst while (memberptr) { 3003229Spst if ((*compare) (key, memberptr->data)) { 3013229Spst tempptr = memberptr; 3023229Spst previous->next = memberptr = memberptr->next; 3033229Spst /* 3043229Spst * Put the brakes on hashi_FreeMembers(). . . . 3053229Spst */ 3063229Spst tempptr->next = NULL; 3073229Spst hashi_FreeMembers(tempptr, free_data); 3083229Spst retval = 0; 3093229Spst } else { 3103229Spst previous = memberptr; 3113229Spst memberptr = memberptr->next; 3123229Spst } 3133229Spst } 3143229Spst return retval; 3153229Spst} 3163229Spst 3173229Spst 3183229Spst 3193229Spst/* 3203229Spst * Locate and return the data entry associated with the given key. 3213229Spst * 3223229Spst * If the data entry is found, a pointer to it is returned. Otherwise, 3233229Spst * NULL is returned. 3243229Spst */ 3253229Spst 3263229Spsthash_datum * 3273229Spsthash_Lookup(hashtable, hashcode, compare, key) 3283229Spst hash_tbl *hashtable; 3293229Spst unsigned hashcode; 3303229Spst hash_cmpfp compare; 3313229Spst hash_datum *key; 3323229Spst{ 3333229Spst hash_member *memberptr; 3343229Spst 3353229Spst memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 3363229Spst while (memberptr) { 3373229Spst if ((*compare) (key, memberptr->data)) { 3383229Spst return (memberptr->data); 3393229Spst } 3403229Spst memberptr = memberptr->next; 3413229Spst } 3423229Spst return NULL; 3433229Spst} 3443229Spst 3453229Spst 3463229Spst 3473229Spst/* 3483229Spst * Return the next available entry in the hashtable for a linear search 3493229Spst */ 3503229Spst 3513229Spsthash_datum * 3523229Spsthash_NextEntry(hashtable) 3533229Spst hash_tbl *hashtable; 3543229Spst{ 3553229Spst register unsigned bucket; 3563229Spst register hash_member *memberptr; 3573229Spst 3583229Spst /* 3593229Spst * First try to pick up where we left off. 3603229Spst */ 3613229Spst memberptr = hashtable->member; 3623229Spst if (memberptr) { 3633229Spst hashtable->member = memberptr->next; /* Set up for next call */ 3643229Spst return memberptr->data; /* Return the data */ 3653229Spst } 3663229Spst /* 3673229Spst * We hit the end of a chain, so look through the array of buckets 3683229Spst * until we find a new chain (non-empty bucket) or run out of buckets. 3693229Spst */ 3703229Spst bucket = hashtable->bucketnum + 1; 3713229Spst while ((bucket < hashtable->size) && 3723229Spst !(memberptr = (hashtable->table)[bucket])) { 3733229Spst bucket++; 3743229Spst } 3753229Spst 3763229Spst /* 3773229Spst * Check to see if we ran out of buckets. 3783229Spst */ 3793229Spst if (bucket >= hashtable->size) { 3803229Spst /* 3813229Spst * Reset to top of table for next call. 3823229Spst */ 3833229Spst hashtable->bucketnum = 0; 3843229Spst hashtable->member = (hashtable->table)[0]; 3853229Spst /* 3863229Spst * But return end-of-table indication to the caller this time. 3873229Spst */ 3883229Spst return NULL; 3893229Spst } 3903229Spst /* 3913229Spst * Must have found a non-empty bucket. 3923229Spst */ 3933229Spst hashtable->bucketnum = bucket; 3943229Spst hashtable->member = memberptr->next; /* Set up for next call */ 3953229Spst return memberptr->data; /* Return the data */ 3963229Spst} 3973229Spst 3983229Spst 3993229Spst 4003229Spst/* 4013229Spst * Return the first entry in a hash table for a linear search 4023229Spst */ 4033229Spst 4043229Spsthash_datum * 4053229Spsthash_FirstEntry(hashtable) 4063229Spst hash_tbl *hashtable; 4073229Spst{ 4083229Spst hashtable->bucketnum = 0; 4093229Spst hashtable->member = (hashtable->table)[0]; 4103229Spst return hash_NextEntry(hashtable); 4113229Spst} 4123229Spst 4133229Spst/* 4143229Spst * Local Variables: 4153229Spst * tab-width: 4 4163229Spst * c-indent-level: 4 4173229Spst * c-argdecl-indent: 4 4183229Spst * c-continued-statement-offset: 4 4193229Spst * c-continued-brace-offset: -4 4203229Spst * c-label-offset: -4 4213229Spst * c-brace-offset: 0 4223229Spst * End: 4233229Spst */ 424