1 //! A path from the root of a B+-tree to a leaf node. 2 3 use super::node::Removed; 4 use super::{slice_insert, slice_shift, Comparator, Forest, Node, NodeData, NodePool, MAX_PATH}; 5 use core::borrow::Borrow; 6 use core::marker::PhantomData; 7 8 #[cfg(test)] 9 use core::fmt; 10 11 pub(super) struct Path<F: Forest> { 12 /// Number of path entries including the root and leaf nodes. 13 size: usize, 14 15 /// Path of node references from the root to a leaf node. 16 node: [Node; MAX_PATH], 17 18 /// Entry number in each node. 19 entry: [u8; MAX_PATH], 20 21 unused: PhantomData<F>, 22 } 23 24 impl<F: Forest> Default for Path<F> { default() -> Self25 fn default() -> Self { 26 Self { 27 size: 0, 28 node: [Node(0); MAX_PATH], 29 entry: [0; MAX_PATH], 30 unused: PhantomData, 31 } 32 } 33 } 34 35 impl<F: Forest> Path<F> { 36 /// Reset path by searching for `key` starting from `root`. 37 /// 38 /// If `key` is in the tree, returns the corresponding value and leaved the path pointing at 39 /// the entry. Otherwise returns `None` and: 40 /// 41 /// - A key smaller than all stored keys returns a path to the first entry of the first leaf. 42 /// - A key larger than all stored keys returns a path to one beyond the last element of the 43 /// last leaf. 44 /// - A key between the stored keys of adjacent leaf nodes returns a path to one beyond the 45 /// last entry of the first of the leaf nodes. 46 /// find( &mut self, key: F::Key, root: Node, pool: &NodePool<F>, comp: &dyn Comparator<F::Key>, ) -> Option<F::Value>47 pub fn find( 48 &mut self, 49 key: F::Key, 50 root: Node, 51 pool: &NodePool<F>, 52 comp: &dyn Comparator<F::Key>, 53 ) -> Option<F::Value> { 54 let mut node = root; 55 for level in 0.. { 56 self.size = level + 1; 57 self.node[level] = node; 58 match pool[node] { 59 NodeData::Inner { size, keys, tree } => { 60 // Invariant: `tree[i]` contains keys smaller than 61 // `keys[i]`, greater or equal to `keys[i-1]`. 62 let i = match comp.search(key, &keys[0..size.into()]) { 63 // We hit an existing key, so follow the >= branch. 64 Ok(i) => i + 1, 65 // Key is less than `keys[i]`, so follow the < branch. 66 Err(i) => i, 67 }; 68 self.entry[level] = i as u8; 69 node = tree[i]; 70 } 71 NodeData::Leaf { size, keys, vals } => { 72 // For a leaf we want either the found key or an insert position. 73 return match comp.search(key, &keys.borrow()[0..size.into()]) { 74 Ok(i) => { 75 self.entry[level] = i as u8; 76 Some(vals.borrow()[i]) 77 } 78 Err(i) => { 79 self.entry[level] = i as u8; 80 None 81 } 82 }; 83 } 84 NodeData::Free { .. } => panic!("Free {} reached from {}", node, root), 85 } 86 } 87 unreachable!(); 88 } 89 90 /// Move path to the first entry of the tree starting at `root` and return it. first(&mut self, root: Node, pool: &NodePool<F>) -> (F::Key, F::Value)91 pub fn first(&mut self, root: Node, pool: &NodePool<F>) -> (F::Key, F::Value) { 92 let mut node = root; 93 for level in 0.. { 94 self.size = level + 1; 95 self.node[level] = node; 96 self.entry[level] = 0; 97 match pool[node] { 98 NodeData::Inner { tree, .. } => node = tree[0], 99 NodeData::Leaf { keys, vals, .. } => return (keys.borrow()[0], vals.borrow()[0]), 100 NodeData::Free { .. } => panic!("Free {} reached from {}", node, root), 101 } 102 } 103 unreachable!(); 104 } 105 106 /// Move this path to the next key-value pair and return it. next(&mut self, pool: &NodePool<F>) -> Option<(F::Key, F::Value)>107 pub fn next(&mut self, pool: &NodePool<F>) -> Option<(F::Key, F::Value)> { 108 match self.leaf_pos() { 109 None => return None, 110 Some((node, entry)) => { 111 let (keys, vals) = pool[node].unwrap_leaf(); 112 if entry + 1 < keys.len() { 113 self.entry[self.size - 1] += 1; 114 return Some((keys[entry + 1], vals[entry + 1])); 115 } 116 } 117 } 118 119 // The current leaf node is exhausted. Move to the next one. 120 let leaf_level = self.size - 1; 121 self.next_node(leaf_level, pool).map(|node| { 122 let (keys, vals) = pool[node].unwrap_leaf(); 123 (keys[0], vals[0]) 124 }) 125 } 126 127 /// Move this path to the previous key-value pair and return it. 128 /// 129 /// If the path is at the off-the-end position, go to the last key-value pair. 130 /// 131 /// If the path is already at the first key-value pair, leave it there and return `None`. prev(&mut self, root: Node, pool: &NodePool<F>) -> Option<(F::Key, F::Value)>132 pub fn prev(&mut self, root: Node, pool: &NodePool<F>) -> Option<(F::Key, F::Value)> { 133 // We use `size == 0` as a generic off-the-end position. 134 if self.size == 0 { 135 self.goto_subtree_last(0, root, pool); 136 let (node, entry) = self.leaf_pos().unwrap(); 137 let (keys, vals) = pool[node].unwrap_leaf(); 138 return Some((keys[entry], vals[entry])); 139 } 140 141 match self.leaf_pos() { 142 None => return None, 143 Some((node, entry)) => { 144 if entry > 0 { 145 self.entry[self.size - 1] -= 1; 146 let (keys, vals) = pool[node].unwrap_leaf(); 147 return Some((keys[entry - 1], vals[entry - 1])); 148 } 149 } 150 } 151 152 // The current leaf node is exhausted. Move to the previous one. 153 self.prev_leaf(pool).map(|node| { 154 let (keys, vals) = pool[node].unwrap_leaf(); 155 let e = self.leaf_entry(); 156 (keys[e], vals[e]) 157 }) 158 } 159 160 /// Move path to the first entry of the next node at level, if one exists. 161 /// 162 /// Returns the new node if it exists. 163 /// 164 /// Reset the path to `size = 0` and return `None` if there is no next node. next_node(&mut self, level: usize, pool: &NodePool<F>) -> Option<Node>165 fn next_node(&mut self, level: usize, pool: &NodePool<F>) -> Option<Node> { 166 match self.right_sibling_branch_level(level, pool) { 167 None => { 168 self.size = 0; 169 None 170 } 171 Some(bl) => { 172 let (_, bnodes) = pool[self.node[bl]].unwrap_inner(); 173 self.entry[bl] += 1; 174 let mut node = bnodes[usize::from(self.entry[bl])]; 175 176 for l in bl + 1..level { 177 self.node[l] = node; 178 self.entry[l] = 0; 179 node = pool[node].unwrap_inner().1[0]; 180 } 181 182 self.node[level] = node; 183 self.entry[level] = 0; 184 Some(node) 185 } 186 } 187 } 188 189 /// Move the path to the last entry of the previous leaf node, if one exists. 190 /// 191 /// Returns the new leaf node if it exists. 192 /// 193 /// Leave the path unchanged and returns `None` if we are already at the first leaf node. prev_leaf(&mut self, pool: &NodePool<F>) -> Option<Node>194 fn prev_leaf(&mut self, pool: &NodePool<F>) -> Option<Node> { 195 self.left_sibling_branch_level(self.size - 1).map(|bl| { 196 let entry = self.entry[bl] - 1; 197 self.entry[bl] = entry; 198 let (_, bnodes) = pool[self.node[bl]].unwrap_inner(); 199 self.goto_subtree_last(bl + 1, bnodes[usize::from(entry)], pool) 200 }) 201 } 202 203 /// Move this path to the last position for the sub-tree at `level, root`. goto_subtree_last(&mut self, level: usize, root: Node, pool: &NodePool<F>) -> Node204 fn goto_subtree_last(&mut self, level: usize, root: Node, pool: &NodePool<F>) -> Node { 205 let mut node = root; 206 for l in level.. { 207 self.node[l] = node; 208 match pool[node] { 209 NodeData::Inner { size, ref tree, .. } => { 210 self.entry[l] = size; 211 node = tree[usize::from(size)]; 212 } 213 NodeData::Leaf { size, .. } => { 214 self.entry[l] = size - 1; 215 self.size = l + 1; 216 break; 217 } 218 NodeData::Free { .. } => panic!("Free {} reached from {}", node, root), 219 } 220 } 221 node 222 } 223 224 /// Set the root node and point the path at the first entry of the node. set_root_node(&mut self, root: Node)225 pub fn set_root_node(&mut self, root: Node) { 226 self.size = 1; 227 self.node[0] = root; 228 self.entry[0] = 0; 229 } 230 231 /// Get the current leaf node and entry, if any. leaf_pos(&self) -> Option<(Node, usize)>232 pub fn leaf_pos(&self) -> Option<(Node, usize)> { 233 let i = self.size.wrapping_sub(1); 234 self.node.get(i).map(|&n| (n, self.entry[i].into())) 235 } 236 237 /// Get the current leaf node. leaf_node(&self) -> Node238 fn leaf_node(&self) -> Node { 239 self.node[self.size - 1] 240 } 241 242 /// Get the current entry in the leaf node. leaf_entry(&self) -> usize243 fn leaf_entry(&self) -> usize { 244 self.entry[self.size - 1].into() 245 } 246 247 /// Is this path pointing to the first entry in the tree? 248 /// This corresponds to the smallest key. at_first_entry(&self) -> bool249 fn at_first_entry(&self) -> bool { 250 self.entry[0..self.size].iter().all(|&i| i == 0) 251 } 252 253 /// Get a mutable reference to the current value. 254 /// This assumes that there is a current value. value_mut<'a>(&self, pool: &'a mut NodePool<F>) -> &'a mut F::Value255 pub fn value_mut<'a>(&self, pool: &'a mut NodePool<F>) -> &'a mut F::Value { 256 &mut pool[self.leaf_node()].unwrap_leaf_mut().1[self.leaf_entry()] 257 } 258 259 /// Insert the key-value pair at the current position. 260 /// The current position must be the correct insertion location for the key. 261 /// This function does not check for duplicate keys. Use `find` or similar for that. 262 /// Returns the new root node. insert(&mut self, key: F::Key, value: F::Value, pool: &mut NodePool<F>) -> Node263 pub fn insert(&mut self, key: F::Key, value: F::Value, pool: &mut NodePool<F>) -> Node { 264 if !self.try_leaf_insert(key, value, pool) { 265 self.split_and_insert(key, value, pool); 266 } 267 self.node[0] 268 } 269 270 /// Try to insert `key, value` at the current position, but fail and return false if the leaf 271 /// node is full. try_leaf_insert(&self, key: F::Key, value: F::Value, pool: &mut NodePool<F>) -> bool272 fn try_leaf_insert(&self, key: F::Key, value: F::Value, pool: &mut NodePool<F>) -> bool { 273 let index = self.leaf_entry(); 274 275 // The case `index == 0` should only ever happen when there are no earlier leaf nodes, 276 // otherwise we should have appended to the previous leaf node instead. This invariant 277 // means that we don't need to update keys stored in inner nodes here. 278 debug_assert!(index > 0 || self.at_first_entry()); 279 280 pool[self.leaf_node()].try_leaf_insert(index, key, value) 281 } 282 283 /// Split the current leaf node and then insert `key, value`. 284 /// This should only be used if `try_leaf_insert()` fails. split_and_insert(&mut self, mut key: F::Key, value: F::Value, pool: &mut NodePool<F>)285 fn split_and_insert(&mut self, mut key: F::Key, value: F::Value, pool: &mut NodePool<F>) { 286 let orig_root = self.node[0]; 287 288 // Loop invariant: We need to split the node at `level` and then retry a failed insertion. 289 // The items to insert are either `(key, ins_node)` or `(key, value)`. 290 let mut ins_node = None; 291 let mut split; 292 for level in (0..self.size).rev() { 293 // Split the current node. 294 let mut node = self.node[level]; 295 let mut entry = self.entry[level].into(); 296 split = pool[node].split(entry); 297 let rhs_node = pool.alloc_node(split.rhs_data); 298 299 // Should the path be moved to the new RHS node? 300 // Prefer the smaller node if we're right in the middle. 301 // Prefer to append to LHS all other things being equal. 302 // 303 // When inserting into an inner node (`ins_node.is_some()`), we must point to a valid 304 // entry in the current node since the new entry is inserted *after* the insert 305 // location. 306 if entry > split.lhs_entries 307 || (entry == split.lhs_entries 308 && (split.lhs_entries > split.rhs_entries || ins_node.is_some())) 309 { 310 node = rhs_node; 311 entry -= split.lhs_entries; 312 self.node[level] = node; 313 self.entry[level] = entry as u8; 314 } 315 316 // Now that we have a not-full node, it must be possible to insert. 317 match ins_node { 318 None => { 319 let inserted = pool[node].try_leaf_insert(entry, key, value); 320 debug_assert!(inserted); 321 // If we inserted at the front of the new rhs_node leaf, we need to propagate 322 // the inserted key as the critical key instead of the previous front key. 323 if entry == 0 && node == rhs_node { 324 split.crit_key = key; 325 } 326 } 327 Some(n) => { 328 let inserted = pool[node].try_inner_insert(entry, key, n); 329 debug_assert!(inserted); 330 // The lower level was moved to the new RHS node, so make sure that is 331 // reflected here. 332 if n == self.node[level + 1] { 333 self.entry[level] += 1; 334 } 335 } 336 } 337 338 // We are now done with the current level, but `rhs_node` must be inserted in the inner 339 // node above us. If we're already at level 0, the root node needs to be split. 340 key = split.crit_key; 341 ins_node = Some(rhs_node); 342 if level > 0 { 343 let pnode = &mut pool[self.node[level - 1]]; 344 let pentry = self.entry[level - 1].into(); 345 if pnode.try_inner_insert(pentry, key, rhs_node) { 346 // If this level level was moved to the new RHS node, update parent entry. 347 if node == rhs_node { 348 self.entry[level - 1] += 1; 349 } 350 return; 351 } 352 } 353 } 354 355 // If we get here we have split the original root node and need to add an extra level. 356 let rhs_node = ins_node.expect("empty path"); 357 let root = pool.alloc_node(NodeData::inner(orig_root, key, rhs_node)); 358 let entry = if self.node[0] == rhs_node { 1 } else { 0 }; 359 self.size += 1; 360 slice_insert(&mut self.node[0..self.size], 0, root); 361 slice_insert(&mut self.entry[0..self.size], 0, entry); 362 } 363 364 /// Remove the key-value pair at the current position and advance the path to the next 365 /// key-value pair, leaving the path in a normalized state. 366 /// 367 /// Return the new root node. remove(&mut self, pool: &mut NodePool<F>) -> Option<Node>368 pub fn remove(&mut self, pool: &mut NodePool<F>) -> Option<Node> { 369 let e = self.leaf_entry(); 370 match pool[self.leaf_node()].leaf_remove(e) { 371 Removed::Healthy => { 372 if e == 0 { 373 self.update_crit_key(pool) 374 } 375 Some(self.node[0]) 376 } 377 status => self.balance_nodes(status, pool), 378 } 379 } 380 381 /// Get the critical key for the current node at `level`. 382 /// 383 /// The critical key is less than or equal to all keys in the sub-tree at `level` and greater 384 /// than all keys to the left of the current node at `level`. 385 /// 386 /// The left-most node at any level does not have a critical key. current_crit_key(&self, level: usize, pool: &NodePool<F>) -> Option<F::Key>387 fn current_crit_key(&self, level: usize, pool: &NodePool<F>) -> Option<F::Key> { 388 // Find the level containing the critical key for the current node. 389 self.left_sibling_branch_level(level).map(|bl| { 390 let (keys, _) = pool[self.node[bl]].unwrap_inner(); 391 keys[usize::from(self.entry[bl]) - 1] 392 }) 393 } 394 395 /// Update the critical key after removing the front entry of the leaf node. update_crit_key(&mut self, pool: &mut NodePool<F>)396 fn update_crit_key(&mut self, pool: &mut NodePool<F>) { 397 // Find the inner level containing the critical key for the current leaf node. 398 let crit_level = match self.left_sibling_branch_level(self.size - 1) { 399 None => return, 400 Some(l) => l, 401 }; 402 let crit_kidx = self.entry[crit_level] - 1; 403 404 // Extract the new critical key from the leaf node. 405 let crit_key = pool[self.leaf_node()].leaf_crit_key(); 406 let crit_node = self.node[crit_level]; 407 408 match pool[crit_node] { 409 NodeData::Inner { 410 size, ref mut keys, .. 411 } => { 412 debug_assert!(crit_kidx < size); 413 keys[usize::from(crit_kidx)] = crit_key; 414 } 415 _ => panic!("Expected inner node"), 416 } 417 } 418 419 /// Given that the current leaf node is in an unhealthy (underflowed or even empty) status, 420 /// balance it with sibling nodes. 421 /// 422 /// Return the new root node. balance_nodes(&mut self, status: Removed, pool: &mut NodePool<F>) -> Option<Node>423 fn balance_nodes(&mut self, status: Removed, pool: &mut NodePool<F>) -> Option<Node> { 424 // The current leaf node is not in a healthy state, and its critical key may have changed 425 // too. 426 // 427 // Start by dealing with a changed critical key for the leaf level. 428 if status != Removed::Empty && self.leaf_entry() == 0 { 429 self.update_crit_key(pool); 430 } 431 432 let leaf_level = self.size - 1; 433 if self.heal_level(status, leaf_level, pool) { 434 // Tree has become empty. 435 self.size = 0; 436 return None; 437 } 438 439 // Discard the root node if it has shrunk to a single sub-tree. 440 let mut ns = 0; 441 while let NodeData::Inner { 442 size: 0, ref tree, .. 443 } = pool[self.node[ns]] 444 { 445 ns += 1; 446 self.node[ns] = tree[0]; 447 } 448 449 if ns > 0 { 450 for l in 0..ns { 451 pool.free_node(self.node[l]); 452 } 453 454 // Shift the whole array instead of just 0..size because `self.size` may be cleared 455 // here if the path is pointing off-the-end. 456 slice_shift(&mut self.node, ns); 457 slice_shift(&mut self.entry, ns); 458 459 if self.size > 0 { 460 self.size -= ns; 461 } 462 } 463 464 // Return the root node, even when `size=0` indicating that we're at the off-the-end 465 // position. 466 Some(self.node[0]) 467 } 468 469 /// After removing an entry from the node at `level`, check its health and rebalance as needed. 470 /// 471 /// Leave the path up to and including `level` in a normalized state where all entries are in 472 /// bounds. 473 /// 474 /// Returns true if the tree becomes empty. heal_level(&mut self, status: Removed, level: usize, pool: &mut NodePool<F>) -> bool475 fn heal_level(&mut self, status: Removed, level: usize, pool: &mut NodePool<F>) -> bool { 476 match status { 477 Removed::Healthy => {} 478 Removed::Rightmost => { 479 // The rightmost entry was removed from the current node, so move the path so it 480 // points at the first entry of the next node at this level. 481 debug_assert_eq!( 482 usize::from(self.entry[level]), 483 pool[self.node[level]].entries() 484 ); 485 self.next_node(level, pool); 486 } 487 Removed::Underflow => self.underflowed_node(level, pool), 488 Removed::Empty => return self.empty_node(level, pool), 489 } 490 false 491 } 492 493 /// The current node at `level` has underflowed, meaning that it is below half capacity but 494 /// not completely empty. 495 /// 496 /// Handle this by balancing entries with the right sibling node. 497 /// 498 /// Leave the path up to and including `level` in a valid state that points to the same entry. underflowed_node(&mut self, level: usize, pool: &mut NodePool<F>)499 fn underflowed_node(&mut self, level: usize, pool: &mut NodePool<F>) { 500 // Look for a right sibling node at this level. If none exists, we allow the underflowed 501 // node to persist as the right-most node at its level. 502 if let Some((crit_key, rhs_node)) = self.right_sibling(level, pool) { 503 // New critical key for the updated right sibling node. 504 let new_ck: Option<F::Key>; 505 let empty; 506 // Make a COPY of the sibling node to avoid fighting the borrow checker. 507 let mut rhs = pool[rhs_node]; 508 match pool[self.node[level]].balance(crit_key, &mut rhs) { 509 None => { 510 // Everything got moved to the RHS node. 511 new_ck = self.current_crit_key(level, pool); 512 empty = true; 513 } 514 Some(key) => { 515 // Entries moved from RHS node. 516 new_ck = Some(key); 517 empty = false; 518 } 519 } 520 // Put back the updated RHS node data. 521 pool[rhs_node] = rhs; 522 // Update the critical key for the RHS node unless it has become a left-most 523 // node. 524 if let Some(ck) = new_ck { 525 self.update_right_crit_key(level, ck, pool); 526 } 527 if empty { 528 let empty_tree = self.empty_node(level, pool); 529 debug_assert!(!empty_tree); 530 } 531 532 // Any Removed::Rightmost state must have been cleared above by merging nodes. If the 533 // current entry[level] was one off the end of the node, it will now point at a proper 534 // entry. 535 debug_assert!(usize::from(self.entry[level]) < pool[self.node[level]].entries()); 536 } else if usize::from(self.entry[level]) >= pool[self.node[level]].entries() { 537 // There's no right sibling at this level, so the node can't be rebalanced. 538 // Check if we are in an off-the-end position. 539 self.size = 0; 540 } 541 } 542 543 /// The current node at `level` has become empty. 544 /// 545 /// Remove the node from its parent node and leave the path in a normalized state. This means 546 /// that the path at this level will go through the right sibling of this node. 547 /// 548 /// If the current node has no right sibling, set `self.size = 0`. 549 /// 550 /// Returns true if the tree becomes empty. empty_node(&mut self, level: usize, pool: &mut NodePool<F>) -> bool551 fn empty_node(&mut self, level: usize, pool: &mut NodePool<F>) -> bool { 552 pool.free_node(self.node[level]); 553 if level == 0 { 554 // We just deleted the root node, so the tree is now empty. 555 return true; 556 } 557 558 // Get the right sibling node before recursively removing nodes. 559 let rhs_node = self.right_sibling(level, pool).map(|(_, n)| n); 560 561 // Remove the current sub-tree from the parent node. 562 let pl = level - 1; 563 let pe = self.entry[pl].into(); 564 let status = pool[self.node[pl]].inner_remove(pe); 565 self.heal_level(status, pl, pool); 566 567 // Finally update the path at this level. 568 match rhs_node { 569 // We'll leave `self.entry[level]` unchanged. It can be non-zero after moving node 570 // entries to the right sibling node. 571 Some(rhs) => self.node[level] = rhs, 572 // We have no right sibling, so we must have deleted the right-most 573 // entry. The path should be moved to the "off-the-end" position. 574 None => self.size = 0, 575 } 576 false 577 } 578 579 /// Find the level where the right sibling to the current node at `level` branches off. 580 /// 581 /// This will be an inner node with two adjacent sub-trees: In one the current node at level is 582 /// a right-most node, in the other, the right sibling is a left-most node. 583 /// 584 /// Returns `None` if the current node is a right-most node so no right sibling exists. right_sibling_branch_level(&self, level: usize, pool: &NodePool<F>) -> Option<usize>585 fn right_sibling_branch_level(&self, level: usize, pool: &NodePool<F>) -> Option<usize> { 586 (0..level).rposition(|l| match pool[self.node[l]] { 587 NodeData::Inner { size, .. } => self.entry[l] < size, 588 _ => panic!("Expected inner node"), 589 }) 590 } 591 592 /// Find the level where the left sibling to the current node at `level` branches off. left_sibling_branch_level(&self, level: usize) -> Option<usize>593 fn left_sibling_branch_level(&self, level: usize) -> Option<usize> { 594 self.entry[0..level].iter().rposition(|&e| e != 0) 595 } 596 597 /// Get the right sibling node to the current node at `level`. 598 /// Also return the critical key between the current node and the right sibling. right_sibling(&self, level: usize, pool: &NodePool<F>) -> Option<(F::Key, Node)>599 fn right_sibling(&self, level: usize, pool: &NodePool<F>) -> Option<(F::Key, Node)> { 600 // Find the critical level: The deepest level where two sibling subtrees contain the 601 // current node and its right sibling. 602 self.right_sibling_branch_level(level, pool).map(|bl| { 603 // Extract the critical key and the `bl+1` node. 604 let be = usize::from(self.entry[bl]); 605 let crit_key; 606 let mut node; 607 { 608 let (keys, tree) = pool[self.node[bl]].unwrap_inner(); 609 crit_key = keys[be]; 610 node = tree[be + 1]; 611 } 612 613 // Follow left-most links back down to `level`. 614 for _ in bl + 1..level { 615 node = pool[node].unwrap_inner().1[0]; 616 } 617 618 (crit_key, node) 619 }) 620 } 621 622 /// Update the critical key for the right sibling node at `level`. update_right_crit_key(&self, level: usize, crit_key: F::Key, pool: &mut NodePool<F>)623 fn update_right_crit_key(&self, level: usize, crit_key: F::Key, pool: &mut NodePool<F>) { 624 let bl = self 625 .right_sibling_branch_level(level, pool) 626 .expect("No right sibling exists"); 627 match pool[self.node[bl]] { 628 NodeData::Inner { ref mut keys, .. } => { 629 keys[usize::from(self.entry[bl])] = crit_key; 630 } 631 _ => panic!("Expected inner node"), 632 } 633 } 634 635 /// Normalize the path position such that it is either pointing at a real entry or `size=0` 636 /// indicating "off-the-end". normalize(&mut self, pool: &mut NodePool<F>)637 pub fn normalize(&mut self, pool: &mut NodePool<F>) { 638 if let Some((leaf, entry)) = self.leaf_pos() { 639 if entry >= pool[leaf].entries() { 640 let leaf_level = self.size - 1; 641 self.next_node(leaf_level, pool); 642 } 643 } 644 } 645 } 646 647 #[cfg(test)] 648 impl<F: Forest> Path<F> { 649 /// Check the internal consistency of this path. verify(&self, pool: &NodePool<F>)650 pub fn verify(&self, pool: &NodePool<F>) { 651 for level in 0..self.size { 652 match pool[self.node[level]] { 653 NodeData::Inner { size, tree, .. } => { 654 assert!( 655 level < self.size - 1, 656 "Expected leaf node at level {}", 657 level 658 ); 659 assert!( 660 self.entry[level] <= size, 661 "OOB inner entry {}/{} at level {}", 662 self.entry[level], 663 size, 664 level 665 ); 666 assert_eq!( 667 self.node[level + 1], 668 tree[usize::from(self.entry[level])], 669 "Node mismatch at level {}", 670 level 671 ); 672 } 673 NodeData::Leaf { size, .. } => { 674 assert_eq!(level, self.size - 1, "Expected inner node"); 675 assert!( 676 self.entry[level] <= size, 677 "OOB leaf entry {}/{}", 678 self.entry[level], 679 size, 680 ); 681 } 682 NodeData::Free { .. } => { 683 panic!("Free {} in path", self.node[level]); 684 } 685 } 686 } 687 } 688 } 689 690 #[cfg(test)] 691 impl<F: Forest> fmt::Display for Path<F> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result692 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 693 if self.size == 0 { 694 write!(f, "<empty path>") 695 } else { 696 write!(f, "{}[{}]", self.node[0], self.entry[0])?; 697 for i in 1..self.size { 698 write!(f, "--{}[{}]", self.node[i], self.entry[i])?; 699 } 700 Ok(()) 701 } 702 } 703 } 704 705 #[cfg(test)] 706 mod tests { 707 use super::super::{Forest, NodeData, NodePool}; 708 use super::*; 709 use core::cmp::Ordering; 710 711 struct TC(); 712 713 impl Comparator<i32> for TC { cmp(&self, a: i32, b: i32) -> Ordering714 fn cmp(&self, a: i32, b: i32) -> Ordering { 715 a.cmp(&b) 716 } 717 } 718 719 struct TF(); 720 721 impl Forest for TF { 722 type Key = i32; 723 type Value = char; 724 type LeafKeys = [i32; 7]; 725 type LeafValues = [char; 7]; 726 splat_key(key: Self::Key) -> Self::LeafKeys727 fn splat_key(key: Self::Key) -> Self::LeafKeys { 728 [key; 7] 729 } 730 splat_value(value: Self::Value) -> Self::LeafValues731 fn splat_value(value: Self::Value) -> Self::LeafValues { 732 [value; 7] 733 } 734 } 735 736 #[test] search_single_leaf()737 fn search_single_leaf() { 738 // Testing Path::new() for trees with a single leaf node. 739 let mut pool = NodePool::<TF>::new(); 740 let root = pool.alloc_node(NodeData::leaf(10, 'a')); 741 let mut p = Path::default(); 742 let comp = TC(); 743 744 // Search for key less than stored key. 745 assert_eq!(p.find(5, root, &pool, &comp), None); 746 assert_eq!(p.size, 1); 747 assert_eq!(p.node[0], root); 748 assert_eq!(p.entry[0], 0); 749 750 // Search for stored key. 751 assert_eq!(p.find(10, root, &pool, &comp), Some('a')); 752 assert_eq!(p.size, 1); 753 assert_eq!(p.node[0], root); 754 assert_eq!(p.entry[0], 0); 755 756 // Search for key greater than stored key. 757 assert_eq!(p.find(15, root, &pool, &comp), None); 758 assert_eq!(p.size, 1); 759 assert_eq!(p.node[0], root); 760 assert_eq!(p.entry[0], 1); 761 762 // Modify leaf node to contain two values. 763 match pool[root] { 764 NodeData::Leaf { 765 ref mut size, 766 ref mut keys, 767 ref mut vals, 768 } => { 769 *size = 2; 770 keys[1] = 20; 771 vals[1] = 'b'; 772 } 773 _ => unreachable!(), 774 } 775 776 // Search for key between stored keys. 777 assert_eq!(p.find(15, root, &pool, &comp), None); 778 assert_eq!(p.size, 1); 779 assert_eq!(p.node[0], root); 780 assert_eq!(p.entry[0], 1); 781 782 // Search for key greater than stored keys. 783 assert_eq!(p.find(25, root, &pool, &comp), None); 784 assert_eq!(p.size, 1); 785 assert_eq!(p.node[0], root); 786 assert_eq!(p.entry[0], 2); 787 } 788 789 #[test] search_single_inner()790 fn search_single_inner() { 791 // Testing Path::new() for trees with a single inner node and two leaves. 792 let mut pool = NodePool::<TF>::new(); 793 let leaf1 = pool.alloc_node(NodeData::leaf(10, 'a')); 794 let leaf2 = pool.alloc_node(NodeData::leaf(20, 'b')); 795 let root = pool.alloc_node(NodeData::inner(leaf1, 20, leaf2)); 796 let mut p = Path::default(); 797 let comp = TC(); 798 799 // Search for key less than stored keys. 800 assert_eq!(p.find(5, root, &pool, &comp), None); 801 assert_eq!(p.size, 2); 802 assert_eq!(p.node[0], root); 803 assert_eq!(p.entry[0], 0); 804 assert_eq!(p.node[1], leaf1); 805 assert_eq!(p.entry[1], 0); 806 807 assert_eq!(p.find(10, root, &pool, &comp), Some('a')); 808 assert_eq!(p.size, 2); 809 assert_eq!(p.node[0], root); 810 assert_eq!(p.entry[0], 0); 811 assert_eq!(p.node[1], leaf1); 812 assert_eq!(p.entry[1], 0); 813 814 // Midway between the two leaf nodes. 815 assert_eq!(p.find(15, root, &pool, &comp), None); 816 assert_eq!(p.size, 2); 817 assert_eq!(p.node[0], root); 818 assert_eq!(p.entry[0], 0); 819 assert_eq!(p.node[1], leaf1); 820 assert_eq!(p.entry[1], 1); 821 822 assert_eq!(p.find(20, root, &pool, &comp), Some('b')); 823 assert_eq!(p.size, 2); 824 assert_eq!(p.node[0], root); 825 assert_eq!(p.entry[0], 1); 826 assert_eq!(p.node[1], leaf2); 827 assert_eq!(p.entry[1], 0); 828 829 assert_eq!(p.find(25, root, &pool, &comp), None); 830 assert_eq!(p.size, 2); 831 assert_eq!(p.node[0], root); 832 assert_eq!(p.entry[0], 1); 833 assert_eq!(p.node[1], leaf2); 834 assert_eq!(p.entry[1], 1); 835 } 836 } 837