Statistics
| Branch: | Revision:

iof-bird-daemon / lib / hash.h @ 9b136840

History | View | Annotate | Download (5.24 KB)

1 bf139664 Ondrej Zajicek
2
3 6a8d3f1c Ondrej Zajicek
#define HASH(type)                struct { type **data; uint count, order; }
4 bf139664 Ondrej Zajicek
#define HASH_TYPE(v)                typeof(** (v).data)
5 6a8d3f1c Ondrej Zajicek
#define HASH_SIZE(v)                (1 << (v).order)
6 e7d2ac44 Ondrej Zajicek
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 bf139664 Ondrej Zajicek
10 6a8d3f1c Ondrej Zajicek
11
#define HASH_INIT(v,pool,init_order)                                        \
12 bf139664 Ondrej Zajicek
  ({                                                                        \
13 6a8d3f1c Ondrej Zajicek
    (v).count = 0;                                                        \
14
    (v).order = (init_order);                                                \
15
    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));        \
16 bf139664 Ondrej Zajicek
  })
17
18 6a8d3f1c Ondrej Zajicek
#define HASH_FIND(v,id,key...)                                                \
19 bf139664 Ondrej Zajicek
  ({                                                                        \
20 e7d2ac44 Ondrej Zajicek
    u32 _h = HASH_FN(v, id, key);                                        \
21 6a8d3f1c Ondrej Zajicek
    HASH_TYPE(v) *_n = (v).data[_h];                                        \
22 e7d2ac44 Ondrej Zajicek
    while (_n && !HASH_EQ(v, id, id##_KEY(_n), key))                        \
23 6a8d3f1c Ondrej Zajicek
      _n = id##_NEXT(_n);                                                \
24 bf139664 Ondrej Zajicek
    _n;                                                                        \
25
  })
26
27 6a8d3f1c Ondrej Zajicek
#define HASH_INSERT(v,id,node)                                                \
28 bf139664 Ondrej Zajicek
  ({                                                                        \
29 e7d2ac44 Ondrej Zajicek
    u32 _h = HASH_FN(v, id, id##_KEY((node)));                                \
30 6a8d3f1c Ondrej Zajicek
    HASH_TYPE(v) **_nn = (v).data + _h;                                        \
31
    id##_NEXT(node) = *_nn;                                                \
32 bf139664 Ondrej Zajicek
    *_nn = node;                                                        \
33 6a8d3f1c Ondrej Zajicek
    (v).count++;                                                        \
34 bf139664 Ondrej Zajicek
  })
35
36 6a8d3f1c Ondrej Zajicek
#define HASH_DO_REMOVE(v,id,_nn)                                        \
37 bf139664 Ondrej Zajicek
  ({                                                                        \
38 e7d2ac44 Ondrej Zajicek
    *_nn = id##_NEXT((*_nn));                                                \
39
    (v).count--;                                                        \
40 bf139664 Ondrej Zajicek
  })
41
42 6a8d3f1c Ondrej Zajicek
#define HASH_DELETE(v,id,key...)                                        \
43
  ({                                                                        \
44 e7d2ac44 Ondrej Zajicek
    u32 _h = HASH_FN(v, id, key);                                        \
45
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;                                \
46 6a8d3f1c Ondrej Zajicek
                                                                        \
47 e7d2ac44 Ondrej Zajicek
    while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key))                \
48 6a8d3f1c Ondrej Zajicek
      _nn = &(id##_NEXT((*_nn)));                                        \
49
                                                                        \
50 e7d2ac44 Ondrej Zajicek
    if (_n = *_nn)                                                        \
51
      HASH_DO_REMOVE(v,id,_nn);                                                \
52
    _n;                                                                        \
53 6a8d3f1c Ondrej Zajicek
  })
54
55 bf139664 Ondrej Zajicek
#define HASH_REMOVE(v,id,node)                                                \
56
  ({                                                                        \
57 e7d2ac44 Ondrej Zajicek
    u32 _h = HASH_FN(v, id, id##_KEY((node)));                                \
58
    HASH_TYPE(v) *_n, **_nn = (v).data + _h;                                \
59 6a8d3f1c Ondrej Zajicek
                                                                        \
60 bf139664 Ondrej Zajicek
    while ((*_nn) && (*_nn != (node)))                                        \
61 6a8d3f1c Ondrej Zajicek
      _nn = &(id##_NEXT((*_nn)));                                        \
62 bf139664 Ondrej Zajicek
                                                                        \
63 e7d2ac44 Ondrej Zajicek
    if (_n = *_nn)                                                        \
64
      HASH_DO_REMOVE(v,id,_nn);                                                \
65
    _n;                                                                        \
66 bf139664 Ondrej Zajicek
  })
67
68
69 6a8d3f1c Ondrej Zajicek
#define HASH_REHASH(v,id,pool,step)                                        \
70
  ({                                                                        \
71
    HASH_TYPE(v) *_n, *_n2, **_od;                                        \
72 e7d2ac44 Ondrej Zajicek
    uint _i, _os;                                                        \
73 6a8d3f1c Ondrej Zajicek
                                                                        \
74 e7d2ac44 Ondrej Zajicek
    _os = HASH_SIZE(v);                                                        \
75 6a8d3f1c Ondrej Zajicek
    _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 e7d2ac44 Ondrej Zajicek
    for (_i = 0; _i < _os; _i++)                                        \
81 6a8d3f1c Ondrej Zajicek
      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 e7d2ac44 Ondrej Zajicek
#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 6a8d3f1c Ondrej Zajicek
  { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
97
98 e7d2ac44 Ondrej Zajicek
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 6a8d3f1c Ondrej Zajicek
  ({                                                                        \
130 e7d2ac44 Ondrej Zajicek
    HASH_INSERT(v, id, node);                                                \
131
    HASH_MAY_STEP_UP(v, id, pool);                                        \
132 6a8d3f1c Ondrej Zajicek
  })
133
134 e7d2ac44 Ondrej Zajicek
#define HASH_DELETE2(v,id,pool,key...)                                        \
135 6a8d3f1c Ondrej Zajicek
  ({                                                                        \
136 e7d2ac44 Ondrej Zajicek
    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 6a8d3f1c Ondrej Zajicek
  })
147 bf139664 Ondrej Zajicek
148 e7d2ac44 Ondrej Zajicek
149 bf139664 Ondrej Zajicek
#define HASH_WALK(v,next,n)                                                \
150
  do {                                                                        \
151
    HASH_TYPE(v) *n;                                                        \
152
    uint _i;                                                                \
153 6a8d3f1c Ondrej Zajicek
    uint _s = HASH_SIZE(v);                                                \
154
    for (_i = 0; _i < _s; _i++)                                                \
155 bf139664 Ondrej Zajicek
      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 6a8d3f1c Ondrej Zajicek
    uint _s = HASH_SIZE(v);                                                \
165
    for (_i = 0; _i < _s; _i++)                                                \
166 bf139664 Ondrej Zajicek
      for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
167
168
#define HASH_WALK_DELSAFE_END } while (0)
169
170
171 e7d2ac44 Ondrej Zajicek
#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)