cuckoo_template.c File Reference

Include dependency graph for cuckoo_template.c:

Go to the source code of this file.

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:

Here is the caller 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:

Here is the caller 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:

Here is the caller 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:

Here is the caller 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

1. double the size of the hash table
2. 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:

Here is the caller 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: