Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Unbound/src/src/util/storage/slabhash.c
diff options
context:
space:
mode:
authorTobias Markmann <tm@ayena.de>2012-03-12 17:32:02 (GMT)
committerTobias Markmann <tm@ayena.de>2012-03-21 20:41:16 (GMT)
commit2878d950c11526094dc2faeb2caeeb1004f1690d (patch)
tree891760e443f9c90135165bb4ec29c72647179bcf /3rdParty/Unbound/src/src/util/storage/slabhash.c
parent2fa37f2976b933ca0bcf5f85dd1615805776d67d (diff)
downloadswift-contrib-2878d950c11526094dc2faeb2caeeb1004f1690d.zip
swift-contrib-2878d950c11526094dc2faeb2caeeb1004f1690d.tar.bz2
Adding basic unbound support.
Diffstat (limited to '3rdParty/Unbound/src/src/util/storage/slabhash.c')
-rw-r--r--3rdParty/Unbound/src/src/util/storage/slabhash.c219
1 files changed, 219 insertions, 0 deletions
diff --git a/3rdParty/Unbound/src/src/util/storage/slabhash.c b/3rdParty/Unbound/src/src/util/storage/slabhash.c
new file mode 100644
index 0000000..9c0c507
--- /dev/null
+++ b/3rdParty/Unbound/src/src/util/storage/slabhash.c
@@ -0,0 +1,219 @@
+/*
+ * util/storage/slabhash.c - hashtable consisting of several smaller tables.
+ *
+ * Copyright (c) 2007, NLnet Labs. All rights reserved.
+ *
+ * This software is open source.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ *
+ * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ *
+ * Neither the name of the NLNET LABS nor the names of its contributors may
+ * be used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/**
+ * \file
+ *
+ * Implementation of hash table that consists of smaller hash tables.
+ * This results in a partitioned lruhash table.
+ * It cannot grow, but that gives it the ability to have multiple
+ * locks. Also this means there are multiple LRU lists.
+ */
+
+#include "config.h"
+#include "util/storage/slabhash.h"
+
+struct slabhash* slabhash_create(size_t numtables, size_t start_size,
+ size_t maxmem, lruhash_sizefunc_t sizefunc,
+ lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc,
+ lruhash_deldatafunc_t deldatafunc, void* arg)
+{
+ size_t i;
+ struct slabhash* sl = (struct slabhash*)calloc(1,
+ sizeof(struct slabhash));
+ if(!sl) return NULL;
+ sl->size = numtables;
+ log_assert(sl->size > 0);
+ sl->array = (struct lruhash**)calloc(sl->size, sizeof(struct lruhash*));
+ if(!sl->array) {
+ free(sl);
+ return NULL;
+ }
+ sl->mask = (uint32_t)(sl->size - 1);
+ if(sl->mask == 0) {
+ sl->shift = 0;
+ } else {
+ log_assert( (sl->size & sl->mask) == 0
+ /* size must be power of 2 */ );
+ sl->shift = 0;
+ while(!(sl->mask & 0x80000000)) {
+ sl->mask <<= 1;
+ sl->shift ++;
+ }
+ }
+ for(i=0; i<sl->size; i++) {
+ sl->array[i] = lruhash_create(start_size, maxmem / sl->size,
+ sizefunc, compfunc, delkeyfunc, deldatafunc, arg);
+ if(!sl->array[i]) {
+ slabhash_delete(sl);
+ return NULL;
+ }
+ }
+ return sl;
+}
+
+void slabhash_delete(struct slabhash* sl)
+{
+ if(!sl)
+ return;
+ if(sl->array) {
+ size_t i;
+ for(i=0; i<sl->size; i++)
+ lruhash_delete(sl->array[i]);
+ free(sl->array);
+ }
+ free(sl);
+}
+
+void slabhash_clear(struct slabhash* sl)
+{
+ size_t i;
+ if(!sl)
+ return;
+ for(i=0; i<sl->size; i++)
+ lruhash_clear(sl->array[i]);
+}
+
+/** helper routine to calculate the slabhash index */
+static unsigned int
+slab_idx(struct slabhash* sl, hashvalue_t hash)
+{
+ return ((hash & sl->mask) >> sl->shift);
+}
+
+void slabhash_insert(struct slabhash* sl, hashvalue_t hash,
+ struct lruhash_entry* entry, void* data, void* arg)
+{
+ lruhash_insert(sl->array[slab_idx(sl, hash)], hash, entry, data, arg);
+}
+
+struct lruhash_entry* slabhash_lookup(struct slabhash* sl,
+ hashvalue_t hash, void* key, int wr)
+{
+ return lruhash_lookup(sl->array[slab_idx(sl, hash)], hash, key, wr);
+}
+
+void slabhash_remove(struct slabhash* sl, hashvalue_t hash, void* key)
+{
+ lruhash_remove(sl->array[slab_idx(sl, hash)], hash, key);
+}
+
+void slabhash_status(struct slabhash* sl, const char* id, int extended)
+{
+ size_t i;
+ char num[17];
+ log_info("Slabhash %s: %u tables mask=%x shift=%d",
+ id, (unsigned)sl->size, (unsigned)sl->mask, sl->shift);
+ for(i=0; i<sl->size; i++) {
+ snprintf(num, sizeof(num), "table %u", (unsigned)i);
+ lruhash_status(sl->array[i], num, extended);
+ }
+}
+
+size_t slabhash_get_size(struct slabhash* sl)
+{
+ size_t i, total = 0;
+ for(i=0; i<sl->size; i++) {
+ lock_quick_lock(&sl->array[i]->lock);
+ total += sl->array[i]->space_max;
+ lock_quick_unlock(&sl->array[i]->lock);
+ }
+ return total;
+}
+
+size_t slabhash_get_mem(struct slabhash* sl)
+{
+ size_t i, total = sizeof(*sl);
+ total += sizeof(struct lruhash*)*sl->size;
+ for(i=0; i<sl->size; i++) {
+ total += lruhash_get_mem(sl->array[i]);
+ }
+ return total;
+}
+
+struct lruhash* slabhash_gettable(struct slabhash* sl, hashvalue_t hash)
+{
+ return sl->array[slab_idx(sl, hash)];
+}
+
+/* test code, here to avoid linking problems with fptr_wlist */
+/** delete key */
+static void delkey(struct slabhash_testkey* k) {
+ lock_rw_destroy(&k->entry.lock); free(k);}
+/** delete data */
+static void deldata(struct slabhash_testdata* d) {free(d);}
+
+size_t test_slabhash_sizefunc(void* ATTR_UNUSED(key), void* ATTR_UNUSED(data))
+{
+ return sizeof(struct slabhash_testkey) +
+ sizeof(struct slabhash_testdata);
+}
+
+int test_slabhash_compfunc(void* key1, void* key2)
+{
+ struct slabhash_testkey* k1 = (struct slabhash_testkey*)key1;
+ struct slabhash_testkey* k2 = (struct slabhash_testkey*)key2;
+ if(k1->id == k2->id)
+ return 0;
+ if(k1->id > k2->id)
+ return 1;
+ return -1;
+}
+
+void test_slabhash_delkey(void* key, void* ATTR_UNUSED(arg))
+{
+ delkey((struct slabhash_testkey*)key);
+}
+
+void test_slabhash_deldata(void* data, void* ATTR_UNUSED(arg))
+{
+ deldata((struct slabhash_testdata*)data);
+}
+
+void slabhash_setmarkdel(struct slabhash* sl, lruhash_markdelfunc_t md)
+{
+ size_t i;
+ for(i=0; i<sl->size; i++) {
+ lruhash_setmarkdel(sl->array[i], md);
+ }
+}
+
+void slabhash_traverse(struct slabhash* sh, int wr,
+ void (*func)(struct lruhash_entry*, void*), void* arg)
+{
+ size_t i;
+ for(i=0; i<sh->size; i++)
+ lruhash_traverse(sh->array[i], wr, func, arg);
+}