cuckoo_template.h File Reference

Include dependency graph for cuckoo_template.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	clib_cuckoo_path_t
struct	CVT

Macros
#define	CV(a)   __cv (a, CLIB_CUCKOO_TYPE)
#define	CVT(a)   __cvt (a, CLIB_CUCKOO_TYPE)
#define	CLIB_CUCKOO_USE_COUNT_BIT_WIDTH   (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
#define	PATH_BITS_REQ   (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
#define	clib_cuckoo_bucket_foreach_idx(var)   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
#define	clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
#define	clib_cuckoo_bucket_foreach_elt_index(var, bucket)   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
#define	clib_cuckoo_foreach_bucket(var, h, body)

Typedefs
typedef u64	clib_cuckoo_bucket_aux_t
typedef u8	path_data_t

Functions
	STATIC_ASSERT (CLIB_CUCKOO_KVP_PER_BUCKET==(1<< CLIB_CUCKOO_LOG2_KVP_PER_BUCKET),"CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET")
static u64	clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
static int	clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
static int	clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
static clib_cuckoo_bucket_aux_t	clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
static clib_cuckoo_bucket_aux_t	clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
static clib_cuckoo_bucket_aux_t	clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux, int use_count)
static clib_cuckoo_bucket_aux_t	clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux, int writer_flag)
struct	CV (clib_cuckoo)
	CVT (clib_cuckoo)
void CV()	clib_cuckoo_init (CVT(clib_cuckoo)*h, const char *name, u64 nbuckets, void(*garbage_callback)(CVT(clib_cuckoo)*, void *), void *garbage_ctx)
void CV()	clib_cuckoo_garbage_collect (CVT(clib_cuckoo)*h)
	perform garbage collection More...
void CV()	clib_cuckoo_free (CVT(clib_cuckoo)*h)
int CV()	clib_cuckoo_add_del (CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*add_v, int is_add)
int CV()	clib_cuckoo_search (CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*search_v, CVT(clib_cuckoo_kv)*return_v)
void CV()	clib_cuckoo_foreach_key_value_pair (CVT(clib_cuckoo)*h, void *callback, void *arg)
float CV()	clib_cuckoo_calc_load (CVT(clib_cuckoo)*h)
format_function_t	CV (format_cuckoo)
format_function_t	CV (format_cuckoo_kvp)
static u8	clib_cuckoo_reduce_hash (u64 hash)
static u64	clib_cuckoo_get_other_bucket (u64 nbuckets, u64 bucket, u8 reduced_hash)
static clib_cuckoo_lookup_info_t CV()	clib_cuckoo_calc_lookup (CVT(clib_cuckoo_bucket)*buckets, u64 hash)
static int CV()	clib_cuckoo_bucket_search (CVT(clib_cuckoo_bucket)*b, CVT(clib_cuckoo_kv)*kvp, u8 reduced_hash)
	search for key within bucket More...
static int CV()	clib_cuckoo_search_inline (CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*kvp)

Macro Definition Documentation

#define clib_cuckoo_bucket_foreach_elt_index	(		var,
			bucket
	)		for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)

Definition at line 234 of file cuckoo_template.h.

#define clib_cuckoo_bucket_foreach_idx

(

var

)

for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)

Definition at line 169 of file cuckoo_template.h.

#define clib_cuckoo_bucket_foreach_idx_unrolled	(		var,
			body
	)

Value:

clib_cuckoo_bucket_foreach_idx (var)                     \
  {                                                        \
    body;                                                  \
  }

Definition at line 227 of file cuckoo_template.h.

#define clib_cuckoo_foreach_bucket	(		var,
			h,
			body
	)

Value:

do                                                    \
    {                                                   \
      CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
      vec_foreach (var, __buckets)                      \
      {                                                 \
        body;                                           \
      }                                                 \
    }                                                   \
  while (0)

Definition at line 237 of file cuckoo_template.h.

#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH   (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

Definition at line 74 of file cuckoo_template.h.

#define CV

(

a

)

