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 */ 9 typedef 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) \ 23 struct _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 \ 31 typedef void (*_n##_rb_walker_t)(_t *, void *); \ 32 \ 33 _t * _n##_rb_delete(struct _n##_rb_head *, _t *); \ 34 void _n##_rb_init(struct _n##_rb_head *); \ 35 void _n##_rb_insert(struct _n##_rb_head *, _t *); \ 36 _t * _n##_rb_search(struct _n##_rb_head *, void *); \ 37 void _n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\ 38 \ 39 static void \ 40 rotate_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 \ 61 static void \ 62 rotate_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 \ 83 void \ 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 \ 146 static void \ 147 deleteblack(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 } \ 284 colour: \ 285 if (color == C_BLACK) \ 286 deleteblack(head, parent, node); \ 287 head->count--; \ 288 return old; \ 289 } \ 290 \ 291 void \ 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 \ 304 void \ 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