vppinfra: don't use memcmp to compare keys in cuckoo

[vpp.git] / src / vppinfra / cuckoo_template.h

diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h
index c3b2bc9..364c291 100644 (file)
--- a/src/vppinfra/cuckoo_template.h
+++ b/src/vppinfra/cuckoo_template.h
@@ -35,7 +35,6 @@
 #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
@@ -301,7 +300,8 @@ void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
 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);
@@ -383,11 +383,7 @@ always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
         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;
@@ -408,45 +404,49 @@ always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
   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 */