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_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, 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

offset

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

clib_bihash_add_del()

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:

clib_bihash_foreach_key_value_pair()

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:

clib_bihash_free()

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:

clib_bihash_get_offset()

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

inlinestatic

Get clib mheap offset given a pointer.

clib_bihash_get_value()

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:

clib_bihash_init()

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:

clib_bihash_prefetch_bucket()

void clib_bihash_prefetch_bucket	(	clib_bihash *	h,
		u64	hash
	)

Prefetch a bi-hash bucket given a hash code.

Parameters

h	- the bi-hash table to search
hash	- the hash code

Note

see also clib_bihash_hash to compute the code

clib_bihash_prefetch_data()

void clib_bihash_prefetch_data	(	clib_bihash *	h,
		u64	hash
	)

Prefetch bi-hash (key,value) data given a hash code.

Parameters

h	- the bi-hash table to search
hash	- the hash code

Note

assumes that the bucket has been prefetched, see clib_bihash_prefetch_bucket

clib_bihash_search_inline()

int clib_bihash_search_inline	(	clib_bihash *	h,
		clib_bihash_kv *	in_out_kv
	)

Search a bi-hash table.

Parameters

h	- the bi-hash table to search
in_out_kv	- (key,value) pair containing the search key

Returns

0 on success (with in_out_kv set), < 0 on error

Here is the caller graph for this function:

clib_bihash_search_inline_2()

int clib_bihash_search_inline_2	(	clib_bihash *	h,
		clib_bihash_kv *	search_key,
		clib_bihash_kv *	valuep
	)

Search a bi-hash table.

Parameters

h	- the bi-hash table to search
search_key	- (key,value) pair containing the search key
valuep	- (key,value) set to search result

Returns

0 on success (with valuep set), < 0 on error

Note

used in situations where key modification is not desired

Here is the caller graph for this function:

clib_bihash_search_inline_with_hash()

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.

Parameters

h	- the bi-hash table to search
hash	- the hash code
in_out_kv	- (key,value) pair containing the search key

Returns

0 on success (with in_out_kv set), < 0 on error

Variable Documentation

as_u64

u64 as_u64

Definition at line 63 of file bihash_doc.h.

clib_bihash_bucket_t

clib_bihash_bucket_t

Definition at line 65 of file bihash_doc.h.

log2_pages

u8 log2_pages

Definition at line 62 of file bihash_doc.h.

pad

u8 pad[3]

log2 (size of the packing page block)

Definition at line 61 of file bihash_doc.h.