1 files changed, 149 insertions, 0 deletions
diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h
new file mode 100644
index 00000000000..e6ab9db6d30
--- /dev/null
+++ b/src/vppinfra/bihash_doc.h
@@ -0,0 +1,149 @@
+/*
+ * 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;
+
+/** 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_v - 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);
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */