Commit | Line | Data |
---|---|---|
e24c98a2 MR |
1 | #ifndef _BLURB_ |
2 | #define _BLURB_ | |
3 | /************************************************************************ | |
4 | Copyright 1988, 1991 by Carnegie Mellon University | |
5 | ||
6 | All Rights Reserved | |
7 | ||
8 | Permission to use, copy, modify, and distribute this software and its | |
9 | documentation for any purpose and without fee is hereby granted, provided | |
10 | that the above copyright notice appear in all copies and that both that | |
11 | copyright notice and this permission notice appear in supporting | |
12 | documentation, and that the name of Carnegie Mellon University not be used | |
13 | in advertising or publicity pertaining to distribution of the software | |
14 | without specific, written prior permission. | |
15 | ||
16 | CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS | |
17 | SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. | |
18 | IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL | |
19 | DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR | |
20 | PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS | |
21 | ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
22 | SOFTWARE. | |
23 | ************************************************************************/ | |
24 | #endif /* _BLURB_ */ | |
25 | ||
26 | ||
27 | #ifndef lint | |
28 | static char rcsid[] = "$Header: /b/source/CVS/othersrc/bootpd/hash.c,v 1.1 1993/08/27 02:10:12 brezak Exp $"; | |
29 | #endif | |
30 | ||
31 | ||
32 | /* | |
33 | * Generalized hash table ADT | |
34 | * | |
35 | * Provides multiple, dynamically-allocated, variable-sized hash tables on | |
36 | * various data and keys. | |
37 | * | |
38 | * This package attempts to follow some of the coding conventions suggested | |
39 | * by Bob Sidebotham and the AFS Clean Code Committee of the | |
40 | * Information Technology Center at Carnegie Mellon. | |
41 | */ | |
42 | ||
43 | ||
44 | #include "hash.h" | |
45 | ||
46 | #define TRUE 1 | |
47 | #define FALSE 0 | |
48 | #define NULL 0 | |
49 | ||
50 | /* | |
51 | * This can be changed to make internal routines visible to debuggers, etc. | |
52 | */ | |
53 | #define PRIVATE static | |
54 | ||
55 | \f | |
56 | ||
57 | /* | |
58 | * Hash table initialization routine. | |
59 | * | |
60 | * This routine creates and intializes a hash table of size "tablesize" | |
61 | * entries. Successful calls return a pointer to the hash table (which must | |
62 | * be passed to other hash routines to identify the hash table). Failed | |
63 | * calls return NULL. | |
64 | */ | |
65 | ||
66 | hash_tbl *hash_Init(tablesize) | |
67 | unsigned tablesize; | |
68 | { | |
69 | register hash_tbl *hashtblptr; | |
70 | register unsigned totalsize; | |
71 | ||
72 | if (tablesize > 0) { | |
73 | totalsize = sizeof(hash_tbl) | |
74 | + sizeof(hash_member *) * (tablesize - 1); | |
75 | hashtblptr = (hash_tbl *) malloc(totalsize); | |
76 | if (hashtblptr) { | |
77 | bzero((char *) hashtblptr, totalsize); | |
78 | hashtblptr->size = tablesize; /* Success! */ | |
79 | hashtblptr->bucketnum = 0; | |
80 | hashtblptr->member = (hashtblptr->table)[0]; | |
81 | } | |
82 | } else { | |
83 | hashtblptr = NULL; /* Disallow zero-length tables */ | |
84 | } | |
85 | return hashtblptr; /* NULL if failure */ | |
86 | } | |
87 | ||
88 | \f | |
89 | ||
90 | /* | |
91 | * Recursively frees an entire linked list of bucket members (used in the open | |
92 | * hashing scheme). Does nothing if the passed pointer is NULL. | |
93 | */ | |
94 | ||
95 | PRIVATE void hashi_FreeMember(bucketptr, free_data) | |
96 | hash_member *bucketptr; | |
97 | void (*free_data)(); | |
98 | { | |
99 | if (bucketptr) { | |
100 | /* | |
101 | * Free next member if necessary | |
102 | */ | |
103 | hashi_FreeMember(bucketptr->next, free_data); | |
104 | (*free_data)(bucketptr->data); | |
105 | free((char *) bucketptr); | |
106 | } | |
107 | } | |
108 | ||
109 | ||
110 | ||
111 | ||
112 | /* | |
113 | * This routine re-initializes the hash table. It frees all the allocated | |
114 | * memory and resets all bucket pointers to NULL. | |
115 | */ | |
116 | ||
117 | void hash_Reset(hashtable, free_data) | |
118 | hash_tbl *hashtable; | |
119 | void (*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_FreeMember(*bucketptr, free_data); | |
127 | *bucketptr++ = NULL; | |
128 | } | |
129 | hashtable->bucketnum = 0; | |
130 | hashtable->member = (hashtable->table)[0]; | |
131 | } | |
132 | ||
133 | \f | |
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(string, len) | |
156 | unsigned char *string; | |
157 | register unsigned len; | |
158 | { | |
159 | register unsigned accum; | |
160 | ||
161 | accum = 0; | |
162 | for (; len > 0; len--) { | |
163 | accum <<= 1; | |
164 | accum += (unsigned) (*string++ & 0xFF); | |
165 | } | |
166 | return accum; | |
167 | } | |
168 | ||
169 | \f | |
170 | ||
171 | /* | |
172 | * Returns TRUE if at least one entry for the given key exists; FALSE | |
173 | * otherwise. | |
174 | */ | |
175 | ||
176 | int hash_Exists(hashtable, hashcode, compare, key) | |
177 | hash_tbl *hashtable; | |
178 | unsigned hashcode; | |
179 | int (*compare)(); | |
180 | hash_datum *key; | |
181 | { | |
182 | register hash_member *memberptr; | |
183 | ||
184 | memberptr = (hashtable->table)[hashcode % (hashtable->size)]; | |
185 | while (memberptr) { | |
186 | if ((*compare)(key, memberptr->data)) { | |
187 | return TRUE; /* Entry does exist */ | |
188 | } | |
189 | memberptr = memberptr->next; | |
190 | } | |
191 | return FALSE; /* Entry does not exist */ | |
192 | } | |
193 | ||
194 | \f | |
195 | ||
196 | /* | |
197 | * Insert the data item "element" into the hash table using "hashcode" | |
198 | * to determine the bucket number, and "compare" and "key" to determine | |
199 | * its uniqueness. | |
200 | * | |
201 | * If the insertion is successful 0 is returned. If a matching entry | |
202 | * already exists in the given bucket of the hash table, or some other error | |
203 | * occurs, -1 is returned and the insertion is not done. | |
204 | */ | |
205 | ||
206 | int hash_Insert(hashtable, hashcode, compare, key, element) | |
207 | hash_tbl *hashtable; | |
208 | unsigned hashcode; | |
209 | int (*compare)(); | |
210 | hash_datum *key, *element; | |
211 | { | |
212 | hash_member *memberptr, *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 | memberptr = (hashtable->table)[hashcode]; | |
219 | temp = (hash_member *) malloc(sizeof(hash_member)); | |
220 | if (temp) { | |
221 | (hashtable->table)[hashcode] = temp; | |
222 | temp->data = element; | |
223 | temp->next = memberptr; | |
224 | return 0; /* Success */ | |
225 | } else { | |
226 | return -1; /* malloc failed! */ | |
227 | } | |
228 | } | |
229 | ||
230 | \f | |
231 | ||
232 | /* | |
233 | * Delete all data elements which match the given key. If at least one | |
234 | * element is found and the deletion is successful, 0 is returned. | |
235 | * If no matching elements can be found in the hash table, -1 is returned. | |
236 | */ | |
237 | ||
238 | int hash_Delete(hashtable, hashcode, compare, key, free_data) | |
239 | hash_tbl *hashtable; | |
240 | unsigned hashcode; | |
241 | int (*compare)(); | |
242 | hash_datum *key; | |
243 | void (*free_data)(); | |
244 | { | |
245 | hash_member *memberptr, *previous, *tempptr; | |
246 | int retval; | |
247 | ||
248 | retval = -1; | |
249 | hashcode %= hashtable->size; | |
250 | ||
251 | /* | |
252 | * Delete the first member of the list if it matches. Since this moves | |
253 | * the second member into the first position we have to keep doing this | |
254 | * over and over until it no longer matches. | |
255 | */ | |
256 | memberptr = (hashtable->table)[hashcode]; | |
257 | while (memberptr && (*compare)(key, memberptr->data)) { | |
258 | (hashtable->table)[hashcode] = memberptr->next; | |
259 | /* | |
260 | * Stop hashi_FreeMember() from recursively deleting the whole list! | |
261 | */ | |
262 | memberptr->next = NULL; | |
263 | hashi_FreeMember(memberptr, free_data); | |
264 | memberptr = (hashtable->table)[hashcode]; | |
265 | retval = 0; | |
266 | } | |
267 | ||
268 | /* | |
269 | * Now traverse the rest of the list | |
270 | */ | |
271 | if (memberptr) { | |
272 | previous = memberptr; | |
273 | memberptr = memberptr->next; | |
274 | } | |
275 | while (memberptr) { | |
276 | if ((*compare)(key, memberptr->data)) { | |
277 | tempptr = memberptr; | |
278 | previous->next = memberptr = memberptr->next; | |
279 | /* | |
280 | * Put the brakes on hashi_FreeMember(). . . . | |
281 | */ | |
282 | tempptr->next = NULL; | |
283 | hashi_FreeMember(tempptr, free_data); | |
284 | retval = 0; | |
285 | } else { | |
286 | previous = memberptr; | |
287 | memberptr = memberptr->next; | |
288 | } | |
289 | } | |
290 | return retval; | |
291 | } | |
292 | ||
293 | \f | |
294 | ||
295 | /* | |
296 | * Locate and return the data entry associated with the given key. | |
297 | * | |
298 | * If the data entry is found, a pointer to it is returned. Otherwise, | |
299 | * NULL is returned. | |
300 | */ | |
301 | ||
302 | hash_datum *hash_Lookup(hashtable, hashcode, compare, key) | |
303 | hash_tbl *hashtable; | |
304 | unsigned hashcode; | |
305 | int (*compare)(); | |
306 | hash_datum *key; | |
307 | { | |
308 | hash_member *memberptr; | |
309 | ||
310 | memberptr = (hashtable->table)[hashcode % (hashtable->size)]; | |
311 | while (memberptr) { | |
312 | if ((*compare)(key, memberptr->data)) { | |
313 | return (memberptr->data); | |
314 | } | |
315 | memberptr = memberptr->next; | |
316 | } | |
317 | return NULL; | |
318 | } | |
319 | ||
320 | \f | |
321 | ||
322 | /* | |
323 | * Return the next available entry in the hashtable for a linear search | |
324 | */ | |
325 | ||
326 | hash_datum *hash_NextEntry(hashtable) | |
327 | hash_tbl *hashtable; | |
328 | { | |
329 | register unsigned bucket; | |
330 | register hash_member *memberptr; | |
331 | ||
332 | /* | |
333 | * First try to pick up where we left off. | |
334 | */ | |
335 | memberptr = hashtable->member; | |
336 | if (memberptr) { | |
337 | hashtable->member = memberptr->next; /* Set up for next call */ | |
338 | return memberptr->data; /* Return the data */ | |
339 | } | |
340 | ||
341 | /* | |
342 | * We hit the end of a chain, so look through the array of buckets | |
343 | * until we find a new chain (non-empty bucket) or run out of buckets. | |
344 | */ | |
345 | bucket = hashtable->bucketnum + 1; | |
346 | while ((bucket < hashtable->size) && | |
347 | !(memberptr = (hashtable->table)[bucket])) { | |
348 | bucket++; | |
349 | } | |
350 | ||
351 | /* | |
352 | * Check to see if we ran out of buckets. | |
353 | */ | |
354 | if (bucket >= hashtable->size) { | |
355 | /* | |
356 | * Reset to top of table for next call. | |
357 | */ | |
358 | hashtable->bucketnum = 0; | |
359 | hashtable->member = (hashtable->table)[0]; | |
360 | /* | |
361 | * But return end-of-table indication to the caller this time. | |
362 | */ | |
363 | return NULL; | |
364 | } | |
365 | ||
366 | /* | |
367 | * Must have found a non-empty bucket. | |
368 | */ | |
369 | hashtable->bucketnum = bucket; | |
370 | hashtable->member = memberptr->next; /* Set up for next call */ | |
371 | return memberptr->data; /* Return the data */ | |
372 | } | |
373 | ||
374 | \f | |
375 | ||
376 | /* | |
377 | * Return the first entry in a hash table for a linear search | |
378 | */ | |
379 | ||
380 | hash_datum *hash_FirstEntry(hashtable) | |
381 | hash_tbl *hashtable; | |
382 | { | |
383 | hashtable->bucketnum = 0; | |
384 | hashtable->member = (hashtable->table)[0]; | |
385 | return hash_NextEntry(hashtable); | |
386 | } |