src/vppinfra/bihash_doc.h

   1 /*
   2  * Copyright (c) 2014 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14 */
  15
  16 #error do not #include this file!
  17
  18 /** \file
  19
  20     Bounded-index extensible hashing. The basic algorithm performs
  21     thread-safe constant-time lookups in the face of a rational number
  22     of hash collisions. The computed hash code h(k) must have
  23     reasonable statistics with respect to the key space. It won't do
  24     to have h(k) = 0 or 1, for all values of k.
  25
  26     Each bucket in the power-of-two bucket array contains the index
  27     (in a private vppinfra memory heap) of the "backing store" for the
  28     bucket, as well as a size field. The size field (log2_pages)
  29     corresponds to 1, 2, 4, ... contiguous "pages" containing the
  30     (key,value) pairs in the bucket.
  31
  32     When a single page fills, we allocate two contiguous pages.  We
  33     recompute h(k) for each (key,value) pair, using an additional bit
  34     to deal the (key, value) pairs into the "top" and "bottom" pages.
  35
  36     At lookup time, we compute h(k), using lg(bucket-array-size) to
  37     pick the bucket. We read the bucket to find the base of the
  38     backing pages.  We use an additional log2_pages' worth of bits
  39     from h(k) to compute the offset of the page which will contain the
  40     (key,value) pair we're trying to find.
  41 */
  42
  43 /** template key/value backing page structure */
  44 typedef struct clib_bihash_value
  45 {
  46   union
  47   {
  48
  49     clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
  50     clib_bihash_value *next_free;  /**< used when a KVP page (or block thereof) is on a freelist */
  51   };
  52 } clib_bihash_value_t
  53 /** bihash bucket structure */
  54   typedef struct
  55 {
  56   union
  57   {
  58     struct
  59     {
  60       u32 offset;  /**< backing page offset in the clib memory heap */
  61       u8 pad[3];   /**< log2 (size of the packing page block) */
  62       u8 log2_pages;
  63     };
  64     u64 as_u64;
  65   };
  66 } clib_bihash_bucket_t;
  67
  68 /** A bounded index extensible hash table */
  69 typedef struct
  70 {
  71   clib_bihash_bucket_t *buckets;  /**< Hash bucket vector, power-of-two in size */
  72   volatile u32 *writer_lock;  /**< Writer lock, in its own cache line */
  73     BVT (clib_bihash_value) ** working_copies;
  74                                             /**< Working copies (various sizes), to avoid locking against readers */
  75   clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
  76   u32 nbuckets;                      /**< Number of hash buckets */
  77   u32 log2_nbuckets;                 /**< lg(nbuckets) */
  78   u8 *name;                          /**< hash table name */
  79     BVT (clib_bihash_value) ** freelists;
  80                                       /**< power of two freelist vector */
  81   void *mheap;  /**< clib memory heap */
  82 } clib_bihash_t;
  83
  84 /** Get pointer to value page given its clib mheap offset */
  85 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
  86
  87 /** Get clib mheap offset given a pointer */
  88 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
  89
  90 /** initialize a bounded index extensible hash table
  91
  92     @param h - the bi-hash table to initialize
  93     @param name - name of the hash table
  94     @param nbuckets - the number of buckets, will be rounded up to
  95 a power of two
  96     @param memory_size - clib mheap size, in bytes
  97 */
  98
  99 void clib_bihash_init
 100   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 101
 102 /** Destroy a bounded index extensible hash table
 103     @param h - the bi-hash table to free
 104 */
 105
 106 void clib_bihash_free (clib_bihash * h);
 107
 108 /** Add or delete a (key,value) pair from a bi-hash table
 109
 110     @param h - the bi-hash table to search
 111     @param add_v - the (key,value) pair to add
 112     @param is_add - add=1, delete=0
 113     @returns 0 on success, < 0 on error
 114     @note This function will replace an existing (key,value) pair if the
 115     new key matches an existing key
 116 */
 117 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 118
 119
 120 /** Search a bi-hash table
 121
 122     @param h - the bi-hash table to search
 123     @param search_v - (key,value) pair containing the search key
 124     @param return_v - (key,value) pair which matches search_v.key
 125     @returns 0 on success (with return_v set), < 0 on error
 126 */
 127 int clib_bihash_search (clib_bihash * h,
 128                         clib_bihash_kv * search_v, clib_bihash_kv * return_v);
 129
 130
 131 /** Visit active (key,value) pairs in a bi-hash table
 132
 133     @param h - the bi-hash table to search
 134     @param callback - function to call with each active (key,value) pair
 135     @param arg - arbitrary second argument passed to the callback function
 136     First argument is the (key,value) pair to visit
 137     @note Trying to supply a proper function prototype for the
 138     callback function appears to be a fool's errand.
 139 */
 140 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 141                                          void *callback, void *arg);
 142
 143 /*
 144  * fd.io coding-style-patch-verification: ON
 145  *
 146  * Local Variables:
 147  * eval: (c-set-style "gnu")
 148  * End:
 149  */