1238106Sdes/* 2238106Sdes * util/storage/slabhash.h - hashtable consisting of several smaller tables. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * Hash table that consists of smaller hash tables. 40238106Sdes * It cannot grow, but that gives it the ability to have multiple 41238106Sdes * locks. Also this means there are multiple LRU lists. 42238106Sdes */ 43238106Sdes 44238106Sdes#ifndef UTIL_STORAGE_SLABHASH_H 45238106Sdes#define UTIL_STORAGE_SLABHASH_H 46238106Sdes#include "util/storage/lruhash.h" 47238106Sdes 48238106Sdes/** default number of slabs */ 49238106Sdes#define HASH_DEFAULT_SLABS 4 50238106Sdes 51238106Sdes/** 52238106Sdes * Hash table formed from several smaller ones. 53238106Sdes * This results in a partitioned lruhash table, a 'slashtable'. 54238106Sdes * None of the data inside the slabhash may be altered. 55238106Sdes * Therefore, no locks are needed to access the structure. 56238106Sdes */ 57238106Sdesstruct slabhash { 58238106Sdes /** the size of the array - must be power of 2 */ 59238106Sdes size_t size; 60238106Sdes /** size bitmask - uses high bits. */ 61238106Sdes uint32_t mask; 62238106Sdes /** shift right this many bits to get index into array. */ 63238106Sdes unsigned int shift; 64238106Sdes /** lookup array of hash tables */ 65238106Sdes struct lruhash** array; 66238106Sdes}; 67238106Sdes 68238106Sdes/** 69238106Sdes * Create new slabbed hash table. 70238106Sdes * @param numtables: number of hash tables to use, other parameters used to 71238106Sdes * initialize these smaller hashtables. 72238106Sdes * @param start_size: size of hashtable array at start, must be power of 2. 73238106Sdes * @param maxmem: maximum amount of memory this table is allowed to use. 74238106Sdes * so every table gets maxmem/numtables to use for itself. 75238106Sdes * @param sizefunc: calculates memory usage of entries. 76238106Sdes * @param compfunc: compares entries, 0 on equality. 77238106Sdes * @param delkeyfunc: deletes key. 78238106Sdes * @param deldatafunc: deletes data. 79238106Sdes * @param arg: user argument that is passed to user function calls. 80238106Sdes * @return: new hash table or NULL on malloc failure. 81238106Sdes */ 82238106Sdesstruct slabhash* slabhash_create(size_t numtables, size_t start_size, 83238106Sdes size_t maxmem, lruhash_sizefunc_t sizefunc, 84238106Sdes lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc, 85238106Sdes lruhash_deldatafunc_t deldatafunc, void* arg); 86238106Sdes 87238106Sdes/** 88238106Sdes * Delete hash table. Entries are all deleted. 89238106Sdes * @param table: to delete. 90238106Sdes */ 91238106Sdesvoid slabhash_delete(struct slabhash* table); 92238106Sdes 93238106Sdes/** 94238106Sdes * Clear hash table. Entries are all deleted. 95238106Sdes * @param table: to make empty. 96238106Sdes */ 97238106Sdesvoid slabhash_clear(struct slabhash* table); 98238106Sdes 99238106Sdes/** 100238106Sdes * Insert a new element into the hashtable, uses lruhash_insert. 101238106Sdes * If key is already present data pointer in that entry is updated. 102238106Sdes * 103238106Sdes * @param table: hash table. 104238106Sdes * @param hash: hash value. User calculates the hash. 105238106Sdes * @param entry: identifies the entry. 106238106Sdes * If key already present, this entry->key is deleted immediately. 107238106Sdes * But entry->data is set to NULL before deletion, and put into 108238106Sdes * the existing entry. The data is then freed. 109238106Sdes * @param data: the data. 110238106Sdes * @param cb_override: if not NULL overrides the cb_arg for deletfunc. 111238106Sdes */ 112238106Sdesvoid slabhash_insert(struct slabhash* table, hashvalue_t hash, 113238106Sdes struct lruhash_entry* entry, void* data, void* cb_override); 114238106Sdes 115238106Sdes/** 116238106Sdes * Lookup an entry in the hashtable. Uses lruhash_lookup. 117238106Sdes * At the end of the function you hold a (read/write)lock on the entry. 118238106Sdes * The LRU is updated for the entry (if found). 119238106Sdes * @param table: hash table. 120238106Sdes * @param hash: hash of key. 121238106Sdes * @param key: what to look for, compared against entries in overflow chain. 122238106Sdes * the hash value must be set, and must work with compare function. 123238106Sdes * @param wr: set to true if you desire a writelock on the entry. 124238106Sdes * with a writelock you can update the data part. 125238106Sdes * @return: pointer to the entry or NULL. The entry is locked. 126238106Sdes * The user must unlock the entry when done. 127238106Sdes */ 128238106Sdesstruct lruhash_entry* slabhash_lookup(struct slabhash* table, 129238106Sdes hashvalue_t hash, void* key, int wr); 130238106Sdes 131238106Sdes/** 132238106Sdes * Remove entry from hashtable. Does nothing if not found in hashtable. 133238106Sdes * Delfunc is called for the entry. Uses lruhash_remove. 134238106Sdes * @param table: hash table. 135238106Sdes * @param hash: hash of key. 136238106Sdes * @param key: what to look for. 137238106Sdes */ 138238106Sdesvoid slabhash_remove(struct slabhash* table, hashvalue_t hash, void* key); 139238106Sdes 140238106Sdes/** 141238106Sdes * Output debug info to the log as to state of the hash table. 142238106Sdes * @param table: hash table. 143238106Sdes * @param id: string printed with table to identify the hash table. 144238106Sdes * @param extended: set to true to print statistics on overflow bin lengths. 145238106Sdes */ 146238106Sdesvoid slabhash_status(struct slabhash* table, const char* id, int extended); 147238106Sdes 148238106Sdes/** 149238106Sdes * Retrieve slab hash total size. 150238106Sdes * @param table: hash table. 151238106Sdes * @return size configured as max. 152238106Sdes */ 153238106Sdessize_t slabhash_get_size(struct slabhash* table); 154238106Sdes 155238106Sdes/** 156238106Sdes * Retrieve slab hash current memory use. 157238106Sdes * @param table: hash table. 158238106Sdes * @return memory in use. 159238106Sdes */ 160238106Sdessize_t slabhash_get_mem(struct slabhash* table); 161238106Sdes 162238106Sdes/** 163238106Sdes * Get lruhash table for a given hash value 164238106Sdes * @param table: slabbed hash table. 165238106Sdes * @param hash: hash value. 166238106Sdes * @return the lru hash table. 167238106Sdes */ 168238106Sdesstruct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_t hash); 169238106Sdes 170238106Sdes/** 171238106Sdes * Set markdel function 172238106Sdes * @param table: slabbed hash table. 173238106Sdes * @param md: markdel function ptr. 174238106Sdes */ 175238106Sdesvoid slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_t md); 176238106Sdes 177238106Sdes/** 178238106Sdes * Traverse a slabhash. 179238106Sdes * @param table: slabbed hash table. 180238106Sdes * @param wr: if true, writelock is obtained, otherwise readlock. 181238106Sdes * @param func: function to call for every element. 182238106Sdes * @param arg: user argument to function. 183238106Sdes */ 184238106Sdesvoid slabhash_traverse(struct slabhash* table, int wr, 185238106Sdes void (*func)(struct lruhash_entry*, void*), void* arg); 186238106Sdes 187238106Sdes/* --- test representation --- */ 188238106Sdes/** test structure contains test key */ 189238106Sdesstruct slabhash_testkey { 190238106Sdes /** the key id */ 191238106Sdes int id; 192238106Sdes /** the entry */ 193238106Sdes struct lruhash_entry entry; 194238106Sdes}; 195238106Sdes/** test structure contains test data */ 196238106Sdesstruct slabhash_testdata { 197238106Sdes /** data value */ 198238106Sdes int data; 199238106Sdes}; 200238106Sdes 201238106Sdes/** test sizefunc for lruhash */ 202238106Sdessize_t test_slabhash_sizefunc(void*, void*); 203238106Sdes/** test comparefunc for lruhash */ 204238106Sdesint test_slabhash_compfunc(void*, void*); 205238106Sdes/** test delkey for lruhash */ 206238106Sdesvoid test_slabhash_delkey(void*, void*); 207238106Sdes/** test deldata for lruhash */ 208238106Sdesvoid test_slabhash_deldata(void*, void*); 209238106Sdes/* --- end test representation --- */ 210238106Sdes 211238106Sdes#endif /* UTIL_STORAGE_SLABHASH_H */ 212