lib/hash.h

   1 /*
   2  *      BIRD Library -- Generic Hash Table
   3  *
   4  *      (c) 2013 Ondrej Zajicek <santiago@crfreenet.org>
   5  *      (c) 2013 CZ.NIC z.s.p.o.
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  */
   9
  10 #ifndef _BIRD_HASH_H_
  11 #define _BIRD_HASH_H_
  12
  13 #define HASH(type)              struct { type **data; uint count, order; }
  14 #define HASH_TYPE(v)            typeof(** (v).data)
  15 #define HASH_SIZE(v)            (1U << (v).order)
  16
  17 #define HASH_EQ(v,id,k1,k2...)  (id##_EQ(k1, k2))
  18 #define HASH_FN(v,id,key...)    ((u32) (id##_FN(key)) >> (32 - (v).order))
  19
  20
  21 #define HASH_INIT(v,pool,init_order)                                    \
  22   ({                                                                    \
  23     (v).count = 0;                                                      \
  24     (v).order = (init_order);                                           \
  25     (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));      \
  26   })
  27
  28 #define HASH_FREE(v)                                                    \
  29   ({                                                                    \
  30     mb_free((v).data);                                                  \
  31     (v) = (typeof(v)){ };                                               \
  32   })
  33
  34 #define HASH_FIND(v,id,key...)                                          \
  35   ({                                                                    \
  36     u32 _h = HASH_FN(v, id, key);                                       \
  37     HASH_TYPE(v) *_n = (v).data[_h];                                    \
  38     while (_n && !HASH_EQ(v, id, id##_KEY(_n), key))                    \
  39       _n = id##_NEXT(_n);                                               \
  40     _n;                                                                 \
  41   })
  42
  43 #define HASH_INSERT(v,id,node)                                          \
  44   ({                                                                    \
  45     u32 _h = HASH_FN(v, id, id##_KEY((node)));                          \
  46     HASH_TYPE(v) **_nn = (v).data + _h;                                 \
  47     id##_NEXT(node) = *_nn;                                             \
  48     *_nn = node;                                                        \
  49     (v).count++;                                                        \
  50   })
  51
  52 #define HASH_DO_REMOVE(v,id,_nn)                                        \
  53   ({                                                                    \
  54     *_nn = id##_NEXT((*_nn));                                           \
  55     (v).count--;                                                        \
  56   })
  57
  58 #define HASH_DELETE(v,id,key...)                                        \
  59   ({                                                                    \
  60     u32 _h = HASH_FN(v, id, key);                                       \
  61     HASH_TYPE(v) *_n, **_nn = (v).data + _h;                            \
  62                                                                         \
  63     while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key))            \
  64       _nn = &(id##_NEXT((*_nn)));                                       \
  65                                                                         \
  66     if (_n = *_nn)                                                      \
  67       HASH_DO_REMOVE(v,id,_nn);                                         \
  68     _n;                                                                 \
  69   })
  70
  71 #define HASH_REMOVE(v,id,node)                                          \
  72   ({                                                                    \
  73     u32 _h = HASH_FN(v, id, id##_KEY((node)));                          \
  74     HASH_TYPE(v) *_n, **_nn = (v).data + _h;                            \
  75                                                                         \
  76     while ((*_nn) && (*_nn != (node)))                                  \
  77       _nn = &(id##_NEXT((*_nn)));                                       \
  78                                                                         \
  79     if (_n = *_nn)                                                      \
  80       HASH_DO_REMOVE(v,id,_nn);                                         \
  81     _n;                                                                 \
  82   })
  83
  84
  85 #define HASH_REHASH(v,id,pool,step)                                     \
  86   ({                                                                    \
  87     HASH_TYPE(v) *_n, *_n2, **_od;                                      \
  88     uint _i, _os;                                                       \
  89                                                                         \
  90     _os = HASH_SIZE(v);                                                 \
  91     _od = (v).data;                                                     \
  92     (v).count = 0;                                                      \
  93     (v).order += (step);                                                \
  94     (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));      \
  95                                                                         \
  96     for (_i = 0; _i < _os; _i++)                                        \
  97       for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2)      \
  98         HASH_INSERT(v, id, _n);                                         \
  99                                                                         \
 100     mb_free(_od);                                                       \
 101   })
 102
 103 #define REHASH_LO_MARK(a,b,c,d,e,f)     a
 104 #define REHASH_HI_MARK(a,b,c,d,e,f)     b
 105 #define REHASH_LO_STEP(a,b,c,d,e,f)     c
 106 #define REHASH_HI_STEP(a,b,c,d,e,f)     d
 107 #define REHASH_LO_BOUND(a,b,c,d,e,f)    e
 108 #define REHASH_HI_BOUND(a,b,c,d,e,f)    f
 109
 110 #define HASH_DEFINE_REHASH_FN(id,type)                                  \
 111   static void id##_REHASH(void *v, pool *p, int step)                   \
 112   { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
 113
 114
 115 #define HASH_MAY_STEP_UP(v,id,pool)     HASH_MAY_STEP_UP_(v,pool, id##_REHASH, id##_PARAMS)
 116 #define HASH_MAY_STEP_DOWN(v,id,pool)   HASH_MAY_STEP_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
 117 #define HASH_MAY_RESIZE_DOWN(v,id,pool) HASH_MAY_RESIZE_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
 118
 119 #define HASH_MAY_STEP_UP_(v,pool,rehash_fn,args)                        \
 120   ({                                                                    \
 121     if (((v).count > (HASH_SIZE(v) REHASH_HI_MARK(args))) &&            \
 122         ((v).order < (REHASH_HI_BOUND(args))))                          \
 123       rehash_fn(&(v), pool, REHASH_HI_STEP(args));                      \
 124   })
 125
 126 #define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)                      \
 127   ({                                                                    \
 128     if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&            \
 129         ((v).order > (REHASH_LO_BOUND(args))))                          \
 130       rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));                   \
 131   })
 132
 133 #define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)                    \
 134   ({                                                                    \
 135     uint _o = (v).order;                                                        \
 136     while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&           \
 137            (_o > (REHASH_LO_BOUND(args))))                              \
 138       _o -= (REHASH_LO_STEP(args));                                     \
 139     if (_o < (v).order)                                                 \
 140       rehash_fn(&(v), pool, _o - (v).order);                            \
 141   })
 142
 143
 144 #define HASH_INSERT2(v,id,pool,node)                                    \
 145   ({                                                                    \
 146     HASH_INSERT(v, id, node);                                           \
 147     HASH_MAY_STEP_UP(v, id, pool);                                      \
 148   })
 149
 150 #define HASH_DELETE2(v,id,pool,key...)                                  \
 151   ({                                                                    \
 152     HASH_TYPE(v) *_n = HASH_DELETE(v, id, key);                         \
 153     if (_n) HASH_MAY_STEP_DOWN(v, id, pool);                            \
 154     _n;                                                                 \
 155   })
 156
 157 #define HASH_REMOVE2(v,id,pool,node)                                    \
 158   ({                                                                    \
 159     HASH_TYPE(v) *_n = HASH_REMOVE(v, id, node);                        \
 160     if (_n) HASH_MAY_STEP_DOWN(v, id, pool);                            \
 161     _n;                                                                 \
 162   })
 163
 164
 165 #define HASH_WALK(v,next,n)                                             \
 166   do {                                                                  \
 167     HASH_TYPE(v) *n;                                                    \
 168     uint _i;                                                            \
 169     uint _s = HASH_SIZE(v);                                             \
 170     for (_i = 0; _i < _s; _i++)                                         \
 171       for (n = (v).data[_i]; n; n = n->next)
 172
 173 #define HASH_WALK_END } while (0)
 174
 175
 176 #define HASH_WALK_DELSAFE(v,next,n)                                     \
 177   do {                                                                  \
 178     HASH_TYPE(v) *n, *_next;                                            \
 179     uint _i;                                                            \
 180     uint _s = HASH_SIZE(v);                                             \
 181     for (_i = 0; _i < _s; _i++)                                         \
 182       for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
 183
 184 #define HASH_WALK_DELSAFE_END } while (0)
 185
 186
 187 #define HASH_WALK_FILTER(v,next,n,nn)                                   \
 188   do {                                                                  \
 189     HASH_TYPE(v) *n, **nn;                                              \
 190     uint _i;                                                            \
 191     uint _s = HASH_SIZE(v);                                             \
 192     for (_i = 0; _i < _s; _i++)                                         \
 193       for (nn = (v).data + _i; n = *nn; (*nn == n) ? (nn = &n->next) : NULL)
 194
 195 #define HASH_WALK_FILTER_END } while (0)
 196
 197 #endif