vppinfra: add new bihash exports

This adds two new exported functions
for the clib_bihash

* clib_bihash_add_with_overwrite_cb allowing
to pass a callback to be called on overwriting
a key with bucket lock held.
* clib_bihash_add_del_with_hash doing an add_del
with a precomputed hash.

Type: feature

Change-Id: I1590c933fa7cf21e6a8ada89b3456a60c4988244
Signed-off-by: Nathan Skrzypczak <nathan.skrzypczak@gmail.com>

1 files changed, 153 insertions, 63 deletions

diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h
index 7c7e5179961..f6d32ce0b56 100644
--- a/src/vppinfra/bihash_doc.h
+++ b/src/vppinfra/bihash_doc.h
@@ -90,83 +90,172 @@ static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
 /** Get clib mheap offset given a pointer */
 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
 
-/** initialize a bounded index extensible hash table
-
-    @param h - the bi-hash table to initialize
-    @param name - name of the hash table
-    @param nbuckets - the number of buckets, will be rounded up to
-a power of two
-    @param memory_size - clib mheap size, in bytes
-*/
-
+/**
+ * initialize a bounded index extensible hash table
+ *
+ * @param h - the bi-hash table to initialize
+ * @param name - name of the hash table
+ * @param nbuckets - the number of buckets, will be rounded up to
+ * a power of two
+ * @param memory_size - clib mheap size, in bytes
+ */
 void clib_bihash_init
   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 
-/** Destroy a bounded index extensible hash table
-    @param h - the bi-hash table to free
-*/
+/**
+ * initialize a bounded index extensible hash table with arguments passed as
+ * a struct
+ *
+ * @param a - initialization parameters
+ *   h - the bi-hash table to initialize;
+ *   name - name of the hash table
+ *   nbuckets - the number of buckets, will be rounded up to a power of two
+ *   memory_size - clib mheap size, in bytes
+ *   format_function_t - format function for the bihash kv pairs
+ *   instantiate_immediately - allocate memory right away
+ *   dont_add_to_all_bihash_list - dont mention in 'show bihash'
+ */
+void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a);
 
-void clib_bihash_free (clib_bihash * h);
+/**
+ * Set the formating function for the bihash
+ *
+ * @param h - the bi-hash table
+ * @param kvp_fmt_fn - the format function
+ */
+void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
+					 format_function_t *kvp_fmt_fn);
 
-/** Add or delete a (key,value) pair from a bi-hash table
+/**
+ * Destroy a bounded index extensible hash table
+ *
+ * @param h - the bi-hash table to free
+ */
+void clib_bihash_free (clib_bihash *h);
 
