Balance this node with its right sibling. It is assumed that the current node has underflowed. Look at the right sibling node and do one of two things: 1. Move all entries to the right node, leaving this node empty, or 2. Distribute entries evenly between the two nodes. In the first case, `None` is returned. In the second case, the new critical key for the right sibling node is returned.
(&mut self, crit_key: F::Key, rhs: &mut Self)
| 361 | /// In the first case, `None` is returned. In the second case, the new critical key for the |
| 362 | /// right sibling node is returned. |
| 363 | pub fn balance(&mut self, crit_key: F::Key, rhs: &mut Self) -> Option<F::Key> { |
| 364 | match (self, rhs) { |
| 365 | ( |
| 366 | &mut Self::Inner { |
| 367 | size: ref mut l_size, |
| 368 | keys: ref mut l_keys, |
| 369 | tree: ref mut l_tree, |
| 370 | }, |
| 371 | &mut Self::Inner { |
| 372 | size: ref mut r_size, |
| 373 | keys: ref mut r_keys, |
| 374 | tree: ref mut r_tree, |
| 375 | }, |
| 376 | ) => { |
| 377 | let l_ents = usize::from(*l_size) + 1; |
| 378 | let r_ents = usize::from(*r_size) + 1; |
| 379 | let ents = l_ents + r_ents; |
| 380 | |
| 381 | if ents <= r_tree.len() { |
| 382 | // All entries will fit in the RHS node. |
| 383 | // We'll leave the LHS node empty, but first use it as a scratch space. |
| 384 | *l_size = 0; |
| 385 | // Insert `crit_key` between the two nodes. |
| 386 | l_keys[l_ents - 1] = crit_key; |
| 387 | l_keys[l_ents..ents - 1].copy_from_slice(&r_keys[0..r_ents - 1]); |
| 388 | r_keys[0..ents - 1].copy_from_slice(&l_keys[0..ents - 1]); |
| 389 | l_tree[l_ents..ents].copy_from_slice(&r_tree[0..r_ents]); |
| 390 | r_tree[0..ents].copy_from_slice(&l_tree[0..ents]); |
| 391 | *r_size = (ents - 1) as u8; |
| 392 | None |
| 393 | } else { |
| 394 | // The entries don't all fit in one node. Distribute some from RHS -> LHS. |
| 395 | // Split evenly with a bias to putting one entry in LHS. |
| 396 | let r_goal = ents / 2; |
| 397 | let l_goal = ents - r_goal; |
| 398 | debug_assert!(l_goal > l_ents, "Node must be underflowed"); |
| 399 | |
| 400 | l_keys[l_ents - 1] = crit_key; |
| 401 | l_keys[l_ents..l_goal - 1].copy_from_slice(&r_keys[0..l_goal - 1 - l_ents]); |
| 402 | l_tree[l_ents..l_goal].copy_from_slice(&r_tree[0..l_goal - l_ents]); |
| 403 | *l_size = (l_goal - 1) as u8; |
| 404 | |
| 405 | let new_crit = r_keys[r_ents - r_goal - 1]; |
| 406 | slice_shift(&mut r_keys[0..r_ents - 1], r_ents - r_goal); |
| 407 | slice_shift(&mut r_tree[0..r_ents], r_ents - r_goal); |
| 408 | *r_size = (r_goal - 1) as u8; |
| 409 | |
| 410 | Some(new_crit) |
| 411 | } |
| 412 | } |
| 413 | ( |
| 414 | &mut Self::Leaf { |
| 415 | size: ref mut l_size, |
| 416 | keys: ref mut l_keys, |
| 417 | vals: ref mut l_vals, |
| 418 | }, |
| 419 | &mut Self::Leaf { |
| 420 | size: ref mut r_size, |
no test coverage detected