comparison: src/tree.c
src/tree.c
- branch
- feature/tree_add
- changeset 866
- 1f636de4a63f
- parent 864
- 7d3061f212cb
- child 867
- 471c714d5b6f
equal
deleted
inserted
replaced
| 865:4b325b639117 | 866:1f636de4a63f |
|---|---|
| 38 #define tree_children(node) CX_TREE_PTR(node, loc_children) | 38 #define tree_children(node) CX_TREE_PTR(node, loc_children) |
| 39 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child) | 39 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child) |
| 40 #define tree_prev(node) CX_TREE_PTR(node, loc_prev) | 40 #define tree_prev(node) CX_TREE_PTR(node, loc_prev) |
| 41 #define tree_next(node) CX_TREE_PTR(node, loc_next) | 41 #define tree_next(node) CX_TREE_PTR(node, loc_next) |
| 42 | 42 |
| 43 #define cx_tree_ptr_locations \ | |
| 44 loc_parent, loc_children, loc_last_child, loc_prev, loc_next | |
| 45 | |
| 46 static void cx_tree_zero_pointers( | |
| 47 void *node, | |
| 48 ptrdiff_t loc_parent, | |
| 49 ptrdiff_t loc_children, | |
| 50 ptrdiff_t loc_last_child, | |
| 51 ptrdiff_t loc_prev, | |
| 52 ptrdiff_t loc_next | |
| 53 ) { | |
| 54 tree_parent(node) = NULL; | |
| 55 tree_prev(node) = NULL; | |
| 56 tree_next(node) = NULL; | |
| 57 tree_children(node) = NULL; | |
| 58 if (loc_last_child >= 0) { | |
| 59 tree_last_child(node) = NULL; | |
| 60 } | |
| 61 } | |
| 62 | |
| 43 void cx_tree_link( | 63 void cx_tree_link( |
| 44 void *restrict parent, | 64 void *restrict parent, |
| 45 void *restrict node, | 65 void *restrict node, |
| 46 ptrdiff_t loc_parent, | 66 ptrdiff_t loc_parent, |
| 47 ptrdiff_t loc_children, | 67 ptrdiff_t loc_children, |
| 50 ptrdiff_t loc_next | 70 ptrdiff_t loc_next |
| 51 ) { | 71 ) { |
| 52 void *current_parent = tree_parent(node); | 72 void *current_parent = tree_parent(node); |
| 53 if (current_parent == parent) return; | 73 if (current_parent == parent) return; |
| 54 if (current_parent != NULL) { | 74 if (current_parent != NULL) { |
| 55 cx_tree_unlink(node, loc_parent, loc_children, loc_last_child, | 75 cx_tree_unlink(node, cx_tree_ptr_locations); |
| 56 loc_prev, loc_next); | |
| 57 } | 76 } |
| 58 | 77 |
| 59 if (tree_children(parent) == NULL) { | 78 if (tree_children(parent) == NULL) { |
| 60 tree_children(parent) = node; | 79 tree_children(parent) = node; |
| 61 if (loc_last_child >= 0) { | 80 if (loc_last_child >= 0) { |
| 436 ptrdiff_t loc_children, | 455 ptrdiff_t loc_children, |
| 437 ptrdiff_t loc_last_child, | 456 ptrdiff_t loc_last_child, |
| 438 ptrdiff_t loc_prev, | 457 ptrdiff_t loc_prev, |
| 439 ptrdiff_t loc_next | 458 ptrdiff_t loc_next |
| 440 ) { | 459 ) { |
| 441 // TODO: implement | 460 if (*root == NULL) { |
| 442 return NULL; | 461 void *node = cfunc(src, NULL, cdata); |
| 462 if (node == NULL) return NULL; | |
| 463 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 464 *root = node; | |
| 465 return node; | |
| 466 } | |
| 467 | |
| 468 void *match = NULL; | |
| 469 int result = cx_tree_search( | |
| 470 *root, | |
| 471 src, | |
| 472 sfunc, | |
| 473 &match, | |
| 474 loc_children, | |
| 475 loc_next | |
| 476 ); | |
| 477 | |
| 478 void *node; | |
| 479 if (result < 0) { | |
| 480 // new node is created as new parent | |
| 481 node = cfunc(src, NULL, cdata); | |
| 482 if (node == NULL) return NULL; | |
| 483 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 484 cx_tree_link(node, *root, cx_tree_ptr_locations); | |
| 485 *root = node; | |
| 486 return node; | |
| 487 } else if (result == 0) { | |
| 488 // data already found in the tree, let cfunc decide | |
| 489 node = cfunc(src, match, cdata); | |
| 490 if (node == NULL) return NULL; | |
| 491 if (node != match) { | |
| 492 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 493 cx_tree_link(match, node, cx_tree_ptr_locations); | |
| 494 } | |
| 495 } else { | |
| 496 // closest match found, add new node as child | |
| 497 node = cfunc(src, NULL, cdata); | |
| 498 if (node == NULL) return NULL; | |
| 499 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 500 cx_tree_link(match, node, cx_tree_ptr_locations); | |
| 501 } | |
| 502 | |
| 503 return node; | |
| 443 } | 504 } |
| 444 | 505 |
| 445 unsigned int cx_tree_add_look_around_depth = 3; | 506 unsigned int cx_tree_add_look_around_depth = 3; |
| 446 | 507 |
| 447 size_t cx_tree_add_iter( | 508 size_t cx_tree_add_iter( |
| 454 ptrdiff_t loc_children, | 515 ptrdiff_t loc_children, |
| 455 ptrdiff_t loc_last_child, | 516 ptrdiff_t loc_last_child, |
| 456 ptrdiff_t loc_prev, | 517 ptrdiff_t loc_prev, |
| 457 ptrdiff_t loc_next | 518 ptrdiff_t loc_next |
| 458 ) { | 519 ) { |
| 459 // TODO: implement | 520 size_t processed = 0; |
| 460 return 0; | 521 void *current_node = *root; |
| 522 for (void **eptr; | |
| 523 iter->valid(iter) && (eptr = iter->current(iter)) != NULL; | |
| 524 iter->next(iter)) { | |
| 525 void *elem = *eptr; | |
| 526 | |
| 527 if (current_node == NULL) { | |
| 528 // no node in tree, yet - add a new one | |
| 529 current_node = cfunc(elem, NULL, cdata); | |
| 530 // node creation failed - stop processing | |
| 531 if (current_node == NULL) { | |
| 532 // but honestly... nothing should have been processed | |
| 533 assert(processed == 0); | |
| 534 return 0; | |
| 535 } | |
| 536 cx_tree_zero_pointers(current_node, cx_tree_ptr_locations); | |
| 537 *root = current_node; | |
| 538 processed++; | |
| 539 continue; | |
| 540 } | |
| 541 | |
| 542 // start searching from current node | |
| 543 void *match; | |
| 544 int result; | |
| 545 unsigned int look_around_retries = cx_tree_add_look_around_depth; | |
| 546 cx_tree_add_look_around_retry: | |
| 547 result = cx_tree_search( | |
| 548 current_node, | |
| 549 elem, | |
| 550 sfunc, | |
| 551 &match, | |
| 552 loc_children, | |
| 553 loc_next | |
| 554 ); | |
| 555 | |
| 556 void *node; | |
| 557 if (result < 0) { | |
| 558 // traverse upwards and try to find better parents | |
| 559 void *parent = tree_parent(current_node); | |
| 560 if (parent != NULL) { | |
| 561 if (look_around_retries > 0) { | |
| 562 look_around_retries--; | |
| 563 current_node = parent; | |
| 564 } else { | |
| 565 // look around retries exhausted, start from the root | |
| 566 current_node = *root; | |
| 567 } | |
| 568 goto cx_tree_add_look_around_retry; | |
| 569 } else { | |
| 570 // no parents. so we (try to) create a new root node | |
| 571 void *new_root = cfunc(elem, NULL, cdata); | |
| 572 if (new_root == NULL) return processed; | |
| 573 cx_tree_zero_pointers(new_root, cx_tree_ptr_locations); | |
| 574 cx_tree_link(new_root, current_node, cx_tree_ptr_locations); | |
| 575 current_node = new_root; | |
| 576 *root = new_root; | |
| 577 } | |
| 578 } else if (result == 0) { | |
| 579 // data already found in the tree, let cfunc decide | |
| 580 node = cfunc(elem, match, cdata); | |
| 581 if (node == NULL) return processed; | |
| 582 if (node != match) { | |
| 583 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 584 cx_tree_link(match, node, cx_tree_ptr_locations); | |
| 585 } | |
| 586 current_node = node; | |
| 587 } else { | |
| 588 // closest match found, add new node as child | |
| 589 node = cfunc(elem, NULL, cdata); | |
| 590 if (node == NULL) return processed; | |
| 591 cx_tree_zero_pointers(node, cx_tree_ptr_locations); | |
| 592 cx_tree_link(match, node, cx_tree_ptr_locations); | |
| 593 // but make the match current and not the new node | |
| 594 // (usually saves one traversal when a lot of siblings are added) | |
| 595 current_node = match; | |
| 596 } | |
| 597 | |
| 598 processed++; | |
| 599 } | |
| 600 return processed; | |
| 461 } | 601 } |
| 462 | 602 |
| 463 size_t cx_tree_add_array( | 603 size_t cx_tree_add_array( |
| 464 void const *src, | 604 void const *src, |
| 465 size_t num, | 605 size_t num, |
