28 #ifndef __included_cuckoo_template_h__ 29 #define __included_cuckoo_template_h__ 39 #ifndef CLIB_CUCKOO_TYPE 40 #error CLIB_CUCKOO_TYPE not defined 43 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS 44 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined 47 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET 48 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined 51 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET 52 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined 55 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH 56 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined 61 "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
63 #define _cv(a, b) a##b 64 #define __cv(a, b) _cv (a, b) 65 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE) 67 #define _cvt(a, b) a##b##_t 68 #define __cvt(a, b) _cvt (a, b) 69 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE) 73 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) 85 return (aux >> 1) & use_count_mask;
98 (use_count << 1) + writer_flag;
127 #define PATH_BITS_REQ \ 128 (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) 130 #if PATH_BITS_REQ <= 8 132 #elif PATH_BITS_REQ <= 16 134 #elif PATH_BITS_REQ <= 32 136 #elif PATH_BITS_REQ <= 64 139 #error no suitable datatype for path storage... 162 volatile clib_cuckoo_bucket_aux_t
aux;
166 }
CVT (clib_cuckoo_bucket);
168 #define clib_cuckoo_bucket_foreach_idx(var) \ 169 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++) 171 #if CLIB_CUCKOO_OPTIMIZE_UNROLL 172 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2 173 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 182 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4 183 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 196 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8 197 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 219 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 220 clib_cuckoo_bucket_foreach_idx (var) \ 226 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 227 clib_cuckoo_bucket_foreach_idx (var) \ 233 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \ 234 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i) 236 #define clib_cuckoo_foreach_bucket(var, h, body) \ 239 CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \ 240 vec_foreach (var, __buckets) \ 247 typedef struct CV (clib_cuckoo)
250 CVT (clib_cuckoo_bucket) *
volatile buckets;
253 CVT (clib_cuckoo_bucket) * *to_be_freed;
265 uword *bfs_search_queue;
280 void (*garbage_callback) (
struct CV (clib_cuckoo) *
h,
void *garbage_ctx);
282 #if CLIB_CUCKOO_DEBUG_COUNTERS 284 u64 bfs_queue_emptied;
294 void (*garbage_callback) (
CVT (clib_cuckoo) *,
303 CVT (clib_cuckoo_kv) * add_v,
int is_add,
306 CVT (clib_cuckoo_kv) * search_v,
307 CVT (clib_cuckoo_kv) * return_v);
310 void *callback,
void *arg);
320 u32 v32 = ((
u32) hash) ^ ((
u32) (hash >> 32));
321 u16 v16 = ((
u16) v32) ^ ((
u16) (v32 >> 16));
322 u8 v8 = ((
u8) v16) ^ ((
u8) (v16 >> 8));
330 return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
340 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH 342 sizeof (*buckets), LOAD);
347 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH 349 sizeof (*buckets), LOAD);
362 CVT (clib_cuckoo_kv) * kvp,
365 clib_cuckoo_bucket_aux_t bucket_aux;
375 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 380 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 386 if (CV (clib_cuckoo_key_compare) (kvp->key, b->elts[i].key))
388 kvp->value = b->elts[i].value;
389 clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
390 if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
391 clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
394 return CLIB_CUCKOO_ERROR_SUCCESS;
399 return CLIB_CUCKOO_ERROR_AGAIN;
404 return CLIB_CUCKOO_ERROR_NOT_FOUND;
409 CVT (clib_cuckoo_kv) * kvp)
411 CVT (clib_cuckoo_bucket) * buckets =
h->buckets;
412 uword bucket1, bucket2;
418 bucket1 = hash &
mask;
425 if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
426 return CLIB_CUCKOO_ERROR_SUCCESS;
444 CVT (clib_cuckoo_kv) * kvp)
446 u64 hash =
CV (clib_cuckoo_hash) (kvp);
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
int CV() clib_cuckoo_search(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *search_v, CVT(clib_cuckoo_kv) *return_v)
u64 start
bucket where this path begins
volatile clib_cuckoo_bucket_aux_t aux
auxiliary data - version, writer flag and used count
u8 length
length of the path
Fixed length block allocator.
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *add_v, int is_add, int dont_overwrite)
u64 clib_cuckoo_bucket_aux_t
#define CLIB_CUCKOO_KVP_PER_BUCKET
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_get_other_bucket(u64 nbuckets, u64 bucket, u8 reduced_hash)
#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH
static u8 clib_cuckoo_reduce_hash(u64 hash)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_version(clib_cuckoo_bucket_aux_t aux, u64 version)
float CV() clib_cuckoo_calc_load(CVT(clib_cuckoo) *h)
void CV() clib_cuckoo_init(CVT(clib_cuckoo) *h, const char *name, uword nbuckets, void(*garbage_callback)(CVT(clib_cuckoo) *, void *), void *garbage_ctx)
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_use_count(clib_cuckoo_bucket_aux_t aux, int use_count)
static u64 clib_cuckoo_bucket_aux_get_version(clib_cuckoo_bucket_aux_t aux)
u64 bucket
bucket at end of path
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
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
static int CV() clib_cuckoo_search_inline_with_hash(CVT(clib_cuckoo) *h, u64 hash, CVT(clib_cuckoo_kv) *kvp)
#define CLIB_PREFETCH(addr, size, type)
sll srl srl sll sra u16x4 i
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
void CV() clib_cuckoo_foreach_key_value_pair(CVT(clib_cuckoo) *h, void *callback, void *arg)
u8 *CV() format_cuckoo(u8 *s, va_list *args)
vl_api_fib_path_t paths[n_paths]
void CV() clib_cuckoo_free(CVT(clib_cuckoo) *h)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_writer_flag(clib_cuckoo_bucket_aux_t aux, int writer_flag)
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket) *buckets, u64 hash)
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *kvp)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo) *h)
perform garbage collection
path_data_t data
holds compressed offsets in buckets along path
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)