lruhash.c File Reference

This file contains a hashtable with LRU keeping of entries. More...

#include "config.h"
#include "util/storage/lruhash.h"
#include "util/fptr_wlist.h"

Functions

void bin_init (struct lruhash_bin *array, size_t size)
 init the hash bins for the table
 
struct lruhashlruhash_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)
 Create new hash table. More...
 
void bin_delete (struct lruhash *table, struct lruhash_bin *bin)
 delete the hash bin and entries inside it
 
void bin_split (struct lruhash *table, struct lruhash_bin *newa, int newmask)
 Split hash bin into two new ones. More...
 
void lruhash_delete (struct lruhash *table)
 Delete hash table. More...
 
void bin_overflow_remove (struct lruhash_bin *bin, struct lruhash_entry *entry)
 Remove entry from bin overflow chain. More...
 
void reclaim_space (struct lruhash *table, struct lruhash_entry **list)
 Try to make space available by deleting old entries. More...
 
struct lruhash_entrybin_find_entry (struct lruhash *table, struct lruhash_bin *bin, hashvalue_type hash, void *key, size_t *collisions)
 Find entry in hash bin. More...
 
void table_grow (struct lruhash *table)
 Grow the table lookup array. More...
 
void lru_front (struct lruhash *table, struct lruhash_entry *entry)
 Put entry at front of lru. More...
 
void lru_remove (struct lruhash *table, struct lruhash_entry *entry)
 Remove entry from lru list. More...
 
void lru_touch (struct lruhash *table, struct lruhash_entry *entry)
 Touch entry, so it becomes the most recently used in the LRU list. More...
 
void lruhash_insert (struct lruhash *table, hashvalue_type hash, struct lruhash_entry *entry, void *data, void *cb_arg)
 Insert a new element into the hashtable. More...
 
struct lruhash_entrylruhash_lookup (struct lruhash *table, hashvalue_type hash, void *key, int wr)
 Lookup an entry in the hashtable. More...
 
void lruhash_remove (struct lruhash *table, hashvalue_type hash, void *key)
 Remove entry from hashtable. More...
 
static void bin_clear (struct lruhash *table, struct lruhash_bin *bin)
 clear bin, respecting locks, does not do space, LRU
 
void lruhash_clear (struct lruhash *table)
 Clear hash table. More...
 
void lruhash_status (struct lruhash *table, const char *id, int extended)
 Output debug info to the log as to state of the hash table. More...
 
size_t lruhash_get_mem (struct lruhash *table)
 Get memory in use now by the lruhash table. More...
 
void lruhash_setmarkdel (struct lruhash *table, lruhash_markdelfunc_type md)
 Set the markdelfunction (or NULL)
 
void lruhash_update_space_used (struct lruhash *table, void *cb_arg, int diff_size)
 Update the size of an element in the hashtable. More...
 
void lruhash_traverse (struct lruhash *h, int wr, void(*func)(struct lruhash_entry *, void *), void *arg)
 Traverse a lruhash. More...
 
void lru_demote (struct lruhash *table, struct lruhash_entry *entry)
 Demote entry, so it becomes the least recently used in the LRU list. More...
 
struct lruhash_entrylruhash_insert_or_retrieve (struct lruhash *table, hashvalue_type hash, struct lruhash_entry *entry, void *data, void *cb_arg)
 Insert a new element into the hashtable, or retrieve the corresponding element of it exits. More...
 

Detailed Description

This file contains a hashtable with LRU keeping of entries.

Function Documentation

◆ lruhash_create()

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 
)

Create new hash table.

Parameters
start_sizesize of hashtable array at start, must be power of 2.
maxmemmaximum amount of memory this table is allowed to use.
sizefunccalculates memory usage of entries.
compfunccompares entries, 0 on equality.
delkeyfuncdeletes key. Calling both delkey and deldata will also free the struct lruhash_entry. Make it part of the key structure and delete it in delkeyfunc.
deldatafuncdeletes data.
arguser argument that is passed to user function calls.
Returns
: new hash table or NULL on malloc failure.

