slabhash.h revision 285206
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 */ 57struct 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 */ 82struct slabhash* slabhash_create(size_t numtables, size_t start_size, 83 size_t maxmem, lruhash_sizefunc_t sizefunc, 84 lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, 85 lruhash_deldatafunc_t deldatafunc, void* arg); 86 87/** 88 * Delete hash table. Entries are all deleted. 89 * @param table: to delete. 90 */ 91void slabhash_delete(struct slabhash* table); 92 93/** 94 * Clear hash table. Entries are all deleted. 95 * @param table: to make empty. 96 */ 97void 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 deletfunc. 111 */ 112void slabhash_insert(struct slabhash* table, hashvalue_t 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 */ 128struct lruhash_entry* slabhash_lookup(struct slabhash* table, 129 hashvalue_t 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 */ 138void slabhash_remove(struct slabhash* table, hashvalue_t 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 */ 146void 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 */ 153size_t slabhash_get_size(struct slabhash* table); 154 155/** 156 * Retrieve slab hash current memory use. 157 * @param table: hash table. 158 * @return memory in use. 159 */ 160size_t slabhash_get_mem(struct slabhash* table); 161 162/** 163 * Get lruhash table for a given hash value 164 * @param table: slabbed hash table. 165 * @param hash: hash value. 166 * @return the lru hash table. 167 */ 168struct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_t hash); 169 170/** 171 * Set markdel function 172 * @param table: slabbed hash table. 173 * @param md: markdel function ptr. 174 */ 175void slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_t md); 176 177/** 178 * Traverse a slabhash. 179 * @param table: slabbed hash table. 180 * @param wr: if true, writelock is obtained, otherwise readlock. 181 * @param func: function to call for every element. 182 * @param arg: user argument to function. 183 */ 184void slabhash_traverse(struct slabhash* table, int wr, 185 void (*func)(struct lruhash_entry*, void*), void* arg); 186 187/* 188 * Count entries in slabhash. 189 * @param table: slabbed hash table; 190 * @return the number of items 191 */ 192size_t count_slabhash_entries(struct slabhash* table); 193 194/* --- test representation --- */ 195/** test structure contains test key */ 196struct slabhash_testkey { 197 /** the key id */ 198 int id; 199 /** the entry */ 200 struct lruhash_entry entry; 201}; 202/** test structure contains test data */ 203struct slabhash_testdata { 204 /** data value */ 205 int data; 206}; 207 208/** test sizefunc for lruhash */ 209size_t test_slabhash_sizefunc(void*, void*); 210/** test comparefunc for lruhash */ 211int test_slabhash_compfunc(void*, void*); 212/** test delkey for lruhash */ 213void test_slabhash_delkey(void*, void*); 214/** test deldata for lruhash */ 215void test_slabhash_deldata(void*, void*); 216/* --- end test representation --- */ 217 218#endif /* UTIL_STORAGE_SLABHASH_H */ 219