Willy Tarreau | be384c6 | 2007-04-28 14:00:17 +0200 | [diff] [blame] | 1 | /* |
| 2 | * tree.h : tree manipulation macros and structures. |
| 3 | * (C) 2002 - Willy Tarreau - willy@ant-computing.com |
| 4 | * |
| 5 | */ |
| 6 | |
| 7 | #ifndef __TREE_H__ |
| 8 | #define __TREE_H__ |
| 9 | |
| 10 | #include <import/bitops.h> |
| 11 | #include <common/memory.h> |
| 12 | |
| 13 | /* binary tree node : either 32 bits unsigned long int values, or |
| 14 | * 64 bits in two 32 bits unsigned long int values |
| 15 | */ |
| 16 | struct ultree { |
| 17 | unsigned long low; /* 32 bits low value of this node */ |
| 18 | unsigned long high; /* 32 bits high value of this node, not used in 32 bits */ |
| 19 | int level; /* bit level of this node */ |
| 20 | void *data; /* carried data */ |
| 21 | struct ultree *left, *right; /* children : left and right. NULL = leaf */ |
| 22 | struct ultree *up; /* parent node. NULL = root */ |
| 23 | }; |
| 24 | |
| 25 | /* binary tree node : 64 bits unsigned long long values */ |
| 26 | struct ulltree { |
| 27 | unsigned long long value; /* 64 bits value of this node */ |
| 28 | int level; /* bit level of this node */ |
| 29 | void *data; /* carried data */ |
| 30 | struct ulltree *left, *right; /* children : left and right. NULL = leaf */ |
| 31 | struct ulltree *up; /* parent node. NULL = root */ |
| 32 | }; |
| 33 | |
| 34 | /* binary tree node : 64 bits in either one ull or two 32 bits unsigned long int values. This |
| 35 | * is the common type for all the above trees, which should be cast into it. This makes |
| 36 | * pool_free() far simpler since all types share a same pool. |
| 37 | */ |
| 38 | struct tree64 { |
| 39 | union { |
| 40 | struct { |
| 41 | unsigned long low; /* 32 bits low value of this node */ |
| 42 | unsigned long high; /* 32 bits high value of this node */ |
| 43 | } ul; |
| 44 | struct { |
| 45 | unsigned long long value; /* 64 bits value of this node */ |
| 46 | } ull; |
| 47 | } value; |
| 48 | int level; /* bit level of this node */ |
| 49 | void *data; /* carried data */ |
| 50 | struct tree64 *left, *right; /* children : left and right. NULL = leaf */ |
| 51 | struct tree64 *up; /* parent node. NULL = root */ |
| 52 | }; |
| 53 | |
| 54 | #define sizeof_tree64 (sizeof (struct tree64)) |
| 55 | extern void **pool_tree64; |
| 56 | |
Willy Tarreau | be384c6 | 2007-04-28 14:00:17 +0200 | [diff] [blame] | 57 | #define ULTREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .low=0, .level=LONGBITS, .data=NULL } |
| 58 | #define ULTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; } |
| 59 | #define ULTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->low=0; (l)->level=LONGBITS; } |
| 60 | |
| 61 | #define ULLTREE_HEAD(l) struct ulltree (l) = { .left=NULL, .right=NULL, .up=NULL, .value=0, .level=LLONGBITS, .data=NULL } |
| 62 | #define ULLTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; } |
| 63 | #define ULLTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->value=0; (l)->level=LLONGBITS; } |
| 64 | |
| 65 | #define UL2TREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .high=0, .low=0, .level=LLONGBITS, .data=NULL } |
| 66 | #define UL2TREE_INIT(l) { (l)->left = (l)->right = (l)->data = NULL; } |
| 67 | #define UL2TREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->high=(l)->low=0; (l)->level=LLONGBITS; } |
| 68 | |
| 69 | /* |
| 70 | * inserts necessary nodes to reach <x> in tree starting at <root>. The node |
| 71 | * is not created if it exists. It is returned. |
| 72 | */ |
| 73 | inline static struct ulltree *__ulltree_insert(struct ulltree *root, unsigned long long x) { |
| 74 | int m; |
| 75 | struct ulltree *next, *new, *node; |
| 76 | struct ulltree **branch; |
| 77 | int ffs; |
| 78 | |
| 79 | next = root; |
| 80 | ffs = ffs_fast64(x); |
| 81 | |
| 82 | do { |
| 83 | root = next; |
| 84 | |
| 85 | if (x == next->value) { |
| 86 | return next; |
| 87 | } |
| 88 | |
| 89 | if (x & (1ULL << (next->level - 1))) { /* right branch */ |
| 90 | branch = &next->right; |
| 91 | next = *branch; |
| 92 | } else { |
| 93 | branch = &next->left; |
| 94 | next = *branch; |
| 95 | } |
| 96 | |
| 97 | if (next == NULL) { |
| 98 | /* we'll have to insert our node here */ |
| 99 | *branch = new = (struct ulltree *)pool_alloc(tree64); |
| 100 | ULLTREE_INIT(new); |
| 101 | new->up = root; |
| 102 | new->value = x; |
| 103 | new->level = ffs; |
| 104 | return new; |
| 105 | } |
| 106 | |
| 107 | /* we'll keep walking down as long as we have all bits in common */ |
| 108 | } while ((x & ~((1ULL << next->level) - 1)) == next->value); |
| 109 | |
| 110 | |
| 111 | /* ok, now we know that we must insert between both. */ |
| 112 | |
| 113 | /* the new interconnect node */ |
| 114 | *branch = node = (struct ulltree *)pool_alloc(tree64); /* was <next> */ |
| 115 | ULLTREE_INIT(node); |
| 116 | node->up = root; |
| 117 | next->up = node; |
| 118 | |
| 119 | /* we need the common higher bits between x and next->value. */ |
| 120 | |
| 121 | /* what differences are there between x and the node here ? |
| 122 | * NOTE that m is always < level(parent) because highest bit |
| 123 | * of x and next-value are identical here (else they would be |
| 124 | * on a different branch). |
| 125 | */ |
| 126 | m = fls_fast64(x ^ next->value) + 1; /* m = lowest identical bit */ |
| 127 | node->value = x & ~((1ULL << m) - 1); /* value of common bits */ |
| 128 | |
| 129 | if (node->value == x) { /* <x> is exactly on this node */ |
| 130 | /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/ |
| 131 | node->level = ffs; |
| 132 | |
| 133 | if (next->value & (1ULL << (node->level - 1))) /* right branch */ |
| 134 | node->right = next; |
| 135 | else |
| 136 | node->left = next; |
| 137 | return node; |
| 138 | } |
| 139 | |
| 140 | /* the new leaf now */ |
| 141 | node->level = m; /* set the level to the lowest common bit */ |
| 142 | new = (struct ulltree *)pool_alloc(tree64); |
| 143 | ULLTREE_INIT(new); |
| 144 | new->value = x; |
| 145 | new->level = ffs; |
| 146 | |
| 147 | if (x > next->value) { |
| 148 | node->left = next; |
| 149 | node->right = new; |
| 150 | } |
| 151 | else { |
| 152 | node->left = new; |
| 153 | node->right = next; |
| 154 | } |
| 155 | new->up = node; |
| 156 | return new; |
| 157 | } |
| 158 | |
| 159 | /* |
| 160 | * inserts necessary nodes to reach <x> in tree starting at <root>. The node |
| 161 | * is not created if it exists. It is returned. |
| 162 | */ |
| 163 | inline static struct ultree *__ultree_insert(struct ultree *root, unsigned long x) { |
| 164 | int m; |
| 165 | struct ultree *next, *new, *node; |
| 166 | struct ultree **branch; |
| 167 | int ffs; |
| 168 | |
| 169 | next = root; |
| 170 | ffs = ffs_fast32(x); |
| 171 | |
| 172 | do { |
| 173 | root = next; |
| 174 | |
| 175 | if (x == next->low) { |
| 176 | return next; |
| 177 | } |
| 178 | |
| 179 | if ((x >> (next->level - 1)) & 1) { /* right branch */ |
| 180 | branch = &next->right; |
| 181 | next = *branch; |
| 182 | } else { |
| 183 | branch = &next->left; |
| 184 | next = *branch; |
| 185 | } |
| 186 | |
| 187 | if (next == NULL) { |
| 188 | /* we'll have to insert our node here */ |
| 189 | *branch = new = (struct ultree *)pool_alloc(tree64); |
| 190 | ULTREE_INIT(new); |
| 191 | new->up = root; |
| 192 | new->low = x; |
| 193 | new->level = ffs; |
| 194 | return new; |
| 195 | } |
| 196 | |
| 197 | /* we'll keep walking down as long as we have all bits in common */ |
| 198 | } while ((x & ~((1 << next->level) - 1)) == next->low); |
| 199 | |
| 200 | /* ok, now we know that we must insert between both. */ |
| 201 | |
| 202 | /* the new interconnect node */ |
| 203 | *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */ |
| 204 | ULTREE_INIT(node); |
| 205 | node->up = root; |
| 206 | next->up = node; |
| 207 | |
| 208 | /* we need the common higher bits between x and next->low. */ |
| 209 | |
| 210 | /* what differences are there between x and the node here ? |
| 211 | * NOTE that m is always < level(parent) because highest bit |
| 212 | * of x and next->low are identical here (else they would be |
| 213 | * on a different branch). |
| 214 | */ |
| 215 | m = fls_fast32(x ^ next->low) + 1; /* m = lower identical bit */ |
| 216 | node->low = x & ~((1 << m) - 1); /* value of common bits */ |
| 217 | |
| 218 | if (node->low == x) { /* <x> is exactly on this node */ |
| 219 | /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/ |
| 220 | node->level = ffs; |
| 221 | |
| 222 | if (next->low & (1 << (node->level - 1))) /* right branch */ |
| 223 | node->right = next; |
| 224 | else |
| 225 | node->left = next; |
| 226 | return node; |
| 227 | } |
| 228 | |
| 229 | /* the new leaf now */ |
| 230 | node->level = m; /* set the level to the lowest common bit */ |
| 231 | new = (struct ultree *)pool_alloc(tree64); |
| 232 | ULTREE_INIT(new); |
| 233 | new->low = x; |
| 234 | new->level = ffs; |
| 235 | |
| 236 | if (x > next->low) { |
| 237 | node->left = next; |
| 238 | node->right = new; |
| 239 | } |
| 240 | else { |
| 241 | node->left = new; |
| 242 | node->right = next; |
| 243 | } |
| 244 | new->up = node; |
| 245 | return new; |
| 246 | } |
| 247 | |
| 248 | |
| 249 | /* |
| 250 | * inserts necessary nodes to reach <h:l> in tree starting at <root>. The node |
| 251 | * is not created if it exists. It is returned. |
| 252 | */ |
| 253 | inline static struct ultree *__ul2tree_insert(struct ultree *root, unsigned long h, unsigned long l) { |
| 254 | int m; |
| 255 | struct ultree *next, *new, *node; |
| 256 | struct ultree **branch; |
| 257 | |
| 258 | next = root; |
| 259 | |
| 260 | do { |
| 261 | root = next; |
| 262 | |
| 263 | if (h == next->high && l == next->low) { |
| 264 | return next; |
| 265 | } |
| 266 | |
| 267 | branch = &next->left; |
| 268 | if (next->level >= 33) { |
| 269 | if ((h >> (next->level - 33)) & 1) { /* right branch */ |
| 270 | branch = &next->right; |
Willy Tarreau | be384c6 | 2007-04-28 14:00:17 +0200 | [diff] [blame] | 271 | } |
| 272 | } |
| 273 | else { |
| 274 | if ((l >> (next->level - 1)) & 1) { /* right branch */ |
| 275 | branch = &next->right; |
Willy Tarreau | be384c6 | 2007-04-28 14:00:17 +0200 | [diff] [blame] | 276 | } |
| 277 | } |
| 278 | next = *branch; |
| 279 | |
Willy Tarreau | be384c6 | 2007-04-28 14:00:17 +0200 | [diff] [blame] | 280 | if (next == NULL) { |
| 281 | /* we'll have to insert our node here */ |
| 282 | *branch = new =(struct ultree *)pool_alloc(tree64); |
| 283 | UL2TREE_INIT(new); |
| 284 | new->up = root; |
| 285 | new->high = h; |
| 286 | new->low = l; |
| 287 | if (l) |
| 288 | new->level = __ffs_fast32(l); |
| 289 | else |
| 290 | new->level = __ffs_fast32(h) + 32; |
| 291 | |
| 292 | return new; |
| 293 | } |
| 294 | |
| 295 | /* we'll keep walking down as long as we have all bits in common */ |
| 296 | if (next->level >= 32) { |
| 297 | if ((h & ~((1 << (next->level-32)) - 1)) != next->high) |
| 298 | break; |
| 299 | } |
| 300 | else { |
| 301 | if (h != next->high) |
| 302 | break; |
| 303 | if ((l & ~((1 << next->level) - 1)) != next->low) |
| 304 | break; |
| 305 | } |
| 306 | } while (1); |
| 307 | |
| 308 | /* ok, now we know that we must insert between both. */ |
| 309 | |
| 310 | /* the new interconnect node */ |
| 311 | *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */ |
| 312 | UL2TREE_INIT(node); |
| 313 | node->up = root; |
| 314 | next->up = node; |
| 315 | |
| 316 | /* we need the common higher bits between x and next->high:low. */ |
| 317 | |
| 318 | /* what differences are there between x and the node here ? |
| 319 | * NOTE that m is always < level(parent) because highest bit |
| 320 | * of x and next->high:low are identical here (else they would be |
| 321 | * on a different branch). |
| 322 | */ |
| 323 | if (h != next->high) { |
| 324 | m = fls_fast32(h ^ next->high) + 1; /* m = lower identical bit */ |
| 325 | node->high = h & ~((1 << m) - 1); /* value of common bits */ |
| 326 | m += 32; |
| 327 | node->low = 0; |
| 328 | } else { |
| 329 | node->high = h; |
| 330 | m = fls_fast32(l ^ next->low) + 1; /* m = lower identical bit */ |
| 331 | node->low = l & ~((1 << m) - 1); /* value of common bits */ |
| 332 | } |
| 333 | |
| 334 | if (node->high == h && node->low == l) { /* <h:l> is exactly on this node */ |
| 335 | /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/ |
| 336 | if (l) { |
| 337 | node->level = ffs_fast32(l); |
| 338 | if (next->low & (1 << (node->level - 1))) /* right branch */ |
| 339 | node->right = next; |
| 340 | else |
| 341 | node->left = next; |
| 342 | } |
| 343 | else { |
| 344 | node->level = ffs_fast32(h) + 32; |
| 345 | if (next->high & (1 << (node->level - 33))) /* right branch */ |
| 346 | node->right = next; |
| 347 | else |
| 348 | node->left = next; |
| 349 | } |
| 350 | return node; |
| 351 | } |
| 352 | |
| 353 | /* the new leaf now */ |
| 354 | node->level = m; /* set the level to the lowest common bit */ |
| 355 | new = (struct ultree *)pool_alloc(tree64); |
| 356 | UL2TREE_INIT(new); |
| 357 | new->high = h; |
| 358 | new->low = l; |
| 359 | if (l) |
| 360 | new->level = __ffs_fast32(l); |
| 361 | else |
| 362 | new->level = __ffs_fast32(h) + 32; |
| 363 | |
| 364 | if (h > next->high || (h == next->high && l > next->low)) { |
| 365 | node->left = next; |
| 366 | node->right = new; |
| 367 | } |
| 368 | else { |
| 369 | node->left = new; |
| 370 | node->right = next; |
| 371 | } |
| 372 | new->up = node; |
| 373 | return new; |
| 374 | } |
| 375 | |
| 376 | |
| 377 | /* |
| 378 | * finds a value in the tree <root>. If it cannot be found, NULL is returned. |
| 379 | */ |
| 380 | inline static struct ultree *__ultree_find(struct ultree *root, unsigned long x) { |
| 381 | do { |
| 382 | if (x == root->low) |
| 383 | return root; |
| 384 | |
| 385 | if ((x >> (root->level - 1)) & 1) |
| 386 | root = root->right; |
| 387 | else |
| 388 | root = root->left; |
| 389 | |
| 390 | if (root == NULL) |
| 391 | return NULL; |
| 392 | |
| 393 | /* we'll keep walking down as long as we have all bits in common */ |
| 394 | } while ((x & ~((1 << root->level) - 1)) == root->low); |
| 395 | |
| 396 | /* should be there, but nothing. */ |
| 397 | return NULL; |
| 398 | } |
| 399 | |
| 400 | /* |
| 401 | * finds a value in the tree <root>. If it cannot be found, NULL is returned. |
| 402 | */ |
| 403 | inline static struct ulltree *__ulltree_find(struct ulltree *root, unsigned long long x) { |
| 404 | do { |
| 405 | if (x == root->value) |
| 406 | return root; |
| 407 | |
| 408 | if ((x >> (root->level - 1)) & 1) |
| 409 | root = root->right; |
| 410 | else |
| 411 | root = root->left; |
| 412 | |
| 413 | if (root == NULL) |
| 414 | return NULL; |
| 415 | |
| 416 | /* we'll keep walking down as long as we have all bits in common */ |
| 417 | } while ((x & ~((1ULL << root->level) - 1)) == root->value); |
| 418 | |
| 419 | /* should be there, but nothing. */ |
| 420 | return NULL; |
| 421 | } |
| 422 | |
| 423 | |
| 424 | /* |
| 425 | * walks down the tree <__root> and assigns each of its data to <__data>. |
| 426 | * <__stack> is an int array of at least N entries where N is the maximum number |
| 427 | * of levels of the tree. <__slen> is an integer variable used as a stack index. |
| 428 | * The instruction following the foreach statement is executed for each data, |
| 429 | * after the data has been unlinked from the tree. |
| 430 | * The nodes are deleted automatically, so it is illegal to manually delete a |
| 431 | * node within this loop. |
| 432 | */ |
| 433 | #define tree64_foreach_destructive(__root, __data, __stack, __slen) \ |
| 434 | for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \ |
| 435 | __label__ __left, __right, __again, __end; \ |
| 436 | typeof(__root) __ptr = __stack[__slen]; \ |
| 437 | __again: \ |
| 438 | __data = __ptr->data; \ |
| 439 | if (__data != NULL) { \ |
| 440 | __ptr->data = NULL; \ |
| 441 | goto __end; \ |
| 442 | } \ |
| 443 | else if (__ptr->left != NULL) { \ |
| 444 | __stack[++__slen] = __ptr = __ptr->left; \ |
| 445 | goto __again; \ |
| 446 | } \ |
| 447 | else \ |
| 448 | __left: \ |
| 449 | if (__ptr->right != NULL) { \ |
| 450 | __stack[++__slen] = __ptr = __ptr->right; \ |
| 451 | goto __again; \ |
| 452 | } \ |
| 453 | else \ |
| 454 | __right: \ |
| 455 | if (!__slen--) \ |
| 456 | goto __end; /* nothing left, don't delete the root node */ \ |
| 457 | else { \ |
| 458 | typeof (__root) __old; \ |
| 459 | pool_free(tree64, __ptr); \ |
| 460 | __old = __ptr; \ |
| 461 | __ptr = __stack[__slen]; \ |
| 462 | if (__ptr->left == __old) { \ |
| 463 | /* unlink this node from its parent */ \ |
| 464 | __ptr->left = NULL; \ |
| 465 | goto __left; \ |
| 466 | } \ |
| 467 | else { \ |
| 468 | /* no need to unlink, the parent will also die */ \ |
| 469 | goto __right; \ |
| 470 | } \ |
| 471 | } \ |
| 472 | __end: \ |
| 473 | (__slen >= 0); /* nothing after loop */}); ) |
| 474 | |
| 475 | |
| 476 | /* |
| 477 | * walks down the tree <__root> of type <__type> and assigns each of its data |
| 478 | * to <__data>. <__stack> is an int array of at least N entries where N is the |
| 479 | * maximum number of levels of the tree. <__slen> is an integer variable used |
| 480 | * as a stack index. The instruction following the foreach statement is |
| 481 | * executed for each data, after the data has been unlinked from the tree. |
| 482 | */ |
| 483 | #define tree_foreach_destructive(__type, __root, __data, __stack, __slen) \ |
| 484 | for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \ |
| 485 | __label__ __left, __right, __again, __end; \ |
| 486 | typeof(__root) __ptr = __stack[__slen]; \ |
| 487 | __again: \ |
| 488 | __data = __ptr->data; \ |
| 489 | if (__data != NULL) { \ |
| 490 | __ptr->data = NULL; \ |
| 491 | goto __end; \ |
| 492 | } \ |
| 493 | else if (__ptr->left != NULL) { \ |
| 494 | __stack[++__slen] = __ptr = __ptr->left; \ |
| 495 | goto __again; \ |
| 496 | } \ |
| 497 | else \ |
| 498 | __left: \ |
| 499 | if (__ptr->right != NULL) { \ |
| 500 | __stack[++__slen] = __ptr = __ptr->right; \ |
| 501 | goto __again; \ |
| 502 | } \ |
| 503 | else \ |
| 504 | __right: \ |
| 505 | if (!__slen--) \ |
| 506 | goto __end; /* nothing left, don't delete the root node */ \ |
| 507 | else { \ |
| 508 | typeof (__root) __old; \ |
| 509 | pool_free(__type, __ptr); \ |
| 510 | __old = __ptr; \ |
| 511 | __ptr = __stack[__slen]; \ |
| 512 | if (__ptr->left == __old) { \ |
| 513 | /* unlink this node from its parent */ \ |
| 514 | __ptr->left = NULL; \ |
| 515 | goto __left; \ |
| 516 | } \ |
| 517 | else { \ |
| 518 | /* no need to unlink, the parent will also die */ \ |
| 519 | goto __right; \ |
| 520 | } \ |
| 521 | } \ |
| 522 | __end: \ |
| 523 | (__slen >= 0); /* nothing after loop */}); ) |
| 524 | |
| 525 | |
| 526 | /* |
| 527 | * walks down the tree <__root> and assigns <__data> a pointer to each of its |
| 528 | * data pointers. <__stack> is an int array of at least N entries where N is the |
| 529 | * maximum number of levels of the tree. <__slen> is an integer variable used as |
| 530 | * a stack index. The instruction following the foreach statement is executed |
| 531 | * for each data. |
| 532 | * The tree will walk down only when the data field is empty (NULL), so it |
| 533 | * allows inner breaks, and will restart without losing items. The nodes data |
| 534 | * will be set to NULL after the inner code, or when the inner code does |
| 535 | * '__stack[__slen]->data = NULL'; |
| 536 | * The nodes are deleted automatically, so it is illegal to manually delete a |
| 537 | * node within this loop. |
| 538 | */ |
| 539 | #define tree64_foreach(__root, __data, __stack, __slen) \ |
| 540 | for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \ |
| 541 | __label__ __left, __right, __again, __end; \ |
| 542 | typeof(__root) __ptr = __stack[__slen]; \ |
| 543 | __again: \ |
| 544 | if (__ptr->data != NULL) { \ |
| 545 | __data = __ptr->data; \ |
| 546 | goto __end; \ |
| 547 | } \ |
| 548 | else if (__ptr->left != NULL) { \ |
| 549 | __stack[++__slen] = __ptr = __ptr->left; \ |
| 550 | goto __again; \ |
| 551 | } \ |
| 552 | else \ |
| 553 | __left: \ |
| 554 | if (__ptr->right != NULL) { \ |
| 555 | __stack[++__slen] = __ptr = __ptr->right; \ |
| 556 | goto __again; \ |
| 557 | } \ |
| 558 | else \ |
| 559 | __right: \ |
| 560 | if (!__slen--) \ |
| 561 | goto __end; /* nothing left, don't delete the root node */ \ |
| 562 | else { \ |
| 563 | typeof (__root) __old; \ |
| 564 | pool_free(tree64, __ptr); \ |
| 565 | __old = __ptr; \ |
| 566 | __ptr = __stack[__slen]; \ |
| 567 | if (__ptr->left == __old) { \ |
| 568 | /* unlink this node from its parent */ \ |
| 569 | __ptr->left = NULL; \ |
| 570 | goto __left; \ |
| 571 | } \ |
| 572 | else { \ |
| 573 | /* no need to unlink, the parent will also die */ \ |
| 574 | goto __right; \ |
| 575 | } \ |
| 576 | } \ |
| 577 | __end: \ |
| 578 | (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL) |
| 579 | |
| 580 | |
| 581 | |
| 582 | /* |
| 583 | * walks down the tree <__root> and assigns <__node> to each of its nodes. |
| 584 | * <__stack> is an int array of at least N entries where N is the |
| 585 | * maximum number of levels of the tree. <__slen> is an integer variable used as |
| 586 | * a stack index. The instruction following the foreach statement is executed |
| 587 | * for each node. |
| 588 | * The tree will walk down only when the data field is empty (NULL), so it |
| 589 | * allows inner breaks, and will restart without losing items. The nodes data |
| 590 | * will be set to NULL after the inner code, or when the inner code does |
| 591 | * '__node->data = NULL'; |
| 592 | * The nodes are deleted automatically, so it is illegal to manually delete a |
| 593 | * node within this loop. |
| 594 | */ |
| 595 | #define tree64_foreach_node(__root, __node, __stack, __slen) \ |
| 596 | for (__slen = 0, __stack[0] = __root; ({ \ |
| 597 | __label__ __left, __right, __again, __end; \ |
| 598 | typeof(__root) __ptr = __stack[__slen]; \ |
| 599 | __again: \ |
| 600 | if (__ptr->data != NULL) { \ |
| 601 | __node = __ptr; \ |
| 602 | goto __end; \ |
| 603 | } \ |
| 604 | else if (__ptr->left != NULL) { \ |
| 605 | __stack[++__slen] = __ptr = __ptr->left; \ |
| 606 | goto __again; \ |
| 607 | } \ |
| 608 | else \ |
| 609 | __left: \ |
| 610 | if (__ptr->right != NULL) { \ |
| 611 | __stack[++__slen] = __ptr = __ptr->right; \ |
| 612 | goto __again; \ |
| 613 | } \ |
| 614 | else \ |
| 615 | __right: \ |
| 616 | if (!__slen--) \ |
| 617 | goto __end; /* nothing left, don't delete the root node */ \ |
| 618 | else { \ |
| 619 | typeof (__root) __old; \ |
| 620 | pool_free(tree64, __ptr); \ |
| 621 | __old = __ptr; \ |
| 622 | __ptr = __stack[__slen]; \ |
| 623 | if (__ptr->left == __old) { \ |
| 624 | /* unlink this node from its parent */ \ |
| 625 | __ptr->left = NULL; \ |
| 626 | goto __left; \ |
| 627 | } \ |
| 628 | else { \ |
| 629 | /* no need to unlink, the parent will also die */ \ |
| 630 | goto __right; \ |
| 631 | } \ |
| 632 | } \ |
| 633 | __end: \ |
| 634 | (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL) |
| 635 | |
| 636 | |
| 637 | /* |
| 638 | * removes the current node if possible, and its parent if it doesn't handle |
| 639 | * data. A pointer to the parent or grandparent is returned (the parent of the |
| 640 | * last one deleted in fact). This function should be compatible with any |
| 641 | * tree struct because of the void types. |
| 642 | * WARNING : never call it from within a tree_foreach() because this last one |
| 643 | * uses a stack which will not be updated. |
| 644 | */ |
| 645 | |
| 646 | inline static void *__tree_delete_only_one(void *firstnode) { |
| 647 | struct tree64 *down, **uplink; |
| 648 | struct tree64 *node = firstnode; |
| 649 | |
| 650 | /* don't kill the root or a populated link */ |
| 651 | if (node->data || node->up == NULL) |
| 652 | return node; |
| 653 | if (node->left && node->right) |
| 654 | return node; |
| 655 | /* since we know that at least left or right is null, we can do arithmetics on them */ |
| 656 | down = (void *)((long)node->left | (long)node->right); |
| 657 | /* find where we are linked */ |
| 658 | if (node == node->up->left) |
| 659 | uplink = &node->up->left; |
| 660 | else |
| 661 | uplink = &node->up->right; |
| 662 | |
| 663 | *uplink = down; /* we relink the lower branch above us or simply cut it */ |
| 664 | if (down) { |
| 665 | down->up = node->up; |
| 666 | /* we know that we cannot do more because we kept one branch */ |
| 667 | } |
| 668 | else { |
| 669 | /* we'll redo this once for the node above us because there was no branch below us, |
| 670 | * so maybe it doesn't need to exist for only one branch |
| 671 | */ |
| 672 | down = node; |
| 673 | node = node->up; |
| 674 | pool_free(tree64, down); |
| 675 | if (node->data || node->up == NULL) |
| 676 | return node; |
| 677 | /* now we're sure we were sharing this empty node with another branch, let's find it */ |
| 678 | down = (void *)((long)node->left | (long)node->right); |
| 679 | if (node == node->up->left) |
| 680 | uplink = &node->up->left; |
| 681 | else |
| 682 | uplink = &node->up->right; |
| 683 | *uplink = down; /* we relink the lower branch above */ |
| 684 | down->up = node->up; |
| 685 | } |
| 686 | /* free the last node */ |
| 687 | pool_free(tree64, node); |
| 688 | return down->up; |
| 689 | } |
| 690 | |
| 691 | /* |
| 692 | * removes the current node if possible, and all of its parents which do not |
| 693 | * carry data. A pointer to the parent of the last one deleted is returned. |
| 694 | * This function should be compatible with any tree struct because of the void |
| 695 | * types. |
| 696 | * WARNING : never call it from within a tree_foreach() because this last one |
| 697 | * uses a stack which will not be updated. |
| 698 | */ |
| 699 | |
| 700 | inline static void *__tree_delete(void *firstnode) { |
| 701 | struct tree64 *down, **uplink, *up; |
| 702 | struct tree64 *node = firstnode; |
| 703 | |
| 704 | while (1) { |
| 705 | /* don't kill the root or a populated link */ |
| 706 | if (node->data || (up = node->up) == NULL) |
| 707 | return node; |
| 708 | if (node->left && node->right) |
| 709 | return node; |
| 710 | /* since we know that at least left or right is null, we can do arithmetics on them */ |
| 711 | down = (void *)((long)node->left | (long)node->right); |
| 712 | /* find where we are linked */ |
| 713 | if (node == up->left) |
| 714 | uplink = &up->left; |
| 715 | else |
| 716 | uplink = &up->right; |
| 717 | |
| 718 | *uplink = down; /* we relink the lower branch above us or simply cut it */ |
| 719 | pool_free(tree64, node); |
| 720 | node = up; |
| 721 | if (down) |
| 722 | down->up = node; |
| 723 | } |
| 724 | } |
| 725 | |
| 726 | #endif /* __TREE_H__ */ |