1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
7 *
8 * See the COPYRIGHT file distributed with this work for additional
9 * information regarding copyright ownership.
10 */
11
12 #include <inttypes.h>
13 #include <string.h>
14
15 #include <isc/hash.h>
16 #include <isc/ht.h>
17 #include <isc/magic.h>
18 #include <isc/mem.h>
19 #include <isc/result.h>
20 #include <isc/types.h>
21 #include <isc/util.h>
22
23 typedef struct isc_ht_node isc_ht_node_t;
24
25 #define ISC_HT_MAGIC ISC_MAGIC('H', 'T', 'a', 'b')
26 #define ISC_HT_VALID(ht) ISC_MAGIC_VALID(ht, ISC_HT_MAGIC)
27
28 struct isc_ht_node {
29 void *value;
30 isc_ht_node_t *next;
31 size_t keysize;
32 unsigned char key[];
33 };
34
35 struct isc_ht {
36 unsigned int magic;
37 isc_mem_t *mctx;
38 size_t size;
39 size_t mask;
40 unsigned int count;
41 isc_ht_node_t **table;
42 };
43
44 struct isc_ht_iter {
45 isc_ht_t *ht;
46 size_t i;
47 isc_ht_node_t *cur;
48 };
49
50 isc_result_t
isc_ht_init(isc_ht_t ** htp,isc_mem_t * mctx,uint8_t bits)51 isc_ht_init(isc_ht_t **htp, isc_mem_t *mctx, uint8_t bits) {
52 isc_ht_t *ht = NULL;
53 size_t i;
54
55 REQUIRE(htp != NULL && *htp == NULL);
56 REQUIRE(mctx != NULL);
57 REQUIRE(bits >= 1 && bits <= (sizeof(size_t) * 8 - 1));
58
59 ht = isc_mem_get(mctx, sizeof(struct isc_ht));
60
61 ht->mctx = NULL;
62 isc_mem_attach(mctx, &ht->mctx);
63
64 ht->size = ((size_t)1 << bits);
65 ht->mask = ((size_t)1 << bits) - 1;
66 ht->count = 0;
67
68 ht->table = isc_mem_get(ht->mctx, ht->size * sizeof(isc_ht_node_t *));
69
70 for (i = 0; i < ht->size; i++) {
71 ht->table[i] = NULL;
72 }
73
74 ht->magic = ISC_HT_MAGIC;
75
76 *htp = ht;
77 return (ISC_R_SUCCESS);
78 }
79
80 void
isc_ht_destroy(isc_ht_t ** htp)81 isc_ht_destroy(isc_ht_t **htp) {
82 isc_ht_t *ht;
83 size_t i;
84
85 REQUIRE(htp != NULL);
86
87 ht = *htp;
88 *htp = NULL;
89
90 REQUIRE(ISC_HT_VALID(ht));
91
92 ht->magic = 0;
93
94 for (i = 0; i < ht->size; i++) {
95 isc_ht_node_t *node = ht->table[i];
96 while (node != NULL) {
97 isc_ht_node_t *next = node->next;
98 ht->count--;
99 isc_mem_put(ht->mctx, node,
100 offsetof(isc_ht_node_t, key) +
101 node->keysize);
102 node = next;
103 }
104 }
105
106 INSIST(ht->count == 0);
107
108 isc_mem_put(ht->mctx, ht->table, ht->size * sizeof(isc_ht_node_t *));
109 isc_mem_putanddetach(&ht->mctx, ht, sizeof(struct isc_ht));
110 }
111
112 isc_result_t
isc_ht_add(isc_ht_t * ht,const unsigned char * key,uint32_t keysize,void * value)113 isc_ht_add(isc_ht_t *ht, const unsigned char *key, uint32_t keysize,
114 void *value) {
115 isc_ht_node_t *node;
116 uint32_t hash;
117
118 REQUIRE(ISC_HT_VALID(ht));
119 REQUIRE(key != NULL && keysize > 0);
120
121 hash = isc_hash_function(key, keysize, true);
122 node = ht->table[hash & ht->mask];
123 while (node != NULL) {
124 if (keysize == node->keysize &&
125 memcmp(key, node->key, keysize) == 0) {
126 return (ISC_R_EXISTS);
127 }
128 node = node->next;
129 }
130
131 node = isc_mem_get(ht->mctx, offsetof(isc_ht_node_t, key) + keysize);
132
133 memmove(node->key, key, keysize);
134 node->keysize = keysize;
135 node->next = ht->table[hash & ht->mask];
136 node->value = value;
137
138 ht->count++;
139 ht->table[hash & ht->mask] = node;
140 return (ISC_R_SUCCESS);
141 }
142
143 isc_result_t
isc_ht_find(const isc_ht_t * ht,const unsigned char * key,uint32_t keysize,void ** valuep)144 isc_ht_find(const isc_ht_t *ht, const unsigned char *key, uint32_t keysize,
145 void **valuep) {
146 isc_ht_node_t *node;
147 uint32_t hash;
148
149 REQUIRE(ISC_HT_VALID(ht));
150 REQUIRE(key != NULL && keysize > 0);
151 REQUIRE(valuep == NULL || *valuep == NULL);
152
153 hash = isc_hash_function(key, keysize, true);
154 node = ht->table[hash & ht->mask];
155 while (node != NULL) {
156 if (keysize == node->keysize &&
157 memcmp(key, node->key, keysize) == 0) {
158 if (valuep != NULL) {
159 *valuep = node->value;
160 }
161 return (ISC_R_SUCCESS);
162 }
163 node = node->next;
164 }
165
166 return (ISC_R_NOTFOUND);
167 }
168
169 isc_result_t
isc_ht_delete(isc_ht_t * ht,const unsigned char * key,uint32_t keysize)170 isc_ht_delete(isc_ht_t *ht, const unsigned char *key, uint32_t keysize) {
171 isc_ht_node_t *node, *prev;
172 uint32_t hash;
173
174 REQUIRE(ISC_HT_VALID(ht));
175 REQUIRE(key != NULL && keysize > 0);
176
177 prev = NULL;
178 hash = isc_hash_function(key, keysize, true);
179 node = ht->table[hash & ht->mask];
180 while (node != NULL) {
181 if (keysize == node->keysize &&
182 memcmp(key, node->key, keysize) == 0) {
183 if (prev == NULL) {
184 ht->table[hash & ht->mask] = node->next;
185 } else {
186 prev->next = node->next;
187 }
188 isc_mem_put(ht->mctx, node,
189 offsetof(isc_ht_node_t, key) +
190 node->keysize);
191 ht->count--;
192
193 return (ISC_R_SUCCESS);
194 }
195
196 prev = node;
197 node = node->next;
198 }
199 return (ISC_R_NOTFOUND);
200 }
201
202 isc_result_t
isc_ht_iter_create(isc_ht_t * ht,isc_ht_iter_t ** itp)203 isc_ht_iter_create(isc_ht_t *ht, isc_ht_iter_t **itp) {
204 isc_ht_iter_t *it;
205
206 REQUIRE(ISC_HT_VALID(ht));
207 REQUIRE(itp != NULL && *itp == NULL);
208
209 it = isc_mem_get(ht->mctx, sizeof(isc_ht_iter_t));
210
211 it->ht = ht;
212 it->i = 0;
213 it->cur = NULL;
214
215 *itp = it;
216
217 return (ISC_R_SUCCESS);
218 }
219
220 void
isc_ht_iter_destroy(isc_ht_iter_t ** itp)221 isc_ht_iter_destroy(isc_ht_iter_t **itp) {
222 isc_ht_iter_t *it;
223 isc_ht_t *ht;
224
225 REQUIRE(itp != NULL && *itp != NULL);
226
227 it = *itp;
228 *itp = NULL;
229 ht = it->ht;
230 isc_mem_put(ht->mctx, it, sizeof(isc_ht_iter_t));
231 }
232
233 isc_result_t
isc_ht_iter_first(isc_ht_iter_t * it)234 isc_ht_iter_first(isc_ht_iter_t *it) {
235 REQUIRE(it != NULL);
236
237 it->i = 0;
238 while (it->i < it->ht->size && it->ht->table[it->i] == NULL) {
239 it->i++;
240 }
241
242 if (it->i == it->ht->size) {
243 return (ISC_R_NOMORE);
244 }
245
246 it->cur = it->ht->table[it->i];
247
248 return (ISC_R_SUCCESS);
249 }
250
251 isc_result_t
isc_ht_iter_next(isc_ht_iter_t * it)252 isc_ht_iter_next(isc_ht_iter_t *it) {
253 REQUIRE(it != NULL);
254 REQUIRE(it->cur != NULL);
255
256 it->cur = it->cur->next;
257 if (it->cur == NULL) {
258 do {
259 it->i++;
260 } while (it->i < it->ht->size && it->ht->table[it->i] == NULL);
261 if (it->i >= it->ht->size) {
262 return (ISC_R_NOMORE);
263 }
264 it->cur = it->ht->table[it->i];
265 }
266
267 return (ISC_R_SUCCESS);
268 }
269
270 isc_result_t
isc_ht_iter_delcurrent_next(isc_ht_iter_t * it)271 isc_ht_iter_delcurrent_next(isc_ht_iter_t *it) {
272 isc_result_t result = ISC_R_SUCCESS;
273 isc_ht_node_t *to_delete = NULL;
274 isc_ht_node_t *prev = NULL;
275 isc_ht_node_t *node = NULL;
276 uint32_t hash;
277 isc_ht_t *ht;
278 REQUIRE(it != NULL);
279 REQUIRE(it->cur != NULL);
280 to_delete = it->cur;
281 ht = it->ht;
282
283 it->cur = it->cur->next;
284 if (it->cur == NULL) {
285 do {
286 it->i++;
287 } while (it->i < ht->size && ht->table[it->i] == NULL);
288 if (it->i >= ht->size) {
289 result = ISC_R_NOMORE;
290 } else {
291 it->cur = ht->table[it->i];
292 }
293 }
294
295 hash = isc_hash_function(to_delete->key, to_delete->keysize, true);
296 node = ht->table[hash & ht->mask];
297 while (node != to_delete) {
298 prev = node;
299 node = node->next;
300 INSIST(node != NULL);
301 }
302
303 if (prev == NULL) {
304 ht->table[hash & ht->mask] = node->next;
305 } else {
306 prev->next = node->next;
307 }
308 isc_mem_put(ht->mctx, node,
309 offsetof(isc_ht_node_t, key) + node->keysize);
310 ht->count--;
311
312 return (result);
313 }
314
315 void
isc_ht_iter_current(isc_ht_iter_t * it,void ** valuep)316 isc_ht_iter_current(isc_ht_iter_t *it, void **valuep) {
317 REQUIRE(it != NULL);
318 REQUIRE(it->cur != NULL);
319 REQUIRE(valuep != NULL && *valuep == NULL);
320
321 *valuep = it->cur->value;
322 }
323
324 void
isc_ht_iter_currentkey(isc_ht_iter_t * it,unsigned char ** key,size_t * keysize)325 isc_ht_iter_currentkey(isc_ht_iter_t *it, unsigned char **key,
326 size_t *keysize) {
327 REQUIRE(it != NULL);
328 REQUIRE(it->cur != NULL);
329 REQUIRE(key != NULL && *key == NULL);
330
331 *key = it->cur->key;
332 *keysize = it->cur->keysize;
333 }
334
335 unsigned int
isc_ht_count(isc_ht_t * ht)336 isc_ht_count(isc_ht_t *ht) {
337 REQUIRE(ISC_HT_VALID(ht));
338
339 return (ht->count);
340 }
341