contrib/unbound/util/storage/slabhash.h

   1 /*
   2  * util/storage/slabhash.h - hashtable consisting of several smaller tables.
   3  *
   4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * Hash table that consists of smaller hash tables.
  40  * It cannot grow, but that gives it the ability to have multiple
  41  * locks. Also this means there are multiple LRU lists.
  42  */
  43
  44 #ifndef UTIL_STORAGE_SLABHASH_H
  45 #define UTIL_STORAGE_SLABHASH_H
  46 #include "util/storage/lruhash.h"
  47
  48 /** default number of slabs */
  49 #define HASH_DEFAULT_SLABS 4
  50
  51 /**
  52  * Hash table formed from several smaller ones.
  53  * This results in a partitioned lruhash table, a 'slashtable'.
  54  * None of the data inside the slabhash may be altered.
  55  * Therefore, no locks are needed to access the structure.
  56  */
  57 struct slabhash {
  58         /** the size of the array - must be power of 2 */
  59         size_t size;
  60         /** size bitmask - uses high bits. */
  61         uint32_t mask;
  62         /** shift right this many bits to get index into array. */
  63         unsigned int shift;
  64         /** lookup array of hash tables */
  65         struct lruhash** array;
  66 };
  67
  68 /**
  69  * Create new slabbed hash table.
  70  * @param numtables: number of hash tables to use, other parameters used to
  71  *      initialize these smaller hashtables.
  72  * @param start_size: size of hashtable array at start, must be power of 2.
  73  * @param maxmem: maximum amount of memory this table is allowed to use.
  74  *      so every table gets maxmem/numtables to use for itself.
  75  * @param sizefunc: calculates memory usage of entries.
  76  * @param compfunc: compares entries, 0 on equality.
  77  * @param delkeyfunc: deletes key.
  78  * @param deldatafunc: deletes data.
  79  * @param arg: user argument that is passed to user function calls.
  80  * @return: new hash table or NULL on malloc failure.
  81  */
  82 struct slabhash* slabhash_create(size_t numtables, size_t start_size,
  83         size_t maxmem, lruhash_sizefunc_type sizefunc,
  84         lruhash_compfunc_type compfunc, lruhash_delkeyfunc_type delkeyfunc,
  85         lruhash_deldatafunc_type deldatafunc, void* arg);
  86
  87 /**
  88  * Delete hash table. Entries are all deleted.
  89  * @param table: to delete.
  90  */
  91 void slabhash_delete(struct slabhash* table);
  92
  93 /**
  94  * Clear hash table. Entries are all deleted.
  95  * @param table: to make empty.
  96  */
  97 void slabhash_clear(struct slabhash* table);
  98
  99 /**
 100  * Insert a new element into the hashtable, uses lruhash_insert.
 101  * If key is already present data pointer in that entry is updated.
 102  *
 103  * @param table: hash table.
 104  * @param hash: hash value. User calculates the hash.
 105  * @param entry: identifies the entry.
 106  *      If key already present, this entry->key is deleted immediately.
 107  *      But entry->data is set to NULL before deletion, and put into
 108  *      the existing entry. The data is then freed.
 109  * @param data: the data.
 110  * @param cb_override: if not NULL overrides the cb_arg for deletefunc.
 111  */
 112 void slabhash_insert(struct slabhash* table, hashvalue_type hash,
 113         struct lruhash_entry* entry, void* data, void* cb_override);
 114
 115 /**
 116  * Lookup an entry in the hashtable. Uses lruhash_lookup.
 117  * At the end of the function you hold a (read/write)lock on the entry.
 118  * The LRU is updated for the entry (if found).
 119  * @param table: hash table.
 120  * @param hash: hash of key.
 121  * @param key: what to look for, compared against entries in overflow chain.
 122  *    the hash value must be set, and must work with compare function.
 123  * @param wr: set to true if you desire a writelock on the entry.
 124  *    with a writelock you can update the data part.
 125  * @return: pointer to the entry or NULL. The entry is locked.
 126  *    The user must unlock the entry when done.
 127  */
 128 struct lruhash_entry* slabhash_lookup(struct slabhash* table,
 129         hashvalue_type hash, void* key, int wr);
 130
 131 /**
 132  * Remove entry from hashtable. Does nothing if not found in hashtable.
 133  * Delfunc is called for the entry. Uses lruhash_remove.
 134  * @param table: hash table.
 135  * @param hash: hash of key.
 136  * @param key: what to look for.
 137  */
 138 void slabhash_remove(struct slabhash* table, hashvalue_type hash, void* key);
 139
 140 /**
 141  * Output debug info to the log as to state of the hash table.
 142  * @param table: hash table.
 143  * @param id: string printed with table to identify the hash table.
 144  * @param extended: set to true to print statistics on overflow bin lengths.
 145  */
 146 void slabhash_status(struct slabhash* table, const char* id, int extended);
 147
 148 /**
 149  * Retrieve slab hash total size.
 150  * @param table: hash table.
 151  * @return size configured as max.
 152  */
 153 size_t slabhash_get_size(struct slabhash* table);
 154
 155 /**
 156  * See if slabhash is of given (size, slabs) configuration.
 157  * @param table: hash table
 158  * @param size: max size to test for
 159  * @param slabs: slab count to test for.
 160  * @return true if equal
 161  */
 162 int slabhash_is_size(struct slabhash* table, size_t size, size_t slabs);
 163
 164 /**
 165  * Retrieve slab hash current memory use.
 166  * @param table: hash table.
 167  * @return memory in use.
 168  */
 169 size_t slabhash_get_mem(struct slabhash* table);
 170
 171 /**
 172  * Get lruhash table for a given hash value
 173  * @param table: slabbed hash table.
 174  * @param hash: hash value.
 175  * @return the lru hash table.
 176  */
 177 struct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_type hash);
 178
 179 /**
 180  * Set markdel function
 181  * @param table: slabbed hash table.
 182  * @param md: markdel function ptr.
 183  */
 184 void slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_type md);
 185
 186 /**
 187  * Traverse a slabhash.
 188  * @param table: slabbed hash table.
 189  * @param wr: if true, writelock is obtained, otherwise readlock.
 190  * @param func: function to call for every element.
 191  * @param arg: user argument to function.
 192  */
 193 void slabhash_traverse(struct slabhash* table, int wr,
 194         void (*func)(struct lruhash_entry*, void*), void* arg);
 195
 196 /*
 197  * Count entries in slabhash.
 198  * @param table: slabbed hash table;
 199  * @return the number of items
 200  */
 201 size_t count_slabhash_entries(struct slabhash* table);
 202
 203 /* --- test representation --- */
 204 /** test structure contains test key */
 205 struct slabhash_testkey {
 206         /** the key id */
 207         int id;
 208         /** the entry */
 209         struct lruhash_entry entry;
 210 };
 211 /** test structure contains test data */
 212 struct slabhash_testdata {
 213         /** data value */
 214         int data;
 215 };
 216
 217 /** test sizefunc for lruhash */
 218 size_t test_slabhash_sizefunc(void*, void*);
 219 /** test comparefunc for lruhash */
 220 int test_slabhash_compfunc(void*, void*);
 221 /** test delkey for lruhash */
 222 void test_slabhash_delkey(void*, void*);
 223 /** test deldata for lruhash */
 224 void test_slabhash_deldata(void*, void*);
 225 /* --- end test representation --- */
 226
 227 #endif /* UTIL_STORAGE_SLABHASH_H */