slabhash.h revision 238106
1100894Srwatson/* 2189503Srwatson * util/storage/slabhash.h - hashtable consisting of several smaller tables. 3100894Srwatson * 4126097Srwatson * Copyright (c) 2007, NLnet Labs. All rights reserved. 5145147Srwatson * 6172930Srwatson * This software is open source. 7182063Srwatson * 8100894Srwatson * Redistribution and use in source and binary forms, with or without 9100894Srwatson * modification, are permitted provided that the following conditions 10100894Srwatson * are met: 11100894Srwatson * 12100894Srwatson * Redistributions of source code must retain the above copyright notice, 13106392Srwatson * this list of conditions and the following disclaimer. 14106392Srwatson * 15106392Srwatson * Redistributions in binary form must reproduce the above copyright notice, 16106392Srwatson * this list of conditions and the following disclaimer in the documentation 17100894Srwatson * and/or other materials provided with the distribution. 18172930Srwatson * 19172930Srwatson * Neither the name of the NLNET LABS nor the names of its contributors may 20172930Srwatson * be used to endorse or promote products derived from this software without 21189503Srwatson * specific prior written permission. 22189503Srwatson * 23189503Srwatson * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24100894Srwatson * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25100894Srwatson * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26100894Srwatson * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27100894Srwatson * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28100894Srwatson * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29100894Srwatson * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30100894Srwatson * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31100894Srwatson * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32100894Srwatson * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33100894Srwatson * POSSIBILITY OF SUCH DAMAGE. 34100894Srwatson */ 35100894Srwatson 36100894Srwatson/** 37100894Srwatson * \file 38100894Srwatson * 39100894Srwatson * Hash table that consists of smaller hash tables. 40100894Srwatson * It cannot grow, but that gives it the ability to have multiple 41100894Srwatson * locks. Also this means there are multiple LRU lists. 42100894Srwatson */ 43100894Srwatson 44100894Srwatson#ifndef UTIL_STORAGE_SLABHASH_H 45116182Sobrien#define UTIL_STORAGE_SLABHASH_H 46116182Sobrien#include "util/storage/lruhash.h" 47116182Sobrien 48116182Sobrien/** default number of slabs */ 49189503Srwatson#define HASH_DEFAULT_SLABS 4 50100894Srwatson 51101173Srwatson/** 52100894Srwatson * Hash table formed from several smaller ones. 53106856Srwatson * This results in a partitioned lruhash table, a 'slashtable'. 54106468Srwatson * None of the data inside the slabhash may be altered. 55100979Srwatson * Therefore, no locks are needed to access the structure. 56100979Srwatson */ 57102949Sbdestruct slabhash { 58100979Srwatson /** the size of the array - must be power of 2 */ 59100979Srwatson size_t size; 60100979Srwatson /** size bitmask - uses high bits. */ 61116701Srwatson uint32_t mask; 62189503Srwatson /** shift right this many bits to get index into array. */ 63100979Srwatson unsigned int shift; 64100979Srwatson /** lookup array of hash tables */ 65100979Srwatson struct lruhash** array; 66100979Srwatson}; 67100979Srwatson 68100979Srwatson/** 69100894Srwatson * Create new slabbed hash table. 70100979Srwatson * @param numtables: number of hash tables to use, other parameters used to 71100979Srwatson * initialize these smaller hashtables. 72100979Srwatson * @param start_size: size of hashtable array at start, must be power of 2. 73100979Srwatson * @param maxmem: maximum amount of memory this table is allowed to use. 74100979Srwatson * so every table gets maxmem/numtables to use for itself. 75163606Srwatson * @param sizefunc: calculates memory usage of entries. 76121361Srwatson * @param compfunc: compares entries, 0 on equality. 77165469Srwatson * @param delkeyfunc: deletes key. 78100979Srwatson * @param deldatafunc: deletes data. 79122524Srwatson * @param arg: user argument that is passed to user function calls. 80122524Srwatson * @return: new hash table or NULL on malloc failure. 81104521Srwatson */ 82122524Srwatsonstruct slabhash* slabhash_create(size_t numtables, size_t start_size, 83104521Srwatson size_t maxmem, lruhash_sizefunc_t sizefunc, 84122524Srwatson lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, 85191731Srwatson lruhash_deldatafunc_t deldatafunc, void* arg); 86122524Srwatson 87104521Srwatson/** 88104521Srwatson * Delete hash table. Entries are all deleted. 89104521Srwatson * @param table: to delete. 90172930Srwatson */ 91105694Srwatsonvoid slabhash_delete(struct slabhash* table); 92105694Srwatson 93182063Srwatson/** 94182063Srwatson * Clear hash table. Entries are all deleted. 95182063Srwatson * @param table: to make empty. 96182063Srwatson */ 97105694Srwatsonvoid slabhash_clear(struct slabhash* table); 98105694Srwatson 99105694Srwatson/** 100122524Srwatson * Insert a new element into the hashtable, uses lruhash_insert. 101104521Srwatson * If key is already present data pointer in that entry is updated. 102104521Srwatson * 103191731Srwatson * @param table: hash table. 104122524Srwatson * @param hash: hash value. User calculates the hash. 105104521Srwatson * @param entry: identifies the entry. 106104521Srwatson * If key already present, this entry->key is deleted immediately. 107104521Srwatson * But entry->data is set to NULL before deletion, and put into 108172930Srwatson * the existing entry. The data is then freed. 109105694Srwatson * @param data: the data. 110105694Srwatson * @param cb_override: if not NULL overrides the cb_arg for deletfunc. 111182063Srwatson */ 112182063Srwatsonvoid slabhash_insert(struct slabhash* table, hashvalue_t hash, 113182063Srwatson struct lruhash_entry* entry, void* data, void* cb_override); 114182063Srwatson 115105694Srwatson/** 116105694Srwatson * Lookup an entry in the hashtable. Uses lruhash_lookup. 117184407Srwatson * At the end of the function you hold a (read/write)lock on the entry. 118184407Srwatson * The LRU is updated for the entry (if found). 119184407Srwatson * @param table: hash table. 120184407Srwatson * @param hash: hash of key. 121184407Srwatson * @param key: what to look for, compared against entries in overflow chain. 122184407Srwatson * the hash value must be set, and must work with compare function. 123184407Srwatson * @param wr: set to true if you desire a writelock on the entry. 124184407Srwatson * with a writelock you can update the data part. 125184407Srwatson * @return: pointer to the entry or NULL. The entry is locked. 126184407Srwatson * The user must unlock the entry when done. 127184407Srwatson */ 128105694Srwatsonstruct lruhash_entry* slabhash_lookup(struct slabhash* table, 129104522Srwatson hashvalue_t hash, void* key, int wr); 130191731Srwatson 131104522Srwatson/** 132104522Srwatson * Remove entry from hashtable. Does nothing if not found in hashtable. 133104522Srwatson * Delfunc is called for the entry. Uses lruhash_remove. 134165425Srwatson * @param table: hash table. 135165425Srwatson * @param hash: hash of key. 136104522Srwatson * @param key: what to look for. 137104521Srwatson */ 138184407Srwatsonvoid slabhash_remove(struct slabhash* table, hashvalue_t hash, void* key); 139104522Srwatson 140104522Srwatson/** 141191731Srwatson * Output debug info to the log as to state of the hash table. 142104522Srwatson * @param table: hash table. 143104522Srwatson * @param id: string printed with table to identify the hash table. 144104522Srwatson * @param extended: set to true to print statistics on overflow bin lengths. 145104522Srwatson */ 146104522Srwatsonvoid slabhash_status(struct slabhash* table, const char* id, int extended); 147104522Srwatson 148104522Srwatson/** 149184407Srwatson * Retrieve slab hash total size. 150104522Srwatson * @param table: hash table. 151104522Srwatson * @return size configured as max. 152191731Srwatson */ 153104522Srwatsonsize_t slabhash_get_size(struct slabhash* table); 154104522Srwatson 155184407Srwatson/** 156184407Srwatson * Retrieve slab hash current memory use. 157184407Srwatson * @param table: hash table. 158172957Srwatson * @return memory in use. 159184407Srwatson */ 160172957Srwatsonsize_t slabhash_get_mem(struct slabhash* table); 161191731Srwatson 162184407Srwatson/** 163184407Srwatson * Get lruhash table for a given hash value 164172957Srwatson * @param table: slabbed hash table. 165172957Srwatson * @param hash: hash value. 166184407Srwatson * @return the lru hash table. 167184407Srwatson */ 168184407Srwatsonstruct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_t hash); 169184407Srwatson 170184407Srwatson/** 171191731Srwatson * Set markdel function 172184407Srwatson * @param table: slabbed hash table. 173184407Srwatson * @param md: markdel function ptr. 174184407Srwatson */ 175184407Srwatsonvoid slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_t md); 176104522Srwatson 177104522Srwatson/** 178165425Srwatson * Traverse a slabhash. 179165425Srwatson * @param table: slabbed hash table. 180104522Srwatson * @param wr: if true, writelock is obtained, otherwise readlock. 181104522Srwatson * @param func: function to call for every element. 182172930Srwatson * @param arg: user argument to function. 183104522Srwatson */ 184104522Srwatsonvoid slabhash_traverse(struct slabhash* table, int wr, 185191731Srwatson void (*func)(struct lruhash_entry*, void*), void* arg); 186191731Srwatson 187104522Srwatson/* --- test representation --- */ 188104522Srwatson/** test structure contains test key */ 189100979Srwatsonstruct slabhash_testkey { 190100979Srwatson /** the key id */ 191100979Srwatson int id; 192100979Srwatson /** the entry */ 193100979Srwatson struct lruhash_entry entry; 194121361Srwatson}; 195172930Srwatson/** test structure contains test data */ 196100979Srwatsonstruct slabhash_testdata { 197100979Srwatson /** data value */ 198191731Srwatson int data; 199100979Srwatson}; 200100979Srwatson 201189503Srwatson/** test sizefunc for lruhash */ 202189503Srwatsonsize_t test_slabhash_sizefunc(void*, void*); 203189503Srwatson/** test comparefunc for lruhash */ 204100979Srwatsonint test_slabhash_compfunc(void*, void*); 205172930Srwatson/** test delkey for lruhash */ 206100979Srwatsonvoid test_slabhash_delkey(void*, void*); 207100979Srwatson/** test deldata for lruhash */ 208100979Srwatsonvoid test_slabhash_deldata(void*, void*); 209191731Srwatson/* --- end test representation --- */ 210189503Srwatson 211100979Srwatson#endif /* UTIL_STORAGE_SLABHASH_H */ 212100979Srwatson