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