__cv (a, CLIB_CUCKOO_TYPE)

Definition at line 66 of file cuckoo_template.h.

#define CVT

(

a

)

__cvt (a, CLIB_CUCKOO_TYPE)

Definition at line 70 of file cuckoo_template.h.

#define PATH_BITS_REQ   (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

Definition at line 128 of file cuckoo_template.h.

Typedef Documentation

typedef u64 clib_cuckoo_bucket_aux_t

Definition at line 72 of file cuckoo_template.h.

typedef u8 path_data_t

Definition at line 132 of file cuckoo_template.h.

Function Documentation

int CV() clib_cuckoo_add_del	(	CVT(clib_cuckoo)*	h,
		CVT(clib_cuckoo_kv)*	add_v,
		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 clib_cuckoo_bucket_aux_get_use_count ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 83 of file cuckoo_template.h.

Here is the caller graph for this function:

static u64 clib_cuckoo_bucket_aux_get_version ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 77 of file cuckoo_template.h.

Here is the caller graph for this function:

static int clib_cuckoo_bucket_aux_get_writer_flag ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 90 of file cuckoo_template.h.

Here is the caller graph for this function:

static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_pack ( u64  version, int  use_count, int  writer_flag  )

inlinestatic

Definition at line 96 of file cuckoo_template.h.

Here is the caller graph for this function:

static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_use_count ( clib_cuckoo_bucket_aux_t  aux, int  use_count  )

inlinestatic

Definition at line 111 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_version ( clib_cuckoo_bucket_aux_t  aux, u64  version  )

inlinestatic

Definition at line 103 of file cuckoo_template.h.

Here is the call graph for this function:

static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_writer_flag ( clib_cuckoo_bucket_aux_t  aux, int  writer_flag  )

inlinestatic

Definition at line 120 of file cuckoo_template.h.

Here is the call graph for this function:

static int CV() clib_cuckoo_bucket_search ( CVT(clib_cuckoo_bucket)*  b, CVT(clib_cuckoo_kv)*  kvp, u8  reduced_hash  )

inlinestatic

search for key within bucket

Definition at line 360 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

float CV() clib_cuckoo_calc_load

(

CVT(clib_cuckoo)*

h

)

Here is the caller graph for this function:

static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup ( CVT(clib_cuckoo_bucket)*  buckets, u64  hash  )

inlinestatic

Definition at line 334 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void CV() clib_cuckoo_foreach_key_value_pair	(	CVT(clib_cuckoo)*	h,
		void *	callback,
		void *	arg
	)

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 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 u64 clib_cuckoo_get_other_bucket ( u64  nbuckets, u64  bucket, u8  reduced_hash  )

inlinestatic

Definition at line 327 of file cuckoo_template.h.

Here is the caller graph for this function:

void CV() clib_cuckoo_init	(	CVT(clib_cuckoo)*	h,
		const char *	name,
		u64	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 u8 clib_cuckoo_reduce_hash ( u64  hash )

inlinestatic

Definition at line 318 of file cuckoo_template.h.

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 int CV() clib_cuckoo_search_inline ( CVT(clib_cuckoo)*  h, CVT(clib_cuckoo_kv)*  kvp  )

inlinestatic

Definition at line 411 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

struct CV

(

clib_cuckoo

)

vector of elements containing key-value pairs and auxiliary data

garbage to be freed once its safe to do so ..

hash table name

pool of cuckoo paths (reused when doing bfd search)

vector used as queue when doing cuckoo path searches - holds offsets in paths pool

writer lock - whether this lock is taken or not has zero effect on readers

caller context passed to callback with garbage notification

garbage notify function - called when some garbage needs to be collected in main thread while other threads are stopped

Definition at line 248 of file cuckoo_template.h.

Here is the call graph for this function:

format_function_t CV

(

format_cuckoo

)

format_function_t CV

(

format_cuckoo_kvp

)

CVT

(

clib_cuckoo

)

STATIC_ASSERT

(

CLIB_CUCKOO_KVP_PER_BUCKET

= =(1<< CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

)