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