1254219Scy/* 2254219Scy * Copyright (C) 2012 by Darren Reed. 3254219Scy * 4254219Scy * See the IPFILTER.LICENCE file for details on licencing. 5254219Scy * 6254219Scy */ 7254219Scytypedef enum rbcolour_e { 8254219Scy C_BLACK = 0, 9254219Scy C_RED = 1 10254219Scy} rbcolour_t; 11254219Scy 12254219Scy#define RBI_LINK(_n, _t) \ 13254219Scy struct _n##_rb_link { \ 14254219Scy struct _t *left; \ 15254219Scy struct _t *right; \ 16254219Scy struct _t *parent; \ 17254219Scy rbcolour_t colour; \ 18254219Scy } 19254219Scy 20254219Scy#define RBI_HEAD(_n, _t) \ 21254219Scystruct _n##_rb_head { \ 22254219Scy struct _t top; \ 23254219Scy int count; \ 24254219Scy int (* compare)(struct _t *, struct _t *); \ 25254219Scy} 26254219Scy 27254219Scy#define RBI_CODE(_n, _t, _f, _cmp) \ 28254219Scy \ 29254219Scytypedef void (*_n##_rb_walker_t)(_t *, void *); \ 30254219Scy \ 31254219Scy_t * _n##_rb_delete(struct _n##_rb_head *, _t *); \ 32254219Scyvoid _n##_rb_init(struct _n##_rb_head *); \ 33254219Scyvoid _n##_rb_insert(struct _n##_rb_head *, _t *); \ 34254219Scy_t * _n##_rb_search(struct _n##_rb_head *, void *); \ 35254219Scyvoid _n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\ 36254219Scy \ 37254219Scystatic void \ 38254219Scyrotate_left(struct _n##_rb_head *head, _t *node) \ 39254219Scy{ \ 40254219Scy _t *parent, *tmp1, *tmp2; \ 41254219Scy \ 42254219Scy parent = node->_f.parent; \ 43254219Scy tmp1 = node->_f.right; \ 44254219Scy tmp2 = tmp1->_f.left; \ 45254219Scy node->_f.right = tmp2; \ 46254219Scy if (tmp2 != & _n##_rb_zero) \ 47254219Scy tmp2->_f.parent = node; \ 48254219Scy if (parent == & _n##_rb_zero) \ 49254219Scy head->top._f.right = tmp1; \ 50254219Scy else if (parent->_f.right == node) \ 51254219Scy parent->_f.right = tmp1; \ 52254219Scy else \ 53254219Scy parent->_f.left = tmp1; \ 54254219Scy tmp1->_f.left = node; \ 55254219Scy tmp1->_f.parent = parent; \ 56254219Scy node->_f.parent = tmp1; \ 57254219Scy} \ 58254219Scy \ 59254219Scystatic void \ 60254219Scyrotate_right(struct _n##_rb_head *head, _t *node) \ 61254219Scy{ \ 62254219Scy _t *parent, *tmp1, *tmp2; \ 63254219Scy \ 64254219Scy parent = node->_f.parent; \ 65254219Scy tmp1 = node->_f.left; \ 66254219Scy tmp2 = tmp1->_f.right; \ 67254219Scy node->_f.left = tmp2; \ 68254219Scy if (tmp2 != &_n##_rb_zero) \ 69254219Scy tmp2->_f.parent = node; \ 70254219Scy if (parent == &_n##_rb_zero) \ 71254219Scy head->top._f.right = tmp1; \ 72254219Scy else if (parent->_f.right == node) \ 73254219Scy parent->_f.right = tmp1; \ 74254219Scy else \ 75254219Scy parent->_f.left = tmp1; \ 76254219Scy tmp1->_f.right = node; \ 77254219Scy tmp1->_f.parent = parent; \ 78254219Scy node->_f.parent = tmp1; \ 79254219Scy} \ 80254219Scy \ 81254219Scyvoid \ 82254219Scy_n##_rb_insert(struct _n##_rb_head *head, _t *node) \ 83254219Scy{ \ 84254219Scy _t *n, *parent, **p, *tmp1, *gparent; \ 85254219Scy \ 86254219Scy parent = &head->top; \ 87254219Scy node->_f.left = &_n##_rb_zero; \ 88254219Scy node->_f.right = &_n##_rb_zero; \ 89254219Scy p = &head->top._f.right; \ 90254219Scy while ((n = *p) != &_n##_rb_zero) { \ 91254219Scy if (_cmp(node, n) < 0) \ 92254219Scy p = &n->_f.left; \ 93254219Scy else \ 94254219Scy p = &n->_f.right; \ 95254219Scy parent = n; \ 96254219Scy } \ 97254219Scy *p = node; \ 98254219Scy node->_f.colour = C_RED; \ 99254219Scy node->_f.parent = parent; \ 100254219Scy \ 101254219Scy while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\ 102254219Scy gparent = parent->_f.parent; \ 103254219Scy if (parent == gparent->_f.left) { \ 104254219Scy tmp1 = gparent->_f.right; \ 105254219Scy if (tmp1->_f.colour == C_RED) { \ 106254219Scy parent->_f.colour = C_BLACK; \ 107254219Scy tmp1->_f.colour = C_BLACK; \ 108254219Scy gparent->_f.colour = C_RED; \ 109254219Scy node = gparent; \ 110254219Scy } else { \ 111254219Scy if (node == parent->_f.right) { \ 112254219Scy node = parent; \ 113254219Scy rotate_left(head, node); \ 114254219Scy parent = node->_f.parent; \ 115254219Scy } \ 116254219Scy parent->_f.colour = C_BLACK; \ 117254219Scy gparent->_f.colour = C_RED; \ 118254219Scy rotate_right(head, gparent); \ 119254219Scy } \ 120254219Scy } else { \ 121254219Scy tmp1 = gparent->_f.left; \ 122254219Scy if (tmp1->_f.colour == C_RED) { \ 123254219Scy parent->_f.colour = C_BLACK; \ 124254219Scy tmp1->_f.colour = C_BLACK; \ 125254219Scy gparent->_f.colour = C_RED; \ 126254219Scy node = gparent; \ 127254219Scy } else { \ 128254219Scy if (node == parent->_f.left) { \ 129254219Scy node = parent; \ 130254219Scy rotate_right(head, node); \ 131254219Scy parent = node->_f.parent; \ 132254219Scy } \ 133254219Scy parent->_f.colour = C_BLACK; \ 134254219Scy gparent->_f.colour = C_RED; \ 135254219Scy rotate_left(head, parent->_f.parent); \ 136254219Scy } \ 137254219Scy } \ 138254219Scy parent = node->_f.parent; \ 139254219Scy } \ 140254219Scy head->top._f.right->_f.colour = C_BLACK; \ 141254219Scy head->count++; \ 142254219Scy} \ 143254219Scy \ 144254219Scystatic void \ 145254219Scydeleteblack(struct _n##_rb_head *head, _t *parent, _t *node) \ 146254219Scy{ \ 147254219Scy _t *tmp; \ 148254219Scy \ 149254219Scy while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) && \ 150254219Scy node != &head->top) { \ 151254219Scy if (parent->_f.left == node) { \ 152254219Scy tmp = parent->_f.right; \ 153254219Scy if (tmp->_f.colour == C_RED) { \ 154254219Scy tmp->_f.colour = C_BLACK; \ 155254219Scy parent->_f.colour = C_RED; \ 156254219Scy rotate_left(head, parent); \ 157254219Scy tmp = parent->_f.right; \ 158254219Scy } \ 159254219Scy if ((tmp->_f.left == &_n##_rb_zero || \ 160254219Scy tmp->_f.left->_f.colour == C_BLACK) && \ 161254219Scy (tmp->_f.right == &_n##_rb_zero || \ 162254219Scy tmp->_f.right->_f.colour == C_BLACK)) { \ 163254219Scy tmp->_f.colour = C_RED; \ 164254219Scy node = parent; \ 165254219Scy parent = node->_f.parent; \ 166254219Scy } else { \ 167254219Scy if (tmp->_f.right == &_n##_rb_zero || \ 168254219Scy tmp->_f.right->_f.colour == C_BLACK) {\ 169254219Scy _t *tmp2 = tmp->_f.left; \ 170254219Scy \ 171254219Scy if (tmp2 != &_n##_rb_zero) \ 172254219Scy tmp2->_f.colour = C_BLACK;\ 173254219Scy tmp->_f.colour = C_RED; \ 174254219Scy rotate_right(head, tmp); \ 175254219Scy tmp = parent->_f.right; \ 176254219Scy } \ 177254219Scy tmp->_f.colour = parent->_f.colour; \ 178254219Scy parent->_f.colour = C_BLACK; \ 179254219Scy if (tmp->_f.right != &_n##_rb_zero) \ 180254219Scy tmp->_f.right->_f.colour = C_BLACK;\ 181254219Scy rotate_left(head, parent); \ 182254219Scy node = head->top._f.right; \ 183254219Scy } \ 184254219Scy } else { \ 185254219Scy tmp = parent->_f.left; \ 186254219Scy if (tmp->_f.colour == C_RED) { \ 187254219Scy tmp->_f.colour = C_BLACK; \ 188254219Scy parent->_f.colour = C_RED; \ 189254219Scy rotate_right(head, parent); \ 190254219Scy tmp = parent->_f.left; \ 191254219Scy } \ 192254219Scy if ((tmp->_f.left == &_n##_rb_zero || \ 193254219Scy tmp->_f.left->_f.colour == C_BLACK) && \ 194254219Scy (tmp->_f.right == &_n##_rb_zero || \ 195254219Scy tmp->_f.right->_f.colour == C_BLACK)) { \ 196254219Scy tmp->_f.colour = C_RED; \ 197254219Scy node = parent; \ 198254219Scy parent = node->_f.parent; \ 199254219Scy } else { \ 200254219Scy if (tmp->_f.left == &_n##_rb_zero || \ 201254219Scy tmp->_f.left->_f.colour == C_BLACK) {\ 202254219Scy _t *tmp2 = tmp->_f.right; \ 203254219Scy \ 204254219Scy if (tmp2 != &_n##_rb_zero) \ 205254219Scy tmp2->_f.colour = C_BLACK;\ 206254219Scy tmp->_f.colour = C_RED; \ 207254219Scy rotate_left(head, tmp); \ 208254219Scy tmp = parent->_f.left; \ 209254219Scy } \ 210254219Scy tmp->_f.colour = parent->_f.colour; \ 211254219Scy parent->_f.colour = C_BLACK; \ 212254219Scy if (tmp->_f.left != &_n##_rb_zero) \ 213254219Scy tmp->_f.left->_f.colour = C_BLACK;\ 214254219Scy rotate_right(head, parent); \ 215254219Scy node = head->top._f.right; \ 216254219Scy break; \ 217254219Scy } \ 218254219Scy } \ 219254219Scy } \ 220254219Scy if (node != &_n##_rb_zero) \ 221254219Scy node->_f.colour = C_BLACK; \ 222254219Scy} \ 223254219Scy \ 224254219Scy_t * \ 225254219Scy_n##_rb_delete(struct _n##_rb_head *head, _t *node) \ 226254219Scy{ \ 227254219Scy _t *child, *parent, *old = node, *left; \ 228254219Scy rbcolour_t color; \ 229254219Scy \ 230254219Scy if (node->_f.left == &_n##_rb_zero) { \ 231254219Scy child = node->_f.right; \ 232254219Scy } else if (node->_f.right == &_n##_rb_zero) { \ 233254219Scy child = node->_f.left; \ 234254219Scy } else { \ 235254219Scy node = node->_f.right; \ 236254219Scy while ((left = node->_f.left) != &_n##_rb_zero) \ 237254219Scy node = left; \ 238254219Scy child = node->_f.right; \ 239254219Scy parent = node->_f.parent; \ 240254219Scy color = node->_f.colour; \ 241254219Scy if (child != &_n##_rb_zero) \ 242254219Scy child->_f.parent = parent; \ 243254219Scy if (parent != &_n##_rb_zero) { \ 244254219Scy if (parent->_f.left == node) \ 245254219Scy parent->_f.left = child; \ 246254219Scy else \ 247254219Scy parent->_f.right = child; \ 248254219Scy } else { \ 249254219Scy head->top._f.right = child; \ 250254219Scy } \ 251254219Scy if (node->_f.parent == old) \ 252254219Scy parent = node; \ 253254219Scy *node = *old; \ 254254219Scy if (old->_f.parent != &_n##_rb_zero) { \ 255254219Scy if (old->_f.parent->_f.left == old) \ 256254219Scy old->_f.parent->_f.left = node; \ 257254219Scy else \ 258254219Scy old->_f.parent->_f.right = node; \ 259254219Scy } else { \ 260254219Scy head->top._f.right = child; \ 261254219Scy } \ 262254219Scy old->_f.left->_f.parent = node; \ 263254219Scy if (old->_f.right != &_n##_rb_zero) \ 264254219Scy old->_f.right->_f.parent = node; \ 265254219Scy if (parent != &_n##_rb_zero) { \ 266254219Scy left = parent; \ 267254219Scy } \ 268254219Scy goto colour; \ 269254219Scy } \ 270254219Scy parent = node->_f.parent; \ 271254219Scy color= node->_f.colour; \ 272254219Scy if (child != &_n##_rb_zero) \ 273254219Scy child->_f.parent = parent; \ 274254219Scy if (parent != &_n##_rb_zero) { \ 275254219Scy if (parent->_f.left == node) \ 276254219Scy parent->_f.left = child; \ 277254219Scy else \ 278254219Scy parent->_f.right = child; \ 279254219Scy } else { \ 280254219Scy head->top._f.right = child; \ 281254219Scy } \ 282254219Scycolour: \ 283254219Scy if (color == C_BLACK) \ 284254219Scy deleteblack(head, parent, node); \ 285254219Scy head->count--; \ 286254219Scy return old; \ 287254219Scy} \ 288254219Scy \ 289254219Scyvoid \ 290254219Scy_n##_rb_init(struct _n##_rb_head *head) \ 291254219Scy{ \ 292254219Scy memset(head, 0, sizeof(*head)); \ 293254219Scy memset(&_n##_rb_zero, 0, sizeof(_n##_rb_zero)); \ 294254219Scy head->top._f.left = &_n##_rb_zero; \ 295254219Scy head->top._f.right = &_n##_rb_zero; \ 296254219Scy head->top._f.parent = &head->top; \ 297254219Scy _n##_rb_zero._f.left = &_n##_rb_zero; \ 298254219Scy _n##_rb_zero._f.right = &_n##_rb_zero; \ 299254219Scy _n##_rb_zero._f.parent = &_n##_rb_zero; \ 300254219Scy} \ 301254219Scy \ 302254219Scyvoid \ 303254219Scy_n##_rb_walktree(struct _n##_rb_head *head, _n##_rb_walker_t func, void *arg)\ 304254219Scy{ \ 305254219Scy _t *prev; \ 306254219Scy _t *next; \ 307254219Scy _t *node = head->top._f.right; \ 308254219Scy _t *base; \ 309254219Scy \ 310254219Scy while (node != &_n##_rb_zero) \ 311254219Scy node = node->_f.left; \ 312254219Scy \ 313254219Scy for (;;) { \ 314254219Scy base = node; \ 315254219Scy prev = node; \ 316254219Scy while ((node->_f.parent->_f.right == node) && \ 317254219Scy (node != &_n##_rb_zero)) { \ 318254219Scy prev = node; \ 319254219Scy node = node->_f.parent; \ 320254219Scy } \ 321254219Scy \ 322254219Scy node = prev; \ 323254219Scy for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\ 324254219Scy node = node->_f.left) \ 325254219Scy prev = node; \ 326254219Scy next = prev; \ 327254219Scy \ 328254219Scy if (node != &_n##_rb_zero) \ 329254219Scy func(node, arg); \ 330254219Scy \ 331254219Scy node = next; \ 332254219Scy if (node == &_n##_rb_zero) \ 333254219Scy break; \ 334254219Scy } \ 335254219Scy} \ 336254219Scy \ 337254219Scy_t * \ 338254219Scy_n##_rb_search(struct _n##_rb_head *head, void *key) \ 339254219Scy{ \ 340254219Scy int match; \ 341254219Scy _t *node; \ 342254219Scy node = head->top._f.right; \ 343254219Scy while (node != &_n##_rb_zero) { \ 344254219Scy match = _cmp(key, node); \ 345254219Scy if (match == 0) \ 346254219Scy break; \ 347254219Scy if (match< 0) \ 348254219Scy node = node->_f.left; \ 349254219Scy else \ 350254219Scy node = node->_f.right; \ 351254219Scy } \ 352254219Scy if (node == &_n##_rb_zero || match != 0) \ 353254219Scy return (NULL); \ 354254219Scy return (node); \ 355254219Scy} 356254219Scy 357254219Scy#define RBI_DELETE(_n, _h, _v) _n##_rb_delete(_h, _v) 358254219Scy#define RBI_FIELD(_n) struct _n##_rb_link 359254219Scy#define RBI_INIT(_n, _h) _n##_rb_init(_h) 360254219Scy#define RBI_INSERT(_n, _h, _v) _n##_rb_insert(_h, _v) 361254219Scy#define RBI_ISEMPTY(_h) ((_h)->count == 0) 362254219Scy#define RBI_SEARCH(_n, _h, _k) _n##_rb_search(_h, _k) 363254219Scy#define RBI_WALK(_n, _h, _w, _a) _n##_rb_walktree(_h, _w, _a) 364254219Scy#define RBI_ZERO(_n) _n##_rb_zero 365