src/vppinfra/bihash_template.h

   1 /*
   2   Copyright (c) 2014 Cisco and/or its affiliates.
   3
   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:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15 */
  16
  17 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
  18
  19 /*
  20  * Note: to instantiate the template multiple times in a single file,
  21  * #undef __included_bihash_template_h__...
  22  */
  23 #ifndef __included_bihash_template_h__
  24 #define __included_bihash_template_h__
  25
  26 #include <vppinfra/heap.h>
  27 #include <vppinfra/format.h>
  28 #include <vppinfra/pool.h>
  29
  30 #ifndef BIHASH_TYPE
  31 #error BIHASH_TYPE not defined
  32 #endif
  33
  34 #define _bv(a,b) a##b
  35 #define __bv(a,b) _bv(a,b)
  36 #define BV(a) __bv(a,BIHASH_TYPE)
  37
  38 #define _bvt(a,b) a##b##_t
  39 #define __bvt(a,b) _bvt(a,b)
  40 #define BVT(a) __bvt(a,BIHASH_TYPE)
  41
  42 typedef struct BV (clib_bihash_value)
  43 {
  44   union
  45   {
  46     BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
  47     struct BV (clib_bihash_value) * next_free;
  48   };
  49 } BVT (clib_bihash_value);
  50
  51 /*
  52  * This is shared across all uses of the template, so it needs
  53  * a "personal" #include recursion block
  54  */
  55 #ifndef __defined_clib_bihash_bucket_t__
  56 #define __defined_clib_bihash_bucket_t__
  57 typedef struct
  58 {
  59   union
  60   {
  61     struct
  62     {
  63       u32 offset;
  64       u8 linear_search;
  65       u8 pad[2];
  66       u8 log2_pages;
  67     };
  68     u64 as_u64;
  69   };
  70 } clib_bihash_bucket_t;
  71 #endif /* __defined_clib_bihash_bucket_t__ */
  72
  73 typedef struct
  74 {
  75   BVT (clib_bihash_value) * values;
  76   clib_bihash_bucket_t *buckets;
  77   volatile u32 *writer_lock;
  78
  79     BVT (clib_bihash_value) ** working_copies;
  80   clib_bihash_bucket_t saved_bucket;
  81
  82   u32 nbuckets;
  83   u32 log2_nbuckets;
  84   u32 linear_buckets;
  85   u8 *name;
  86
  87     BVT (clib_bihash_value) ** freelists;
  88   void *mheap;
  89
  90 } BVT (clib_bihash);
  91
  92
  93 static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
  94                                                 uword offset)
  95 {
  96   u8 *hp = h->mheap;
  97   u8 *vp = hp + offset;
  98
  99   return (void *) vp;
 100 }
 101
 102 static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h,
 103                                                  void *v)
 104 {
 105   u8 *hp, *vp;
 106
 107   hp = (u8 *) h->mheap;
 108   vp = (u8 *) v;
 109
 110   ASSERT ((vp - hp) < 0x100000000ULL);
 111   return vp - hp;
 112 }
 113
 114 void BV (clib_bihash_init)
 115   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
 116
 117 void BV (clib_bihash_free) (BVT (clib_bihash) * h);
 118
 119 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
 120                               BVT (clib_bihash_kv) * add_v, int is_add);
 121 int BV (clib_bihash_search) (const BVT (clib_bihash) * h,
 122                              BVT (clib_bihash_kv) * search_v,
 123                              BVT (clib_bihash_kv) * return_v);
 124
 125 void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
 126                                               void *callback, void *arg);
 127
 128 format_function_t BV (format_bihash);
 129 format_function_t BV (format_bihash_kvp);
 130
 131
 132 static inline int BV (clib_bihash_search_inline)
 133   (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
 134 {
 135   u64 hash;
 136   u32 bucket_index;
 137   BVT (clib_bihash_value) * v;
 138   clib_bihash_bucket_t *b;
 139   int i, limit;
 140
 141   hash = BV (clib_bihash_hash) (kvp);
 142
 143   bucket_index = hash & (h->nbuckets - 1);
 144   b = &h->buckets[bucket_index];
 145
 146   if (b->offset == 0)
 147     return -1;
 148
 149   hash >>= h->log2_nbuckets;
 150
 151   v = BV (clib_bihash_get_value) (h, b->offset);
 152
 153   /* If the bucket has unresolvable collisions, use linear search */
 154   limit = BIHASH_KVP_PER_PAGE;
 155   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 156   if (PREDICT_FALSE (b->linear_search))
 157     limit <<= b->log2_pages;
 158
 159   for (i = 0; i < limit; i++)
 160     {
 161       if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
 162         {
 163           *kvp = v->kvp[i];
 164           return 0;
 165         }
 166     }
 167   return -1;
 168 }
 169
 170 static inline int BV (clib_bihash_search_inline_2)
 171   (const BVT (clib_bihash) * h,
 172    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 173 {
 174   u64 hash;
 175   u32 bucket_index;
 176   BVT (clib_bihash_value) * v;
 177   clib_bihash_bucket_t *b;
 178   int i, limit;
 179
 180   ASSERT (valuep);
 181
 182   hash = BV (clib_bihash_hash) (search_key);
 183
 184   bucket_index = hash & (h->nbuckets - 1);
 185   b = &h->buckets[bucket_index];
 186
 187   if (b->offset == 0)
 188     return -1;
 189
 190   hash >>= h->log2_nbuckets;
 191   v = BV (clib_bihash_get_value) (h, b->offset);
 192
 193   /* If the bucket has unresolvable collisions, use linear search */
 194   limit = BIHASH_KVP_PER_PAGE;
 195   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 196   if (PREDICT_FALSE (b->linear_search))
 197     limit <<= b->log2_pages;
 198
 199   for (i = 0; i < limit; i++)
 200     {
 201       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 202         {
 203           *valuep = v->kvp[i];
 204           return 0;
 205         }
 206     }
 207   return -1;
 208 }
 209
 210
 211 #endif /* __included_bihash_template_h__ */
 212
 213 /** @endcond */
 214
 215 /*
 216  * fd.io coding-style-patch-verification: ON
 217  *
 218  * Local Variables:
 219  * eval: (c-set-style "gnu")
 220  * End:
 221  */