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   int *working_copy_lengths;
  81   clib_bihash_bucket_t saved_bucket;
  82
  83   u32 nbuckets;
  84   u32 log2_nbuckets;
  85   u32 linear_buckets;
  86   u8 *name;
  87
  88     BVT (clib_bihash_value) ** freelists;
  89   void *mheap;
  90
  91 } BVT (clib_bihash);
  92
  93
  94 static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
  95                                                 uword offset)
  96 {
  97   u8 *hp = h->mheap;
  98   u8 *vp = hp + offset;
  99
 100   return (void *) vp;
 101 }
 102
 103 static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h,
 104                                                  void *v)
 105 {
 106   u8 *hp, *vp;
 107
 108   hp = (u8 *) h->mheap;
 109   vp = (u8 *) v;
 110
 111   ASSERT ((vp - hp) < 0x100000000ULL);
 112   return vp - hp;
 113 }
 114
 115 void BV (clib_bihash_init)
 116   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
 117
 118 void BV (clib_bihash_free) (BVT (clib_bihash) * h);
 119
 120 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
 121                               BVT (clib_bihash_kv) * add_v, int is_add);
 122 int BV (clib_bihash_search) (const BVT (clib_bihash) * h,
 123                              BVT (clib_bihash_kv) * search_v,
 124                              BVT (clib_bihash_kv) * return_v);
 125
 126 void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
 127                                               void *callback, void *arg);
 128
 129 format_function_t BV (format_bihash);
 130 format_function_t BV (format_bihash_kvp);
 131
 132
 133 static inline int BV (clib_bihash_search_inline)
 134   (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
 135 {
 136   u64 hash;
 137   u32 bucket_index;
 138   BVT (clib_bihash_value) * v;
 139   clib_bihash_bucket_t *b;
 140   int i, limit;
 141
 142   hash = BV (clib_bihash_hash) (kvp);
 143
 144   bucket_index = hash & (h->nbuckets - 1);
 145   b = &h->buckets[bucket_index];
 146
 147   if (b->offset == 0)
 148     return -1;
 149
 150   hash >>= h->log2_nbuckets;
 151
 152   v = BV (clib_bihash_get_value) (h, b->offset);
 153
 154   /* If the bucket has unresolvable collisions, use linear search */
 155   limit = BIHASH_KVP_PER_PAGE;
 156   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 157   if (PREDICT_FALSE (b->linear_search))
 158     limit <<= b->log2_pages;
 159
 160   for (i = 0; i < limit; i++)
 161     {
 162       if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
 163         {
 164           *kvp = v->kvp[i];
 165           return 0;
 166         }
 167     }
 168   return -1;
 169 }
 170
 171 static inline int BV (clib_bihash_search_inline_2)
 172   (const BVT (clib_bihash) * h,
 173    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 174 {
 175   u64 hash;
 176   u32 bucket_index;
 177   BVT (clib_bihash_value) * v;
 178   clib_bihash_bucket_t *b;
 179   int i, limit;
 180
 181   ASSERT (valuep);
 182
 183   hash = BV (clib_bihash_hash) (search_key);
 184
 185   bucket_index = hash & (h->nbuckets - 1);
 186   b = &h->buckets[bucket_index];
 187
 188   if (b->offset == 0)
 189     return -1;
 190
 191   hash >>= h->log2_nbuckets;
 192   v = BV (clib_bihash_get_value) (h, b->offset);
 193
 194   /* If the bucket has unresolvable collisions, use linear search */
 195   limit = BIHASH_KVP_PER_PAGE;
 196   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 197   if (PREDICT_FALSE (b->linear_search))
 198     limit <<= b->log2_pages;
 199
 200   for (i = 0; i < limit; i++)
 201     {
 202       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 203         {
 204           *valuep = v->kvp[i];
 205           return 0;
 206         }
 207     }
 208   return -1;
 209 }
 210
 211
 212 #endif /* __included_bihash_template_h__ */
 213
 214 /** @endcond */
 215
 216 /*
 217  * fd.io coding-style-patch-verification: ON
 218  *
 219  * Local Variables:
 220  * eval: (c-set-style "gnu")
 221  * End:
 222  */