Include dependency graph for cuckoo_template.c:

Macros
#define	CLIB_CUCKOO_DEEP_SELF_CHECK(h)

#define	CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)

#define	CLIB_CUCKOO_DEBUG_PATH (1)

#define	CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)

Functions
int CV()	clib_cuckoo_search (CVT(clib_cuckoo) h, CVT(clib_cuckoo_kv) search_v, CVT(clib_cuckoo_kv) *return_v)

static	CVT (clib_cuckoo_bucket)

static uword CV()	clib_cuckoo_get_nbuckets (CVT(clib_cuckoo) *h)

static uword CV()	clib_cuckoo_elt_in_bucket_to_offset (CVT(clib_cuckoo_bucket) b, CVT(clib_cuckoo_kv) e)

u8 *CV()	format_cuckoo_elt (u8 s, va_list args)

u8 *CV()	format_cuckoo_bucket (u8 s, va_list args)

void CV()	clib_cuckoo_init (CVT(clib_cuckoo) h, const char name, uword nbuckets, void(garbage_callback)(CVT(clib_cuckoo) , void ), void garbage_ctx)

void CV()	clib_cuckoo_free (CVT(clib_cuckoo) *h)

static clib_cuckoo_bucket_aux_t CV()	clib_cuckoo_bucket_version_bump_and_lock (CVT(clib_cuckoo_bucket) *b)

static void CV()	clib_cuckoo_bucket_unlock (CVT(clib_cuckoo_bucket) *b, clib_cuckoo_bucket_aux_t aux)

static clib_cuckoo_path_t *CV()	clib_cuckoo_path_get (CVT(clib_cuckoo) *h)

static void CV()	clib_cuckoo_path_put (CVT(clib_cuckoo) *h, uword path_idx)

static clib_cuckoo_path_t *CV()	clib_cuckoo_path_begin (CVT(clib_cuckoo) *h, uword bucket, uword next_offset)

static uword CV()	clib_cuckoo_path_extend (CVT(clib_cuckoo) *h, uword path_idx, uword bucket, unsigned offset)
	create a new path based on existing path extended by adding a bucket and offset More...

static uword CV()	clib_cuckoo_path_peek_offset (const clib_cuckoo_path_t *path)
	return the offset of the last element in the path More...

static	CVT (clib_cuckoo_kv)

static void	clib_cuckoo_path_walk (CVT(clib_cuckoo) h, uword path_idx, uword buckets, uword *offsets)
	walk the cuckoo path two ways, first backwards, extracting offsets, then forward, extracting buckets More...

static int CV()	clib_cuckoo_find_empty_slot_bfs (CVT(clib_cuckoo) h, clib_cuckoo_lookup_info_t lookup, uword path_idx_out, uword found_bucket, CVT(clib_cuckoo_kv) **found_elt)

static void CV()	clib_cuckoo_swap_elts_in_bucket (CVT(clib_cuckoo_bucket) *b, uword e1, uword e2)

static void CV()	clib_cuckoo_bucket_tidy (CVT(clib_cuckoo_bucket) *b)

static void CV()	clib_cuckoo_free_locked_elt (CVT(clib_cuckoo_kv) *elt)

static void CV()	clib_cuckoo_free_elt_in_bucket (CVT(clib_cuckoo_bucket) b, CVT(clib_cuckoo_kv) elt)

static void CV()	clib_cuckoo_set_locked_elt (CVT(clib_cuckoo_bucket) b, CVT(clib_cuckoo_kv) elt, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)

static void CV()	clib_cuckoo_set_elt (CVT(clib_cuckoo_bucket) b, CVT(clib_cuckoo_kv) elt, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)

static int CV()	clib_cuckoo_add_slow (CVT(clib_cuckoo) h, CVT(clib_cuckoo_kv) kvp, clib_cuckoo_lookup_info_t *lookup, u8 reduced_hash)

static int CV()	clib_cuckoo_add_fast (CVT(clib_cuckoo) h, clib_cuckoo_lookup_info_t lookup, CVT(clib_cuckoo_kv) *kvp, u8 reduced_hash)

void CV()	clib_cuckoo_garbage_collect (CVT(clib_cuckoo) *h)
	perform garbage collection More...

static void CV()	clib_cuckoo_rehash (CVT(clib_cuckoo) *h)
	expand and rehash a cuckoo hash More...

static int CV()	clib_cuckoo_bucket_search_internal (CVT(clib_cuckoo) h, uword bucket, CVT(clib_cuckoo_kv) kvp, CVT(clib_cuckoo_kv) **found)

int CV()	clib_cuckoo_add_del (CVT(clib_cuckoo) h, CVT(clib_cuckoo_kv) kvp, int is_add, int dont_overwrite)

u8 *CV()	format_cuckoo (u8 s, va_list args)

float CV()	clib_cuckoo_calculate_load_factor (CVT(clib_cuckoo) *h)

Macro Definition Documentation

◆ CLIB_CUCKOO_ASSERT_BUCKET_SORTED

#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED ( b )

Definition at line 160 of file cuckoo_template.c.

◆ CLIB_CUCKOO_DEBUG_PATH

