Electroneum
lruhash.h
Go to the documentation of this file.
1 /*
2  * util/storage/lruhash.h - hashtable, hash function, LRU keeping.
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 
107 #ifndef UTIL_STORAGE_LRUHASH_H
108 #define UTIL_STORAGE_LRUHASH_H
109 #include "util/locks.h"
110 struct lruhash_bin;
111 struct lruhash_entry;
112 
114 #define HASH_DEFAULT_STARTARRAY 1024 /* entries in array */
115 
116 #define HASH_DEFAULT_MAXMEM 4*1024*1024 /* bytes */
117 
120 
127 typedef size_t (*lruhash_sizefunc_type)(void*, void*);
128 
130 typedef int (*lruhash_compfunc_type)(void*, void*);
131 
135 typedef void (*lruhash_delkeyfunc_type)(void*, void*);
136 
138 typedef void (*lruhash_deldatafunc_type)(void*, void*);
139 
142 typedef void (*lruhash_markdelfunc_type)(void*);
143 
147 struct lruhash {
161  void* cb_arg;
162 
164  size_t size;
169 
174 
176  size_t num;
178  size_t space_used;
180  size_t space_max;
181 };
182 
186 struct lruhash_bin {
194 };
195 
220  void* key;
222  void* data;
223 };
224 
238 struct lruhash* lruhash_create(size_t start_size, size_t maxmem,
242 
247 void lruhash_delete(struct lruhash* table);
248 
254 void lruhash_clear(struct lruhash* table);
255 
273  struct lruhash_entry* entry, void* data, void* cb_override);
274 
288 struct lruhash_entry* lruhash_lookup(struct lruhash* table,
289  hashvalue_type hash, void* key, int wr);
290 
297 void lru_touch(struct lruhash* table, struct lruhash_entry* entry);
298 
303 
304 /************************* getdns functions ************************/
305 /*** these are used by getdns only and not by unbound. ***/
306 
313 void lru_demote(struct lruhash* table, struct lruhash_entry* entry);
314 
334  struct lruhash_entry* entry, void* data, void* cb_arg);
335 
336 /************************* Internal functions ************************/
337 /*** these are only exposed for unit tests. ***/
338 
346 void lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key);
347 
349 void bin_init(struct lruhash_bin* array, size_t size);
350 
352 void bin_delete(struct lruhash* table, struct lruhash_bin* bin);
353 
362 struct lruhash_entry* bin_find_entry(struct lruhash* table,
363  struct lruhash_bin* bin, hashvalue_type hash, void* key);
364 
371 void bin_overflow_remove(struct lruhash_bin* bin,
372  struct lruhash_entry* entry);
373 
384 void bin_split(struct lruhash* table, struct lruhash_bin* newa,
385  int newmask);
386 
395 void reclaim_space(struct lruhash* table, struct lruhash_entry** list);
396 
403 void table_grow(struct lruhash* table);
404 
411 void lru_front(struct lruhash* table, struct lruhash_entry* entry);
412 
419 void lru_remove(struct lruhash* table, struct lruhash_entry* entry);
420 
427 void lruhash_status(struct lruhash* table, const char* id, int extended);
428 
434 size_t lruhash_get_mem(struct lruhash* table);
435 
443 void lruhash_traverse(struct lruhash* h, int wr,
444  void (*func)(struct lruhash_entry*, void*), void* arg);
445 
446 #endif /* UTIL_STORAGE_LRUHASH_H */
lock_quick_type lock
Definition: lruhash.h:191
lruhash_delkeyfunc_type delkeyfunc
Definition: lruhash.h:155
void lru_remove(struct lruhash *table, struct lruhash_entry *entry)
struct lruhash_entry * lru_next
Definition: lruhash.h:214
std::vector< std::vector< _variant_t > > table
void reclaim_space(struct lruhash *table, struct lruhash_entry **list)
void lru_touch(struct lruhash *table, struct lruhash_entry *entry)
void(* lruhash_deldatafunc_type)(void *, void *)
Definition: lruhash.h:138
lock_quick_type lock
Definition: lruhash.h:149
void * data
Definition: lruhash.h:222
const char * key
Definition: hmac_keccak.cpp:39
void bin_overflow_remove(struct lruhash_bin *bin, struct lruhash_entry *entry)
struct lruhash * lruhash_create(size_t start_size, size_t maxmem, lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc, lruhash_delkeyfunc_type delkeyfunc, lruhash_deldatafunc_type deldatafunc, void *arg)
struct lruhash_entry * overflow_next
Definition: lruhash.h:212
size_t lruhash_get_mem(struct lruhash *table)
void lruhash_setmarkdel(struct lruhash *table, lruhash_markdelfunc_type md)
lruhash_deldatafunc_type deldatafunc
Definition: lruhash.h:157
void(* lruhash_markdelfunc_type)(void *)
Definition: lruhash.h:142
struct lruhash_entry * bin_find_entry(struct lruhash *table, struct lruhash_bin *bin, hashvalue_type hash, void *key)
struct lruhash_entry * lru_start
Definition: lruhash.h:171
int lock_quick_type
Definition: locks.h:276
struct lruhash_entry * overflow_list
Definition: lruhash.h:193
void lruhash_status(struct lruhash *table, const char *id, int extended)
void lruhash_delete(struct lruhash *table)
size_t num
Definition: lruhash.h:176
lruhash_markdelfunc_type markdelfunc
Definition: lruhash.h:159
lruhash_sizefunc_type sizefunc
Definition: lruhash.h:151
void(* lruhash_delkeyfunc_type)(void *, void *)
Definition: lruhash.h:135
struct lruhash_entry * lruhash_lookup(struct lruhash *table, hashvalue_type hash, void *key, int wr)
unsigned int uint32_t
Definition: stdint.h:126
uint32_t hashvalue_type
Definition: lruhash.h:119
void table_grow(struct lruhash *table)
void bin_init(struct lruhash_bin *array, size_t size)
void * cb_arg
Definition: lruhash.h:161
int(* lruhash_compfunc_type)(void *, void *)
Definition: lruhash.h:130
lock_rw_type lock
Definition: lruhash.h:210
void lruhash_clear(struct lruhash *table)
void bin_split(struct lruhash *table, struct lruhash_bin *newa, int newmask)
void lru_demote(struct lruhash *table, struct lruhash_entry *entry)
lruhash_compfunc_type compfunc
Definition: lruhash.h:153
void lru_front(struct lruhash *table, struct lruhash_entry *entry)
size_t space_used
Definition: lruhash.h:178
size_t size
Definition: lruhash.h:164
void lruhash_insert(struct lruhash *table, hashvalue_type hash, struct lruhash_entry *entry, void *data, void *cb_override)
struct lruhash_entry * lru_prev
Definition: lruhash.h:216
struct lruhash_entry * lruhash_insert_or_retrieve(struct lruhash *table, hashvalue_type hash, struct lruhash_entry *entry, void *data, void *cb_arg)
size_t(* lruhash_sizefunc_type)(void *, void *)
Definition: lruhash.h:127
POD_CLASS hash
Definition: hash.h:50
void lruhash_traverse(struct lruhash *h, int wr, void(*func)(struct lruhash_entry *, void *), void *arg)
size_t space_max
Definition: lruhash.h:180
struct lruhash_bin * array
Definition: lruhash.h:168
void lruhash_remove(struct lruhash *table, hashvalue_type hash, void *key)
void bin_delete(struct lruhash *table, struct lruhash_bin *bin)
Definition: lruhash.h:203
struct lruhash_entry * lru_end
Definition: lruhash.h:173
int size_mask
Definition: lruhash.h:166
void * key
Definition: lruhash.h:220
hashvalue_type hash
Definition: lruhash.h:218
int lock_rw_type
Definition: locks.h:261