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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #error do not #include this file!
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.
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.
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.
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.
43 /** template key/value backing page structure */
44 typedef struct clib_bihash_value
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 */
53 /** bihash bucket structure */
60 u32 offset; /**< backing page offset in the clib memory heap */
61 u8 pad[3]; /**< log2 (size of the packing page block) */
66 } clib_bihash_bucket_t;
68 /** A bounded index extensible hash table */
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 */
84 /** Get pointer to value page given its clib mheap offset */
85 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
87 /** Get clib mheap offset given a pointer */
88 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
90 /** initialize a bounded index extensible hash table
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
96 @param memory_size - clib mheap size, in bytes
100 (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
102 /** Destroy a bounded index extensible hash table
103 @param h - the bi-hash table to free
106 void clib_bihash_free (clib_bihash * h);
108 /** Add or delete a (key,value) pair from a bi-hash table
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
117 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
120 /** Search a bi-hash table
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
127 int clib_bihash_search (clib_bihash * h,
128 clib_bihash_kv * search_v, clib_bihash_kv * return_v);
131 /** Visit active (key,value) pairs in a bi-hash table
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.
140 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
141 void *callback, void *arg);
144 * fd.io coding-style-patch-verification: ON
147 * eval: (c-set-style "gnu")