#define CLIB_CUCKOO_DEBUG_PATH (1)

Definition at line 217 of file cuckoo_template.c.

◆ CLIB_CUCKOO_DEBUG_PATH_DETAIL

#define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)

Definition at line 218 of file cuckoo_template.c.

◆ CLIB_CUCKOO_DEEP_SELF_CHECK

#define CLIB_CUCKOO_DEEP_SELF_CHECK ( h )

Definition at line 159 of file cuckoo_template.c.

Function Documentation

◆ clib_cuckoo_add_del()

int CV() clib_cuckoo_add_del	(	CVT(clib_cuckoo) *	h,
		CVT(clib_cuckoo_kv) *	kvp,
		int	is_add,
		int	dont_overwrite
	)

Definition at line 820 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_add_fast()

static int CV() clib_cuckoo_add_fast	(	CVT(clib_cuckoo) *	h,
		clib_cuckoo_lookup_info_t *	lookup,
		CVT(clib_cuckoo_kv) *	kvp,
		u8	reduced_hash
	)

static

Definition at line 642 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_add_slow()

static int CV() clib_cuckoo_add_slow	(	CVT(clib_cuckoo) *	h,
		CVT(clib_cuckoo_kv) *	kvp,
		clib_cuckoo_lookup_info_t *	lookup,
		u8	reduced_hash
	)

static

Definition at line 578 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_bucket_search_internal()

static int CV() clib_cuckoo_bucket_search_internal	(	CVT(clib_cuckoo) *	h,
		uword	bucket,
		CVT(clib_cuckoo_kv) *	kvp,
		CVT(clib_cuckoo_kv) **	found
	)

static

Definition at line 798 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_bucket_tidy()

static void CV() clib_cuckoo_bucket_tidy ( CVT(clib_cuckoo_bucket) * b )

static

Definition at line 500 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_bucket_unlock()

static void CV() clib_cuckoo_bucket_unlock	(	CVT(clib_cuckoo_bucket) *	b,
		clib_cuckoo_bucket_aux_t	aux
	)

static

Definition at line 206 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_bucket_version_bump_and_lock()

static clib_cuckoo_bucket_aux_t CV() clib_cuckoo_bucket_version_bump_and_lock ( CVT(clib_cuckoo_bucket) * b )

static

Definition at line 194 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_calculate_load_factor()

float CV() clib_cuckoo_calculate_load_factor ( CVT(clib_cuckoo) * h )

Definition at line 969 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_elt_in_bucket_to_offset()

static uword CV() clib_cuckoo_elt_in_bucket_to_offset	(	CVT(clib_cuckoo_bucket) *	b,
		CVT(clib_cuckoo_kv) *	e
	)

inlinestatic

Definition at line 51 of file cuckoo_template.c.

Here is the caller graph for this function:

◆ clib_cuckoo_find_empty_slot_bfs()

static int CV() clib_cuckoo_find_empty_slot_bfs	(	CVT(clib_cuckoo) *	h,
		clib_cuckoo_lookup_info_t *	lookup,
		uword *	path_idx_out,
		uword *	found_bucket,
		CVT(clib_cuckoo_kv) **	found_elt
	)

static

Definition at line 372 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_free()

void CV() clib_cuckoo_free ( CVT(clib_cuckoo) * h )

Definition at line 188 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_free_elt_in_bucket()

static void CV() clib_cuckoo_free_elt_in_bucket	(	CVT(clib_cuckoo_bucket) *	b,
		CVT(clib_cuckoo_kv) *	elt
	)

static

Definition at line 538 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_free_locked_elt()

static void CV() clib_cuckoo_free_locked_elt ( CVT(clib_cuckoo_kv) * elt )

static

Definition at line 529 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_garbage_collect()

void CV() clib_cuckoo_garbage_collect ( CVT(clib_cuckoo) * h )

perform garbage collection

this function assumes there is no other thread touching the cuckoo hash, not even a reader, it's meant to be called from main thread in a stop-the-world situation

Definition at line 694 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_get_nbuckets()

static uword CV() clib_cuckoo_get_nbuckets ( CVT(clib_cuckoo) * h )

static

Definition at line 45 of file cuckoo_template.c.

Here is the caller graph for this function:

◆ clib_cuckoo_init()

void CV() clib_cuckoo_init	(	CVT(clib_cuckoo) *	h,
		const char *	name,
		uword	nbuckets,
		void()(CVT(clib_cuckoo) , void *)	garbage_callback,
		void *	garbage_ctx
	)

Definition at line 163 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_path_begin()

static clib_cuckoo_path_t* CV() clib_cuckoo_path_begin	(	CVT(clib_cuckoo) *	h,
		uword	bucket,
		uword	next_offset
	)

static

Definition at line 244 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_path_extend()

static uword CV() clib_cuckoo_path_extend	(	CVT(clib_cuckoo) *	h,
		uword	path_idx,
		uword	bucket,
		unsigned	offset
	)

static

create a new path based on existing path extended by adding a bucket and offset

Definition at line 268 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_path_get()

static clib_cuckoo_path_t* CV() clib_cuckoo_path_get ( CVT(clib_cuckoo) * h )

