FD.io VPP  v17.07.01-10-g3be13f0
Vector Packet Processing
bihash_doc.h File Reference

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...
 

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 (clib_bihash *h, clib_bihash_kv *search_v, clib_bihash_kv *return_v)
 Search a bi-hash table. More...
 
void clib_bihash_foreach_key_value_pair (clib_bihash *h, void *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
 

Detailed Description

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 Documentation

typedef struct clib_bihash_value offset

template key/value backing page structure

bihash bucket structure backing page offset in the clib memory heap

Function Documentation

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.

Parameters
h- the bi-hash table to search
add_v- the (key,value) pair to add
is_add- add=1, delete=0
Returns
0 on success, < 0 on error
Note
This function will replace an existing (key,value) pair if the new key matches an existing key

+ Here is the caller graph for this function:

void clib_bihash_foreach_key_value_pair ( clib_bihash *  h,
void *  callback,
void *  arg 
)

Visit active (key,value) pairs in a bi-hash table.

Parameters
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
Note
Trying to supply a proper function prototype for the callback function appears to be a fool's errand.

+ Here is the caller graph for this function:

void clib_bihash_free ( clib_bihash *  h)

Destroy a bounded index extensible hash table.

Parameters
h- the bi-hash table to free

+ Here is the caller graph for this function:

static uword clib_bihash_get_offset ( clib_bihash *  h,
void *  v 
)
inlinestatic

Get clib mheap offset given a pointer.

static void* clib_bihash_get_value ( clib_bihash *  h,
uword  offset 
)
inlinestatic

Get pointer to value page given its clib mheap offset.

+ Here is the caller graph for this function:

void clib_bihash_init ( clib_bihash *  h,
char *  name,
u32  nbuckets,
uword  memory_size 
)

initialize a bounded index extensible hash table

Parameters
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

+ Here is the caller graph for this function:

int clib_bihash_search ( clib_bihash *  h,
clib_bihash_kv *  search_v,
clib_bihash_kv *  return_v 
)

Search a bi-hash table.

Parameters
h- the bi-hash table to search
search_v- (key,value) pair containing the search key
return_v- (key,value) pair which matches search_v.key
Returns
0 on success (with return_v set), < 0 on error

+ Here is the caller graph for this function:

Variable Documentation

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.