-    @param h - the bi-hash table to search
-    @param add_v - the (key,value) pair to add
-    @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
-    @returns 0 on success, < 0 on error
-    @note This function will replace an existing (key,value) pair if the
-    new key matches an existing key
-*/
+/**
+ * Add or delete a (key,value) pair from a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 
+/**
+ * Add or delete a (key,value) pair from a bi-hash table, using a pre-computed
+ * hash
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param hash - the precomputed hash of the key
+ * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
+					BVT (clib_bihash_kv) * add_v, u64 hash,
+					int is_add);
 
-/** Search a bi-hash table, use supplied hash code
+/**
+ * Add a (key,value) pair to a bi-hash table, and tries to free stale entries
+ * on collisions with passed filter.
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param is_stale_cb - callback receiving a kv pair, returning 1 if the kv is
+ * stale and can be overwriten. This will be called on adding a kv in a full
+ * page before trying to split & rehash its bucket.
+ * @param arg - opaque arguement passed to is_stale_cb
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_or_overwrite_stale) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 
-    @param h - the bi-hash table to search
-    @param hash - the hash code
-    @param in_out_kv - (key,value) pair containing the search key
-    @returns 0 on success (with in_out_kv set), < 0 on error
-*/
-int clib_bihash_search_inline_with_hash
-  (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
+/**
+ * Add a (key,value) pair to a bi-hash table, calling a callback on overwrite
+ * with the bucket lock held.
+ *
+ * @param h - the bi-hash table to search
+ * @param add_v - the (key,value) pair to add
+ * @param overwrite_cb - callback called when overwriting a key, allowing
+ * you to cleanup the value with the bucket lock held.
+ * @param arg - opaque arguement passed to overwrite_cb
+ * @returns 0 on success, < 0 on error
+ * @note This function will replace an existing (key,value) pair if the
+ * new key matches an existing key
+ */
+int BV (clib_bihash_add_with_overwrite_cb) (
+  BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
+  void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 
-/** Search a bi-hash table
+/**
+ * Tells if the bihash was initialised (i.e. mem allocated by first add)
+ *
+ * @param h - the bi-hash table to search
+ */
+int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h);
 
-    @param h - the bi-hash table to search
-    @param in_out_kv - (key,value) pair containing the search key
-    @returns 0 on success (with in_out_kv set), < 0 on error
-*/
-int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
+/**
+ * Search a bi-hash table, use supplied hash code
+ *
+ * @param h - the bi-hash table to search
+ * @param hash - the hash code
+ * @param in_out_kv - (key,value) pair containing the search key
+ * @returns 0 on success (with in_out_kv set), < 0 on error
+ */
+int clib_bihash_search_inline_with_hash (clib_bihash *h, u64 hash,
+					 clib_bihash_kv *in_out_kv);
 
-/** Prefetch a bi-hash bucket given a hash code
+/**
+ * Search a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param in_out_kv - (key,value) pair containing the search key
+ * @returns 0 on success (with in_out_kv set), < 0 on error
+ */
+int clib_bihash_search_inline (clib_bihash *h, clib_bihash_kv *in_out_kv);
 
-    @param h - the bi-hash table to search
-    @param hash - the hash code
-    @note see also clib_bihash_hash to compute the code
-*/
+/**
+ * Prefetch a bi-hash bucket given a hash code
+ *
+ * @param h - the bi-hash table to search
+ * @param hash - the hash code
+ * @note see also clib_bihash_hash to compute the code
+ */
 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
 
-/** Prefetch bi-hash (key,value) data given a hash code
-
-    @param h - the bi-hash table to search
-    @param hash - the hash code
-    @note assumes that the bucket has been prefetched, see
-     clib_bihash_prefetch_bucket
-*/
+/**
+ * Prefetch bi-hash (key,value) data given a hash code
+ *
+ * @param h - the bi-hash table to search
+ * @param hash - the hash code
+ * @note assumes that the bucket has been prefetched, see
+ * clib_bihash_prefetch_bucket
+ */
 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
 
-/** Search a bi-hash table
-
-    @param h - the bi-hash table to search
-    @param search_key - (key,value) pair containing the search key
-    @param valuep - (key,value) set to search result
-    @returns 0 on success (with valuep set), < 0 on error
-    @note used in situations where key modification is not desired
-*/
+/**
+ * Search a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param search_key - (key,value) pair containing the search key
+ * @param valuep - (key,value) set to search result
+ * @returns 0 on success (with valuep set), < 0 on error
+ * @note used in situations where key modification is not desired
+ */
 int clib_bihash_search_inline_2
   (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
 
-/* Calback function for walking a bihash table
+/**
+ * Calback function for walking a bihash table
  *
  * @param kv - KV pair visited
  * @param ctx - Context passed to the walk
@@ -175,13 +264,14 @@ int clib_bihash_search_inline_2
 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
 						      void *ctx);
 
-/** Visit active (key,value) pairs in a bi-hash table
-
-    @param h - the bi-hash table to search
-    @param callback - function to call with each active (key,value) pair
-    @param arg - arbitrary second argument passed to the callback function
-    First argument is the (key,value) pair to visit
-*/
+/**
+ * Visit active (key,value) pairs in a bi-hash table
+ *
+ * @param h - the bi-hash table to search
+ * @param callback - function to call with each active (key,value) pair
+ * @param arg - arbitrary second argument passed to the callback function
+ * First argument is the (key,value) pair to visit
+ */
 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 					 clib_bihash_foreach_key_value_pair_cb
 					 * callback, void *arg);