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 /** 204 * Retrieves number of items in slabhash and the current max collision level 205 * @param table: slabbed hash table. 206 * @param entries_count: where to save the current number of elements. 207 * @param max_collisions: where to save the current max collisions level. 208 */ 209 void get_slabhash_stats(struct slabhash* table, 210 long long* entries_count, long long* max_collisions); 211 212 /* --- test representation --- */ 213 /** test structure contains test key */ 214 struct slabhash_testkey { 215 /** the key id */ 216 int id; 217 /** the entry */ 218 struct lruhash_entry entry; 219 }; 220 /** test structure contains test data */ 221 struct slabhash_testdata { 222 /** data value */ 223 int data; 224 }; 225 226 /** test sizefunc for lruhash */ 227 size_t test_slabhash_sizefunc(void*, void*); 228 /** test comparefunc for lruhash */ 229 int test_slabhash_compfunc(void*, void*); 230 /** test delkey for lruhash */ 231 void test_slabhash_delkey(void*, void*); 232 /** test deldata for lruhash */ 233 void test_slabhash_deldata(void*, void*); 234 /* --- end test representation --- */ 235 236 #endif /* UTIL_STORAGE_SLABHASH_H */ 237