2 * Copyright (C) 2012 by Darren Reed.
4 * See the IPFILTER.LICENCE file for details on licencing.
7 typedef enum rbcolour_e {
12 #define RBI_LINK(_n, _t) \
13 struct _n##_rb_link { \
20 #define RBI_HEAD(_n, _t) \
21 struct _n##_rb_head { \
24 int (* compare)(struct _t *, struct _t *); \
27 #define RBI_CODE(_n, _t, _f, _cmp) \
29 typedef void (*_n##_rb_walker_t)(_t *, void *); \
31 _t * _n##_rb_delete(struct _n##_rb_head *, _t *); \
32 void _n##_rb_init(struct _n##_rb_head *); \
33 void _n##_rb_insert(struct _n##_rb_head *, _t *); \
34 _t * _n##_rb_search(struct _n##_rb_head *, void *); \
35 void _n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\
38 rotate_left(struct _n##_rb_head *head, _t *node) \
40 _t *parent, *tmp1, *tmp2; \
42 parent = node->_f.parent; \
43 tmp1 = node->_f.right; \
44 tmp2 = tmp1->_f.left; \
45 node->_f.right = tmp2; \
46 if (tmp2 != & _n##_rb_zero) \
47 tmp2->_f.parent = node; \
48 if (parent == & _n##_rb_zero) \
49 head->top._f.right = tmp1; \
50 else if (parent->_f.right == node) \
51 parent->_f.right = tmp1; \
53 parent->_f.left = tmp1; \
54 tmp1->_f.left = node; \
55 tmp1->_f.parent = parent; \
56 node->_f.parent = tmp1; \
60 rotate_right(struct _n##_rb_head *head, _t *node) \
62 _t *parent, *tmp1, *tmp2; \
64 parent = node->_f.parent; \
65 tmp1 = node->_f.left; \
66 tmp2 = tmp1->_f.right; \
67 node->_f.left = tmp2; \
68 if (tmp2 != &_n##_rb_zero) \
69 tmp2->_f.parent = node; \
70 if (parent == &_n##_rb_zero) \
71 head->top._f.right = tmp1; \
72 else if (parent->_f.right == node) \
73 parent->_f.right = tmp1; \
75 parent->_f.left = tmp1; \
76 tmp1->_f.right = node; \
77 tmp1->_f.parent = parent; \
78 node->_f.parent = tmp1; \
82 _n##_rb_insert(struct _n##_rb_head *head, _t *node) \
84 _t *n, *parent, **p, *tmp1, *gparent; \
86 parent = &head->top; \
87 node->_f.left = &_n##_rb_zero; \
88 node->_f.right = &_n##_rb_zero; \
89 p = &head->top._f.right; \
90 while ((n = *p) != &_n##_rb_zero) { \
91 if (_cmp(node, n) < 0) \
98 node->_f.colour = C_RED; \
99 node->_f.parent = parent; \
101 while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\
102 gparent = parent->_f.parent; \
103 if (parent == gparent->_f.left) { \
104 tmp1 = gparent->_f.right; \
105 if (tmp1->_f.colour == C_RED) { \
106 parent->_f.colour = C_BLACK; \
107 tmp1->_f.colour = C_BLACK; \
108 gparent->_f.colour = C_RED; \
111 if (node == parent->_f.right) { \
113 rotate_left(head, node); \
114 parent = node->_f.parent; \
116 parent->_f.colour = C_BLACK; \
117 gparent->_f.colour = C_RED; \
118 rotate_right(head, gparent); \
121 tmp1 = gparent->_f.left; \
122 if (tmp1->_f.colour == C_RED) { \
123 parent->_f.colour = C_BLACK; \
124 tmp1->_f.colour = C_BLACK; \
125 gparent->_f.colour = C_RED; \
128 if (node == parent->_f.left) { \
130 rotate_right(head, node); \
131 parent = node->_f.parent; \
133 parent->_f.colour = C_BLACK; \
134 gparent->_f.colour = C_RED; \
135 rotate_left(head, parent->_f.parent); \
138 parent = node->_f.parent; \
140 head->top._f.right->_f.colour = C_BLACK; \
145 deleteblack(struct _n##_rb_head *head, _t *parent, _t *node) \
149 while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) && \
150 node != &head->top) { \
151 if (parent->_f.left == node) { \
152 tmp = parent->_f.right; \
153 if (tmp->_f.colour == C_RED) { \
154 tmp->_f.colour = C_BLACK; \
155 parent->_f.colour = C_RED; \
156 rotate_left(head, parent); \
157 tmp = parent->_f.right; \
159 if ((tmp->_f.left == &_n##_rb_zero || \
160 tmp->_f.left->_f.colour == C_BLACK) && \
161 (tmp->_f.right == &_n##_rb_zero || \
162 tmp->_f.right->_f.colour == C_BLACK)) { \
163 tmp->_f.colour = C_RED; \
165 parent = node->_f.parent; \
167 if (tmp->_f.right == &_n##_rb_zero || \
168 tmp->_f.right->_f.colour == C_BLACK) {\
169 _t *tmp2 = tmp->_f.left; \
171 if (tmp2 != &_n##_rb_zero) \
172 tmp2->_f.colour = C_BLACK;\
173 tmp->_f.colour = C_RED; \
174 rotate_right(head, tmp); \
175 tmp = parent->_f.right; \
177 tmp->_f.colour = parent->_f.colour; \
178 parent->_f.colour = C_BLACK; \
179 if (tmp->_f.right != &_n##_rb_zero) \
180 tmp->_f.right->_f.colour = C_BLACK;\
181 rotate_left(head, parent); \
182 node = head->top._f.right; \
185 tmp = parent->_f.left; \
186 if (tmp->_f.colour == C_RED) { \
187 tmp->_f.colour = C_BLACK; \
188 parent->_f.colour = C_RED; \
189 rotate_right(head, parent); \
190 tmp = parent->_f.left; \
192 if ((tmp->_f.left == &_n##_rb_zero || \
193 tmp->_f.left->_f.colour == C_BLACK) && \
194 (tmp->_f.right == &_n##_rb_zero || \
195 tmp->_f.right->_f.colour == C_BLACK)) { \
196 tmp->_f.colour = C_RED; \
198 parent = node->_f.parent; \
200 if (tmp->_f.left == &_n##_rb_zero || \
201 tmp->_f.left->_f.colour == C_BLACK) {\
202 _t *tmp2 = tmp->_f.right; \
204 if (tmp2 != &_n##_rb_zero) \
205 tmp2->_f.colour = C_BLACK;\
206 tmp->_f.colour = C_RED; \
207 rotate_left(head, tmp); \
208 tmp = parent->_f.left; \
210 tmp->_f.colour = parent->_f.colour; \
211 parent->_f.colour = C_BLACK; \
212 if (tmp->_f.left != &_n##_rb_zero) \
213 tmp->_f.left->_f.colour = C_BLACK;\
214 rotate_right(head, parent); \
215 node = head->top._f.right; \
220 if (node != &_n##_rb_zero) \
221 node->_f.colour = C_BLACK; \
225 _n##_rb_delete(struct _n##_rb_head *head, _t *node) \
227 _t *child, *parent, *old = node, *left; \
230 if (node->_f.left == &_n##_rb_zero) { \
231 child = node->_f.right; \
232 } else if (node->_f.right == &_n##_rb_zero) { \
233 child = node->_f.left; \
235 node = node->_f.right; \
236 while ((left = node->_f.left) != &_n##_rb_zero) \
238 child = node->_f.right; \
239 parent = node->_f.parent; \
240 color = node->_f.colour; \
241 if (child != &_n##_rb_zero) \
242 child->_f.parent = parent; \
243 if (parent != &_n##_rb_zero) { \
244 if (parent->_f.left == node) \
245 parent->_f.left = child; \
247 parent->_f.right = child; \
249 head->top._f.right = child; \
251 if (node->_f.parent == old) \
254 if (old->_f.parent != &_n##_rb_zero) { \
255 if (old->_f.parent->_f.left == old) \
256 old->_f.parent->_f.left = node; \
258 old->_f.parent->_f.right = node; \
260 head->top._f.right = child; \
262 old->_f.left->_f.parent = node; \
263 if (old->_f.right != &_n##_rb_zero) \
264 old->_f.right->_f.parent = node; \
265 if (parent != &_n##_rb_zero) { \
270 parent = node->_f.parent; \
271 color= node->_f.colour; \
272 if (child != &_n##_rb_zero) \
273 child->_f.parent = parent; \
274 if (parent != &_n##_rb_zero) { \
275 if (parent->_f.left == node) \
276 parent->_f.left = child; \
278 parent->_f.right = child; \
280 head->top._f.right = child; \
283 if (color == C_BLACK) \
284 deleteblack(head, parent, node); \
290 _n##_rb_init(struct _n##_rb_head *head) \
292 memset(head, 0, sizeof(*head)); \
293 memset(&_n##_rb_zero, 0, sizeof(_n##_rb_zero)); \
294 head->top._f.left = &_n##_rb_zero; \
295 head->top._f.right = &_n##_rb_zero; \
296 head->top._f.parent = &head->top; \
297 _n##_rb_zero._f.left = &_n##_rb_zero; \
298 _n##_rb_zero._f.right = &_n##_rb_zero; \
299 _n##_rb_zero._f.parent = &_n##_rb_zero; \
303 _n##_rb_walktree(struct _n##_rb_head *head, _n##_rb_walker_t func, void *arg)\
307 _t *node = head->top._f.right; \
310 while (node != &_n##_rb_zero) \
311 node = node->_f.left; \
316 while ((node->_f.parent->_f.right == node) && \
317 (node != &_n##_rb_zero)) { \
319 node = node->_f.parent; \
323 for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\
324 node = node->_f.left) \
328 if (node != &_n##_rb_zero) \
332 if (node == &_n##_rb_zero) \
338 _n##_rb_search(struct _n##_rb_head *head, void *key) \
342 node = head->top._f.right; \
343 while (node != &_n##_rb_zero) { \
344 match = _cmp(key, node); \
348 node = node->_f.left; \
350 node = node->_f.right; \
352 if (node == &_n##_rb_zero || match != 0) \
357 #define RBI_DELETE(_n, _h, _v) _n##_rb_delete(_h, _v)
358 #define RBI_FIELD(_n) struct _n##_rb_link
359 #define RBI_INIT(_n, _h) _n##_rb_init(_h)
360 #define RBI_INSERT(_n, _h, _v) _n##_rb_insert(_h, _v)
361 #define RBI_ISEMPTY(_h) ((_h)->count == 0)
362 #define RBI_SEARCH(_n, _h, _k) _n##_rb_search(_h, _k)
363 #define RBI_WALK(_n, _h, _w, _a) _n##_rb_walktree(_h, _w, _a)
364 #define RBI_ZERO(_n) _n##_rb_zero