#include <vppinfra/error.h>
#include <vppinfra/hash.h>
#include <vppinfra/cache.h>
-#include <vppinfra/cuckoo_8_8.h>
#ifndef CLIB_CUCKOO_TYPE
#error CLIB_CUCKOO_TYPE not defined
} CVT (clib_cuckoo);
void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
- u64 nbuckets,
+ uword nbuckets,
void (*garbage_callback) (CVT (clib_cuckoo) *,
void *),
void *garbage_ctx);
void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
- CVT (clib_cuckoo_kv) * add_v, int is_add);
+ CVT (clib_cuckoo_kv) * add_v, int is_add,
+ int dont_overwrite);
int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
CVT (clib_cuckoo_kv) * search_v,
CVT (clib_cuckoo_kv) * return_v);
break;
}
#endif
- if (
-#if CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
- reduced_hash == b->reduced_hashes[i] &&
-#endif
- 0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
+ if (CV (clib_cuckoo_key_compare) (kvp->key, b->elts[i].key))
{
kvp->value = b->elts[i].value;
clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
return CLIB_CUCKOO_ERROR_NOT_FOUND;
}
-always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
- CVT (clib_cuckoo_kv) * kvp)
+always_inline int
+CV (clib_cuckoo_search_inline_with_hash) (CVT (clib_cuckoo) * h, u64 hash,
+ CVT (clib_cuckoo_kv) * kvp)
{
- clib_cuckoo_lookup_info_t lookup;
+ CVT (clib_cuckoo_bucket) * buckets = h->buckets;
+ uword bucket1, bucket2;
+ u8 reduced_hash;
+ u64 nbuckets = vec_len (buckets);
+ u64 mask = nbuckets - 1;
int rv;
- u64 hash = CV (clib_cuckoo_hash) (kvp);
- CVT (clib_cuckoo_bucket) * buckets;
+ bucket1 = hash & mask;
+ reduced_hash = clib_cuckoo_reduce_hash (hash);
+
again:
- buckets = h->buckets;
- lookup = CV (clib_cuckoo_calc_lookup) (buckets, hash);
- do
- {
- rv =
- CV (clib_cuckoo_bucket_search) (vec_elt_at_index
- (buckets, lookup.bucket1), kvp,
- lookup.reduced_hash);
- }
- while (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv));
- if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
- {
- return CLIB_CUCKOO_ERROR_SUCCESS;
- }
+ rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket1),
+ kvp, reduced_hash);
+
+ if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
+ return CLIB_CUCKOO_ERROR_SUCCESS;
+
+ if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
+ goto again;
+
+ bucket2 = clib_cuckoo_get_other_bucket (nbuckets, bucket1, reduced_hash);
+ rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket2),
+ kvp, reduced_hash);
+
+ /* change to 2nd bucket could bump the item to 1st bucket and the bucket
+ * indexes might not even be valid anymore - restart the search */
+ if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
+ goto again;
- rv =
- CV (clib_cuckoo_bucket_search) (vec_elt_at_index
- (buckets, lookup.bucket2), kvp,
- lookup.reduced_hash);
- if (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv))
- {
- /*
- * change to 2nd bucket could bump the item to 1st bucket and the bucket
- * indexes might not even be valid anymore - restart the search
- */
- goto again;
- }
return rv;
}
+always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
+ CVT (clib_cuckoo_kv) * kvp)
+{
+ u64 hash = CV (clib_cuckoo_hash) (kvp);
+ return CV (clib_cuckoo_search_inline_with_hash) (h, hash, kvp);
+}
+
#endif /* __included_cuckoo_template_h__ */
/** @endcond */