1 sub split_and_promote { 2 my $self = shift; 3 my ($cur_node, @path) = @_; 4 5 for (;;) { 6 my ($newleft, $newright, $kdp) = $cur_node->halves($self->B / 2); 7 my ($up, $where) = @{pop @path}; 8 if ($up) { 9 $up->insert_kdp(@$kdp); 10 $up->subnode($where, $newleft); 11 $up->subnode($where+1, $newright); 12 return unless $self->node_overfull($up); 13 $cur_node = $up; 14 } else { # We're at the top; make a new root. 15 my $newroot = new BTree::Node ([$kdp->[0]], 16 [$kdp->[1]], 17 [$newleft, $newright]); 18 $self->root($newroot); 19 return; 20 } 21 } 22 }