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$ 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 6497417SalfredPRIVATE void hashi_FreeMembers(hash_member *, hash_freefp); 653229Spst 663229Spst 673229Spst 683229Spst 693229Spst/* 703229Spst * Hash table initialization routine. 713229Spst * 723229Spst * This routine creates and intializes a hash table of size "tablesize" 733229Spst * entries. Successful calls return a pointer to the hash table (which must 743229Spst * be passed to other hash routines to identify the hash table). Failed 753229Spst * calls return NULL. 763229Spst */ 773229Spst 783229Spsthash_tbl * 793229Spsthash_Init(tablesize) 803229Spst unsigned tablesize; 813229Spst{ 823229Spst register hash_tbl *hashtblptr; 833229Spst register unsigned totalsize; 843229Spst 853229Spst if (tablesize > 0) { 863229Spst totalsize = sizeof(hash_tbl) 873229Spst + sizeof(hash_member *) * (tablesize - 1); 883229Spst hashtblptr = (hash_tbl *) malloc(totalsize); 893229Spst if (hashtblptr) { 903229Spst bzero((char *) hashtblptr, totalsize); 913229Spst hashtblptr->size = tablesize; /* Success! */ 923229Spst hashtblptr->bucketnum = 0; 933229Spst hashtblptr->member = (hashtblptr->table)[0]; 943229Spst } 953229Spst } else { 963229Spst hashtblptr = NULL; /* Disallow zero-length tables */ 973229Spst } 983229Spst return hashtblptr; /* NULL if failure */ 993229Spst} 1003229Spst 1013229Spst 1023229Spst 1033229Spst/* 1043229Spst * Frees an entire linked list of bucket members (used in the open 1053229Spst * hashing scheme). Does nothing if the passed pointer is NULL. 1063229Spst */ 1073229Spst 1083229SpstPRIVATE void 1093229Spsthashi_FreeMembers(bucketptr, free_data) 1103229Spst hash_member *bucketptr; 1113229Spst hash_freefp free_data; 1123229Spst{ 1133229Spst hash_member *nextbucket; 1143229Spst while (bucketptr) { 1153229Spst nextbucket = bucketptr->next; 1163229Spst (*free_data) (bucketptr->data); 1173229Spst free((char *) bucketptr); 1183229Spst bucketptr = nextbucket; 1193229Spst } 1203229Spst} 1213229Spst 1223229Spst 1233229Spst 1243229Spst 1253229Spst/* 1263229Spst * This routine re-initializes the hash table. It frees all the allocated 1273229Spst * memory and resets all bucket pointers to NULL. 1283229Spst */ 1293229Spst 1303229Spstvoid 1313229Spsthash_Reset(hashtable, free_data) 1323229Spst hash_tbl *hashtable; 1333229Spst hash_freefp free_data; 1343229Spst{ 1353229Spst hash_member **bucketptr; 1363229Spst unsigned i; 1373229Spst 1383229Spst bucketptr = hashtable->table; 1393229Spst for (i = 0; i < hashtable->size; i++) { 1403229Spst hashi_FreeMembers(*bucketptr, free_data); 1413229Spst *bucketptr++ = NULL; 1423229Spst } 1433229Spst hashtable->bucketnum = 0; 1443229Spst hashtable->member = (hashtable->table)[0]; 1453229Spst} 1463229Spst 1473229Spst 1483229Spst 1493229Spst/* 1503229Spst * Generic hash function to calculate a hash code from the given string. 1513229Spst * 1523229Spst * For each byte of the string, this function left-shifts the value in an 1533229Spst * accumulator and then adds the byte into the accumulator. The contents of 1543229Spst * the accumulator is returned after the entire string has been processed. 1553229Spst * It is assumed that this result will be used as the "hashcode" parameter in 1563229Spst * calls to other functions in this package. These functions automatically 1573229Spst * adjust the hashcode for the size of each hashtable. 1583229Spst * 1593229Spst * This algorithm probably works best when the hash table size is a prime 1603229Spst * number. 1613229Spst * 1623229Spst * Hopefully, this function is better than the previous one which returned 1633229Spst * the sum of the squares of all the bytes. I'm still open to other 1643229Spst * suggestions for a default hash function. The programmer is more than 1653229Spst * welcome to supply his/her own hash function as that is one of the design 1663229Spst * features of this package. 1673229Spst */ 1683229Spst 1693229Spstunsigned 1703229Spsthash_HashFunction(string, len) 1713229Spst unsigned char *string; 1723229Spst register unsigned len; 1733229Spst{ 1743229Spst register unsigned accum; 1753229Spst 1763229Spst accum = 0; 1773229Spst for (; len > 0; len--) { 1783229Spst accum <<= 1; 1793229Spst accum += (unsigned) (*string++ & 0xFF); 1803229Spst } 1813229Spst return accum; 1823229Spst} 1833229Spst 1843229Spst 1853229Spst 1863229Spst/* 1873229Spst * Returns TRUE if at least one entry for the given key exists; FALSE 1883229Spst * otherwise. 1893229Spst */ 1903229Spst 1913229Spstint 1923229Spsthash_Exists(hashtable, hashcode, compare, key) 1933229Spst hash_tbl *hashtable; 1943229Spst unsigned hashcode; 1953229Spst hash_cmpfp compare; 1963229Spst hash_datum *key; 1973229Spst{ 1983229Spst register hash_member *memberptr; 1993229Spst 2003229Spst memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 2013229Spst while (memberptr) { 2023229Spst if ((*compare) (key, memberptr->data)) { 2033229Spst return TRUE; /* Entry does exist */ 2043229Spst } 2053229Spst memberptr = memberptr->next; 2063229Spst } 2073229Spst return FALSE; /* Entry does not exist */ 2083229Spst} 2093229Spst 2103229Spst 2113229Spst 2123229Spst/* 2133229Spst * Insert the data item "element" into the hash table using "hashcode" 2143229Spst * to determine the bucket number, and "compare" and "key" to determine 2153229Spst * its uniqueness. 2163229Spst * 2173229Spst * If the insertion is successful 0 is returned. If a matching entry 2183229Spst * already exists in the given bucket of the hash table, or some other error 2193229Spst * occurs, -1 is returned and the insertion is not done. 2203229Spst */ 2213229Spst 2223229Spstint 2233229Spsthash_Insert(hashtable, hashcode, compare, key, element) 2243229Spst hash_tbl *hashtable; 2253229Spst unsigned hashcode; 2263229Spst hash_cmpfp compare; 2273229Spst hash_datum *key, *element; 2283229Spst{ 2293229Spst hash_member *temp; 2303229Spst 2313229Spst hashcode %= hashtable->size; 2323229Spst if (hash_Exists(hashtable, hashcode, compare, key)) { 2333229Spst return -1; /* At least one entry already exists */ 2343229Spst } 2353229Spst temp = (hash_member *) malloc(sizeof(hash_member)); 2363229Spst if (!temp) 2373229Spst return -1; /* malloc failed! */ 2383229Spst 2393229Spst temp->data = element; 2403229Spst temp->next = (hashtable->table)[hashcode]; 2413229Spst (hashtable->table)[hashcode] = temp; 2423229Spst return 0; /* Success */ 2433229Spst} 2443229Spst 2453229Spst 2463229Spst 2473229Spst/* 2483229Spst * Delete all data elements which match the given key. If at least one 2493229Spst * element is found and the deletion is successful, 0 is returned. 2503229Spst * If no matching elements can be found in the hash table, -1 is returned. 2513229Spst */ 2523229Spst 2533229Spstint 2543229Spsthash_Delete(hashtable, hashcode, compare, key, free_data) 2553229Spst hash_tbl *hashtable; 2563229Spst unsigned hashcode; 2573229Spst hash_cmpfp compare; 2583229Spst hash_datum *key; 2593229Spst hash_freefp free_data; 2603229Spst{ 2613229Spst hash_member *memberptr, *tempptr; 2623229Spst hash_member *previous = NULL; 2633229Spst int retval; 2643229Spst 2653229Spst retval = -1; 2663229Spst hashcode %= hashtable->size; 2673229Spst 2683229Spst /* 2693229Spst * Delete the first member of the list if it matches. Since this moves 2703229Spst * the second member into the first position we have to keep doing this 2713229Spst * over and over until it no longer matches. 2723229Spst */ 2733229Spst memberptr = (hashtable->table)[hashcode]; 2743229Spst while (memberptr && (*compare) (key, memberptr->data)) { 2753229Spst (hashtable->table)[hashcode] = memberptr->next; 2763229Spst /* 2773229Spst * Stop hashi_FreeMembers() from deleting the whole list! 2783229Spst */ 2793229Spst memberptr->next = NULL; 2803229Spst hashi_FreeMembers(memberptr, free_data); 2813229Spst memberptr = (hashtable->table)[hashcode]; 2823229Spst retval = 0; 2833229Spst } 2843229Spst 2853229Spst /* 2863229Spst * Now traverse the rest of the list 2873229Spst */ 2883229Spst if (memberptr) { 2893229Spst previous = memberptr; 2903229Spst memberptr = memberptr->next; 2913229Spst } 2923229Spst while (memberptr) { 2933229Spst if ((*compare) (key, memberptr->data)) { 2943229Spst tempptr = memberptr; 2953229Spst previous->next = memberptr = memberptr->next; 2963229Spst /* 2973229Spst * Put the brakes on hashi_FreeMembers(). . . . 2983229Spst */ 2993229Spst tempptr->next = NULL; 3003229Spst hashi_FreeMembers(tempptr, free_data); 3013229Spst retval = 0; 3023229Spst } else { 3033229Spst previous = memberptr; 3043229Spst memberptr = memberptr->next; 3053229Spst } 3063229Spst } 3073229Spst return retval; 3083229Spst} 3093229Spst 3103229Spst 3113229Spst 3123229Spst/* 3133229Spst * Locate and return the data entry associated with the given key. 3143229Spst * 3153229Spst * If the data entry is found, a pointer to it is returned. Otherwise, 3163229Spst * NULL is returned. 3173229Spst */ 3183229Spst 3193229Spsthash_datum * 3203229Spsthash_Lookup(hashtable, hashcode, compare, key) 3213229Spst hash_tbl *hashtable; 3223229Spst unsigned hashcode; 3233229Spst hash_cmpfp compare; 3243229Spst hash_datum *key; 3253229Spst{ 3263229Spst hash_member *memberptr; 3273229Spst 3283229Spst memberptr = (hashtable->table)[hashcode % (hashtable->size)]; 3293229Spst while (memberptr) { 3303229Spst if ((*compare) (key, memberptr->data)) { 3313229Spst return (memberptr->data); 3323229Spst } 3333229Spst memberptr = memberptr->next; 3343229Spst } 3353229Spst return NULL; 3363229Spst} 3373229Spst 3383229Spst 3393229Spst 3403229Spst/* 3413229Spst * Return the next available entry in the hashtable for a linear search 3423229Spst */ 3433229Spst 3443229Spsthash_datum * 3453229Spsthash_NextEntry(hashtable) 3463229Spst hash_tbl *hashtable; 3473229Spst{ 3483229Spst register unsigned bucket; 3493229Spst register hash_member *memberptr; 3503229Spst 3513229Spst /* 3523229Spst * First try to pick up where we left off. 3533229Spst */ 3543229Spst memberptr = hashtable->member; 3553229Spst if (memberptr) { 3563229Spst hashtable->member = memberptr->next; /* Set up for next call */ 3573229Spst return memberptr->data; /* Return the data */ 3583229Spst } 3593229Spst /* 3603229Spst * We hit the end of a chain, so look through the array of buckets 3613229Spst * until we find a new chain (non-empty bucket) or run out of buckets. 3623229Spst */ 3633229Spst bucket = hashtable->bucketnum + 1; 3643229Spst while ((bucket < hashtable->size) && 3653229Spst !(memberptr = (hashtable->table)[bucket])) { 3663229Spst bucket++; 3673229Spst } 3683229Spst 3693229Spst /* 3703229Spst * Check to see if we ran out of buckets. 3713229Spst */ 3723229Spst if (bucket >= hashtable->size) { 3733229Spst /* 3743229Spst * Reset to top of table for next call. 3753229Spst */ 3763229Spst hashtable->bucketnum = 0; 3773229Spst hashtable->member = (hashtable->table)[0]; 3783229Spst /* 3793229Spst * But return end-of-table indication to the caller this time. 3803229Spst */ 3813229Spst return NULL; 3823229Spst } 3833229Spst /* 3843229Spst * Must have found a non-empty bucket. 3853229Spst */ 3863229Spst hashtable->bucketnum = bucket; 3873229Spst hashtable->member = memberptr->next; /* Set up for next call */ 3883229Spst return memberptr->data; /* Return the data */ 3893229Spst} 3903229Spst 3913229Spst 3923229Spst 3933229Spst/* 3943229Spst * Return the first entry in a hash table for a linear search 3953229Spst */ 3963229Spst 3973229Spsthash_datum * 3983229Spsthash_FirstEntry(hashtable) 3993229Spst hash_tbl *hashtable; 4003229Spst{ 4013229Spst hashtable->bucketnum = 0; 4023229Spst hashtable->member = (hashtable->table)[0]; 4033229Spst return hash_NextEntry(hashtable); 4043229Spst} 4053229Spst 4063229Spst/* 4073229Spst * Local Variables: 4083229Spst * tab-width: 4 4093229Spst * c-indent-level: 4 4103229Spst * c-argdecl-indent: 4 4113229Spst * c-continued-statement-offset: 4 4123229Spst * c-continued-brace-offset: -4 4133229Spst * c-label-offset: -4 4143229Spst * c-brace-offset: 0 4153229Spst * End: 4163229Spst */ 417