The current node at `level` has underflowed, meaning that it is below half capacity but not completely empty. Handle this by balancing entries with the right sibling node. Leave the path up to and including `level` in a valid state that points to the same entry.
(&mut self, level: usize, pool: &mut NodePool<F>)
| 509 | /// |
| 510 | /// Leave the path up to and including `level` in a valid state that points to the same entry. |
| 511 | fn underflowed_node(&mut self, level: usize, pool: &mut NodePool<F>) { |
| 512 | // Look for a right sibling node at this level. If none exists, we allow the underflowed |
| 513 | // node to persist as the right-most node at its level. |
| 514 | if let Some((crit_key, rhs_node)) = self.right_sibling(level, pool) { |
| 515 | // New critical key for the updated right sibling node. |
| 516 | let new_ck: Option<F::Key>; |
| 517 | let empty; |
| 518 | // Make a COPY of the sibling node to avoid fighting the borrow checker. |
| 519 | let mut rhs = pool[rhs_node]; |
| 520 | match pool[self.node[level]].balance(crit_key, &mut rhs) { |
| 521 | None => { |
| 522 | // Everything got moved to the RHS node. |
| 523 | new_ck = self.current_crit_key(level, pool); |
| 524 | empty = true; |
| 525 | } |
| 526 | Some(key) => { |
| 527 | // Entries moved from RHS node. |
| 528 | new_ck = Some(key); |
| 529 | empty = false; |
| 530 | } |
| 531 | } |
| 532 | // Put back the updated RHS node data. |
| 533 | pool[rhs_node] = rhs; |
| 534 | // Update the critical key for the RHS node unless it has become a left-most |
| 535 | // node. |
| 536 | if let Some(ck) = new_ck { |
| 537 | self.update_right_crit_key(level, ck, pool); |
| 538 | } |
| 539 | if empty { |
| 540 | let empty_tree = self.empty_node(level, pool); |
| 541 | debug_assert!(!empty_tree); |
| 542 | } |
| 543 | |
| 544 | // Any Removed::Rightmost state must have been cleared above by merging nodes. If the |
| 545 | // current entry[level] was one off the end of the node, it will now point at a proper |
| 546 | // entry. |
| 547 | debug_assert!(usize::from(self.entry[level]) < pool[self.node[level]].entries()); |
| 548 | } else if usize::from(self.entry[level]) >= pool[self.node[level]].entries() { |
| 549 | // There's no right sibling at this level, so the node can't be rebalanced. |
| 550 | // Check if we are in an off-the-end position. |
| 551 | self.size = 0; |
| 552 | } |
| 553 | } |
| 554 | |
| 555 | /// The current node at `level` has become empty. |
| 556 | /// |
no test coverage detected