diff options
| -rw-r--r-- | vppinfra/vppinfra/bihash_8_8.h | 20 | ||||
| -rw-r--r-- | vppinfra/vppinfra/bihash_doc.h | 140 | ||||
| -rw-r--r-- | vppinfra/vppinfra/bihash_template.c | 4 | ||||
| -rw-r--r-- | vppinfra/vppinfra/bihash_template.h | 4 |
4 files changed, 166 insertions, 2 deletions
diff --git a/vppinfra/vppinfra/bihash_8_8.h b/vppinfra/vppinfra/bihash_8_8.h index 21cb59ad67c..221e1f25534 100644 --- a/vppinfra/vppinfra/bihash_8_8.h +++ b/vppinfra/vppinfra/bihash_8_8.h @@ -25,11 +25,15 @@ #include <vppinfra/pool.h> #include <vppinfra/xxhash.h> +/** 8 octet key, 8 octet key value pair */ typedef struct { - u64 key; - u64 value; + u64 key; /**< the key */ + u64 value; /**< the value */ } clib_bihash_kv_8_8_t; +/** Decide if a clib_bihash_kv_8_8_t instance is free + @param v- pointer to the (key,value) pair +*/ static inline int clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t *v) { if (v->key == ~0ULL && v->value == ~0ULL) @@ -37,11 +41,19 @@ static inline int clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t *v) return 0; } +/** Hash a clib_bihash_kv_8_8_t instance + @param v - pointer to the (key,value) pair, hash the key (only) +*/ static inline u64 clib_bihash_hash_8_8 (clib_bihash_kv_8_8_t *v) { return clib_xxhash (v->key); } +/** Format a clib_bihash_kv_8_8_t instance + @param s - u8 * vector under construction + @param v (vararg) - the (key,value) pair to format + @return s - the u8 * vector under construction +*/ static inline u8 * format_bihash_kvp_8_8 (u8 * s, va_list * args) { clib_bihash_kv_8_8_t * v = va_arg (*args, clib_bihash_kv_8_8_t *); @@ -50,6 +62,10 @@ static inline u8 * format_bihash_kvp_8_8 (u8 * s, va_list * args) return s; } +/** Compare two clib_bihash_kv_8_8_t instances + @param a - first key + @param b - second key +*/ static inline int clib_bihash_key_compare_8_8 (u64 a, u64 b) { return a == b; diff --git a/vppinfra/vppinfra/bihash_doc.h b/vppinfra/vppinfra/bihash_doc.h new file mode 100644 index 00000000000..037e7cc90e6 --- /dev/null +++ b/vppinfra/vppinfra/bihash_doc.h @@ -0,0 +1,140 @@ +/* + * Copyright (c) 2014 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. +*/ + +#error do not #include this file! + +/** \file + + Bounded-index extensible hashing. The basic algorithm performs + thread-safe constant-time lookups in the face of a rational number + of hash collisions. The computed hash code h(k) must have + reasonable statistics with respect to the key space. It won't do + to have h(k) = 0 or 1, for all values of k. + + Each bucket in the power-of-two bucket array contains the index + (in a private vppinfra memory heap) of the "backing store" for the + bucket, as well as a size field. The size field (log2_pages) + corresponds to 1, 2, 4, ... contiguous "pages" containing the + (key,value) pairs in the bucket. + + When a single page fills, we allocate two contiguous pages. We + recompute h(k) for each (key,value) pair, using an additional bit + to deal the (key, value) pairs into the "top" and "bottom" pages. + + At lookup time, we compute h(k), using lg(bucket-array-size) to + pick the bucket. We read the bucket to find the base of the + backing pages. We use an additional log2_pages' worth of bits + from h(k) to compute the offset of the page which will contain the + (key,value) pair we're trying to find. +*/ + +/** template key/value backing page structure */ +typedef struct clib_bihash_value { + union { + + clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */ + clib_bihash_value * next_free; /**< used when a KVP page (or block thereof) is on a freelist */ + }; +} clib_bihash_value_t + +/** bihash bucket structure */ +typedef struct { + union { + struct { + u32 offset; /**< backing page offset in the clib memory heap */ + u8 pad[3]; /**< log2 (size of the packing page block) */ + u8 log2_pages; + }; + u64 as_u64; + }; +} clib_bihash_bucket_t; +#endif /* __defined_clib_bihash_bucket_t__ */ + +/** A bounded index extensible hash table */ +typedef struct { + clib_bihash_bucket_t * buckets; /**< Hash bucket vector, power-of-two in size */ + volatile u32 * writer_lock; /**< Writer lock, in its own cache line */ + BVT(clib_bihash_value) ** working_copies; /**< Working copies (various sizes), to avoid locking against readers */ + clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */ + u32 nbuckets; /**< Number of hash buckets */ + u32 log2_nbuckets; /**< lg(nbuckets) */ + u8 * name; /**< hash table name */ + BVT(clib_bihash_value) **freelists; /**< power of two freelist vector */ + void * mheap; /**< clib memory heap */ +} clib_bihash_t; + +/** Get pointer to value page given its clib mheap offset */ +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 +*/ + +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 +*/ + +void clib_bihash_free (clib_bihash * h); + +/** Add or delete a (key,value) pair from a bi-hash table + + @param h - the bi-hash table to search + @param add_kv - the (key,value) pair to add + @param is_add - add=1, delete=0 + @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); + + +/** Search a bi-hash table + + @param h - the bi-hash table to search + @param search_v - (key,value) pair containing the search key + @param return_v - (key,value) pair which matches search_v.key + @returns 0 on success (with return_v set), < 0 on error +*/ +int clib_bihash_search (clib_bihash * h, + clib_bihash_kv * search_v, + clib_bihash_kv * return_v); + + +/** 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 + @note Trying to supply a proper function prototype for the + callback function appears to be a fool's errand. +*/ +void clib_bihash_foreach_key_value_pair (clib_bihash) * h, + void *callback, + void *arg); diff --git a/vppinfra/vppinfra/bihash_template.c b/vppinfra/vppinfra/bihash_template.c index 35384a38067..0ee92c07570 100644 --- a/vppinfra/vppinfra/bihash_template.c +++ b/vppinfra/vppinfra/bihash_template.c @@ -13,6 +13,8 @@ * limitations under the License. */ +/** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */ + void BV(clib_bihash_init) (BVT(clib_bihash) * h, char * name, u32 nbuckets, uword memory_size) @@ -452,3 +454,5 @@ void BV(clib_bihash_foreach_key_value_pair) } } } + +/** @endif */ diff --git a/vppinfra/vppinfra/bihash_template.h b/vppinfra/vppinfra/bihash_template.h index b7968e75453..5f80e7af044 100644 --- a/vppinfra/vppinfra/bihash_template.h +++ b/vppinfra/vppinfra/bihash_template.h @@ -14,6 +14,8 @@ * limitations under the License. */ +/** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */ + /* * Note: to instantiate the template multiple times in a single file, * #undef __included_bihash_template_h__... @@ -197,3 +199,5 @@ static inline int BV(clib_bihash_search_inline_2) #endif /* __included_bihash_template_h__ */ + +/** @endif */ |