1 #include <string.h>
2 #include <stdlib.h>
3
4 #include "bin.h"
5 #include "ht.h"
6 #include "mem.h"
7
ht_init(ht * x,unsigned tab,unsigned long (* hash)(const void *,unsigned))8 int ht_init(ht *x, unsigned tab, unsigned long (*hash)(const void *,unsigned))
9 {
10 unsigned tmps;
11
12 x->b = (htbucket **)mem_alloc(tmps = tab * sizeof(htbucket *));
13 if (!x->b) return -1;
14 memzero(x->b, tmps);
15
16 x->ondel = 0;
17 x->onwrite = 0;
18 x->onfail = 0;
19
20 x->s = tab;
21 x->hash = hash;
22 return 1;
23 }
ht_die_fn(ht * x,void * key,unsigned klen,void * data)24 static int ht_die_fn(ht *x, void *key, unsigned klen, void *data)
25 {
26 if (ht_delete(x, key, klen) != 1)
27 return HT_WILLFAIL;
28 return HT_RESTART;
29 }
ht_die(ht * x)30 int ht_die(ht *x)
31 {
32 if (ht_walk(x, ht_die_fn) == -1)
33 return 1;
34 return 0;
35 }
ht_ondelete(ht * x,int (* fn)(void * data))36 int ht_ondelete(ht *x, int (*fn)(void *data))
37 {
38 x->ondel = fn;
39 return 1;
40 }
ht_onwrite(ht * x,void (* fn)(const void *,unsigned,const void *))41 int ht_onwrite(ht *x, void (*fn)(const void *,unsigned,const void *))
42 {
43 x->onwrite = fn;
44 return 1;
45 }
ht_onfail(ht * x,int (* fn)(const void *,unsigned))46 int ht_onfail(ht *x, int (*fn)(const void *, unsigned))
47 {
48 x->onfail = fn;
49 return 1;
50 }
ht_walk(ht * x,int (* fn)(ht * x,void * key,unsigned klen,void * data))51 int ht_walk(ht *x, int (*fn)(ht *x, void *key, unsigned klen, void *data))
52 {
53 unsigned i;
54 union { void *A; const void *B; } qu;
55 htbucket *n;
56 int ret = -1;
57
58 restart_l:
59 for (i = 0; i < x->s; i++) {
60 n = x->b[i];
61 if (n == 0)
62 continue;
63 while (n) {
64 qu.B = n->key;
65 switch (fn(x, qu.A, n->klen, n->data)) {
66 case HT_RESTART: goto restart_l;
67 case HT_FAILNOW: return 0;
68 case HT_SUCCESSNOW: return 1;
69 case HT_TRIPSUCCESS: ret = 1; break;
70 case HT_TRIPFAIL: ret = 0; break;
71 case HT_WILLSUCCESS: if (ret != 0) ret = 1; break;
72 case HT_WILLFAIL: if (ret != 1) ret = 0; break;
73 case HT_NEXT: break;
74 case HT_AGAIN: continue;
75 };
76 n = (htbucket *)n->next;
77 }
78 }
79 return ret;
80 }
81
ht_store_flag(ht * x,const void * key,unsigned klen,void * data,int flag,int i)82 static int ht_store_flag(ht *x, const void *key, unsigned klen,
83 void *data, int flag, int i)
84 {
85 htbucket *n;
86 unsigned long hash;
87 unsigned pos;
88 bin_t kx;
89
90 hash = x->hash(key, klen);
91 n = x->b[pos = hash % x->s];
92 while (n) {
93 if (n->hash == hash && n->klen == klen &&
94 memcmp(key, n->key, klen) == 0) {
95 return 0; /* collision */
96 }
97 n = (htbucket *)n->next;
98 }
99
100 n = (htbucket *)mem_alloc(sizeof(htbucket));
101 if (!n) return -1;
102
103 bin_init(kx);
104 bin_copy(kx, key, klen);
105 n->key = caddr(kx);
106 n->klen = klen;
107 n->hash = x->hash(key, klen);;
108 n->data = data;
109 n->next = (void *)x->b[pos];
110 n->free_data = flag;
111 n->idata = i;
112
113 x->b[pos] = (htbucket *)n;
114 /* write to log (as necessary) */
115 if (x->onwrite)
116 x->onwrite(n->key, n->klen, n->data);
117
118 return 1;
119 }
ht_store(ht * x,const void * key,unsigned klen,void * data)120 int ht_store(ht *x, const void *key, unsigned klen, void *data)
121 {
122 return ht_store_flag(x, key, klen, data, 0, -1);
123 }
ht_storeint(ht * x,const void * key,unsigned klen,int i)124 int ht_storeint(ht *x, const void *key, unsigned klen, int i)
125 {
126 return ht_store_flag(x, key, klen, 0, 0, i);
127 }
ht_storecopy(ht * x,const void * key,unsigned klen,void * data,unsigned dlen)128 int ht_storecopy(ht *x, const void *key, unsigned klen, void *data, unsigned dlen)
129 {
130 int ret;
131 void *copy;
132
133 copy = (void *)mem_alloc(dlen);
134 if (!copy) return -1;
135 memcpy(copy, data, dlen);
136 ret = ht_store_flag(x, key, klen, copy, 1, -1);
137
138 if (ret != 1)
139 mem_free(copy);
140 return ret;
141 }
ht_fetchint(ht * x,const void * key,unsigned klen)142 int ht_fetchint(ht *x, const void *key, unsigned klen)
143 {
144 htbucket *n, *sn;
145 unsigned long hash;
146 int retry = 0;
147
148 hash = x->hash(key, klen);
149 sn = n = x->b[hash % x->s];
150 retry_fetchint_l:
151 while (n) {
152 if (n->hash == hash && n->klen == klen &&
153 memcmp(key, n->key, klen) == 0) {
154 return n->idata;
155 }
156 n = (htbucket *)n->next;
157 }
158 if (x->onfail && !retry) {
159 if (x->onfail(key, klen) == HT_RESTART) {
160 n = sn;
161 retry = 1;
162 goto retry_fetchint_l;
163 }
164 }
165 return -1;
166 }
ht_fetch(ht * x,const void * key,unsigned klen)167 void *ht_fetch(ht *x, const void *key, unsigned klen)
168 {
169 htbucket *n, *sn;
170 unsigned long hash;
171 int retry = 0;
172
173 hash = x->hash(key, klen);
174 sn = n = x->b[hash % x->s];
175 retry_fetch_l:
176 while (n) {
177 if (n->hash == hash && n->klen == klen &&
178 memcmp(key, n->key, klen) == 0) {
179 return n->data;
180 }
181 n = (htbucket *)n->next;
182 }
183 if (x->onfail && !retry) {
184 if (x->onfail(key, klen) == HT_RESTART) {
185 n = sn;
186 retry = 1;
187 goto retry_fetch_l;
188 }
189 }
190 return (void *)0;
191 }
ht_delete(ht * x,const void * key,unsigned klen)192 int ht_delete(ht *x, const void *key, unsigned klen)
193 {
194 htbucket *n, *ln;
195 unsigned long hash;
196 unsigned pos;
197
198 hash = x->hash(key, klen);
199 n = x->b[pos = hash % x->s];
200 ln = 0;
201 while (n) {
202 if (n->hash == hash && n->klen == klen &&
203 memcmp(key, n->key, klen) == 0) {
204 if (ln)
205 ln->next = n->next;
206 else
207 x->b[pos] = n->next;
208 mem_free(n->key);
209 if (n->free_data)
210 mem_free(n->data);
211 mem_free(n);
212 return 1;
213 }
214 ln = n;
215 n = (htbucket *)n->next;
216 }
217 return 0;
218 }
219