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... 161 volatile clib_cuckoo_bucket_aux_t
aux;
165 }
CVT (clib_cuckoo_bucket);
167 #define clib_cuckoo_bucket_foreach_idx(var) \ 168 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++) 170 #if CLIB_CUCKOO_OPTIMIZE_UNROLL 171 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2 172 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 181 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4 182 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 195 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8 196 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 218 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 219 clib_cuckoo_bucket_foreach_idx (var) \ 225 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \ 226 clib_cuckoo_bucket_foreach_idx (var) \ 232 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \ 233 for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i) 235 #define clib_cuckoo_foreach_bucket(var, h, body) \ 238 CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \ 239 vec_foreach (var, __buckets) \ 246 typedef struct CV (clib_cuckoo)
249 CVT (clib_cuckoo_bucket) *
volatile buckets;
252 CVT (clib_cuckoo_bucket) * *to_be_freed;
264 uword *bfs_search_queue;
279 void (*garbage_callback) (
struct CV (clib_cuckoo) *
h,
void *garbage_ctx);
281 #if CLIB_CUCKOO_DEBUG_COUNTERS 283 u64 bfs_queue_emptied;
293 void (*garbage_callback) (
CVT (clib_cuckoo) *,
302 CVT (clib_cuckoo_kv) * add_v,
int is_add);
304 CVT (clib_cuckoo_kv) * search_v,
305 CVT (clib_cuckoo_kv) * return_v);
308 void *callback,
void *arg);
318 u32 v32 = ((
u32) hash) ^ ((
u32) (hash >> 32));
319 u16 v16 = ((
u16) v32) ^ ((
u16) (v32 >> 16));
320 u8 v8 = ((
u8) v16) ^ ((
u8) (v16 >> 8));
327 u64 mask = (nbuckets - 1);
328 return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
336 u64 mask = (nbuckets - 1);
338 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH 340 sizeof (*buckets), LOAD);
345 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH 347 sizeof (*buckets), LOAD);
360 CVT (clib_cuckoo_kv) * kvp,
363 clib_cuckoo_bucket_aux_t bucket_aux;
373 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 378 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH 386 reduced_hash == b->reduced_hashes[i] &&
388 0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
390 kvp->value = b->elts[i].value;
391 clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
392 if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
393 clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
396 return CLIB_CUCKOO_ERROR_SUCCESS;
401 return CLIB_CUCKOO_ERROR_AGAIN;
406 return CLIB_CUCKOO_ERROR_NOT_FOUND;
410 CVT (clib_cuckoo_kv) * kvp)
415 u64 hash =
CV (clib_cuckoo_hash) (kvp);
416 CVT (clib_cuckoo_bucket) * buckets;
418 buckets = h->buckets;
424 (buckets, lookup.
bucket1), kvp,
428 if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
430 return CLIB_CUCKOO_ERROR_SUCCESS;
435 (buckets, lookup.
bucket2), kvp,
#define clib_cuckoo_bucket_foreach_idx_unrolled(var, body)
sll srl srl sll sra u16x4 i
void CV() clib_cuckoo_foreach_key_value_pair(CVT(clib_cuckoo)*h, void *callback, void *arg)
void CV() clib_cuckoo_garbage_collect(CVT(clib_cuckoo)*h)
perform garbage collection
u64 start
bucket where this path begins
static clib_cuckoo_lookup_info_t CV() clib_cuckoo_calc_lookup(CVT(clib_cuckoo_bucket)*buckets, u64 hash)
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
int CV() clib_cuckoo_search(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*search_v, CVT(clib_cuckoo_kv)*return_v)
static u64 clib_cuckoo_get_other_bucket(u64 nbuckets, u64 bucket, u8 reduced_hash)
#define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH
void CV() clib_cuckoo_free(CVT(clib_cuckoo)*h)
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)
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 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 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)
float CV() clib_cuckoo_calc_load(CVT(clib_cuckoo)*h)
static u64 clib_cuckoo_bucket_aux_get_version(clib_cuckoo_bucket_aux_t aux)
u64 bucket
bucket at end of path
#define CLIB_CUCKOO_KVP_PER_BUCKET
int CV() clib_cuckoo_add_del(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*add_v, int is_add)
static hash_pair_t * lookup(void *v, uword key, enum lookup_opcode op, void *new_value, void *old_value)
void CV() clib_cuckoo_init(CVT(clib_cuckoo)*h, const char *name, u64 nbuckets, void(*garbage_callback)(CVT(clib_cuckoo)*, void *), void *garbage_ctx)
#define CLIB_PREFETCH(addr, size, type)
static int clib_cuckoo_bucket_aux_get_use_count(clib_cuckoo_bucket_aux_t aux)
u8 *CV() format_cuckoo(u8 *s, va_list *args)
#define CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
static int CV() clib_cuckoo_search_inline(CVT(clib_cuckoo)*h, CVT(clib_cuckoo_kv)*kvp)
static clib_cuckoo_bucket_aux_t clib_cuckoo_bucket_aux_set_writer_flag(clib_cuckoo_bucket_aux_t aux, int writer_flag)
#define CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
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)