Statistics
| Branch: | Revision:

iof-bird-daemon / lib / hash.h @ c8cafc8e

History | View | Annotate | Download (5.49 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_FIND(v,id,key...)                                                \
29
  ({                                                                        \
30
    u32 _h = HASH_FN(v, id, key);                                        \
31
    HASH_TYPE(v) *_n = (v).data[_h];                                        \
32
    while (_n && !HASH_EQ(v, id, id##_KEY(_n), key))                        \
33
      _n = id##_NEXT(_n);                                                \
34
    _n;                                                                        \
35
  })
36

    
37
#define HASH_INSERT(v,id,node)                                                \
38
  ({                                                                        \
39
    u32 _h = HASH_FN(v, id, id##_KEY((node)));                                \
40
    HASH_TYPE(v) **_nn = (v).data + _h;                                        \
41
    id##_NEXT(node) = *_nn;                                                \
42
    *_nn = node;                                                        \
43
    (v).count++;                                                        \
44
  })
45

    
46
#define HASH_DO_REMOVE(v,id,_nn)                                        \
47
  ({                                                                        \
48
    *_nn = id##_NEXT((*_nn));                                                \
49
    (v).count--;                                                        \
50
  })
51

    
52
#define HASH_DELETE(v,id,key...)                                        \
53
  ({                                                                        \
54
    u32 _h = HASH_FN(v, id, key);                                        \
55
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;                                \
56
                                                                        \
57
    while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key))                \
58
      _nn = &(id##_NEXT((*_nn)));                                        \
59
                                                                        \
60
    if (_n = *_nn)                                                        \
61
      HASH_DO_REMOVE(v,id,_nn);                                                \
62
    _n;                                                                        \
63
  })
64

    
65
#define HASH_REMOVE(v,id,node)                                                \
66
  ({                                                                        \
67
    u32 _h = HASH_FN(v, id, id##_KEY((node)));                                \
68
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;                                \
69
                                                                        \
70
    while ((*_nn) && (*_nn != (node)))                                        \
71
      _nn = &(id##_NEXT((*_nn)));                                        \
72
                                                                        \
73
    if (_n = *_nn)                                                        \
74
      HASH_DO_REMOVE(v,id,_nn);                                                \
75
    _n;                                                                        \
76
  })
77

    
78

    
79
#define HASH_REHASH(v,id,pool,step)                                        \
80
  ({                                                                        \
81
    HASH_TYPE(v) *_n, *_n2, **_od;                                        \
82
    uint _i, _os;                                                        \
83
                                                                        \
84
    _os = HASH_SIZE(v);                                                        \
85
    _od = (v).data;                                                        \
86
    (v).count = 0;                                                        \
87
    (v).order += (step);                                                \
88
    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));        \
89
                                                                        \
90
    for (_i = 0; _i < _os; _i++)                                        \
91
      for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2)        \
92
        HASH_INSERT(v, id, _n);                                                \
93
                                                                        \
94
    mb_free(_od);                                                        \
95
  })
96

    
97
#define REHASH_LO_MARK(a,b,c,d,e,f)        a
98
#define REHASH_HI_MARK(a,b,c,d,e,f)        b
99
#define REHASH_LO_STEP(a,b,c,d,e,f)        c
100
#define REHASH_HI_STEP(a,b,c,d,e,f)        d
101
#define REHASH_LO_BOUND(a,b,c,d,e,f)        e
102
#define REHASH_HI_BOUND(a,b,c,d,e,f)        f
103

    
104
#define HASH_DEFINE_REHASH_FN(id,type)                                        \
105
  static void id##_REHASH(void *v, pool *p, int step)                        \
106
  { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
107

    
108

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

    
113
#define HASH_MAY_STEP_UP_(v,pool,rehash_fn,args)                        \
114
  ({                                                                    \
115
    if (((v).count > (HASH_SIZE(v) REHASH_HI_MARK(args))) &&                \
116
        ((v).order < (REHASH_HI_BOUND(args))))                                \
117
      rehash_fn(&(v), pool, REHASH_HI_STEP(args));                        \
118
  })
119

    
120
#define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)                        \
121
  ({                                                                    \
122
    if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&                \
123
        ((v).order > (REHASH_LO_BOUND(args))))                                \
124
      rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));                        \
125
  })
126

    
127
#define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)                        \
128
  ({                                                                    \
129
    uint _o = (v).order;                                                        \
130
    while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&                \
131
           (_o > (REHASH_LO_BOUND(args))))                                \
132
      _o -= (REHASH_LO_STEP(args));                                        \
133
    if (_o < (v).order)                                                        \
134
      rehash_fn(&(v), pool, _o - (v).order);                                \
135
  })
136

    
137

    
138
#define HASH_INSERT2(v,id,pool,node)                                        \
139
  ({                                                                        \
140
    HASH_INSERT(v, id, node);                                                \
141
    HASH_MAY_STEP_UP(v, id, pool);                                        \
142
  })
143

    
144
#define HASH_DELETE2(v,id,pool,key...)                                        \
145
  ({                                                                        \
146
    HASH_TYPE(v) *_n = HASH_DELETE(v, id, key);                                \
147
    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);                                \
148
    _n;                                                                        \
149
  })
150

    
151
#define HASH_REMOVE2(v,id,pool,node)                                        \
152
  ({                                                                        \
153
    HASH_TYPE(v) *_n = HASH_REMOVE(v, id, node);                        \
154
    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);                                \
155
    _n;                                                                        \
156
  })
157

    
158

    
159
#define HASH_WALK(v,next,n)                                                \
160
  do {                                                                        \
161
    HASH_TYPE(v) *n;                                                        \
162
    uint _i;                                                                \
163
    uint _s = HASH_SIZE(v);                                                \
164
    for (_i = 0; _i < _s; _i++)                                                \
165
      for (n = (v).data[_i]; n; n = n->next)
166

    
167
#define HASH_WALK_END } while (0)
168

    
169

    
170
#define HASH_WALK_DELSAFE(v,next,n)                                        \
171
  do {                                                                        \
172
    HASH_TYPE(v) *n, *_next;                                                \
173
    uint _i;                                                                \
174
    uint _s = HASH_SIZE(v);                                                \
175
    for (_i = 0; _i < _s; _i++)                                                \
176
      for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
177

    
178
#define HASH_WALK_DELSAFE_END } while (0)
179

    
180

    
181
#define HASH_WALK_FILTER(v,next,n,nn)                                        \
182
  do {                                                                        \
183
    HASH_TYPE(v) *n, **nn;                                                \
184
    uint _i;                                                                \
185
    uint _s = HASH_SIZE(v);                                                \
186
    for (_i = 0; _i < _s; _i++)                                                \
187
      for (nn = (v).data + _i; n = *nn; (*nn == n) ? (nn = &n->next) : NULL)
188

    
189
#define HASH_WALK_FILTER_END } while (0)
190

    
191
#endif