- let (old_kv, mut pos, was_internal) = match self.force() {
- ForceResult::Leaf(leaf) => {
- let (old_kv, pos) = leaf.remove();
- (old_kv, pos, false)
- }
- ForceResult::Internal(mut internal) => {
- // Replace the location freed in the internal node with an
- // adjacent KV, and remove that adjacent KV from its leaf.
- // Always choose the adjacent KV on the left side because
- // it is typically faster to pop an element from the end
- // of the KV arrays without needing to shift other elements.
-
- let key_loc = internal.kv_mut().0 as *mut K;
- let val_loc = internal.kv_mut().1 as *mut V;
-
- let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok();
- let to_remove = unsafe { unwrap_unchecked(to_remove) };
-
- let (kv, pos) = to_remove.remove();
-
- let old_key = unsafe { mem::replace(&mut *key_loc, kv.0) };
- let old_val = unsafe { mem::replace(&mut *val_loc, kv.1) };
-
- ((old_key, old_val), pos, true)
- }
- };
-
- // Handle underflow
- let mut cur_node = unsafe { ptr::read(&pos).into_node().forget_type() };
- let mut at_leaf = true;
- while cur_node.len() < node::MIN_LEN {
- match handle_underfull_node(cur_node) {
- UnderflowResult::AtRoot => break,
- UnderflowResult::Merged(edge, merged_with_left, offset) => {
- // If we merged with our right sibling then our tracked
- // position has not changed. However if we merged with our
- // left sibling then our tracked position is now dangling.
- if at_leaf && merged_with_left {
- let idx = pos.idx() + offset;
- let node = match unsafe { ptr::read(&edge).descend().force() } {
- ForceResult::Leaf(leaf) => leaf,
- ForceResult::Internal(_) => unreachable!(),
- };
- pos = unsafe { Handle::new_edge(node, idx) };
- }