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, uword 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 dont_overwrite)
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_with_hash (CVT(clib_cuckoo) *h, u64 hash, CVT(clib_cuckoo_kv) *kvp)
static int CV()	clib_cuckoo_search_inline (CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp)

Macro Definition Documentation

clib_cuckoo_bucket_foreach_elt_index

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

Definition at line 233 of file cuckoo_template.h.

clib_cuckoo_bucket_foreach_idx

#define clib_cuckoo_bucket_foreach_idx

(

var

)

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

Definition at line 168 of file cuckoo_template.h.

clib_cuckoo_bucket_foreach_idx_unrolled

#define clib_cuckoo_bucket_foreach_idx_unrolled	(		var,
			body
	)

Value:

  clib_cuckoo_bucket_foreach_idx (var)                     \
  {                                                        \
    body;                                                  \
  }

Definition at line 226 of file cuckoo_template.h.

clib_cuckoo_foreach_bucket

#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 236 of file cuckoo_template.h.

CLIB_CUCKOO_USE_COUNT_BIT_WIDTH

#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH   (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

Definition at line 73 of file cuckoo_template.h.

CV

#define CV

(

a

)

__cv (a, CLIB_CUCKOO_TYPE)

Definition at line 65 of file cuckoo_template.h.

CVT

#define CVT

(

a

)

__cvt (a, CLIB_CUCKOO_TYPE)

Definition at line 69 of file cuckoo_template.h.

PATH_BITS_REQ

#define PATH_BITS_REQ   (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

Definition at line 127 of file cuckoo_template.h.

Typedef Documentation

clib_cuckoo_bucket_aux_t

typedef u64 clib_cuckoo_bucket_aux_t

Definition at line 71 of file cuckoo_template.h.

path_data_t

typedef u8 path_data_t

Definition at line 131 of file cuckoo_template.h.

Function Documentation

clib_cuckoo_add_del()

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

static int clib_cuckoo_bucket_aux_get_use_count ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 82 of file cuckoo_template.h.

Here is the caller graph for this function:

clib_cuckoo_bucket_aux_get_version()

static u64 clib_cuckoo_bucket_aux_get_version ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 76 of file cuckoo_template.h.

Here is the caller graph for this function:

clib_cuckoo_bucket_aux_get_writer_flag()

static int clib_cuckoo_bucket_aux_get_writer_flag ( clib_cuckoo_bucket_aux_t  aux )

inlinestatic

Definition at line 89 of file cuckoo_template.h.

Here is the caller graph for this function:

clib_cuckoo_bucket_aux_pack()

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

inlinestatic

Definition at line 95 of file cuckoo_template.h.

Here is the caller graph for this function:

clib_cuckoo_bucket_aux_set_use_count()

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 110 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

clib_cuckoo_bucket_aux_set_version()

static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_version ( clib_cuckoo_bucket_aux_t  aux, u64  version  )

inlinestatic

Definition at line 102 of file cuckoo_template.h.

Here is the call graph for this function:

clib_cuckoo_bucket_aux_set_writer_flag()

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 119 of file cuckoo_template.h.

Here is the call graph for this function:

clib_cuckoo_bucket_search()

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:

clib_cuckoo_calc_load()

float CV() clib_cuckoo_calc_load

(

CVT(clib_cuckoo) *

h

)

clib_cuckoo_calc_lookup()

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:

clib_cuckoo_foreach_key_value_pair()

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

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_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_other_bucket()

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:

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_reduce_hash()

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:

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_search_inline()

static int CV() clib_cuckoo_search_inline ( CVT(clib_cuckoo) *  h, CVT(clib_cuckoo_kv) *  kvp  )

inlinestatic

Definition at line 443 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

clib_cuckoo_search_inline_with_hash()

static int CV() clib_cuckoo_search_inline_with_hash ( CVT(clib_cuckoo) *  h, u64  hash, CVT(clib_cuckoo_kv) *  kvp  )

inlinestatic

Definition at line 408 of file cuckoo_template.h.

Here is the call graph for this function:

Here is the caller graph for this function:

CV() [1/3]

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 247 of file cuckoo_template.h.

CV() [2/3]

format_function_t CV

(

format_cuckoo

)

CV() [3/3]

format_function_t CV

(

format_cuckoo_kvp

)

CVT()

CVT

(

clib_cuckoo

)

STATIC_ASSERT()

STATIC_ASSERT

(

CLIB_CUCKOO_KVP_PER_BUCKET

= =(1<< CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)

)