lib/hash.h

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