References lruhash::array, bin_init(), lruhash::cb_arg, lruhash::compfunc, lruhash::deldatafunc, lruhash::delkeyfunc, lruhash::lock, lruhash::lru_end, lruhash::lru_start, lruhash::max_collisions, lruhash::num, lruhash::size, lruhash::size_mask, lruhash::sizefunc, lruhash::space_max, and lruhash::space_used.

Referenced by lruhash_test(), and slabhash_create().

◆ bin_split()

void bin_split ( struct lruhash table,
struct lruhash_bin newa,
int  newmask 
)

Split hash bin into two new ones.

Based on increased size_mask. Caller must hold hash table lock. At the end the routine acquires all hashbin locks (in the old array). This makes it wait for other threads to finish with the bins. So the bins are ready to be deleted after this function.

Parameters
tablehash table with function pointers.
newanew increased array.
newmasknew lookup mask.

References lruhash::array, lruhash_entry::hash, lruhash_bin::lock, lruhash_bin::overflow_list, lruhash_entry::overflow_next, lruhash::size, and lruhash::size_mask.

Referenced by table_grow().

◆ lruhash_delete()

void lruhash_delete ( struct lruhash table)

Delete hash table.

Entries are all deleted.

Parameters
tableto delete.

References lruhash::array, bin_delete(), lruhash::lock, and lruhash::size.

Referenced by lruhash_test(), and slabhash_delete().

◆ bin_overflow_remove()

void bin_overflow_remove ( struct lruhash_bin bin,
struct lruhash_entry entry 
)

Remove entry from bin overflow chain.

You must have locked the bin.

Parameters
binhash bin to look into.
entryentry ptr that needs removal.

References lruhash_bin::overflow_list, and lruhash_entry::overflow_next.

Referenced by lruhash_remove(), reclaim_space(), and test_bin_find_entry().

◆ reclaim_space()

void reclaim_space ( struct lruhash table,
struct lruhash_entry **  list 
)

Try to make space available by deleting old entries.

Assumes that the lock on the hashtable is being held by caller. Caller must not hold bin locks.

Parameters
tablehash table.
listlist of entries that are to be deleted later. Entries have been removed from the hash table and writelock is held.

References lruhash::array, bin_overflow_remove(), lruhash_entry::data, lruhash_entry::hash, lruhash_entry::key, lruhash_bin::lock, lruhash_entry::lock, log_assert, lruhash::lru_end, lruhash_entry::lru_next, lruhash_entry::lru_prev, lruhash::markdelfunc, lruhash::num, lruhash_entry::overflow_next, lruhash::size_mask, lruhash::sizefunc, lruhash::space_max, and lruhash::space_used.

Referenced by lruhash_insert(), lruhash_insert_or_retrieve(), and lruhash_update_space_used().

◆ bin_find_entry()

struct lruhash_entry* bin_find_entry ( struct lruhash table,
struct lruhash_bin bin,
hashvalue_type  hash,
void *  key,
size_t *  collisions 
)

Find entry in hash bin.

You must have locked the bin.

Parameters
tablehash table with function pointers.
binhash bin to look into.
hashhash value to look for.
keykey to look for.
collisionshow many collisions were found during the search.
Returns
: the entry or NULL if not found.

References lruhash::compfunc, lruhash_entry::hash, lruhash_entry::key, lruhash_bin::overflow_list, and lruhash_entry::overflow_next.

Referenced by lruhash_insert(), lruhash_insert_or_retrieve(), lruhash_lookup(), lruhash_remove(), and test_bin_find_entry().

◆ table_grow()

void table_grow ( struct lruhash table)

Grow the table lookup array.

Becomes twice as large. Caller must hold the hash table lock. Must not hold any bin locks. Tries to grow, on malloc failure, nothing happened.

Parameters
tablehash table.

References lruhash::array, bin_init(), bin_split(), lruhash::lock, lruhash_bin::lock, log_err(), lruhash::size, and lruhash::size_mask.

Referenced by lruhash_insert(), and lruhash_insert_or_retrieve().

◆ lru_front()

void lru_front ( struct lruhash table,
struct lruhash_entry entry 
)

Put entry at front of lru.

entry must be unlinked from lru. Caller must hold hash table lock.

Parameters
tablehash table with lru head and tail.
entryentry to make most recently used.

References lruhash::lru_end, lruhash_entry::lru_prev, and lruhash::lru_start.

