28 #ifndef __included_cuckoo_template_h__ 29 #define __included_cuckoo_template_h__ 40 #ifndef CLIB_CUCKOO_TYPE 41 #error CLIB_CUCKOO_TYPE not defined 44 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS 45 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined 48 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET 49 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined 52 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET 53 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined 56 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH 57 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined 62 "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
64 #define _cv(a, b) a##b 65 #define __cv(a, b) _cv (a, b) 66 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE) 68 #define _cvt(a, b) a##b##_t 69 #define __cvt(a, b) _cvt (a, b) 70 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE) 74 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) 86 return (aux >> 1) & use_count_mask;
99 (use_count << 1) + writer_flag;
128 #define PATH_BITS_REQ \ 129 (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) 131 #if PATH_BITS_REQ <= 8 133 #elif PATH_BITS_REQ <= 16 135 #elif PATH_BITS_REQ <= 32 137 #elif PATH_BITS_REQ <= 64 140 #error no suitable datatype for path storage... 163 volatile clib_cuckoo_bucket_aux_t
aux;
167 }
CVT (clib_cuckoo_bucket);
169 #define clib_cuckoo_bucket_foreach_idx(var) \ 170 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++) 172 #if CLIB_CUCKOO_OPTIMIZE_UNROLL 173 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2 174 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 183 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4 184 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 197 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8 198 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 220 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 221 clib_cuckoo_bucket_foreach_idx (var) \ 227 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 228 clib_cuckoo_bucket_foreach_idx (var) \ 234 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \ 235 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i) 237 #define clib_cuckoo_foreach_bucket(var, h, body) \ 240 CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \ 241 vec_foreach (var, __buckets) \ 248 typedef struct CV (clib_cuckoo)
251 CVT (clib_cuckoo_bucket) *
volatile buckets;
254 CVT (clib_cuckoo_bucket) * *to_be_freed;
266 uword *bfs_search_queue;
281 void (*garbage_callback) (
struct CV (clib_cuckoo) *
h,
void *garbage_ctx);
283 #if CLIB_CUCKOO_DEBUG_COUNTERS 285 u64 bfs_queue_emptied;
295 void (*garbage_callback) (
CVT (clib_cuckoo) *,
304 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));
329 u64 mask = (nbuckets - 1);
330 return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
338 u64 mask = (nbuckets - 1);
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 388 reduced_hash == b->reduced_hashes[i] &&
390 0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
392 kvp->value = b->elts[i].value;
393 clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
394 if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
395 clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
398 return CLIB_CUCKOO_ERROR_SUCCESS;
403 return CLIB_CUCKOO_ERROR_AGAIN;
408 return CLIB_CUCKOO_ERROR_NOT_FOUND;
412 CVT (clib_cuckoo_kv) * kvp)
417 u64 hash =
CV (clib_cuckoo_hash) (kvp);
418 CVT (clib_cuckoo_bucket) * buckets;
420 buckets =
h->buckets;
426 (buckets, lookup.
bucket1), kvp,
430 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
432 return CLIB_CUCKOO_ERROR_SUCCESS;
437 (buckets, lookup.
bucket2), 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.
u64 clib_cuckoo_bucket_aux_t
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)
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo) *h, CVT(clib_cuckoo_kv) *add_v, int is_add)
#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 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
#define CLIB_CUCKOO_KVP_PER_BUCKET
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
#define CLIB_PREFETCH(addr, size, type)
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)
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
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)
#define CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_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)