Statistics
| Branch: | Revision:

iof-bird-daemon / lib / hash.h @ 3e236955

History | View | Annotate | Download (5.24 KB)

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)                (1U << (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
    uint _o = (v).order;                                                        \
120
    while (((v).count < ((1U << _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 - (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