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