Mercurial > repo

comparison src/ploki/hash.c @ 4223:ac0403686959

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<oerjan> rm -rf src/ploki; mv ploki src
author HackBot
date Fri, 20 Dec 2013 22:18:50 +0000
parents
children
comparison
equal deleted inserted replaced
4222:b0f3e267bb1e 4223:ac0403686959
1 #include "config.h"
2 #include "hash.h"
3 #include "main.h"
4 #include "main_opt.h"
5 #include "random.h"
6 #include "xmalloc.h"
7
8 #include <errno.h>
9 #include <stddef.h>
10 #include <stdio.h>
11 #include <assert.h>
12
13 struct h_entry {
14 size_t hash;
15 void *key;
16 void *value;
17 };
18
19 struct h_node {
20 struct h_entry entry;
21 struct h_node *next;
22 };
23
24 enum {MAGIC = 112};
25
26 void h_init(
27 Hash *h,
28 size_t (*hash)(const void *, size_t),
29 int (*cmp)(const void *, const void *),
30 void (*delk)(void *),
31 void (*delv)(void *)
32 ) {
33 size_t i;
34
35 h->entries = 0;
36 h->brk = -1;
37 h->iter = -1;
38 h->iterptr = NULL;
39 h->seed = randval() * (size_t)-1;
40 h->delk = delk;
41 h->delv = delv;
42 assert(hash != NULL);
43 h->hash = hash;
44 assert(cmp != NULL);
45 h->cmp = cmp;
46 h->table = xmalloc(h->newsize = h->size = MAGIC, sizeof *h->table);
47 for (i = 0; i < h->size; ++i) {
48 h->table[i] = NULL;
49 }
50 }
51
52 #define DELKV(p) \
53 do { \
54 if (h->delk) { \
55 h->delk((p)->entry.key); \
56 } \
57 if (h->delv) { \
58 h->delv((p)->entry.value); \
59 } \
60 } while (0)
61
62 void h_end(Hash *h) {
63 size_t size, b;
64
65 if (!h->table)
66 return;
67
68 for (b = 0, size = h->newsize; h->newsize; h->newsize--) {
69 struct h_node *p;
70
71 if ((p = h->table[h->newsize - 1])) {
72 ++b;
73 for (; p; p = h->table[h->newsize - 1]) {
74 h->table[h->newsize - 1] = p->next;
75 DELKV(p);
76 xfree(p);
77 }
78 }
79 }
80 xfree(h->table);
81 h->table = NULL;
82
83 if (Opt.debug & DBG_HASH) {
84 fprintf(stderr, "%s: hash[%lu/%lu/%lu]\n", Prog, (unsigned long)h->entries, (unsigned long)b, (unsigned long)size);
85 }
86 }
87
88 ATTR_PURE
89 static size_t xclip(const Hash *h, const size_t hash_unc) {
90 size_t hash;
91
92 hash = hash_unc % h->size;
93 if (hash > h->brk) {
94 hash = hash_unc % h->newsize;
95 }
96
97 return hash;
98 }
99
100 #if 0
101 ATTR_PURE
102 static size_t xhash(const Hash *h, const void *key) {
103 return xclip(h, h->hash(key, h->seed));
104 }
105 #endif
106
107 #define XRESIZN(h) ((h)->brk + 1u)
108 #define XSTEP(h) do { if (XRESIZN(h)) xstep(h); } while (0)
109
110 static void xstep(Hash *h) {
111 struct h_node *rev = NULL;
112 struct h_node *p;
113 struct h_node *tmp;
114
115 assert(h->table != NULL);
116
117 for (p = h->table[h->brk]; p; p = tmp) {
118 tmp = p->next;
119 p->next = rev;
120 rev = p;
121 }
122 h->table[h->brk--] = NULL;
123
124 if (!XRESIZN(h)) {
125 h->size = h->newsize;
126 }
127
128 for (p = rev; p; p = tmp) {
129 const size_t i = xclip(h, p->entry.hash);
130 tmp = p->next;
131 p->next = h->table[i];
132 h->table[i] = p;
133 }
134 }
135
136 static void xincentries(Hash *h) {
137 h->entries++;
138 if (!(XRESIZN(h)) && h->entries / h->size > 3u) {
139 size_t i;
140 h->table = xrealloc(h->table, h->newsize = h->size * 2u + 1u);
141 for (i = h->size; i < h->newsize; ++i) {
142 h->table[i] = NULL;
143 }
144 h->brk = h->size - 1u;
145 xstep(h);
146 }
147 }
148
149 int h_get(Hash *h, const void *key, void **res) {
150 XSTEP(h);
151 {
152 const size_t hash_unc = h->hash(key, h->seed);
153 const size_t hash = xclip(h, hash_unc);
154 struct h_node *p;
155
156 for (p = h->table[hash]; p; p = p->next) {
157 if (hash_unc == p->entry.hash && h->cmp(p->entry.key, key) == 0) {
158 if (res) {
159 *res = p->entry.value;
160 }
161 return H_OK;
162 }
163 }
164 }
165 return H_NOENT;
166 }
167
168 int h_del(Hash *h, const void *key) {
169 XSTEP(h);
170 {
171 const size_t hash_unc = h->hash(key, h->seed);
172 const size_t hash = xclip(h, hash_unc);
173 struct h_node **p;
174
175 for (p = &h->table[hash]; *p; p = &(*p)->next) {
176 if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
177 struct h_node *tmp = *p;
178 *p = (*p)->next;
179 DELKV(tmp);
180 xfree(tmp);
181 h->entries--;
182 return H_OK;
183 }
184 }
185 }
186
187 return H_NOENT;
188 }
189
190 #if 0
191 void h_push(Hash *h, void *key, void *val) {
192 XSTEP(h);
193 {
194 const size_t hash_unc = h->hash(key, h->seed);
195 const size_t hash = xclip(h, hash_unc);
196 struct h_node *p;
197
198 p = xmalloc(1, sizeof *p);
199 p->entry.hash = hash_unc;
200 p->entry.key = key;
201 p->entry.value = val;
202 p->next = h->table[hash];
203 h->table[hash] = p;
204
205 xincentries(h);
206 }
207 }
208 #endif
209
210 int h_put(Hash *h, void *key, void *val, int replace) {
211 XSTEP(h);
212 {
213 const size_t hash_unc = h->hash(key, h->seed);
214 const size_t hash = xclip(h, hash_unc);
215 struct h_node **p;
216
217 for (p = &h->table[hash]; *p; p = &(*p)->next) {
218 if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
219 if (replace) {
220 DELKV(*p);
221 (*p)->entry.key = key;
222 (*p)->entry.value = val;
223 return H_OK;
224 } else {
225 return H_EXIST;
226 }
227 }
228 }
229
230 *p = xmalloc(1, sizeof **p);
231
232 (*p)->entry.hash = hash_unc;
233 (*p)->entry.key = key;
234 (*p)->entry.value = val;
235 (*p)->next = NULL;
236
237 xincentries(h);
238 }
239
240 return H_OK;
241 }
242
243 void h_reset(Hash *h) {
244 h->iter = -1;
245 h->iterptr = NULL;
246 }
247
248 int h_nextkv(Hash *h, void **k, void **v) {
249 if (h->iterptr) {
250 *k = h->iterptr->entry.key;
251 *v = h->iterptr->entry.value;
252 h->iterptr = h->iterptr->next;
253 return H_OK;
254 }
255
256 for (h->iter++; h->iter < h->newsize; h->iter++) {
257 if ((h->iterptr = h->table[h->iter])) {
258 *k = h->iterptr->entry.key;
259 *v = h->iterptr->entry.value;
260 h->iterptr = h->iterptr->next;
261 return H_OK;
262 }
263 }
264
265 h->iter = -1;
266 return H_NOENT;
267 }
268
269 #if 0
270 size_t (h_entries)(const Hash *h) {
271 return h_entries(h);
272 }
273 #endif