Split off the second half of this node. It is assumed that this a completely full inner or leaf node. The `insert_index` parameter is the position where an insertion was tried and failed. The node will be split in half with a bias towards an even split after the insertion is retried.
(&mut self, insert_index: usize)
| 222 | /// The `insert_index` parameter is the position where an insertion was tried and failed. The |
| 223 | /// node will be split in half with a bias towards an even split after the insertion is retried. |
| 224 | pub fn split(&mut self, insert_index: usize) -> SplitOff<F> { |
| 225 | match *self { |
| 226 | Self::Inner { |
| 227 | ref mut size, |
| 228 | ref keys, |
| 229 | ref tree, |
| 230 | } => { |
| 231 | debug_assert_eq!(usize::from(*size), keys.len(), "Node not full"); |
| 232 | |
| 233 | // Number of tree entries in the lhs node. |
| 234 | let l_ents = split_pos(tree.len(), insert_index + 1); |
| 235 | let r_ents = tree.len() - l_ents; |
| 236 | |
| 237 | // With INNER_SIZE=8, we get l_ents=4 and: |
| 238 | // |
| 239 | // self: [ n0 k0 n1 k1 n2 k2 n3 k3 n4 k4 n5 k5 n6 k6 n7 ] |
| 240 | // lhs: [ n0 k0 n1 k1 n2 k2 n3 ] |
| 241 | // crit_key = k3 (not present in either node) |
| 242 | // rhs: [ n4 k4 n5 k5 n6 k6 n7 ] |
| 243 | |
| 244 | // 1. Truncate the LHS. |
| 245 | *size = (l_ents - 1) as u8; |
| 246 | |
| 247 | // 2. Copy second half to `rhs_data`. |
| 248 | let mut r_keys = *keys; |
| 249 | r_keys[0..r_ents - 1].copy_from_slice(&keys[l_ents..]); |
| 250 | |
| 251 | let mut r_tree = *tree; |
| 252 | r_tree[0..r_ents].copy_from_slice(&tree[l_ents..]); |
| 253 | |
| 254 | SplitOff { |
| 255 | lhs_entries: l_ents, |
| 256 | rhs_entries: r_ents, |
| 257 | crit_key: keys[l_ents - 1], |
| 258 | rhs_data: Self::Inner { |
| 259 | size: (r_ents - 1) as u8, |
| 260 | keys: r_keys, |
| 261 | tree: r_tree, |
| 262 | }, |
| 263 | } |
| 264 | } |
| 265 | Self::Leaf { |
| 266 | ref mut size, |
| 267 | ref keys, |
| 268 | ref vals, |
| 269 | } => { |
| 270 | let o_keys = keys.borrow(); |
| 271 | let o_vals = vals.borrow(); |
| 272 | debug_assert_eq!(usize::from(*size), o_keys.len(), "Node not full"); |
| 273 | |
| 274 | let l_size = split_pos(o_keys.len(), insert_index); |
| 275 | let r_size = o_keys.len() - l_size; |
| 276 | |
| 277 | // 1. Truncate the LHS node at `l_size`. |
| 278 | *size = l_size as u8; |
| 279 | |
| 280 | // 2. Copy second half to `rhs_data`. |
| 281 | let mut r_keys = *keys; |