| 499 | */ |
| 500 | template <typename Key> |
| 501 | static Radix::Node<Key> *remove(Radix::Node<Key> *node, Key key) |
| 502 | { |
| 503 | if (node == nullptr) |
| 504 | return nullptr; |
| 505 | |
| 506 | if (!node->inner) |
| 507 | { |
| 508 | if (node->key != key) |
| 509 | return node; |
| 510 | delete node; |
| 511 | return nullptr; |
| 512 | } |
| 513 | |
| 514 | unsigned idx = index(node, key); |
| 515 | Radix::Node<Key> *child = remove(node->child[idx], key); |
| 516 | node->child[idx] = child; |
| 517 | if (child != nullptr) |
| 518 | { |
| 519 | fix(node); |
| 520 | return node; |
| 521 | } |
| 522 | |
| 523 | // If the number of child is reduced to 1, then delete the inner node: |
| 524 | Radix::Node<Key> *seen = nullptr; |
| 525 | for (int i = 0; i < BRANCH_MAX; i++) |
| 526 | { |
| 527 | if (node->child[i] == nullptr) |
| 528 | continue; |
| 529 | if (seen != nullptr) |
| 530 | return node; // 2 or more... |
| 531 | seen = node->child[i]; |
| 532 | } |
| 533 | delete node; |
| 534 | return seen; |
| 535 | } |
| 536 | |
| 537 | /* |
| 538 | * Merge a mapping with an existing mapping (if possible). |