1 /*
2 ** $Id: table.c 135 2006-03-15 07:23:41Z boote $
3 */
4 /************************************************************************
5 * *
6 * Copyright (C) 2002 *
7 * Internet2 *
8 * All Rights Reserved *
9 * *
10 ************************************************************************/
11 /*
12 ** File: table.c
13 **
14 ** Author: Anatoly Karp
15 ** Jeff W. Boote
16 **
17 ** Date: Thu Apr 19 13:47:17 EDT 2002
18 **
19 ** Description: Simple hash table - implementation.
20 */
21 #include "table.h"
22
23 #include <stdlib.h>
24 #include <limits.h>
25 #include <stddef.h>
26 #include <assert.h>
27 #include <stdio.h>
28 #include <errno.h>
29 #include <string.h>
30
31 /*
32 * this type is used to hold a single key/value pair.
33 */
34 typedef struct I2BindingRec I2BindingRec, *I2Binding;
35 struct I2BindingRec{
36 I2Datum key;
37 I2Datum value;
38 I2Boolean delete;
39 I2Binding next;
40 };
41
42 /* Types used to define a hash table. */
43 struct I2Table {
44 I2ErrHandle eh;
45 I2TableDataSizeT size;
46 int hint;
47 I2HashCmpFunc cmp;
48 I2HashFunc hash;
49 I2TableDataSizeT length;
50 I2Binding *buckets;
51 I2Binding freelist;
52 I2Binding *alist;
53 int num_alist;
54 int size_alist;
55 I2Boolean in_iterate;
56 I2TableDataSizeT delete_nodes;
57 };
58
59 /* Static functions (used by default unless specified). */
60 static int
cmpatom(I2Datum x,I2Datum y)61 cmpatom(
62 I2Datum x,
63 I2Datum y
64 )
65 {
66 /* return x != y; */
67 return (!(x.dsize == y.dsize) ||
68 memcmp(x.dptr, y.dptr, x.dsize));
69 }
70
71 static uint32_t
hashatom(I2Datum key)72 hashatom(
73 I2Datum key
74 )
75 {
76 unsigned long i;
77 unsigned char *ptr = (unsigned char *)(key.dptr);
78 unsigned long ret = 0;
79 for (i = 0; i < key.dsize; i++, ptr++)
80 ret += *ptr;
81 return ret;
82 }
83
84 static int
alloc_freelist(I2Table table)85 alloc_freelist(
86 I2Table table
87 )
88 {
89 I2Binding t;
90 int i;
91
92 if(table->num_alist <= table->size_alist){
93 I2Binding *alist;
94 if(!(alist = realloc(table->alist,sizeof(I2Binding)*
95 (table->size_alist+table->hint) ))){
96 I2ErrLogP(table->eh,errno,"WARNING: realloc(): %M");
97 return -1;
98 }
99 table->size_alist += table->hint;
100 table->alist = alist;
101 }
102
103 if(!(t = calloc(sizeof(I2BindingRec),table->hint))){
104 I2ErrLogP(table->eh,errno,"WARNING: calloc(): %M");
105 return -1;
106 }
107
108 table->alist[table->num_alist++] = t;
109
110 for(i=0;i<table->hint;i++){
111 t[i].next = table->freelist;
112 table->freelist = &t[i];
113 }
114
115 return 0;
116 }
117
118 static I2Binding
alloc_binding(I2Table table)119 alloc_binding(
120 I2Table table
121 )
122 {
123 I2Binding node;
124
125 if(!table->freelist && (alloc_freelist(table) != 0)){
126 return NULL;
127 }
128
129 node = table->freelist;
130 table->freelist = node->next;
131 node->next = NULL;
132
133 return node;
134 }
135
136 static void
free_binding(I2Table table,I2Binding node)137 free_binding(
138 I2Table table,
139 I2Binding node
140 )
141 {
142 node->next = table->freelist;
143 table->freelist = node;
144
145 return;
146 }
147
148 I2TableDataSizeT
I2HashNumEntries(I2Table table)149 I2HashNumEntries(
150 I2Table table
151 )
152 {
153 if(table->delete_nodes > table->length){
154 I2ErrLogP(table->eh,0,
155 "WARNING: I2HashNumEntries - table invalid!");
156 return 0;
157 }
158
159 return table->length - table->delete_nodes;
160 }
161
162 I2Table
I2HashInit(I2ErrHandle eh,int hint,int cmp (I2Datum x,I2Datum y),uint32_t hash (I2Datum key))163 I2HashInit(
164 I2ErrHandle eh,
165 int hint,
166 int cmp(I2Datum x, I2Datum y),
167 uint32_t hash(I2Datum key)
168 )
169 {
170 I2Table table;
171 int i;
172 int primes[] = {31, 67, 127, 251, 509, 1021, 2053, 4093, 8191,
173 16381, 32771, 65521};
174
175 for(i=I2Number(primes)-1;
176 (i>0) && (primes[i] > hint);i--);
177
178 table = (void *)calloc(1,sizeof(*table));
179 if(!table){
180 I2ErrLogP(eh, ENOMEM, "FATAL: calloc for hash table");
181 return NULL;
182 }
183 table->buckets = malloc(primes[i]*sizeof(table->buckets[0]));
184 if(!table->buckets){
185 I2ErrLogP(eh, ENOMEM, "FATAL: malloc for hash buckets");
186 goto error;
187 }
188 memset(table->buckets,0,primes[i]*sizeof(table->buckets[0]));
189
190 table->eh = eh;
191 table->size = primes[i];
192 table->hint = (hint) ? hint : primes[i];
193 table->cmp = cmp ? cmp : cmpatom;
194 table->hash = hash ? hash : hashatom;
195 table->length = 0;
196
197 table->freelist = NULL;
198 table->alist = NULL;
199 table->num_alist = table->size_alist = 0;
200
201 table->in_iterate=False;
202 table->delete_nodes=0;
203
204 if(alloc_freelist(table) != 0){
205 goto error;
206 }
207
208 return table;
209
210 error:
211 if(table->buckets){
212 free(table->buckets);
213 }
214
215 if(table->size_alist){
216 for(i=0;i<table->num_alist;i++){
217 free(table->alist[i]);
218 }
219 free(table->alist);
220 }
221 free(table);
222
223 return NULL;
224 }
225
226 void
I2HashClose(I2Table table)227 I2HashClose(
228 I2Table table
229 )
230 {
231 int i;
232 assert(table);
233 assert(!table->in_iterate);
234
235 free(table->buckets);
236
237 if(table->size_alist){
238 for(i=0;i<table->num_alist;i++){
239 free(table->alist[i]);
240 }
241 free(table->alist);
242 }
243
244 free(table);
245
246 return;
247 }
248
249 int
I2HashDelete(I2Table table,I2Datum key)250 I2HashDelete(
251 I2Table table,
252 I2Datum key
253 )
254 {
255 I2TableDataSizeT i;
256 I2Binding *p;
257 I2Binding q;
258
259 assert(table);
260
261 /* Search table for key. */
262 i = (*table->hash)(key)%table->size;
263 for (p = &table->buckets[i]; *p; p = &(*p)->next){
264 if (!(*p)->delete && ((*table->cmp)(key, (*p)->key) == 0)){
265 break;
266 }
267 }
268
269 if (!*p) /* not found */
270 return -1;
271
272 if(table->in_iterate){
273 (*p)->delete = True;
274 table->delete_nodes++;
275 return 0;
276 }
277
278 q = *p;
279 *p = q->next;
280 free_binding(table,q);
281 table->length--;
282
283 return 0;
284 }
285
286 /*
287 ** Save a key/value in the hash. Return 0 on success, and -1 on failure.
288 */
289 int
I2HashStore(I2Table table,I2Datum key,I2Datum value)290 I2HashStore(
291 I2Table table,
292 I2Datum key,
293 I2Datum value
294 )
295 {
296 I2TableDataSizeT i;
297 I2Binding q;
298
299 assert(table);
300
301 assert(!table->in_iterate);
302
303 i=0;
304 i=~i;
305 if(table->size == i){
306 I2ErrLogP(table->eh,0,"FATAL: hash table full");
307 return -1;
308 }
309
310 /* Search table for key. */
311 i = (*table->hash)(key)%table->size;
312 for (q = table->buckets[i]; q; q = q->next){
313 if ((*table->cmp)(key, q->key) == 0)
314 break;
315 }
316
317 if (q == NULL){ /* not found */
318 q = alloc_binding(table);
319 if (q == NULL){
320 return -1;
321 }
322 q->key = key;
323 q->delete = False;
324 q->next = table->buckets[i];
325 table->buckets[i] = q;
326 table->length++;
327 }
328 q->value = value;
329 return 0;
330 }
331
332 /*
333 ** Look up the value corresponding to a given key. Returns
334 ** the value datum on success, or NULL on failure.
335 */
336 I2Boolean
I2HashFetch(I2Table table,I2Datum key,I2Datum * ret)337 I2HashFetch(
338 I2Table table,
339 I2Datum key,
340 I2Datum *ret
341 )
342 {
343 I2TableDataSizeT i;
344 I2Binding p;
345
346 assert(table);
347 assert(ret);
348
349 /* Search table for key. */
350 i = (*table->hash)(key)%table->size;
351
352 for (p = table->buckets[i]; p; p = p->next){
353 if (!p->delete && ((*table->cmp)(key, p->key) == 0)){
354 break;
355 }
356 }
357
358 if(!p)
359 return False;
360
361 *ret = p->value;
362 return True;
363 }
364
365 void
I2HashIterate(I2Table table,I2HashIterateFunc ifunc,void * app_data)366 I2HashIterate(
367 I2Table table,
368 I2HashIterateFunc ifunc,
369 void *app_data
370 )
371 {
372 I2TableDataSizeT i;
373 I2Binding *p;
374 I2Binding q;
375
376 assert(table);
377 assert(!table->in_iterate);
378 assert(ifunc);
379
380 table->in_iterate = True;
381 table->delete_nodes = 0;
382 for (i = 0; i < table->size; i++){
383 for (q = table->buckets[i]; q; q = q->next){
384 if(q->delete){
385 continue;
386 }
387 if(!((*ifunc)(q->key,q->value,app_data)))
388 goto done_iterate;
389 }
390 }
391 done_iterate:
392
393 /*
394 * Now delete any nodes that were removed during the iterate.
395 */
396 for (i = 0;((i < table->size)&&(table->delete_nodes > 0)); i++){
397 p = &table->buckets[i];
398 while(*p && (table->delete_nodes > 0)){
399 if((*p)->delete){
400 q = *p;
401 *p = q->next;
402 free_binding(table,q);
403 table->delete_nodes--;
404 table->length--;
405 }
406 else{
407 p = &(*p)->next;
408 }
409 }
410 }
411 table->in_iterate = False;
412 }
413
414 void
I2HashClean(I2Table table)415 I2HashClean(
416 I2Table table
417 )
418 {
419 I2TableDataSizeT i;
420 I2Binding *p;
421 I2Binding q;
422
423 assert(table);
424 assert(!table->in_iterate);
425
426 for (i = 0;((i < table->size) && (table->length > 0)); i++){
427 p = &table->buckets[i];
428 while(*p){
429 q = *p;
430 *p = q->next;
431 free_binding(table,q);
432 table->length--;
433 }
434 }
435
436 assert(table->length == 0);
437
438 return;
439 }
440