| 444 | */ |
| 445 | template <typename Key> |
| 446 | static Radix::Node<Key> *insert(Radix::Node<Key> *node, Key key, |
| 447 | Mapping *mapping) |
| 448 | { |
| 449 | if (node == nullptr) |
| 450 | { |
| 451 | Radix::Node<Key> *leaf = new Radix::Node<Key>(); |
| 452 | leaf->inner = false; |
| 453 | leaf->shift = 0; |
| 454 | leaf->key = key; |
| 455 | leaf->leaf.mappings = mapping; |
| 456 | return leaf; |
| 457 | } |
| 458 | |
| 459 | if (!node->inner) |
| 460 | { |
| 461 | Key diff = node->key ^ key; |
| 462 | if (diff == 0) |
| 463 | { |
| 464 | // Add to existing node: |
| 465 | mapping->next = node->leaf.mappings; |
| 466 | node->leaf.mappings = mapping; |
| 467 | return node; |
| 468 | } |
| 469 | |
| 470 | // Add new branch: |
| 471 | unsigned shift = tzcount(diff) / BRANCH_BITS; |
| 472 | Radix::Node<Key> *inner = new Radix::Node<Key>(); |
| 473 | inner->inner = true; |
| 474 | inner->shift = shift; |
| 475 | for (unsigned i = 0; i < BRANCH_MAX; i++) |
| 476 | inner->child[i] = nullptr; |
| 477 | inner->child[index(inner, node->key)] = node; |
| 478 | |
| 479 | Radix::Node<Key> *leaf = new Radix::Node<Key>(); |
| 480 | leaf->inner = false; |
| 481 | leaf->shift = 0; |
| 482 | leaf->key = key; |
| 483 | leaf->leaf.mappings = mapping; |
| 484 | inner->child[index(inner, leaf->key)] = leaf; |
| 485 | |
| 486 | fix(inner); |
| 487 | return inner; |
| 488 | } |
| 489 | |
| 490 | unsigned idx = index(node, key); |
| 491 | node->child[idx] = insert(node->child[idx], key, mapping); |
| 492 | fix(node); |
| 493 | |
| 494 | return node; |
| 495 | } |
| 496 | |
| 497 | /* |
| 498 | * Remove the leaf node matching `key`. |