Lines Matching refs:ht
1 /* $NetBSD: ht.c,v 1.1 2024/02/18 20:57:49 christos Exp $ */
20 #include <isc/ht.h>
30 #define ISC_HT_VALID(ht) ISC_MAGIC_VALID(ht, ISC_HT_MAGIC)
38 #define TRY_NEXTTABLE(idx, ht) (idx == ht->hindex && rehashing_in_progress(ht))
65 isc_ht_t *ht;
72 isc__ht_find(const isc_ht_t *ht, const unsigned char *key,
75 isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
78 isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
82 rehash_bits(isc_ht_t *ht, size_t newcount);
85 hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits);
87 hashtable_free(isc_ht_t *ht, const uint8_t idx);
89 hashtable_rehash(isc_ht_t *ht, uint32_t newbits);
91 hashtable_rehash_one(isc_ht_t *ht);
93 maybe_rehash(isc_ht_t *ht, size_t newcount);
156 rehashing_in_progress(const isc_ht_t *ht) {
157 return (ht->table[HT_NEXTTABLE(ht->hindex)] != NULL);
161 hashtable_is_overcommited(isc_ht_t *ht) {
162 return (ht->count >= (ht->size[ht->hindex] * HT_OVERCOMMIT));
166 rehash_bits(isc_ht_t *ht, size_t newcount) {
167 uint32_t newbits = ht->hashbits[ht->hindex];
180 hashtable_rehash(isc_ht_t *ht, uint32_t newbits) {
181 uint8_t oldindex = ht->hindex;
182 uint32_t oldbits = ht->hashbits[oldindex];
185 REQUIRE(ht->hashbits[oldindex] >= HT_MIN_BITS);
186 REQUIRE(ht->hashbits[oldindex] <= HT_MAX_BITS);
187 REQUIRE(ht->table[oldindex] != NULL);
190 REQUIRE(ht->hashbits[newindex] == HT_NO_BITS);
191 REQUIRE(ht->table[newindex] == NULL);
195 hashtable_new(ht, newindex, newbits);
197 ht->hindex = newindex;
199 hashtable_rehash_one(ht);
203 hashtable_rehash_one(isc_ht_t *ht) {
204 isc_ht_node_t **newtable = ht->table[ht->hindex];
205 uint32_t oldsize = ht->size[HT_NEXTTABLE(ht->hindex)];
206 isc_ht_node_t **oldtable = ht->table[HT_NEXTTABLE(ht->hindex)];
211 while (ht->hiter < oldsize && oldtable[ht->hiter] == NULL) {
212 ht->hiter++;
216 if (ht->hiter == oldsize) {
217 hashtable_free(ht, HT_NEXTTABLE(ht->hindex));
218 ht->hiter = 0;
223 for (node = oldtable[ht->hiter]; node != NULL; node = nextnode) {
225 ht->hashbits[ht->hindex]);
231 oldtable[ht->hiter] = NULL;
233 ht->hiter++;
237 maybe_rehash(isc_ht_t *ht, size_t newcount) {
238 uint32_t newbits = rehash_bits(ht, newcount);
240 if (ht->hashbits[ht->hindex] < newbits && newbits <= HT_MAX_BITS) {
241 hashtable_rehash(ht, newbits);
246 hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits) {
248 REQUIRE(ht->hashbits[idx] == HT_NO_BITS);
249 REQUIRE(ht->table[idx] == NULL);
253 ht->hashbits[idx] = bits;
254 ht->size[idx] = HASHSIZE(ht->hashbits[idx]);
256 size = ht->size[idx] * sizeof(isc_ht_node_t *);
258 ht->table[idx] = isc_mem_get(ht->mctx, size);
259 memset(ht->table[idx], 0, size);
263 hashtable_free(isc_ht_t *ht, const uint8_t idx) {
264 size_t size = ht->size[idx] * sizeof(isc_ht_node_t *);
266 for (size_t i = 0; i < ht->size[idx]; i++) {
267 isc_ht_node_t *node = ht->table[idx][i];
270 ht->count--;
271 isc_mem_put(ht->mctx, node,
277 isc_mem_put(ht->mctx, ht->table[idx], size);
278 ht->hashbits[idx] = HT_NO_BITS;
279 ht->table[idx] = NULL;
285 isc_ht_t *ht = NULL;
292 ht = isc_mem_get(mctx, sizeof(*ht));
293 *ht = (isc_ht_t){
297 isc_mem_attach(mctx, &ht->mctx);
299 hashtable_new(ht, 0, bits);
301 ht->magic = ISC_HT_MAGIC;
303 *htp = ht;
308 isc_ht_t *ht;
313 ht = *htp;
315 ht->magic = 0;
318 if (ht->table[i] != NULL) {
319 hashtable_free(ht, i);
323 INSIST(ht->count == 0);
325 isc_mem_putanddetach(&ht->mctx, ht, sizeof(*ht));
329 isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
334 hash = hash_32(hashval, ht->hashbits[idx]);
336 node = isc_mem_get(ht->mctx, sizeof(*node) + keysize);
340 .next = ht->table[idx][hash],
346 ht->count++;
347 ht->table[idx][hash] = node;
351 isc_ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
355 REQUIRE(ISC_HT_VALID(ht));
358 if (rehashing_in_progress(ht)) {
360 hashtable_rehash_one(ht);
361 } else if (hashtable_is_overcommited(ht)) {
363 maybe_rehash(ht, ht->count);
366 hashval = isc_hash32(key, keysize, ht->case_sensitive);
368 if (isc__ht_find(ht, key, keysize, hashval, ht->hindex) != NULL) {
372 isc__ht_add(ht, key, keysize, hashval, ht->hindex, value);
378 isc__ht_find(const isc_ht_t *ht, const unsigned char *key,
385 hash = hash_32(hashval, ht->hashbits[findex]);
386 for (isc_ht_node_t *node = ht->table[findex][hash]; node != NULL;
390 ht->case_sensitive))
395 if (TRY_NEXTTABLE(findex, ht)) {
407 isc_ht_find(const isc_ht_t *ht, const unsigned char *key,
412 REQUIRE(ISC_HT_VALID(ht));
416 hashval = isc_hash32(key, keysize, ht->case_sensitive);
418 node = isc__ht_find(ht, key, keysize, hashval, ht->hindex);
430 isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
435 hash = hash_32(hashval, ht->hashbits[idx]);
437 for (isc_ht_node_t *node = ht->table[idx][hash]; node != NULL;
441 ht->case_sensitive))
444 ht->table[idx][hash] = node->next;
448 isc_mem_put(ht->mctx, node,
450 ht->count--;
460 isc_ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize) {
465 REQUIRE(ISC_HT_VALID(ht));
468 if (rehashing_in_progress(ht)) {
470 hashtable_rehash_one(ht);
473 hindex = ht->hindex;
474 hashval = isc_hash32(key, keysize, ht->case_sensitive);
476 result = isc__ht_delete(ht, key, keysize, hashval, hindex);
478 if (result == ISC_R_NOTFOUND && TRY_NEXTTABLE(hindex, ht)) {
490 isc_ht_iter_create(isc_ht_t *ht, isc_ht_iter_t **itp) {
493 REQUIRE(ISC_HT_VALID(ht));
496 it = isc_mem_get(ht->mctx, sizeof(isc_ht_iter_t));
498 .ht = ht,
499 .hindex = ht->hindex,
508 isc_ht_t *ht;
514 ht = it->ht;
515 isc_mem_put(ht->mctx, it, sizeof(*it));
520 isc_ht_t *ht;
524 ht = it->ht;
526 it->hindex = ht->hindex;
534 isc_ht_t *ht = it->ht;
536 while (it->i < ht->size[it->hindex] &&
537 ht->table[it->hindex][it->i] == NULL)
542 if (it->i < ht->size[it->hindex]) {
543 it->cur = ht->table[it->hindex][it->i];
548 if (TRY_NEXTTABLE(it->hindex, ht)) {
578 isc_ht_t *ht;
584 ht = it->ht;
590 dresult = isc__ht_delete(ht, dnode->key, dnode->keysize, dnode->hashval,
618 isc_ht_count(const isc_ht_t *ht) {
619 REQUIRE(ISC_HT_VALID(ht));
621 return (ht->count);
Indexes created Fri Apr 03 00:24:04 UTC 2026