| 539 | */ |
| 540 | template <typename Key> |
| 541 | static Radix::Node<Key> *merge(Radix::Node<Key> *tree, Key key, |
| 542 | Mapping *mapping) |
| 543 | { |
| 544 | Radix::Node<Key> *node = find(tree, key); |
| 545 | if (node != nullptr) |
| 546 | { |
| 547 | // Add to existing node for key: |
| 548 | mapping->next = node->leaf.mappings; |
| 549 | node->leaf.mappings = mapping; |
| 550 | log(COLOR_NONE, '+'); |
| 551 | return tree; |
| 552 | } |
| 553 | |
| 554 | node = findAnyComplement(tree, key); |
| 555 | if (node != nullptr) |
| 556 | { |
| 557 | // Merge with negated node: |
| 558 | Mapping *mappingCmp = node->leaf.mappings; |
| 559 | node->leaf.mappings = mappingCmp->next; |
| 560 | mappingCmp->next = nullptr; |
| 561 | mapping->merged = mappingCmp; |
| 562 | key |= node->key; |
| 563 | if (node->leaf.mappings == nullptr) |
| 564 | { |
| 565 | // Leaf node is now empty, so remove it. |
| 566 | tree = remove(tree, node->key); |
| 567 | } |
| 568 | log(COLOR_GREEN, 'M'); |
| 569 | } |
| 570 | else |
| 571 | log(COLOR_NONE, '+'); |
| 572 | |
| 573 | // Insert a new node: |
| 574 | tree = insert(tree, key, mapping); |
| 575 | return tree; |
| 576 | } |
| 577 | |
| 578 | /* |
| 579 | * Collect all (optimized) mappings and free the tree. |
no test coverage detected