Referenced by lru_touch(), lruhash_insert(), lruhash_insert_or_retrieve(), and test_lru().

◆ lru_remove()

void lru_remove ( struct lruhash table,
struct lruhash_entry entry 
)

Remove entry from lru list.

Caller must hold hash table lock.

Parameters
tablehash table with lru head and tail.
entryentry to remove from lru.

References lruhash::lru_end, and lruhash::lru_start.

Referenced by lru_demote(), lru_touch(), lruhash_remove(), and test_lru().

◆ lru_touch()

void lru_touch ( struct lruhash table,
struct lruhash_entry entry 
)

Touch entry, so it becomes the most recently used in the LRU list.

Caller must hold hash table lock. The entry must be inserted already.

Parameters
tablehash table.
entryentry to make first in LRU.

References log_assert, lru_front(), lru_remove(), and lruhash::lru_start.

Referenced by lruhash_insert(), lruhash_lookup(), and rrset_cache_touch().

◆ lruhash_insert()

void lruhash_insert ( struct lruhash table,
hashvalue_type  hash,
struct lruhash_entry entry,
void *  data,
void *  cb_override 
)

Insert a new element into the hashtable.

If key is already present data pointer in that entry is updated. The space calculation function is called with the key, data. If necessary the least recently used entries are deleted to make space. If necessary the hash array is grown up.

Parameters
tablehash table.
hashhash value. User calculates the hash.
entryidentifies the entry. If key already present, this entry->key is deleted immediately. But entry->data is set to NULL before deletion, and put into the existing entry. The data is then freed.
datathe data.
cb_overrideif not null overrides the cb_arg for the deletefunc.

References lruhash::array, bin_find_entry(), lruhash::cb_arg, lruhash::compfunc, lruhash_entry::data, lruhash::deldatafunc, lruhash::delkeyfunc, fptr_ok, fptr_whitelist_hash_compfunc(), fptr_whitelist_hash_deldatafunc(), fptr_whitelist_hash_delkeyfunc(), fptr_whitelist_hash_markdelfunc(), fptr_whitelist_hash_sizefunc(), lruhash_entry::hash, lruhash_entry::key, lruhash::lock, lruhash_bin::lock, lruhash_entry::lock, lru_front(), lru_touch(), lruhash::markdelfunc, lruhash::max_collisions, lruhash::num, lruhash_bin::overflow_list, lruhash_entry::overflow_next, reclaim_space(), lruhash::size, lruhash::size_mask, lruhash::sizefunc, lruhash::space_max, lruhash::space_used, and table_grow().

Referenced by slabhash_insert(), test_short_table(), testadd(), and testadd_unlim().

◆ lruhash_lookup()

struct lruhash_entry* lruhash_lookup ( struct lruhash table,
hashvalue_type  hash,
void *  key,
int  wr 
)

Lookup an entry in the hashtable.

At the end of the function you hold a (read/write)lock on the entry. The LRU is updated for the entry (if found).

Parameters
tablehash table.
hashhash of key.
keywhat to look for, compared against entries in overflow chain. the hash value must be set, and must work with compare function.
wrset to true if you desire a writelock on the entry. with a writelock you can update the data part.
Returns
: pointer to the entry or NULL. The entry is locked. The user must unlock the entry when done.

References lruhash::array, bin_find_entry(), lruhash::compfunc, fptr_ok, fptr_whitelist_hash_compfunc(), lruhash::lock, lruhash_bin::lock, lru_touch(), and lruhash::size_mask.

Referenced by slabhash_lookup(), test_short_table(), testlookup(), and testlookup_unlim().

◆ lruhash_remove()

◆ lruhash_clear()

void lruhash_clear ( struct lruhash table)

◆ lruhash_status()

void lruhash_status ( struct lruhash table,
const char *  id,
int  extended 
)

Output debug info to the log as to state of the hash table.

Parameters
tablehash table.
idstring printed with table to identify the hash table.
extendedset to true to print statistics on overflow bin lengths.

References lruhash::array, lruhash::lock, lruhash_bin::lock, log_info(), lruhash::num, lruhash_bin::overflow_list, lruhash_entry::overflow_next, lruhash::size, lruhash::size_mask, lruhash::space_max, and lruhash::space_used.

