blob: 796ebbee6295d5131fc6cfa815924a0ee6692781 [file] [log] [blame]
bigbiff bigbiff9c754052013-01-09 09:09:08 -05001/* listhash/libtar_hash.c. Generated from hash.c.in by configure. */
2
3/*
4** Copyright 1998-2002 University of Illinois Board of Trustees
5** Copyright 1998-2002 Mark D. Roth
6** All rights reserved.
7**
8** libtar_hash.c - hash table routines
9**
10** Mark D. Roth <roth@uiuc.edu>
11** Campus Information Technologies and Educational Services
12** University of Illinois at Urbana-Champaign
13*/
14
15#include <config.h>
16#include <compat.h>
17
18#include <libtar_listhash.h>
19
20#include <stdio.h>
21#include <errno.h>
22
23#ifdef STDC_HEADERS
24# include <stdlib.h>
25#endif
26
27
28/*
29** libtar_hashptr_reset() - reset a hash pointer
30*/
31void
32libtar_hashptr_reset(libtar_hashptr_t *hp)
33{
34 libtar_listptr_reset(&(hp->node));
35 hp->bucket = -1;
36}
37
38
39/*
40** libtar_hashptr_data() - retrieve the data being pointed to
41*/
42void *
43libtar_hashptr_data(libtar_hashptr_t *hp)
44{
45 return libtar_listptr_data(&(hp->node));
46}
47
48
49/*
50** libtar_str_hashfunc() - default hash function, optimized for
51** 7-bit strings
52*/
53unsigned int
54libtar_str_hashfunc(char *key, unsigned int num_buckets)
55{
56#if 0
57 register unsigned result = 0;
58 register int i;
59
60 if (key == NULL)
61 return 0;
62
63 for (i = 0; *key != '\0' && i < 32; i++)
64 result = result * 33U + *key++;
65
66 return (result % num_buckets);
67#else
68 if (key == NULL)
69 return 0;
70
71 return (key[0] % num_buckets);
72#endif
73}
74
75
76/*
77** libtar_hash_nents() - return number of elements from hash
78*/
79unsigned int
80libtar_hash_nents(libtar_hash_t *h)
81{
82 return h->nents;
83}
84
85
86/*
87** libtar_hash_new() - create a new hash
88*/
89libtar_hash_t *
90libtar_hash_new(int num, libtar_hashfunc_t hashfunc)
91{
92 libtar_hash_t *hash;
93
94 hash = (libtar_hash_t *)calloc(1, sizeof(libtar_hash_t));
95 if (hash == NULL)
96 return NULL;
97 hash->numbuckets = num;
98 if (hashfunc != NULL)
99 hash->hashfunc = hashfunc;
100 else
101 hash->hashfunc = (libtar_hashfunc_t)libtar_str_hashfunc;
102
103 hash->table = (libtar_list_t **)calloc(num, sizeof(libtar_list_t *));
104 if (hash->table == NULL)
105 {
106 free(hash);
107 return NULL;
108 }
109
110 return hash;
111}
112
113
114/*
115** libtar_hash_next() - get next element in hash
116** returns:
117** 1 data found
118** 0 end of list
119*/
120int
121libtar_hash_next(libtar_hash_t *h,
122 libtar_hashptr_t *hp)
123{
124#ifdef DS_DEBUG
125 printf("==> libtar_hash_next(h=0x%lx, hp={%d,0x%lx})\n",
126 h, hp->bucket, hp->node);
127#endif
128
129 if (hp->bucket >= 0 && hp->node != NULL &&
130 libtar_list_next(h->table[hp->bucket], &(hp->node)) != 0)
131 {
132#ifdef DS_DEBUG
133 printf(" libtar_hash_next(): found additional "
134 "data in current bucket (%d), returing 1\n",
135 hp->bucket);
136#endif
137 return 1;
138 }
139
140#ifdef DS_DEBUG
141 printf(" libtar_hash_next(): done with bucket %d\n",
142 hp->bucket);
143#endif
144
145 for (hp->bucket++; hp->bucket < h->numbuckets; hp->bucket++)
146 {
147#ifdef DS_DEBUG
148 printf(" libtar_hash_next(): "
149 "checking bucket %d\n", hp->bucket);
150#endif
151 hp->node = NULL;
152 if (h->table[hp->bucket] != NULL &&
153 libtar_list_next(h->table[hp->bucket],
154 &(hp->node)) != 0)
155 {
156#ifdef DS_DEBUG
157 printf(" libtar_hash_next(): "
158 "found data in bucket %d, returing 1\n",
159 hp->bucket);
160#endif
161 return 1;
162 }
163 }
164
165 if (hp->bucket == h->numbuckets)
166 {
167#ifdef DS_DEBUG
168 printf(" libtar_hash_next(): hash pointer "
169 "wrapped to 0\n");
170#endif
171 hp->bucket = -1;
172 hp->node = NULL;
173 }
174
175#ifdef DS_DEBUG
176 printf("<== libtar_hash_next(): no more data, "
177 "returning 0\n");
178#endif
179 return 0;
180}
181
182
183/*
184** libtar_hash_del() - delete an entry from the hash
185** returns:
186** 0 success
187** -1 (and sets errno) failure
188*/
189int
190libtar_hash_del(libtar_hash_t *h,
191 libtar_hashptr_t *hp)
192{
193 if (hp->bucket < 0
194 || hp->bucket >= h->numbuckets
195 || h->table[hp->bucket] == NULL
196 || hp->node == NULL)
197 {
198 errno = EINVAL;
199 return -1;
200 }
201
202 libtar_list_del(h->table[hp->bucket], &(hp->node));
203 h->nents--;
204 return 0;
205}
206
207
208/*
209** libtar_hash_empty() - empty the hash
210*/
211void
212libtar_hash_empty(libtar_hash_t *h, libtar_freefunc_t freefunc)
213{
214 int i;
215
216 for (i = 0; i < h->numbuckets; i++)
217 if (h->table[i] != NULL)
218 libtar_list_empty(h->table[i], freefunc);
219
220 h->nents = 0;
221}
222
223
224/*
225** libtar_hash_free() - delete all of the nodes in the hash
226*/
227void
228libtar_hash_free(libtar_hash_t *h, libtar_freefunc_t freefunc)
229{
230 int i;
231
232 for (i = 0; i < h->numbuckets; i++)
233 if (h->table[i] != NULL)
234 libtar_list_free(h->table[i], freefunc);
235
236 free(h->table);
237 free(h);
238}
239
240
241/*
242** libtar_hash_search() - iterative search for an element in a hash
243** returns:
244** 1 match found
245** 0 no match
246*/
247int
248libtar_hash_search(libtar_hash_t *h,
249 libtar_hashptr_t *hp, void *data,
250 libtar_matchfunc_t matchfunc)
251{
252 while (libtar_hash_next(h, hp) != 0)
253 if ((*matchfunc)(data, libtar_listptr_data(&(hp->node))) != 0)
254 return 1;
255
256 return 0;
257}
258
259
260/*
261** libtar_hash_getkey() - hash-based search for an element in a hash
262** returns:
263** 1 match found
264** 0 no match
265*/
266int
267libtar_hash_getkey(libtar_hash_t *h,
268 libtar_hashptr_t *hp, void *key,
269 libtar_matchfunc_t matchfunc)
270{
271#ifdef DS_DEBUG
272 printf("==> libtar_hash_getkey(h=0x%lx, hp={%d,0x%lx}, "
273 "key=0x%lx, matchfunc=0x%lx)\n",
274 h, hp->bucket, hp->node, key, matchfunc);
275#endif
276
277 if (hp->bucket == -1)
278 {
279 hp->bucket = (*(h->hashfunc))(key, h->numbuckets);
280#ifdef DS_DEBUG
281 printf(" libtar_hash_getkey(): hp->bucket "
282 "set to %d\n", hp->bucket);
283#endif
284 }
285
286 if (h->table[hp->bucket] == NULL)
287 {
288#ifdef DS_DEBUG
289 printf(" libtar_hash_getkey(): no list "
290 "for bucket %d, returning 0\n", hp->bucket);
291#endif
292 hp->bucket = -1;
293 return 0;
294 }
295
296#ifdef DS_DEBUG
297 printf("<== libtar_hash_getkey(): "
298 "returning libtar_list_search()\n");
299#endif
300 return libtar_list_search(h->table[hp->bucket], &(hp->node),
301 key, matchfunc);
302}
303
304
305/*
306** libtar_hash_add() - add an element to the hash
307** returns:
308** 0 success
309** -1 (and sets errno) failure
310*/
311int
312libtar_hash_add(libtar_hash_t *h, void *data)
313{
314 int bucket, i;
315
316#ifdef DS_DEBUG
317 printf("==> libtar_hash_add(h=0x%lx, data=0x%lx)\n",
318 h, data);
319#endif
320
321 bucket = (*(h->hashfunc))(data, h->numbuckets);
322#ifdef DS_DEBUG
323 printf(" libtar_hash_add(): inserting in bucket %d\n",
324 bucket);
325#endif
326 if (h->table[bucket] == NULL)
327 {
328#ifdef DS_DEBUG
329 printf(" libtar_hash_add(): creating new list\n");
330#endif
331 h->table[bucket] = libtar_list_new(LIST_QUEUE, NULL);
332 }
333
334#ifdef DS_DEBUG
335 printf("<== libtar_hash_add(): "
336 "returning libtar_list_add()\n");
337#endif
338 i = libtar_list_add(h->table[bucket], data);
339 if (i == 0)
340 h->nents++;
341 return i;
342}
343
344