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