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