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