1 /************************************************************************
2 Copyright 1988, 1991 by Carnegie Mellon University
3
4 All Rights Reserved
5
6 Permission to use, copy, modify, and distribute this software and its
7 documentation for any purpose and without fee is hereby granted, provided
8 that the above copyright notice appear in all copies and that both that
9 copyright notice and this permission notice appear in supporting
10 documentation, and that the name of Carnegie Mellon University not be used
11 in advertising or publicity pertaining to distribution of the software
12 without specific, written prior permission.
13
14 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
15 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
16 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
17 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
18 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
19 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
20 SOFTWARE.
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
55 PRIVATE 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
69 hash_tbl *
hash_Init(unsigned tablesize)70 hash_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
98 PRIVATE void
hashi_FreeMembers(hash_member * bucketptr,hash_freefp free_data)99 hashi_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
118 void
hash_Reset(hash_tbl * hashtable,hash_freefp free_data)119 hash_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
155 unsigned
hash_HashFunction(unsigned char * string,unsigned len)156 hash_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
175 int
hash_Exists(hash_tbl * hashtable,unsigned hashcode,hash_cmpfp compare,hash_datum * key)176 hash_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
203 int
hash_Insert(hash_tbl * hashtable,unsigned hashcode,hash_cmpfp compare,hash_datum * key,hash_datum * element)204 hash_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
231 int
hash_Delete(hash_tbl * hashtable,unsigned hashcode,hash_cmpfp compare,hash_datum * key,hash_freefp free_data)232 hash_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
293 hash_datum *
hash_Lookup(hash_tbl * hashtable,unsigned hashcode,hash_cmpfp compare,hash_datum * key)294 hash_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
315 hash_datum *
hash_NextEntry(hash_tbl * hashtable)316 hash_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
367 hash_datum *
hash_FirstEntry(hash_tbl * hashtable)368 hash_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