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)
u8 *CV()	format_cuckoo (u8 *s, va_list *args)
float CV()	clib_cuckoo_calculate_load_factor (CVT(clib_cuckoo)*h)

Macro Definition Documentation

#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED

(

b

)

Definition at line 162 of file cuckoo_template.c.

#define CLIB_CUCKOO_DEBUG_PATH   (1)

Definition at line 219 of file cuckoo_template.c.

#define CLIB_CUCKOO_DEBUG_PATH_DETAIL   (0)

Definition at line 220 of file cuckoo_template.c.

#define CLIB_CUCKOO_DEEP_SELF_CHECK

(

h

)

Definition at line 161 of file cuckoo_template.c.

Function Documentation

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

Definition at line 822 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 644 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 580 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 800 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 502 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 208 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 196 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

float CV() clib_cuckoo_calculate_load_factor

(

CVT(clib_cuckoo)*

h

)

Definition at line 956 of file cuckoo_template.c.

Here is the call graph for this function:

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

inlinestatic

Definition at line 52 of file cuckoo_template.c.

Here is the caller graph for this function:

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 374 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

void CV() clib_cuckoo_free

(

CVT(clib_cuckoo)*

h

)

Definition at line 190 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 540 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 531 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 696 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 46 of file cuckoo_template.c.

Here is the caller graph for this function:

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 165 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 246 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 270 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 226 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 290 of file cuckoo_template.c.

Here is the caller graph for this function:

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

static

Definition at line 237 of file cuckoo_template.c.

Here is the caller graph for this function:

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 321 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 723 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 26 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 569 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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 557 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

static

Definition at line 490 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

static CVT ( clib_cuckoo_bucket  )

static

Definition at line 40 of file cuckoo_template.c.

Here is the caller graph for this function:

static CVT ( clib_cuckoo_kv  )

static

Definition at line 300 of file cuckoo_template.c.

Here is the call graph for this function:

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

Definition at line 901 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 76 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 60 of file cuckoo_template.c.

Here is the call graph for this function:

Here is the caller graph for this function: