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 * Update the size of an element in the hashtable, uses 166 * lruhash_update_space_used. 167 * 168 * @param table: hash table. 169 * @param hash: hash value. User calculates the hash. 170 * @param cb_override: if not NULL overrides the cb_arg for deletefunc. 171 * @param diff_size: difference in size to the hash table storage. 172 */ 173 void slabhash_update_space_used(struct slabhash* table, hashvalue_type hash, 174 void* cb_override, int diff_size); 175 176 /** 177 * Retrieve slab hash current memory use. 178 * @param table: hash table. 179 * @return memory in use. 180 */ 181 size_t slabhash_get_mem(struct slabhash* table); 182 183 /** 184 * Get lruhash table for a given hash value 185 * @param table: slabbed hash table. 186 * @param hash: hash value. 187 * @return the lru hash table. 188 */ 189 struct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_type hash); 190 191 /** 192 * Set markdel function 193 * @param table: slabbed hash table. 194 * @param md: markdel function ptr. 195 */ 196 void slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_type md); 197 198 /** 199 * Traverse a slabhash. 200 * @param table: slabbed hash table. 201 * @param wr: if true, writelock is obtained, otherwise readlock. 202 * @param func: function to call for every element. 203 * @param arg: user argument to function. 204 */ 205 void slabhash_traverse(struct slabhash* table, int wr, 206 void (*func)(struct lruhash_entry*, void*), void* arg); 207 208 /* 209 * Count entries in slabhash. 210 * @param table: slabbed hash table; 211 * @return the number of items 212 */ 213 size_t count_slabhash_entries(struct slabhash* table); 214 215 /** 216 * Retrieves number of items in slabhash and the current max collision level 217 * @param table: slabbed hash table. 218 * @param entries_count: where to save the current number of elements. 219 * @param max_collisions: where to save the current max collisions level. 220 */ 221 void get_slabhash_stats(struct slabhash* table, 222 long long* entries_count, long long* max_collisions); 223 224 /* --- test representation --- */ 225 /** test structure contains test key */ 226 struct slabhash_testkey { 227 /** the key id */ 228 int id; 229 /** the entry */ 230 struct lruhash_entry entry; 231 }; 232 /** test structure contains test data */ 233 struct slabhash_testdata { 234 /** data value */ 235 int data; 236 }; 237 238 /** test sizefunc for lruhash */ 239 size_t test_slabhash_sizefunc(void*, void*); 240 /** test comparefunc for lruhash */ 241 int test_slabhash_compfunc(void*, void*); 242 /** test delkey for lruhash */ 243 void test_slabhash_delkey(void*, void*); 244 /** test deldata for lruhash */ 245 void test_slabhash_deldata(void*, void*); 246 /* --- end test representation --- */ 247 248 #endif /* UTIL_STORAGE_SLABHASH_H */ 249