FD.io VPP
v21.01.1
Vector Packet Processing
|
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) |
#define CLIB_CUCKOO_ASSERT_BUCKET_SORTED | ( | b | ) |
Definition at line 160 of file cuckoo_template.c.
#define CLIB_CUCKOO_DEBUG_PATH (1) |
Definition at line 217 of file cuckoo_template.c.
#define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0) |
Definition at line 218 of file cuckoo_template.c.
#define CLIB_CUCKOO_DEEP_SELF_CHECK | ( | h | ) |
Definition at line 159 of file cuckoo_template.c.
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.
|
static |
Definition at line 642 of file cuckoo_template.c.
|
static |
Definition at line 578 of file cuckoo_template.c.
|
static |
Definition at line 798 of file cuckoo_template.c.
Definition at line 500 of file cuckoo_template.c.
|
static |
Definition at line 206 of file cuckoo_template.c.
|
static |
Definition at line 194 of file cuckoo_template.c.
|
static |
Definition at line 372 of file cuckoo_template.c.
Definition at line 188 of file cuckoo_template.c.
|
static |
Definition at line 538 of file cuckoo_template.c.
Definition at line 529 of file cuckoo_template.c.
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.
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.
|
static |
Definition at line 244 of file cuckoo_template.c.
|
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.
|
static |
Definition at line 224 of file cuckoo_template.c.
|
static |
return the offset of the last element in the path
Definition at line 288 of file cuckoo_template.c.
|
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.
expand and rehash a cuckoo hash
Definition at line 721 of file cuckoo_template.c.
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.
|
static |
Definition at line 567 of file cuckoo_template.c.
|
static |
Definition at line 555 of file cuckoo_template.c.
|
static |
Definition at line 488 of file cuckoo_template.c.
|
static |
|
static |
Definition at line 914 of file cuckoo_template.c.
Definition at line 75 of file cuckoo_template.c.
Definition at line 59 of file cuckoo_template.c.