FD.io VPP
v20.05.1-6-gf53edbc3b
Vector Packet Processing
|
Bounded-index extensible hashing. More...
Go to the source code of this file.
Data Structures | |
struct | clib_bihash_value |
template key/value backing page structure More... | |
struct | clib_bihash_t |
A bounded index extensible hash table. More... | |
Typedefs | |
typedef struct clib_bihash_value | offset |
template key/value backing page structure More... | |
typedef int(* | clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv *kv, void *ctx) |
Functions | |
static void * | clib_bihash_get_value (clib_bihash *h, uword offset) |
Get pointer to value page given its clib mheap offset. More... | |
static uword | clib_bihash_get_offset (clib_bihash *h, void *v) |
Get clib mheap offset given a pointer. More... | |
void | clib_bihash_init (clib_bihash *h, char *name, u32 nbuckets, uword memory_size) |
initialize a bounded index extensible hash table More... | |
void | clib_bihash_free (clib_bihash *h) |
Destroy a bounded index extensible hash table. More... | |
int | clib_bihash_add_del (clib_bihash *h, clib_bihash_kv *add_v, int is_add) |
Add or delete a (key,value) pair from a bi-hash table. More... | |
int | clib_bihash_search_inline_with_hash (clib_bihash *h, u64 hash, clib_bihash_kv *in_out_kv) |
Search a bi-hash table, use supplied hash code. More... | |
int | clib_bihash_search_inline (clib_bihash *h, clib_bihash_kv *in_out_kv) |
Search a bi-hash table. More... | |
void | clib_bihash_prefetch_bucket (clib_bihash *h, u64 hash) |
Prefetch a bi-hash bucket given a hash code. More... | |
void | clib_bihash_prefetch_data (clib_bihash *h, u64 hash) |
Prefetch bi-hash (key,value) data given a hash code. More... | |
int | clib_bihash_search_inline_2 (clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep) |
Search a bi-hash table. More... | |
void | clib_bihash_foreach_key_value_pair (clib_bihash *h, clib_bihash_foreach_key_value_pair_cb *callback, void *arg) |
Visit active (key,value) pairs in a bi-hash table. More... | |
Variables | |
u8 | pad [3] |
log2 (size of the packing page block) More... | |
u8 | log2_pages |
u64 | as_u64 |
clib_bihash_bucket_t | |
Bounded-index extensible hashing.
The basic algorithm performs thread-safe constant-time lookups in the face of a rational number of hash collisions. The computed hash code h(k) must have reasonable statistics with respect to the key space. It won't do to have h(k) = 0 or 1, for all values of k.
Each bucket in the power-of-two bucket array contains the index (in a private vppinfra memory heap) of the "backing store" for the bucket, as well as a size field. The size field (log2_pages) corresponds to 1, 2, 4, ... contiguous "pages" containing the (key,value) pairs in the bucket.
When a single page fills, we allocate two contiguous pages. We recompute h(k) for each (key,value) pair, using an additional bit to deal the (key, value) pairs into the "top" and "bottom" pages.
At lookup time, we compute h(k), using lg(bucket-array-size) to pick the bucket. We read the bucket to find the base of the backing pages. We use an additional log2_pages' worth of bits from h(k) to compute the offset of the page which will contain the (key,value) pair we're trying to find.
Definition in file bihash_doc.h.
typedef int(* clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv *kv, void *ctx) |
Definition at line 175 of file bihash_doc.h.
typedef struct clib_bihash_value offset |
template key/value backing page structure
bihash bucket structure backing page offset in the clib memory heap
int clib_bihash_add_del | ( | clib_bihash * | h, |
clib_bihash_kv * | add_v, | ||
int | is_add | ||
) |
Add or delete a (key,value) pair from a bi-hash table.
h | - the bi-hash table to search |
add_v | - the (key,value) pair to add |
is_add | - add=1, delete=0 |
void clib_bihash_foreach_key_value_pair | ( | clib_bihash * | h, |
clib_bihash_foreach_key_value_pair_cb * | callback, | ||
void * | arg | ||
) |
Visit active (key,value) pairs in a bi-hash table.
h | - the bi-hash table to search |
callback | - function to call with each active (key,value) pair |
arg | - arbitrary second argument passed to the callback function First argument is the (key,value) pair to visit |
void clib_bihash_free | ( | clib_bihash * | h | ) |
Destroy a bounded index extensible hash table.
h | - the bi-hash table to free |
|
inlinestatic |
Get clib mheap offset given a pointer.
|
inlinestatic |
Get pointer to value page given its clib mheap offset.
initialize a bounded index extensible hash table
h | - the bi-hash table to initialize |
name | - name of the hash table |
nbuckets | - the number of buckets, will be rounded up to a power of two |
memory_size | - clib mheap size, in bytes |
void clib_bihash_prefetch_bucket | ( | clib_bihash * | h, |
u64 | hash | ||
) |
Prefetch a bi-hash bucket given a hash code.
h | - the bi-hash table to search |
hash | - the hash code |
void clib_bihash_prefetch_data | ( | clib_bihash * | h, |
u64 | hash | ||
) |
Prefetch bi-hash (key,value) data given a hash code.
h | - the bi-hash table to search |
hash | - the hash code |
int clib_bihash_search_inline | ( | clib_bihash * | h, |
clib_bihash_kv * | in_out_kv | ||
) |
Search a bi-hash table.
h | - the bi-hash table to search |
in_out_kv | - (key,value) pair containing the search key |
int clib_bihash_search_inline_2 | ( | clib_bihash * | h, |
clib_bihash_kv * | search_key, | ||
clib_bihash_kv * | valuep | ||
) |
Search a bi-hash table.
h | - the bi-hash table to search |
search_key | - (key,value) pair containing the search key |
valuep | - (key,value) set to search result |
int clib_bihash_search_inline_with_hash | ( | clib_bihash * | h, |
u64 | hash, | ||
clib_bihash_kv * | in_out_kv | ||
) |
Search a bi-hash table, use supplied hash code.
h | - the bi-hash table to search |
hash | - the hash code |
in_out_kv | - (key,value) pair containing the search key |
u64 as_u64 |
Definition at line 63 of file bihash_doc.h.
clib_bihash_bucket_t |
Definition at line 65 of file bihash_doc.h.
u8 log2_pages |
Definition at line 62 of file bihash_doc.h.
u8 pad[3] |
log2 (size of the packing page block)
Definition at line 61 of file bihash_doc.h.