2 Copyright (c) 2014 Cisco and/or its affiliates.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 * Note: to instantiate the template multiple times in a single file,
19 * #undef __included_bihash_template_h__...
21 #ifndef __included_bihash_template_h__
22 #define __included_bihash_template_h__
24 #include <vppinfra/heap.h>
25 #include <vppinfra/format.h>
26 #include <vppinfra/pool.h>
29 #error BIHASH_TYPE not defined
33 #define __bv(a,b) _bv(a,b)
34 #define BV(a) __bv(a,BIHASH_TYPE)
36 #define _bvt(a,b) a##b##_t
37 #define __bvt(a,b) _bvt(a,b)
38 #define BVT(a) __bvt(a,BIHASH_TYPE)
40 typedef struct BV(clib_bihash_value) {
42 BVT(clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
43 struct BV(clib_bihash_value) * next_free;
45 } BVT(clib_bihash_value);
48 * This is shared across all uses of the template, so it needs
49 * a "personal" #include recursion block
51 #ifndef __defined_clib_bihash_bucket_t__
52 #define __defined_clib_bihash_bucket_t__
62 } clib_bihash_bucket_t;
63 #endif /* __defined_clib_bihash_bucket_t__ */
66 BVT(clib_bihash_value) * values;
67 clib_bihash_bucket_t * buckets;
68 volatile u32 * writer_lock;
70 BVT(clib_bihash_value) ** working_copies;
71 clib_bihash_bucket_t saved_bucket;
77 BVT(clib_bihash_value) **freelists;
84 BV(clib_bihash_get_value) (BVT(clib_bihash) * h, uword offset)
87 u8 * vp = hp + offset;
92 static inline uword BV(clib_bihash_get_offset) (BVT(clib_bihash) * h, void * v)
99 ASSERT((vp - hp) < 0x100000000ULL);
103 void BV(clib_bihash_init)
104 (BVT(clib_bihash) * h, char * name, u32 nbuckets, uword memory_size);
106 void BV(clib_bihash_free)
107 (BVT(clib_bihash) * h);
109 int BV(clib_bihash_add_del) (BVT(clib_bihash) * h,
110 BVT(clib_bihash_kv) * add_v,
112 int BV(clib_bihash_search) (BVT(clib_bihash) * h,
113 BVT(clib_bihash_kv) * search_v,
114 BVT(clib_bihash_kv) * return_v);
116 void BV(clib_bihash_foreach_key_value_pair) (BVT(clib_bihash) * h,
120 format_function_t BV(format_bihash);
121 format_function_t BV(format_bihash_kvp);
124 static inline int BV(clib_bihash_search_inline)
125 (BVT(clib_bihash) * h, BVT(clib_bihash_kv) * kvp)
130 BVT(clib_bihash_value) * v;
131 clib_bihash_bucket_t * b;
134 hash = BV(clib_bihash_hash) (kvp);
136 bucket_index = hash & (h->nbuckets-1);
137 b = &h->buckets[bucket_index];
142 hash >>= h->log2_nbuckets;
144 v = BV(clib_bihash_get_value) (h, b->offset);
145 value_index = hash & ((1<<b->log2_pages)-1);
148 for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
150 if (BV(clib_bihash_key_compare)(v->kvp[i].key, kvp->key))
159 static inline int BV(clib_bihash_search_inline_2)
160 (BVT(clib_bihash) * h,
161 BVT(clib_bihash_kv) *search_key,
162 BVT(clib_bihash_kv) *valuep)
167 BVT(clib_bihash_value) * v;
168 clib_bihash_bucket_t * b;
173 hash = BV(clib_bihash_hash) (search_key);
175 bucket_index = hash & (h->nbuckets-1);
176 b = &h->buckets[bucket_index];
181 hash >>= h->log2_nbuckets;
183 v = BV(clib_bihash_get_value) (h, b->offset);
184 value_index = hash & ((1<<b->log2_pages)-1);
187 for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
189 if (BV(clib_bihash_key_compare)(v->kvp[i].key, search_key->key))
199 #endif /* __included_bihash_template_h__ */