Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / hash.h @ 6b3f1a54

History | View | Annotate | Download (6.17 KB)

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

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

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

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

    
214
  for (i=s & ~0x3; i<s; i++)
215
    *h = *h * multiplier + pp[i];
216
}
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
  mem_hash_init(&h);
229
  mem_hash_mix(&h, p, s);
230
  return mem_hash_value(&h);
231
}
232

    
233
#endif