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