Referenced by slabhash_status(), test_long_table(), test_thr_main(), and test_threaded_table().

◆ lruhash_get_mem()

size_t lruhash_get_mem ( struct lruhash table)

Get memory in use now by the lruhash table.

Parameters
tablehash table. Will be locked before use. And unlocked after.
Returns
size in bytes.

References lruhash::array, lruhash::lock, lruhash_bin::lock, lruhash::size, and lruhash::space_used.

Referenced by slabhash_get_mem().

◆ lruhash_update_space_used()

void lruhash_update_space_used ( struct lruhash table,
void *  cb_override,
int  diff_size 
)

Update the size of an element in the hashtable.

Parameters
tablehash table.
cb_overrideif not NULL overrides the cb_arg for deletefunc.
diff_sizedifference in size to the hash table storage. This is newsize - oldsize, a positive number uses more space.

References lruhash::cb_arg, lruhash_entry::data, lruhash::deldatafunc, lruhash::delkeyfunc, fptr_ok, fptr_whitelist_hash_deldatafunc(), fptr_whitelist_hash_delkeyfunc(), fptr_whitelist_hash_markdelfunc(), fptr_whitelist_hash_sizefunc(), lruhash_entry::key, lruhash::lock, lruhash::markdelfunc, lruhash_entry::overflow_next, reclaim_space(), lruhash::sizefunc, lruhash::space_max, and lruhash::space_used.

Referenced by slabhash_update_space_used().

◆ lruhash_traverse()

void lruhash_traverse ( struct lruhash h,
int  wr,
void(*)(struct lruhash_entry *, void *)  func,
void *  arg 
)

Traverse a lruhash.

Call back for every element in the table.

Parameters
hhash table. Locked before use.
wrif true writelock is obtained on element, otherwise readlock.
funcfunction for every element. Do not lock or unlock elements.
arguser argument to func.

References lruhash::array, lruhash::lock, lruhash_bin::lock, lruhash_entry::lock, lruhash_bin::overflow_list, lruhash_entry::overflow_next, and lruhash::size.

Referenced by slabhash_traverse().

◆ lru_demote()

void lru_demote ( struct lruhash table,
struct lruhash_entry entry 
)

Demote entry, so it becomes the least recently used in the LRU list.

Caller must hold hash table lock. The entry must be inserted already.

Parameters
tablehash table.
entryentry to make last in LRU.

References log_assert, lruhash::lru_end, lruhash_entry::lru_next, lru_remove(), and lruhash::lru_start.

◆ lruhash_insert_or_retrieve()

struct lruhash_entry* lruhash_insert_or_retrieve ( struct lruhash table,
hashvalue_type  hash,
struct lruhash_entry entry,
void *  data,
void *  cb_arg 
)

Insert a new element into the hashtable, or retrieve the corresponding element of it exits.

If key is already present data pointer in that entry is kept. If it is not present, a new entry is created. In that case, the space calculation function is called with the key, data. If necessary the least recently used entries are deleted to make space. If necessary the hash array is grown up.

Parameters
tablehash table.
hashhash value. User calculates the hash.
entryidentifies the entry.
datathe data.
cb_argif not null overrides the cb_arg for the deletefunc.
Returns
: pointer to the existing entry if the key was already present, or to the entry argument if it was not.

References lruhash::array, bin_find_entry(), lruhash::cb_arg, lruhash::compfunc, lruhash_entry::data, lruhash::deldatafunc, lruhash::delkeyfunc, fptr_ok, fptr_whitelist_hash_compfunc(), fptr_whitelist_hash_deldatafunc(), fptr_whitelist_hash_delkeyfunc(), fptr_whitelist_hash_markdelfunc(), fptr_whitelist_hash_sizefunc(), lruhash_entry::hash, lruhash_entry::key, lruhash::lock, lruhash_bin::lock, lruhash_entry::lock, lru_front(), lruhash::markdelfunc, lruhash::max_collisions, lruhash::num, lruhash_bin::overflow_list, lruhash_entry::overflow_next, reclaim_space(), lruhash::size, lruhash::size_mask, lruhash::sizefunc, lruhash::space_max, lruhash::space_used, and table_grow().