*/
#include <vppinfra/vec.h>
-#include <vppinfra/cuckoo_template.h>
int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
CVT (clib_cuckoo_kv) * search_v,
CVT (clib_cuckoo_bucket) * bucket;
uword bucket_idx = 0;
/* *INDENT-OFF* */
- clib_cuckoo_foreach_bucket (bucket, h)
- {
+ clib_cuckoo_foreach_bucket (bucket, h, {
int i = 0;
int used = 0;
clib_cuckoo_bucket_foreach_idx (i)
if (!CV (clib_cuckoo_kv_is_free) (elt))
{
u64 hash = CV (clib_cuckoo_hash) (elt);
- clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) (
- CV (clib_cuckoo_get_snapshot) (h), hash);
+ clib_cuckoo_lookup_info_t lookup =
+ CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
CVT (clib_cuckoo_kv) kv = *elt;
int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
bucket->reduced_hashes[i]);
CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
}
- ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
+ ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
++used;
}
clib_cuckoo_bucket_aux_t aux = bucket->aux;
ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
++bucket_idx;
- }
+ });
/* *INDENT-ON* */
// CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
}
void *garbage_ctx)
{
uword log2_nbuckets = max_log2 (nbuckets);
- nbuckets = 1 << (log2_nbuckets);
+ nbuckets = 1ULL << (log2_nbuckets);
CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
CVT (clib_cuckoo_bucket) * buckets = NULL;
vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
CVT (clib_cuckoo_bucket) * bucket;
/* *INDENT-OFF* */
clib_cuckoo_foreach_bucket (
- bucket, h, { memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
+ bucket, h, { clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
/* *INDENT-ON* */
h->name = name;
h->garbage_callback = garbage_callback;
void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
{
- memset (h, 0, sizeof (*h));
+ clib_memset (h, 0, sizeof (*h));
}
static clib_cuckoo_bucket_aux_t
{
clib_cuckoo_path_t *path;
pool_get (h->paths, path);
- memset (path, 0, sizeof (*path));
+ clib_memset (path, 0, sizeof (*path));
#if CLIB_CUCKOO_DEBUG_PATH_DETAIL
CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
#endif
static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
{
/*
- * FIXME - improve performance by getting rid of this memset - make all
+ * FIXME - improve performance by getting rid of this clib_memset - make all
* functions in this file not rely on clib_cuckoo_kv_is_free but instead
* take use_count into account */
- memset (elt, 0xff, sizeof (*elt));
+ clib_memset (elt, 0xff, sizeof (*elt));
}
static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
CVT (clib_cuckoo_bucket) * bucket;
for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
{
- memset (bucket->elts, 0xff, sizeof (bucket->elts));
+ clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
}
/*
* this for loop manipulates the new (unseen) memory, so no locks
}
int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
- CVT (clib_cuckoo_kv) * kvp, int is_add)
+ CVT (clib_cuckoo_kv) * kvp, int is_add,
+ int dont_overwrite)
{
CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
kvp);
clib_cuckoo_lookup_info_t lookup;
u64 hash = CV (clib_cuckoo_hash) (kvp);
- clib_spinlock_lock (&h->writer_lock);
u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
+ clib_spinlock_lock (&h->writer_lock);
restart:
lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
CVT (clib_cuckoo_bucket) * b =
{
if (is_add)
{
- /* prevent readers reading this bucket while we switch the values */
- clib_cuckoo_bucket_aux_t aux =
- CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
- clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
- CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
- found, b->reduced_hashes[found - b->elts]);
- CV (clib_cuckoo_bucket_unlock) (b, aux);
+ if (dont_overwrite)
+ {
+ CLIB_CUCKOO_DBG ("Refused replacing existing %U",
+ CV (format_cuckoo_elt), found,
+ b->reduced_hashes[found - b->elts]);
+ rv = CLIB_CUCKOO_ERROR_AGAIN;
+ }
+ else
+ {
+ /* prevent readers reading this bucket while we switch the values */
+ clib_cuckoo_bucket_aux_t aux =
+ CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+ clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
+ CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
+ found, b->reduced_hashes[found - b->elts]);
+ CV (clib_cuckoo_bucket_unlock) (b, aux);
+ rv = CLIB_CUCKOO_ERROR_SUCCESS;
+ }
}
else
{
CV (clib_cuckoo_free_elt_in_bucket) (b, found);
+ rv = CLIB_CUCKOO_ERROR_SUCCESS;
}
- rv = CLIB_CUCKOO_ERROR_SUCCESS;
CLIB_CUCKOO_DEEP_SELF_CHECK (h);
goto unlock;
}
CLIB_CUCKOO_DEEP_SELF_CHECK (h);
if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
{
- CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1),
- CV (format_cuckoo_bucket),
- CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
+ CLIB_CUCKOO_DBG
+ ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
+ lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
+ CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
+ CV (format_cuckoo_bucket),
+ CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
/* slow path */
rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
CLIB_CUCKOO_DEEP_SELF_CHECK (h);