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