vppinfra/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 /** @if 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   union {
  44     BVT(clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
  45     struct BV(clib_bihash_value) * next_free;
  46   };
  47 } BVT(clib_bihash_value);
  48
  49 /*
  50  * This is shared across all uses of the template, so it needs
  51  * a "personal" #include recursion block
  52  */
  53 #ifndef __defined_clib_bihash_bucket_t__
  54 #define __defined_clib_bihash_bucket_t__
  55 typedef struct {
  56   union {
  57     struct {
  58       u32 offset;
  59       u8 pad[3];
  60       u8 log2_pages;
  61     };
  62     u64 as_u64;
  63   };
  64 } clib_bihash_bucket_t;
  65 #endif /* __defined_clib_bihash_bucket_t__ */
  66
  67 typedef struct {
  68   BVT(clib_bihash_value) * values;
  69   clib_bihash_bucket_t * buckets;
  70   volatile u32 * writer_lock;
  71
  72   BVT(clib_bihash_value) ** working_copies;
  73   clib_bihash_bucket_t saved_bucket;
  74
  75   u32 nbuckets;
  76   u32 log2_nbuckets;
  77   u8 * name;
  78
  79   BVT(clib_bihash_value) **freelists;
  80   void * mheap;
  81
  82 } BVT(clib_bihash);
  83
  84
  85 static inline void *
  86 BV(clib_bihash_get_value) (BVT(clib_bihash) * h, uword offset)
  87 {
  88   u8 * hp = h->mheap;
  89   u8 * vp = hp + offset;
  90
  91   return (void *) vp;
  92 }
  93
  94 static inline uword BV(clib_bihash_get_offset) (BVT(clib_bihash) * h, void * v)
  95 {
  96   u8 * hp, * vp;
  97
  98   hp = (u8 *) h->mheap;
  99   vp = (u8 *) v;
 100
 101   ASSERT((vp - hp) < 0x100000000ULL);
 102   return vp - hp;
 103 }
 104
 105 void BV(clib_bihash_init)
 106      (BVT(clib_bihash) * h, char * name, u32 nbuckets, uword memory_size);
 107
 108 void BV(clib_bihash_free)
 109      (BVT(clib_bihash) * h);
 110
 111 int BV(clib_bihash_add_del) (BVT(clib_bihash) * h,
 112                              BVT(clib_bihash_kv) * add_v,
 113                              int is_add);
 114 int BV(clib_bihash_search) (BVT(clib_bihash) * h,
 115                             BVT(clib_bihash_kv) * search_v,
 116                             BVT(clib_bihash_kv) * return_v);
 117
 118 void BV(clib_bihash_foreach_key_value_pair) (BVT(clib_bihash) * h,
 119                                              void *callback,
 120                                              void *arg);
 121
 122 format_function_t BV(format_bihash);
 123 format_function_t BV(format_bihash_kvp);
 124
 125
 126 static inline int BV(clib_bihash_search_inline)
 127     (BVT(clib_bihash) * h, BVT(clib_bihash_kv) * kvp)
 128 {
 129   u64 hash;
 130   u32 bucket_index;
 131   uword value_index;
 132   BVT(clib_bihash_value) * v;
 133   clib_bihash_bucket_t * b;
 134   int i;
 135
 136   hash = BV(clib_bihash_hash) (kvp);
 137
 138   bucket_index = hash & (h->nbuckets-1);
 139   b = &h->buckets[bucket_index];
 140
 141   if (b->offset == 0)
 142     return -1;
 143
 144   hash >>= h->log2_nbuckets;
 145
 146   v = BV(clib_bihash_get_value) (h, b->offset);
 147   value_index = hash & ((1<<b->log2_pages)-1);
 148   v += value_index;
 149
 150   for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 151     {
 152       if (BV(clib_bihash_key_compare)(v->kvp[i].key, kvp->key))
 153         {
 154           *kvp = v->kvp[i];
 155           return 0;
 156         }
 157     }
 158   return -1;
 159 }
 160
 161 static inline int BV(clib_bihash_search_inline_2)
 162      (BVT(clib_bihash) * h,
 163       BVT(clib_bihash_kv) *search_key,
 164       BVT(clib_bihash_kv) *valuep)
 165 {
 166   u64 hash;
 167   u32 bucket_index;
 168   uword value_index;
 169   BVT(clib_bihash_value) * v;
 170   clib_bihash_bucket_t * b;
 171   int i;
 172
 173   ASSERT(valuep);
 174
 175   hash = BV(clib_bihash_hash) (search_key);
 176
 177   bucket_index = hash & (h->nbuckets-1);
 178   b = &h->buckets[bucket_index];
 179
 180   if (b->offset == 0)
 181     return -1;
 182
 183   hash >>= h->log2_nbuckets;
 184
 185   v = BV(clib_bihash_get_value) (h, b->offset);
 186   value_index = hash & ((1<<b->log2_pages)-1);
 187   v += value_index;
 188
 189   for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 190     {
 191       if (BV(clib_bihash_key_compare)(v->kvp[i].key, search_key->key))
 192         {
 193           *valuep = v->kvp[i];
 194           return 0;
 195         }
 196     }
 197   return -1;
 198 }
 199
 200
 201 #endif /* __included_bihash_template_h__ */
 202
 203 /** @endif */