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