2 * util/storage/slabhash.h - hashtable consisting of several smaller tables.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
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.
44 #ifndef UTIL_STORAGE_SLABHASH_H
45 #define UTIL_STORAGE_SLABHASH_H
46 #include "util/storage/lruhash.h"
48 /** default number of slabs */
49 #define HASH_DEFAULT_SLABS 4
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.
58 /** the size of the array - must be power of 2 */
60 /** size bitmask - uses high bits. */
62 /** shift right this many bits to get index into array. */
64 /** lookup array of hash tables */
65 struct lruhash** array;
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.
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);
88 * Delete hash table. Entries are all deleted.
89 * @param table: to delete.
91 void slabhash_delete(struct slabhash* table);
94 * Clear hash table. Entries are all deleted.
95 * @param table: to make empty.
97 void slabhash_clear(struct slabhash* table);
100 * Insert a new element into the hashtable, uses lruhash_insert.
101 * If key is already present data pointer in that entry is updated.
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.
112 void slabhash_insert(struct slabhash* table, hashvalue_type hash,
113 struct lruhash_entry* entry, void* data, void* cb_override);
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.
128 struct lruhash_entry* slabhash_lookup(struct slabhash* table,
129 hashvalue_type hash, void* key, int wr);
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.
138 void slabhash_remove(struct slabhash* table, hashvalue_type hash, void* key);
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.
146 void slabhash_status(struct slabhash* table, const char* id, int extended);
149 * Retrieve slab hash total size.
150 * @param table: hash table.
151 * @return size configured as max.
153 size_t slabhash_get_size(struct slabhash* table);
156 * Retrieve slab hash current memory use.
157 * @param table: hash table.
158 * @return memory in use.
160 size_t slabhash_get_mem(struct slabhash* table);
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.
168 struct lruhash* slabhash_gettable(struct slabhash* table, hashvalue_type hash);
171 * Set markdel function
172 * @param table: slabbed hash table.
173 * @param md: markdel function ptr.
175 void slabhash_setmarkdel(struct slabhash* table, lruhash_markdelfunc_type md);
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.
184 void slabhash_traverse(struct slabhash* table, int wr,
185 void (*func)(struct lruhash_entry*, void*), void* arg);
188 * Count entries in slabhash.
189 * @param table: slabbed hash table;
190 * @return the number of items
192 size_t count_slabhash_entries(struct slabhash* table);
194 /* --- test representation --- */
195 /** test structure contains test key */
196 struct slabhash_testkey {
200 struct lruhash_entry entry;
202 /** test structure contains test data */
203 struct slabhash_testdata {
208 /** test sizefunc for lruhash */
209 size_t test_slabhash_sizefunc(void*, void*);
210 /** test comparefunc for lruhash */
211 int test_slabhash_compfunc(void*, void*);
212 /** test delkey for lruhash */
213 void test_slabhash_delkey(void*, void*);
214 /** test deldata for lruhash */
215 void test_slabhash_deldata(void*, void*);
216 /* --- end test representation --- */
218 #endif /* UTIL_STORAGE_SLABHASH_H */