"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.16.7/lib/isc/ht.c" (4 Sep 2020, 6966 Bytes) of package /linux/misc/dns/bind9/9.16.7/bind-9.16.7.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ht.c" see the Fossies "Dox" file reference documentation.

    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 http://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[FLEXIBLE_ARRAY_MEMBER];
   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
   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
   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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  336 isc_ht_count(isc_ht_t *ht) {
  337     REQUIRE(ISC_HT_VALID(ht));
  338 
  339     return (ht->count);
  340 }