/* $NetBSD: ipf_rb.h,v 1.1.1.2 2012/07/22 13:44:25 darrenr Exp $ */ /* * Copyright (C) 2012 by Darren Reed. * * See the IPFILTER.LICENCE file for details on licencing. * */ typedef enum rbcolour_e { C_BLACK = 0, C_RED = 1 } rbcolour_t; #define RBI_LINK(_n, _t) \ struct _n##_rb_link { \ struct _t *left; \ struct _t *right; \ struct _t *parent; \ rbcolour_t colour; \ } #define RBI_HEAD(_n, _t) \ struct _n##_rb_head { \ struct _t top; \ int count; \ int (* compare)(struct _t *, struct _t *); \ } #define RBI_CODE(_n, _t, _f, _cmp) \ \ typedef void (*_n##_rb_walker_t)(_t *, void *); \ \ _t * _n##_rb_delete(struct _n##_rb_head *, _t *); \ void _n##_rb_init(struct _n##_rb_head *); \ void _n##_rb_insert(struct _n##_rb_head *, _t *); \ _t * _n##_rb_search(struct _n##_rb_head *, void *); \ void _n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\ \ static void \ rotate_left(struct _n##_rb_head *head, _t *node) \ { \ _t *parent, *tmp1, *tmp2; \ \ parent = node->_f.parent; \ tmp1 = node->_f.right; \ tmp2 = tmp1->_f.left; \ node->_f.right = tmp2; \ if (tmp2 != & _n##_rb_zero) \ tmp2->_f.parent = node; \ if (parent == & _n##_rb_zero) \ head->top._f.right = tmp1; \ else if (parent->_f.right == node) \ parent->_f.right = tmp1; \ else \ parent->_f.left = tmp1; \ tmp1->_f.left = node; \ tmp1->_f.parent = parent; \ node->_f.parent = tmp1; \ } \ \ static void \ rotate_right(struct _n##_rb_head *head, _t *node) \ { \ _t *parent, *tmp1, *tmp2; \ \ parent = node->_f.parent; \ tmp1 = node->_f.left; \ tmp2 = tmp1->_f.right; \ node->_f.left = tmp2; \ if (tmp2 != &_n##_rb_zero) \ tmp2->_f.parent = node; \ if (parent == &_n##_rb_zero) \ head->top._f.right = tmp1; \ else if (parent->_f.right == node) \ parent->_f.right = tmp1; \ else \ parent->_f.left = tmp1; \ tmp1->_f.right = node; \ tmp1->_f.parent = parent; \ node->_f.parent = tmp1; \ } \ \ void \ _n##_rb_insert(struct _n##_rb_head *head, _t *node) \ { \ _t *n, *parent, **p, *tmp1, *gparent; \ \ parent = &head->top; \ node->_f.left = &_n##_rb_zero; \ node->_f.right = &_n##_rb_zero; \ p = &head->top._f.right; \ while ((n = *p) != &_n##_rb_zero) { \ if (_cmp(node, n) < 0) \ p = &n->_f.left; \ else \ p = &n->_f.right; \ parent = n; \ } \ *p = node; \ node->_f.colour = C_RED; \ node->_f.parent = parent; \ \ while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\ gparent = parent->_f.parent; \ if (parent == gparent->_f.left) { \ tmp1 = gparent->_f.right; \ if (tmp1->_f.colour == C_RED) { \ parent->_f.colour = C_BLACK; \ tmp1->_f.colour = C_BLACK; \ gparent->_f.colour = C_RED; \ node = gparent; \ } else { \ if (node == parent->_f.right) { \ node = parent; \ rotate_left(head, node); \ parent = node->_f.parent; \ } \ parent->_f.colour = C_BLACK; \ gparent->_f.colour = C_RED; \ rotate_right(head, gparent); \ } \ } else { \ tmp1 = gparent->_f.left; \ if (tmp1->_f.colour == C_RED) { \ parent->_f.colour = C_BLACK; \ tmp1->_f.colour = C_BLACK; \ gparent->_f.colour = C_RED; \ node = gparent; \ } else { \ if (node == parent->_f.left) { \ node = parent; \ rotate_right(head, node); \ parent = node->_f.parent; \ } \ parent->_f.colour = C_BLACK; \ gparent->_f.colour = C_RED; \ rotate_left(head, parent->_f.parent); \ } \ } \ parent = node->_f.parent; \ } \ head->top._f.right->_f.colour = C_BLACK; \ head->count++; \ } \ \ static void \ deleteblack(struct _n##_rb_head *head, _t *parent, _t *node) \ { \ _t *tmp; \ \ while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) && \ node != &head->top) { \ if (parent->_f.left == node) { \ tmp = parent->_f.right; \ if (tmp->_f.colour == C_RED) { \ tmp->_f.colour = C_BLACK; \ parent->_f.colour = C_RED; \ rotate_left(head, parent); \ tmp = parent->_f.right; \ } \ if ((tmp->_f.left == &_n##_rb_zero || \ tmp->_f.left->_f.colour == C_BLACK) && \ (tmp->_f.right == &_n##_rb_zero || \ tmp->_f.right->_f.colour == C_BLACK)) { \ tmp->_f.colour = C_RED; \ node = parent; \ parent = node->_f.parent; \ } else { \ if (tmp->_f.right == &_n##_rb_zero || \ tmp->_f.right->_f.colour == C_BLACK) {\ _t *tmp2 = tmp->_f.left; \ \ if (tmp2 != &_n##_rb_zero) \ tmp2->_f.colour = C_BLACK;\ tmp->_f.colour = C_RED; \ rotate_right(head, tmp); \ tmp = parent->_f.right; \ } \ tmp->_f.colour = parent->_f.colour; \ parent->_f.colour = C_BLACK; \ if (tmp->_f.right != &_n##_rb_zero) \ tmp->_f.right->_f.colour = C_BLACK;\ rotate_left(head, parent); \ node = head->top._f.right; \ } \ } else { \ tmp = parent->_f.left; \ if (tmp->_f.colour == C_RED) { \ tmp->_f.colour = C_BLACK; \ parent->_f.colour = C_RED; \ rotate_right(head, parent); \ tmp = parent->_f.left; \ } \ if ((tmp->_f.left == &_n##_rb_zero || \ tmp->_f.left->_f.colour == C_BLACK) && \ (tmp->_f.right == &_n##_rb_zero || \ tmp->_f.right->_f.colour == C_BLACK)) { \ tmp->_f.colour = C_RED; \ node = parent; \ parent = node->_f.parent; \ } else { \ if (tmp->_f.left == &_n##_rb_zero || \ tmp->_f.left->_f.colour == C_BLACK) {\ _t *tmp2 = tmp->_f.right; \ \ if (tmp2 != &_n##_rb_zero) \ tmp2->_f.colour = C_BLACK;\ tmp->_f.colour = C_RED; \ rotate_left(head, tmp); \ tmp = parent->_f.left; \ } \ tmp->_f.colour = parent->_f.colour; \ parent->_f.colour = C_BLACK; \ if (tmp->_f.left != &_n##_rb_zero) \ tmp->_f.left->_f.colour = C_BLACK;\ rotate_right(head, parent); \ node = head->top._f.right; \ break; \ } \ } \ } \ if (node != &_n##_rb_zero) \ node->_f.colour = C_BLACK; \ } \ \ _t * \ _n##_rb_delete(struct _n##_rb_head *head, _t *node) \ { \ _t *child, *parent, *old = node, *left; \ rbcolour_t color; \ \ if (node->_f.left == &_n##_rb_zero) { \ child = node->_f.right; \ } else if (node->_f.right == &_n##_rb_zero) { \ child = node->_f.left; \ } else { \ node = node->_f.right; \ while ((left = node->_f.left) != &_n##_rb_zero) \ node = left; \ child = node->_f.right; \ parent = node->_f.parent; \ color = node->_f.colour; \ if (child != &_n##_rb_zero) \ child->_f.parent = parent; \ if (parent != &_n##_rb_zero) { \ if (parent->_f.left == node) \ parent->_f.left = child; \ else \ parent->_f.right = child; \ } else { \ head->top._f.right = child; \ } \ if (node->_f.parent == old) \ parent = node; \ *node = *old; \ if (old->_f.parent != &_n##_rb_zero) { \ if (old->_f.parent->_f.left == old) \ old->_f.parent->_f.left = node; \ else \ old->_f.parent->_f.right = node; \ } else { \ head->top._f.right = child; \ } \ old->_f.left->_f.parent = node; \ if (old->_f.right != &_n##_rb_zero) \ old->_f.right->_f.parent = node; \ if (parent != &_n##_rb_zero) { \ left = parent; \ } \ goto colour; \ } \ parent = node->_f.parent; \ color= node->_f.colour; \ if (child != &_n##_rb_zero) \ child->_f.parent = parent; \ if (parent != &_n##_rb_zero) { \ if (parent->_f.left == node) \ parent->_f.left = child; \ else \ parent->_f.right = child; \ } else { \ head->top._f.right = child; \ } \ colour: \ if (color == C_BLACK) \ deleteblack(head, parent, node); \ head->count--; \ return old; \ } \ \ void \ _n##_rb_init(struct _n##_rb_head *head) \ { \ memset(head, 0, sizeof(*head)); \ memset(&_n##_rb_zero, 0, sizeof(_n##_rb_zero)); \ head->top._f.left = &_n##_rb_zero; \ head->top._f.right = &_n##_rb_zero; \ head->top._f.parent = &head->top; \ _n##_rb_zero._f.left = &_n##_rb_zero; \ _n##_rb_zero._f.right = &_n##_rb_zero; \ _n##_rb_zero._f.parent = &_n##_rb_zero; \ } \ \ void \ _n##_rb_walktree(struct _n##_rb_head *head, _n##_rb_walker_t func, void *arg)\ { \ _t *prev; \ _t *next; \ _t *node = head->top._f.right; \ _t *base; \ \ while (node != &_n##_rb_zero) \ node = node->_f.left; \ \ for (;;) { \ base = node; \ prev = node; \ while ((node->_f.parent->_f.right == node) && \ (node != &_n##_rb_zero)) { \ prev = node; \ node = node->_f.parent; \ } \ \ node = prev; \ for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\ node = node->_f.left) \ prev = node; \ next = prev; \ \ if (node != &_n##_rb_zero) \ func(node, arg); \ \ node = next; \ if (node == &_n##_rb_zero) \ break; \ } \ } \ \ _t * \ _n##_rb_search(struct _n##_rb_head *head, void *key) \ { \ int match; \ _t *node; \ node = head->top._f.right; \ while (node != &_n##_rb_zero) { \ match = _cmp(key, node); \ if (match == 0) \ break; \ if (match< 0) \ node = node->_f.left; \ else \ node = node->_f.right; \ } \ if (node == &_n##_rb_zero || match != 0) \ return (NULL); \ return (node); \ } #define RBI_DELETE(_n, _h, _v) _n##_rb_delete(_h, _v) #define RBI_FIELD(_n) struct _n##_rb_link #define RBI_INIT(_n, _h) _n##_rb_init(_h) #define RBI_INSERT(_n, _h, _v) _n##_rb_insert(_h, _v) #define RBI_ISEMPTY(_h) ((_h)->count == 0) #define RBI_SEARCH(_n, _h, _k) _n##_rb_search(_h, _k) #define RBI_WALK(_n, _h, _w, _a) _n##_rb_walktree(_h, _w, _a) #define RBI_ZERO(_n) _n##_rb_zero