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