static

Definition at line 224 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_path_peek_offset()

static uword CV() clib_cuckoo_path_peek_offset ( const clib_cuckoo_path_t * path )

static

return the offset of the last element in the path

Definition at line 288 of file cuckoo_template.c.

Here is the caller graph for this function:

◆ clib_cuckoo_path_put()

static void CV() clib_cuckoo_path_put	(	CVT(clib_cuckoo) *	h,
		uword	path_idx
	)

static

Definition at line 235 of file cuckoo_template.c.

Here is the caller graph for this function:

◆ clib_cuckoo_path_walk()

static void clib_cuckoo_path_walk	(	CVT(clib_cuckoo) *	h,
		uword	path_idx,
		uword *	buckets,
		uword *	offsets
	)

static

walk the cuckoo path two ways, first backwards, extracting offsets, then forward, extracting buckets

buckets and offsets are arrays filled with elements extracted from path the arrays must be able to contain CLIB_CUCKOO_BFS_MAX_PATH_LENGTH elements

Definition at line 319 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_rehash()

static void CV() clib_cuckoo_rehash ( CVT(clib_cuckoo) * h )

static

expand and rehash a cuckoo hash

double the size of the hash table
move items to new locations derived from the new size

Definition at line 721 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_search()

int CV() clib_cuckoo_search	(	CVT(clib_cuckoo) *	h,
		CVT(clib_cuckoo_kv) *	search_v,
		CVT(clib_cuckoo_kv) *	return_v
	)

Definition at line 25 of file cuckoo_template.c.

Here is the call graph for this function:

◆ clib_cuckoo_set_elt()

static void CV() clib_cuckoo_set_elt	(	CVT(clib_cuckoo_bucket) *	b,
		CVT(clib_cuckoo_kv) *	elt,
		CVT(clib_cuckoo_kv) *	kvp,
		u8	reduced_hash
	)

static

Definition at line 567 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_set_locked_elt()

static void CV() clib_cuckoo_set_locked_elt	(	CVT(clib_cuckoo_bucket) *	b,
		CVT(clib_cuckoo_kv) *	elt,
		CVT(clib_cuckoo_kv) *	kvp,
		u8	reduced_hash
	)

static

Definition at line 555 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clib_cuckoo_swap_elts_in_bucket()

static void CV() clib_cuckoo_swap_elts_in_bucket	(	CVT(clib_cuckoo_bucket) *	b,
		uword	e1,
		uword	e2
	)

static

Definition at line 488 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CVT() [1/2]

static CVT ( clib_cuckoo_bucket )

static

Definition at line 39 of file cuckoo_template.c.

Here is the caller graph for this function:

◆ CVT() [2/2]

static CVT ( clib_cuckoo_kv )

static

Definition at line 298 of file cuckoo_template.c.

Here is the call graph for this function:

◆ format_cuckoo()

u8* CV() format_cuckoo	(	u8 *	s,
		va_list *	args
	)

Definition at line 914 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ format_cuckoo_bucket()

u8* CV() format_cuckoo_bucket	(	u8 *	s,
		va_list *	args
	)

Definition at line 75 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ format_cuckoo_elt()

u8* CV() format_cuckoo_elt	(	u8 *	s,
		va_list *	args
	)

Definition at line 59 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Macros

Functions

Macro Definition Documentation

◆ CLIB_CUCKOO_ASSERT_BUCKET_SORTED

◆ CLIB_CUCKOO_DEBUG_PATH

◆ CLIB_CUCKOO_DEBUG_PATH_DETAIL

◆ CLIB_CUCKOO_DEEP_SELF_CHECK

Function Documentation

◆ clib_cuckoo_add_del()

◆ clib_cuckoo_add_fast()

◆ clib_cuckoo_add_slow()

◆ clib_cuckoo_bucket_search_internal()

◆ clib_cuckoo_bucket_tidy()

◆ clib_cuckoo_bucket_unlock()

◆ clib_cuckoo_bucket_version_bump_and_lock()

◆ clib_cuckoo_calculate_load_factor()

◆ clib_cuckoo_elt_in_bucket_to_offset()

◆ clib_cuckoo_find_empty_slot_bfs()

◆ clib_cuckoo_free()

◆ clib_cuckoo_free_elt_in_bucket()

◆ clib_cuckoo_free_locked_elt()

◆ clib_cuckoo_garbage_collect()

◆ clib_cuckoo_get_nbuckets()

◆ clib_cuckoo_init()

◆ clib_cuckoo_path_begin()

◆ clib_cuckoo_path_extend()

◆ clib_cuckoo_path_get()

◆ clib_cuckoo_path_peek_offset()

◆ clib_cuckoo_path_put()

◆ clib_cuckoo_path_walk()

◆ clib_cuckoo_rehash()

◆ clib_cuckoo_search()

◆ clib_cuckoo_set_elt()

◆ clib_cuckoo_set_locked_elt()

◆ clib_cuckoo_swap_elts_in_bucket()

◆ CVT() [1/2]

◆ CVT() [2/2]

◆ format_cuckoo()

◆ format_cuckoo_bucket()

◆ format_cuckoo_elt()