hash.h 6.17 KB
Newer Older
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1 2 3 4 5 6 7 8 9 10 11
/*
 *	BIRD Library -- Generic Hash Table
 *
 *	(c) 2013 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2013 CZ.NIC z.s.p.o.
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#ifndef _BIRD_HASH_H_
#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)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
16 17 18

#define HASH_EQ(v,id,k1,k2...)	(id##_EQ(k1, k2))
#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 24 25
    (v).count = 0;							\
    (v).order = (init_order);						\
    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
26 27
  })

28 29 30 31 32 33
#define HASH_FREE(v)							\
  ({									\
    mb_free((v).data);							\
    (v) = (typeof(v)){ };						\
  })

34
#define HASH_FIND(v,id,key...)						\
35
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
36
    u32 _h = HASH_FN(v, id, key);					\
37
    HASH_TYPE(v) *_n = (v).data[_h];					\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
38
    while (_n && !HASH_EQ(v, id, id##_KEY(_n), key))			\
39
      _n = id##_NEXT(_n);						\
40 41 42
    _n;									\
  })

43
#define HASH_INSERT(v,id,node)						\
44
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
45
    u32 _h = HASH_FN(v, id, id##_KEY((node)));				\
46 47
    HASH_TYPE(v) **_nn = (v).data + _h;					\
    id##_NEXT(node) = *_nn;						\
48
    *_nn = node;							\
49
    (v).count++;							\
50 51
  })

52
#define HASH_DO_REMOVE(v,id,_nn)					\
53
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
54 55
    *_nn = id##_NEXT((*_nn));						\
    (v).count--;							\
56 57
  })

58 59
#define HASH_DELETE(v,id,key...)					\
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
60 61
    u32 _h = HASH_FN(v, id, key);					\
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;				\
62
									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
63
    while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key))		\
64 65
      _nn = &(id##_NEXT((*_nn)));					\
									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
66 67 68
    if (_n = *_nn)							\
      HASH_DO_REMOVE(v,id,_nn);						\
    _n;									\
69 70
  })

71 72
#define HASH_REMOVE(v,id,node)						\
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
73 74
    u32 _h = HASH_FN(v, id, id##_KEY((node)));				\
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;				\
75
									\
76
    while ((*_nn) && (*_nn != (node)))					\
77
      _nn = &(id##_NEXT((*_nn)));					\
78
									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
79 80 81
    if (_n = *_nn)							\
      HASH_DO_REMOVE(v,id,_nn);						\
    _n;									\
82 83 84
  })


85 86 87
#define HASH_REHASH(v,id,pool,step)					\
  ({									\
    HASH_TYPE(v) *_n, *_n2, **_od;					\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
88
    uint _i, _os;							\
89
									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
90
    _os = HASH_SIZE(v);							\
91 92 93 94 95
    _od = (v).data;							\
    (v).count = 0;							\
    (v).order += (step);						\
    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
96
    for (_i = 0; _i < _os; _i++)					\
97 98 99 100 101 102
      for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2)	\
	HASH_INSERT(v, id, _n);						\
									\
    mb_free(_od);							\
  })

Ondřej Zajíček's avatar
Ondřej Zajíček committed
103 104 105 106 107 108 109 110 111
#define REHASH_LO_MARK(a,b,c,d,e,f)	a
#define REHASH_HI_MARK(a,b,c,d,e,f)	b
#define REHASH_LO_STEP(a,b,c,d,e,f)	c
#define REHASH_HI_STEP(a,b,c,d,e,f)	d
#define REHASH_LO_BOUND(a,b,c,d,e,f)	e
#define REHASH_HI_BOUND(a,b,c,d,e,f)	f

#define HASH_DEFINE_REHASH_FN(id,type)					\
  static void id##_REHASH(void *v, pool *p, int step)			\
112 113
  { HASH_REHASH(* (HASH(type) *) v, id, p, step); }

Ondřej Zajíček's avatar
Ondřej Zajíček committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134

#define HASH_MAY_STEP_UP(v,id,pool)	HASH_MAY_STEP_UP_(v,pool, id##_REHASH, id##_PARAMS)
#define HASH_MAY_STEP_DOWN(v,id,pool)	HASH_MAY_STEP_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
#define HASH_MAY_RESIZE_DOWN(v,id,pool)	HASH_MAY_RESIZE_DOWN_(v,pool, id##_REHASH, id##_PARAMS)

#define HASH_MAY_STEP_UP_(v,pool,rehash_fn,args)			\
  ({                                                                    \
    if (((v).count > (HASH_SIZE(v) REHASH_HI_MARK(args))) &&		\
	((v).order < (REHASH_HI_BOUND(args))))				\
      rehash_fn(&(v), pool, REHASH_HI_STEP(args));			\
  })

#define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)			\
  ({                                                                    \
    if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&		\
	((v).order > (REHASH_LO_BOUND(args))))				\
      rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));			\
  })

#define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)			\
  ({                                                                    \
135 136
    uint _o = (v).order;							\
    while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&		\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
137 138 139
	   (_o > (REHASH_LO_BOUND(args))))				\
      _o -= (REHASH_LO_STEP(args));					\
    if (_o < (v).order)							\
140
      rehash_fn(&(v), pool, _o - (v).order);				\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
141 142 143 144
  })


#define HASH_INSERT2(v,id,pool,node)					\
145
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
146 147
    HASH_INSERT(v, id, node);						\
    HASH_MAY_STEP_UP(v, id, pool);					\
148 149
  })

Ondřej Zajíček's avatar
Ondřej Zajíček committed
150
#define HASH_DELETE2(v,id,pool,key...)					\
151
  ({									\
Ondřej Zajíček's avatar
Ondřej Zajíček committed
152 153 154 155 156 157 158 159 160 161
    HASH_TYPE(v) *_n = HASH_DELETE(v, id, key);				\
    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);				\
    _n;									\
  })

#define HASH_REMOVE2(v,id,pool,node)					\
  ({									\
    HASH_TYPE(v) *_n = HASH_REMOVE(v, id, node);			\
    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);				\
    _n;									\
162
  })
163

Ondřej Zajíček's avatar
Ondřej Zajíček committed
164

165 166 167 168
#define HASH_WALK(v,next,n)						\
  do {									\
    HASH_TYPE(v) *n;							\
    uint _i;								\
169 170
    uint _s = HASH_SIZE(v);						\
    for (_i = 0; _i < _s; _i++)						\
171 172 173 174 175 176 177 178 179
      for (n = (v).data[_i]; n; n = n->next)

#define HASH_WALK_END } while (0)


#define HASH_WALK_DELSAFE(v,next,n)					\
  do {									\
    HASH_TYPE(v) *n, *_next;						\
    uint _i;								\
180 181
    uint _s = HASH_SIZE(v);						\
    for (_i = 0; _i < _s; _i++)						\
182 183 184 185 186
      for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)

#define HASH_WALK_DELSAFE_END } while (0)


Ondřej Zajíček's avatar
Ondřej Zajíček committed
187 188 189 190 191 192 193 194 195 196
#define HASH_WALK_FILTER(v,next,n,nn)					\
  do {									\
    HASH_TYPE(v) *n, **nn;						\
    uint _i;								\
    uint _s = HASH_SIZE(v);						\
    for (_i = 0; _i < _s; _i++)						\
      for (nn = (v).data + _i; n = *nn; (*nn == n) ? (nn = &n->next) : NULL)

#define HASH_WALK_FILTER_END } while (0)

197

198
static inline void
199
mem_hash_init(u64 *h)
200 201 202 203 204
{
  *h = 0x001047d54778bcafULL;
}

static inline void
205
mem_hash_mix(u64 *h, void *p, uint s)
206 207
{
  const u64 multiplier = 0xb38bc09a61202731ULL;
208 209
  const char *pp = p;
  uint i;
210

211 212
  for (i=0; i<s/4; i++)
    *h = *h * multiplier + ((const u32 *)pp)[i];
213

214
  for (i=s & ~0x3; i<s; i++)
215 216
    *h = *h * multiplier + pp[i];
}
217

218
static inline uint
219
mem_hash_value(u64 *h)
220
{
221
  return ((*h >> 32) ^ (*h & 0xffffffff));
222 223
}

224
static inline uint
225
mem_hash(void *p, uint s)
226
{
227
  static u64 h;
228 229 230 231 232
  mem_hash_init(&h);
  mem_hash_mix(&h, p, s);
  return mem_hash_value(&h);
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
233
#endif