diff options
| -rw-r--r-- | src/vppinfra/bihash_doc.h | 216 | ||||
| -rw-r--r-- | src/vppinfra/bihash_template.c | 31 | ||||
| -rw-r--r-- | src/vppinfra/bihash_template.h | 7 |
3 files changed, 185 insertions, 69 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); diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 1c9f3b8708a..48830508114 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -672,9 +672,10 @@ BV (split_and_rehash_linear) return new_values; } -static_always_inline int BV (clib_bihash_add_del_inline_with_hash) - (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add, - int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) +static_always_inline int BV (clib_bihash_add_del_inline_with_hash) ( + BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add, + int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *is_stale_arg, + void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *overwrite_arg) { BVT (clib_bihash_bucket) * b, tmp_b; BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy; @@ -776,7 +777,8 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) BV (clib_bihash_unlock_bucket) (b); return (-2); } - + if (overwrite_cb) + overwrite_cb (&(v->kvp[i]), overwrite_arg); clib_memcpy_fast (&(v->kvp[i].value), &add_v->value, sizeof (add_v->value)); BV (clib_bihash_unlock_bucket) (b); @@ -812,7 +814,7 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) { for (i = 0; i < limit; i++) { - if (is_stale_cb (&(v->kvp[i]), arg)) + if (is_stale_cb (&(v->kvp[i]), is_stale_arg)) { clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); CLIB_MEMORY_STORE_BARRIER (); @@ -994,7 +996,15 @@ static_always_inline int BV (clib_bihash_add_del_inline) { u64 hash = BV (clib_bihash_hash) (add_v); return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, - is_stale_cb, arg); + is_stale_cb, arg, 0, 0); +} + +int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h, + BVT (clib_bihash_kv) * add_v, u64 hash, + int is_add) +{ + return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, 0, + 0, 0, 0); } int BV (clib_bihash_add_del) @@ -1010,6 +1020,15 @@ int BV (clib_bihash_add_or_overwrite_stale) return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg); } +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) +{ + u64 hash = BV (clib_bihash_hash) (add_v); + return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, 1, 0, 0, + overwrite_cb, arg); +} + int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 2a5c5861d88..c4e120e4a1f 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -356,12 +356,19 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h); int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add); + +int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h, + BVT (clib_bihash_kv) * add_v, u64 hash, + int is_add); 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); +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); int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_v, BVT (clib_bihash_kv) * return_v); |