Find the right split position for halving a full node with `len` entries to recover from a failed insertion at `ins`. If `len` is even, we should split straight down the middle regardless of `len`. If `len` is odd, we should split the node such that the two halves are the same size after the insertion is retried.
(len: usize, ins: usize)
| 471 | /// If `len` is odd, we should split the node such that the two halves are the same size after the |
| 472 | /// insertion is retried. |
| 473 | fn split_pos(len: usize, ins: usize) -> usize { |
| 474 | // Anticipate `len` being a compile time constant, so this all folds away when `len` is even. |
| 475 | if ins <= len / 2 { |
| 476 | len / 2 |
| 477 | } else { |
| 478 | (len + 1) / 2 |
| 479 | } |
| 480 | } |
| 481 | |
| 482 | /// The result of splitting off the second half of a node. |
| 483 | pub(super) struct SplitOff<F: Forest> { |