diff options
Diffstat (limited to '')
| -rw-r--r-- | external/unbound/util/storage/slabhash.h | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/external/unbound/util/storage/slabhash.h b/external/unbound/util/storage/slabhash.h new file mode 100644 index 000000000..031a9da0f --- /dev/null +++ b/external/unbound/util/storage/slabhash.h @@ -0,0 +1,218 @@ +/* + * util/storage/slabhash.h - 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 COPYRIGHT + * HOLDER 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 + * + * Hash table that consists of smaller hash tables. + * It cannot grow, but that gives it the ability to have multiple + * locks. Also this means there are multiple LRU lists. + */ + +#ifndef UTIL_STORAGE_SLABHASH_H +#define UTIL_STORAGE_SLABHASH_H +#include "util/storage/lruhash.h" + +/** default number of slabs */ +#define HASH_DEFAULT_SLABS 4 + +/** + * Hash table formed from several smaller ones. + * This results in a partitioned lruhash table, a 'slashtable'. + * None of the data inside the slabhash may be altered. + * Therefore, no locks are needed to access the structure. + */ +struct slabhash { + /** the size of the array - must be power of 2 */ + size_t size; + /** size bitmask - uses high bits. */ + uint32_t mask; + /** shift right this many bits to get index into array. */ + unsigned int shift; + /** lookup array of hash tables */ + struct lruhash** array; +}; + +/** + * Create new slabbed hash table. + * @param numtables: number of hash tables to use, other parameters used to + * initialize these smaller hashtables. + * @param start_size: size of hashtable array at start, must be power of 2. + * @param maxmem: maximum amount of memory this table is allowed to use. + * so every table gets maxmem/numtables to use for itself. + * @param sizefunc: calculates memory usage of entries. + * @param compfunc: compares entries, 0 on equality. + * @param delkeyfunc: deletes key. + * @param deldatafunc: deletes data. + * @param arg: user argument that is passed to user function calls. + * @return: new hash table or NULL on malloc failure. + */ +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); + +/** + * Delete hash table. Entries are all deleted. + * @param table: to delete. + */ +void slabhash_delete(struct slabhash* table); + +/** + * Clear hash table. Entries are all deleted. + * @param table: to make empty. + */ +void slabhash_clear(struct slabhash* table); + +/** + * Insert a new element into the hashtable, uses lruhash_insert. + * If key is already present data pointer in that entry is updated. + * + * @param table: hash table. + * @param hash: hash value. User calculates the hash. + * @param entry: identifies the entry. + * If key already present, this entry->key is deleted immediately. + * But entry->data is set to NULL before deletion, and put into + * the existing entry. The data is then freed. + * @param data: the data. + * @param cb_override: if not NULL overrides the cb_arg for deletfunc. + */ +void slabhash_insert(struct slabhash* table, hashvalue_t hash, + struct lruhash_entry* entry, void* data, void* cb_override); + +/** + * Lookup an entry in the hashtable. Uses lruhash_lookup. + * At the end of the function you hold a (read/write)lock on the entry. + * The LRU is updated for the entry (if found). + * @param table: hash table. + * @param hash: hash of key. + * @param key: what to look for, compared against entries in overflow chain. + * the hash value must be set, and must work with compare function. + * @param wr: set to true if you desire a writelock on the entry. + * with a writelock you can update the data part. + * @return: pointer to the entry or NULL. The entry is locked. + * The user must unlock the entry when done. + */ +struct lruhash_entry* slabhash_lookup(struct slabhash* table, + hashvalue_t hash, void* key, int wr); + +/** + * Remove entry from hashtable. Does nothing if not found in hashtable. + * Delfunc is called for the entry. Uses lruhash_remove. + * @param table: hash table. + * @param hash: hash of key. + * @param key: what to look for. + */ +void slabhash_remove(struct slabhash* table, hashvalue_t hash, void* key); + +/** + * Output debug info to the log as to state of the hash table. + * @param table: hash table. + * @param id: string printed with table to identify the hash table. + * @param extended: set to true to print statistics on overflow bin lengths. + */ +void slabhash_status(struct slabhash* table, const char* id, int extended); + +/** + * Retrieve slab hash total size. + * @param table: hash table. + * @return size configured as max. + */ +size_t slabhash_get_size(struct slabhash* table); + +/** + * Retrieve slab hash current memory use. + * @param table: hash table. + * @return memory in use. + */ +size_t slabhash_get_mem(struct slabhash* table); + +/** + * Get lruhash table for a given hash value + * @param table: slabbed hash table. + * @param hash: hash value. + * @return the lru hash table. + */ +struct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_t hash); + +/** + * Set markdel function + * @param table: slabbed hash table. + * @param md: markdel function ptr. + */ +void slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_t md); + +/** + * Traverse a slabhash. + * @param table: slabbed hash table. + * @param wr: if true, writelock is obtained, otherwise readlock. + * @param func: function to call for every element. + * @param arg: user argument to function. + */ +void slabhash_traverse(struct slabhash* table, int wr, + void (*func)(struct lruhash_entry*, void*), void* arg); + +/* + * Count entries in slabhash. + * @param table: slabbed hash table; + * @return the number of items + */ +size_t count_slabhash_entries(struct slabhash* table); + +/* --- test representation --- */ +/** test structure contains test key */ +struct slabhash_testkey { + /** the key id */ + int id; + /** the entry */ + struct lruhash_entry entry; +}; +/** test structure contains test data */ +struct slabhash_testdata { + /** data value */ + int data; +}; + +/** test sizefunc for lruhash */ +size_t test_slabhash_sizefunc(void*, void*); +/** test comparefunc for lruhash */ +int test_slabhash_compfunc(void*, void*); +/** test delkey for lruhash */ +void test_slabhash_delkey(void*, void*); +/** test deldata for lruhash */ +void test_slabhash_deldata(void*, void*); +/* --- end test representation --- */ + +#endif /* UTIL_STORAGE_SLABHASH_H */ |