1/*	$NetBSD: ipf_rb.h,v 1.1.1.2 2012/07/22 13:44:25 darrenr Exp $	*/
2
3/*
4 * Copyright (C) 2012 by Darren Reed.
5 *
6 * See the IPFILTER.LICENCE file for details on licencing.
7 *
8 */
9typedef enum rbcolour_e {
10	C_BLACK = 0,
11	C_RED = 1
12} rbcolour_t;
13
14#define	RBI_LINK(_n, _t)							\
15	struct _n##_rb_link {						\
16		struct _t	*left;					\
17		struct _t	*right;					\
18		struct _t	*parent;				\
19		rbcolour_t	colour;					\
20	}
21
22#define	RBI_HEAD(_n, _t)						\
23struct _n##_rb_head {							\
24	struct _t	top;						\
25	int		count;						\
26	int		(* compare)(struct _t *, struct _t *);		\
27}
28
29#define	RBI_CODE(_n, _t, _f, _cmp)					\
30									\
31typedef	void	(*_n##_rb_walker_t)(_t *, void *);			\
32									\
33_t *	_n##_rb_delete(struct _n##_rb_head *, _t *);			\
34void	_n##_rb_init(struct _n##_rb_head *);				\
35void	_n##_rb_insert(struct _n##_rb_head *, _t *);			\
36_t *	_n##_rb_search(struct _n##_rb_head *, void *);			\
37void	_n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\
38									\
39static void								\
40rotate_left(struct _n##_rb_head *head, _t *node)			\
41{									\
42	_t *parent, *tmp1, *tmp2;					\
43									\
44	parent = node->_f.parent;					\
45	tmp1 = node->_f.right;						\
46	tmp2 = tmp1->_f.left;						\
47	node->_f.right = tmp2;						\
48	if (tmp2 != & _n##_rb_zero)					\
49		tmp2->_f.parent = node;					\
50	if (parent == & _n##_rb_zero)					\
51		head->top._f.right = tmp1;				\
52	else if (parent->_f.right == node)				\
53		parent->_f.right = tmp1;				\
54	else								\
55		parent->_f.left = tmp1;					\
56	tmp1->_f.left = node;						\
57	tmp1->_f.parent = parent;					\
58	node->_f.parent = tmp1;						\
59}									\
60									\
61static void								\
62rotate_right(struct _n##_rb_head *head, _t *node)			\
63{									\
64	_t *parent, *tmp1, *tmp2;					\
65									\
66	parent = node->_f.parent;					\
67	tmp1 = node->_f.left;						\
68	tmp2 = tmp1->_f.right;						\
69	node->_f.left = tmp2;						\
70	if (tmp2 != &_n##_rb_zero)					\
71		tmp2->_f.parent = node;					\
72	if (parent == &_n##_rb_zero)					\
73		head->top._f.right = tmp1;				\
74	else if (parent->_f.right == node)				\
75		parent->_f.right = tmp1;				\
76	else								\
77		parent->_f.left = tmp1;					\
78	tmp1->_f.right = node;						\
79	tmp1->_f.parent = parent;					\
80	node->_f.parent = tmp1;						\
81}									\
82									\
83void									\
84_n##_rb_insert(struct _n##_rb_head *head, _t *node)			\
85{									\
86	_t *n, *parent, **p, *tmp1, *gparent;				\
87									\
88	parent = &head->top;						\
89	node->_f.left = &_n##_rb_zero;					\
90	node->_f.right = &_n##_rb_zero;					\
91	p = &head->top._f.right;					\
92	while ((n = *p) != &_n##_rb_zero) {				\
93		if (_cmp(node, n) < 0)					\
94			p = &n->_f.left;				\
95		else							\
96			p = &n->_f.right;				\
97		parent = n;						\
98	}								\
99	*p = node;							\
100	node->_f.colour = C_RED;					\
101	node->_f.parent = parent;					\
102									\
103	while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\
104		gparent = parent->_f.parent;				\
105		if (parent == gparent->_f.left) {			\
106			tmp1 = gparent->_f.right;			\
107			if (tmp1->_f.colour == C_RED) {			\
108				parent->_f.colour = C_BLACK;		\
109				tmp1->_f.colour = C_BLACK;		\
110				gparent->_f.colour = C_RED;		\
111				node = gparent;				\
112			} else {					\
113				if (node == parent->_f.right) {		\
114					node = parent;			\
115					rotate_left(head, node);	\
116					parent = node->_f.parent;	\
117				}					\
118				parent->_f.colour = C_BLACK;		\
119				gparent->_f.colour = C_RED;		\
120				rotate_right(head, gparent);		\
121			}						\
122		} else {						\
123			tmp1 = gparent->_f.left;			\
124			if (tmp1->_f.colour == C_RED) {			\
125				parent->_f.colour = C_BLACK;		\
126				tmp1->_f.colour = C_BLACK;		\
127				gparent->_f.colour = C_RED;		\
128				node = gparent;				\
129			} else {					\
130				if (node == parent->_f.left) {		\
131					node = parent;			\
132					rotate_right(head, node);	\
133					parent = node->_f.parent;	\
134				}					\
135				parent->_f.colour = C_BLACK;		\
136				gparent->_f.colour = C_RED;		\
137				rotate_left(head, parent->_f.parent);	\
138			}						\
139		}							\
140		parent = node->_f.parent;				\
141	}								\
142	head->top._f.right->_f.colour = C_BLACK;			\
143	head->count++;						\
144}									\
145									\
146static void								\
147deleteblack(struct _n##_rb_head *head, _t *parent, _t *node)		\
148{									\
149	_t *tmp;							\
150									\
151	while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) &&	\
152	       node != &head->top) {					\
153		if (parent->_f.left == node) {				\
154			tmp = parent->_f.right;				\
155			if (tmp->_f.colour == C_RED) {			\
156				tmp->_f.colour = C_BLACK;		\
157				parent->_f.colour = C_RED;		\
158				rotate_left(head, parent);		\
159				tmp = parent->_f.right;			\
160			}						\
161			if ((tmp->_f.left == &_n##_rb_zero ||		\
162			     tmp->_f.left->_f.colour == C_BLACK) &&	\
163			    (tmp->_f.right == &_n##_rb_zero ||		\
164			     tmp->_f.right->_f.colour == C_BLACK)) {	\
165				tmp->_f.colour = C_RED;			\
166				node = parent;				\
167				parent = node->_f.parent;		\
168			} else {					\
169				if (tmp->_f.right == &_n##_rb_zero ||	\
170				    tmp->_f.right->_f.colour == C_BLACK) {\
171					_t *tmp2 = tmp->_f.left;	\
172									\
173					if (tmp2 != &_n##_rb_zero)	\
174						tmp2->_f.colour = C_BLACK;\
175					tmp->_f.colour = C_RED;		\
176					rotate_right(head, tmp);	\
177					tmp = parent->_f.right;		\
178				}					\
179				tmp->_f.colour = parent->_f.colour;	\
180				parent->_f.colour = C_BLACK;		\
181				if (tmp->_f.right != &_n##_rb_zero)	\
182					tmp->_f.right->_f.colour = C_BLACK;\
183				rotate_left(head, parent);		\
184				node = head->top._f.right;		\
185			}						\
186		} else {						\
187			tmp = parent->_f.left;				\
188			if (tmp->_f.colour == C_RED) {			\
189				tmp->_f.colour = C_BLACK;		\
190				parent->_f.colour = C_RED;		\
191				rotate_right(head, parent);		\
192				tmp = parent->_f.left;			\
193			}						\
194			if ((tmp->_f.left == &_n##_rb_zero ||		\
195			     tmp->_f.left->_f.colour == C_BLACK) &&	\
196			    (tmp->_f.right == &_n##_rb_zero ||		\
197			     tmp->_f.right->_f.colour == C_BLACK)) {	\
198				tmp->_f.colour = C_RED;			\
199				node = parent;				\
200				parent = node->_f.parent;		\
201			} else {					\
202				if (tmp->_f.left == &_n##_rb_zero ||	\
203				    tmp->_f.left->_f.colour == C_BLACK) {\
204					_t *tmp2 = tmp->_f.right;	\
205									\
206					if (tmp2 != &_n##_rb_zero)	\
207						tmp2->_f.colour = C_BLACK;\
208					tmp->_f.colour = C_RED;		\
209					rotate_left(head, tmp);		\
210					tmp = parent->_f.left;		\
211				}					\
212				tmp->_f.colour = parent->_f.colour;	\
213				parent->_f.colour = C_BLACK;		\
214				if (tmp->_f.left != &_n##_rb_zero)	\
215					tmp->_f.left->_f.colour = C_BLACK;\
216				rotate_right(head, parent);		\
217				node = head->top._f.right;		\
218				break;					\
219			}						\
220		}							\
221	}								\
222	if (node != &_n##_rb_zero)					\
223		node->_f.colour = C_BLACK;				\
224}									\
225									\
226_t *									\
227_n##_rb_delete(struct _n##_rb_head *head, _t *node)			\
228{									\
229	_t *child, *parent, *old = node, *left;				\
230	rbcolour_t color;						\
231									\
232	if (node->_f.left == &_n##_rb_zero) {				\
233		child = node->_f.right;					\
234	} else if (node->_f.right == &_n##_rb_zero) {			\
235		child = node->_f.left;					\
236	} else {							\
237		node = node->_f.right;					\
238		while ((left = node->_f.left) != &_n##_rb_zero)		\
239			node = left;					\
240		child = node->_f.right;					\
241		parent = node->_f.parent;				\
242		color = node->_f.colour;				\
243		if (child != &_n##_rb_zero)				\
244			child->_f.parent = parent;			\
245		if (parent != &_n##_rb_zero) {				\
246			if (parent->_f.left == node)			\
247				parent->_f.left = child;		\
248			else						\
249				parent->_f.right = child;		\
250		} else {						\
251			head->top._f.right = child;			\
252		}							\
253		if (node->_f.parent == old)				\
254			parent = node;					\
255		*node = *old;						\
256		if (old->_f.parent != &_n##_rb_zero) {			\
257			if (old->_f.parent->_f.left == old)		\
258				old->_f.parent->_f.left = node;		\
259			else						\
260				old->_f.parent->_f.right = node;	\
261		} else {						\
262			head->top._f.right = child;			\
263		}							\
264		old->_f.left->_f.parent = node;				\
265		if (old->_f.right != &_n##_rb_zero)			\
266			old->_f.right->_f.parent = node;		\
267		if (parent != &_n##_rb_zero) {				\
268			left = parent;					\
269		}							\
270		goto colour;						\
271	}								\
272	parent = node->_f.parent;					\
273	color= node->_f.colour;						\
274	if (child != &_n##_rb_zero)					\
275		child->_f.parent = parent;				\
276	if (parent != &_n##_rb_zero) {					\
277		if (parent->_f.left == node)				\
278			parent->_f.left = child;			\
279		else							\
280			parent->_f.right = child;			\
281	} else {							\
282		head->top._f.right = child;				\
283	}								\
284colour:									\
285	if (color == C_BLACK)						\
286		deleteblack(head, parent, node);			\
287	head->count--;							\
288	return old;							\
289}									\
290									\
291void									\
292_n##_rb_init(struct _n##_rb_head *head)					\
293{									\
294	memset(head, 0, sizeof(*head));					\
295	memset(&_n##_rb_zero, 0, sizeof(_n##_rb_zero));			\
296	head->top._f.left = &_n##_rb_zero;				\
297	head->top._f.right = &_n##_rb_zero;				\
298	head->top._f.parent = &head->top;				\
299	_n##_rb_zero._f.left = &_n##_rb_zero;				\
300	_n##_rb_zero._f.right = &_n##_rb_zero;				\
301	_n##_rb_zero._f.parent = &_n##_rb_zero;				\
302}									\
303									\
304void									\
305_n##_rb_walktree(struct _n##_rb_head *head, _n##_rb_walker_t func, void *arg)\
306{									\
307	_t *prev;							\
308	_t *next;							\
309	_t *node = head->top._f.right;					\
310	_t *base;							\
311									\
312	while (node != &_n##_rb_zero)					\
313		node = node->_f.left;					\
314									\
315	for (;;) {							\
316		base = node;						\
317		prev = node;						\
318		while ((node->_f.parent->_f.right == node) &&		\
319		       (node != &_n##_rb_zero))	{			\
320			prev = node;					\
321			node = node->_f.parent;				\
322		}							\
323									\
324		node = prev;						\
325		for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\
326		     node = node->_f.left)				\
327			prev = node;					\
328		next = prev;						\
329									\
330		if (node != &_n##_rb_zero)				\
331			func(node, arg);				\
332									\
333		node = next;						\
334		if (node == &_n##_rb_zero)				\
335			break;						\
336	}								\
337}									\
338									\
339_t *									\
340_n##_rb_search(struct _n##_rb_head *head, void *key)			\
341{									\
342	int	match;							\
343	_t	*node;							\
344	node = head->top._f.right;					\
345	while (node != &_n##_rb_zero) {					\
346		match = _cmp(key, node);				\
347		if (match == 0)						\
348			break;						\
349		if (match< 0)						\
350			node = node->_f.left;				\
351		else							\
352			node = node->_f.right;				\
353	}								\
354	if (node == &_n##_rb_zero || match != 0)			\
355		return (NULL);						\
356	return (node);							\
357}
358
359#define	RBI_DELETE(_n, _h, _v)		_n##_rb_delete(_h, _v)
360#define	RBI_FIELD(_n)			struct _n##_rb_link
361#define	RBI_INIT(_n, _h)		_n##_rb_init(_h)
362#define	RBI_INSERT(_n, _h, _v)		_n##_rb_insert(_h, _v)
363#define	RBI_ISEMPTY(_h)			((_h)->count == 0)
364#define	RBI_SEARCH(_n, _h, _k)		_n##_rb_search(_h, _k)
365#define	RBI_WALK(_n, _h, _w, _a)	_n##_rb_walktree(_h, _w, _a)
366#define	RBI_ZERO(_n)			_n##_rb_zero
367