contrib/ipfilter/ipf_rb.h

12 #define	RBI_LINK(_n, _t)							\
13 	struct _n##_rb_link {						\
20 #define	RBI_HEAD(_n, _t)						\
21 struct _n##_rb_head {							\
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)			\
46 	if (tmp2 != & _n##_rb_zero)					\
48 	if (parent == & _n##_rb_zero)					\
60 rotate_right(struct _n##_rb_head *head, _t *node)			\
68 	if (tmp2 != &_n##_rb_zero)					\
70 	if (parent == &_n##_rb_zero)					\
82 _n##_rb_insert(struct _n##_rb_head *head, _t *node)			\
87 	node->_f.left = &_n##_rb_zero;					\
88 	node->_f.right = &_n##_rb_zero;					\
90 	while ((n = *p) != &_n##_rb_zero) {				\
101 	while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\
145 deleteblack(struct _n##_rb_head *head, _t *parent, _t *node)		\
149 	while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) &&	\
159 			if ((tmp->_f.left == &_n##_rb_zero ||		\
161 			    (tmp->_f.right == &_n##_rb_zero ||		\
167 				if (tmp->_f.right == &_n##_rb_zero ||	\
171 					if (tmp2 != &_n##_rb_zero)	\
179 				if (tmp->_f.right != &_n##_rb_zero)	\
192 			if ((tmp->_f.left == &_n##_rb_zero ||		\
194 			    (tmp->_f.right == &_n##_rb_zero ||		\
200 				if (tmp->_f.left == &_n##_rb_zero ||	\
204 					if (tmp2 != &_n##_rb_zero)	\
212 				if (tmp->_f.left != &_n##_rb_zero)	\
220 	if (node != &_n##_rb_zero)					\
225 _n##_rb_delete(struct _n##_rb_head *head, _t *node)			\
230 	if (node->_f.left == &_n##_rb_zero) {				\
232 	} else if (node->_f.right == &_n##_rb_zero) {			\
236 		while ((left = node->_f.left) != &_n##_rb_zero)		\
241 		if (child != &_n##_rb_zero)				\
243 		if (parent != &_n##_rb_zero) {				\
254 		if (old->_f.parent != &_n##_rb_zero) {			\
263 		if (old->_f.right != &_n##_rb_zero)			\
265 		if (parent != &_n##_rb_zero) {				\
272 	if (child != &_n##_rb_zero)					\
274 	if (parent != &_n##_rb_zero) {					\
290 _n##_rb_init(struct _n##_rb_head *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;				\
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)\
310 	while (node != &_n##_rb_zero)					\
317 		       (node != &_n##_rb_zero))	{			\
323 		for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\
328 		if (node != &_n##_rb_zero)				\
332 		if (node == &_n##_rb_zero)				\
338 _n##_rb_search(struct _n##_rb_head *head, void *key)			\
343 	while (node != &_n##_rb_zero) {					\
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)
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