Lines Matching refs:pool
52 pool: &NodePool<F>, in find()
59 match pool[node] { in find()
92 pub fn first(&mut self, root: Node, pool: &NodePool<F>) -> (F::Key, F::Value) { in first()
98 match pool[node] { in first()
108 pub fn next(&mut self, pool: &NodePool<F>) -> Option<(F::Key, F::Value)> { in next()
112 let (keys, vals) = pool[node].unwrap_leaf(); in next()
122 self.next_node(leaf_level, pool).map(|node| { in next()
123 let (keys, vals) = pool[node].unwrap_leaf(); in next()
133 pub fn prev(&mut self, root: Node, pool: &NodePool<F>) -> Option<(F::Key, F::Value)> { in prev()
136 self.goto_subtree_last(0, root, pool); in prev()
138 let (keys, vals) = pool[node].unwrap_leaf(); in prev()
147 let (keys, vals) = pool[node].unwrap_leaf(); in prev()
154 self.prev_leaf(pool).map(|node| { in prev()
155 let (keys, vals) = pool[node].unwrap_leaf(); in prev()
166 fn next_node(&mut self, level: usize, pool: &NodePool<F>) -> Option<Node> { in next_node()
167 match self.right_sibling_branch_level(level, pool) { in next_node()
173 let (_, bnodes) = pool[self.node[bl]].unwrap_inner(); in next_node()
180 node = pool[node].unwrap_inner().1[0]; in next_node()
195 fn prev_leaf(&mut self, pool: &NodePool<F>) -> Option<Node> { in prev_leaf()
199 let (_, bnodes) = pool[self.node[bl]].unwrap_inner(); in prev_leaf()
200 self.goto_subtree_last(bl + 1, bnodes[usize::from(entry)], pool) in prev_leaf()
205 fn goto_subtree_last(&mut self, level: usize, root: Node, pool: &NodePool<F>) -> Node { in goto_subtree_last()
209 match pool[node] { in goto_subtree_last()
256 pub fn value_mut<'a>(&self, pool: &'a mut NodePool<F>) -> &'a mut F::Value { in value_mut()
257 &mut pool[self.leaf_node()].unwrap_leaf_mut().1[self.leaf_entry()] in value_mut()
268 pool: &mut NodePool<F>, in insert()
270 if !self.try_leaf_insert(key, value, pool) { in insert()
271 self.split_and_insert(key, value, pool)?; in insert()
278 fn try_leaf_insert(&self, key: F::Key, value: F::Value, pool: &mut NodePool<F>) -> bool { in try_leaf_insert()
286 pool[self.leaf_node()].try_leaf_insert(index, key, value) in try_leaf_insert()
295 pool: &mut NodePool<F>, in split_and_insert()
307 split = pool[node].split(entry); in split_and_insert()
308 let rhs_node = pool.alloc_node(split.rhs_data)?; in split_and_insert()
330 let inserted = pool[node].try_leaf_insert(entry, key, value); in split_and_insert()
339 let inserted = pool[node].try_inner_insert(entry, key, n); in split_and_insert()
354 let pnode = &mut pool[self.node[level - 1]]; in split_and_insert()
368 let root = pool.alloc_node(NodeData::inner(orig_root, key, rhs_node))?; in split_and_insert()
380 pub fn remove(&mut self, pool: &mut NodePool<F>) -> Option<Node> { in remove()
382 match pool[self.leaf_node()].leaf_remove(e) { in remove()
385 self.update_crit_key(pool) in remove()
389 status => self.balance_nodes(status, pool), in remove()
399 fn current_crit_key(&self, level: usize, pool: &NodePool<F>) -> Option<F::Key> { in current_crit_key()
402 let (keys, _) = pool[self.node[bl]].unwrap_inner(); in current_crit_key()
408 fn update_crit_key(&mut self, pool: &mut NodePool<F>) { in update_crit_key()
417 let crit_key = pool[self.leaf_node()].leaf_crit_key(); in update_crit_key()
420 match pool[crit_node] { in update_crit_key()
435 fn balance_nodes(&mut self, status: Removed, pool: &mut NodePool<F>) -> Option<Node> { in balance_nodes()
441 self.update_crit_key(pool); in balance_nodes()
445 if self.heal_level(status, leaf_level, pool) { in balance_nodes()
455 } = pool[self.node[ns]] in balance_nodes()
463 pool.free_node(self.node[l]); in balance_nodes()
487 fn heal_level(&mut self, status: Removed, level: usize, pool: &mut NodePool<F>) -> bool { in heal_level()
495 pool[self.node[level]].entries() in heal_level()
497 self.next_node(level, pool); in heal_level()
499 Removed::Underflow => self.underflowed_node(level, pool), in heal_level()
500 Removed::Empty => return self.empty_node(level, pool), in heal_level()
511 fn underflowed_node(&mut self, level: usize, pool: &mut NodePool<F>) { in underflowed_node()
514 if let Some((crit_key, rhs_node)) = self.right_sibling(level, pool) { in underflowed_node()
519 let mut rhs = pool[rhs_node]; in underflowed_node()
520 match pool[self.node[level]].balance(crit_key, &mut rhs) { in underflowed_node()
523 new_ck = self.current_crit_key(level, pool); in underflowed_node()
533 pool[rhs_node] = rhs; in underflowed_node()
537 self.update_right_crit_key(level, ck, pool); in underflowed_node()
540 let empty_tree = self.empty_node(level, pool); in underflowed_node()
547 debug_assert!(usize::from(self.entry[level]) < pool[self.node[level]].entries()); in underflowed_node()
548 } else if usize::from(self.entry[level]) >= pool[self.node[level]].entries() { in underflowed_node()
563 fn empty_node(&mut self, level: usize, pool: &mut NodePool<F>) -> bool { in empty_node()
564 pool.free_node(self.node[level]); in empty_node()
571 let rhs_node = self.right_sibling(level, pool).map(|(_, n)| n); in empty_node()
576 let status = pool[self.node[pl]].inner_remove(pe); in empty_node()
577 self.heal_level(status, pl, pool); in empty_node()
597 fn right_sibling_branch_level(&self, level: usize, pool: &NodePool<F>) -> Option<usize> { in right_sibling_branch_level()
598 (0..level).rposition(|l| match pool[self.node[l]] { in right_sibling_branch_level()
611 fn right_sibling(&self, level: usize, pool: &NodePool<F>) -> Option<(F::Key, Node)> { in right_sibling()
614 self.right_sibling_branch_level(level, pool).map(|bl| { in right_sibling()
620 let (keys, tree) = pool[self.node[bl]].unwrap_inner(); in right_sibling()
627 node = pool[node].unwrap_inner().1[0]; in right_sibling()
635 fn update_right_crit_key(&self, level: usize, crit_key: F::Key, pool: &mut NodePool<F>) { in update_right_crit_key()
637 .right_sibling_branch_level(level, pool) in update_right_crit_key()
639 match pool[self.node[bl]] { in update_right_crit_key()
649 pub fn normalize(&mut self, pool: &NodePool<F>) { in normalize()
651 if entry >= pool[leaf].entries() { in normalize()
653 self.next_node(leaf_level, pool); in normalize()
662 pub fn verify(&self, pool: &NodePool<F>) { in verify()
664 match pool[self.node[level]] { in verify()
747 let mut pool = NodePool::<TF>::new(); in search_single_leaf() localVariable
748 let root = pool.alloc_node(NodeData::leaf(10, 'a')).panic_on_oom(); in search_single_leaf()
753 assert_eq!(p.find(5, root, &pool, &comp), None); in search_single_leaf()
759 assert_eq!(p.find(10, root, &pool, &comp), Some('a')); in search_single_leaf()
765 assert_eq!(p.find(15, root, &pool, &comp), None); in search_single_leaf()
771 match pool[root] { in search_single_leaf()
785 assert_eq!(p.find(15, root, &pool, &comp), None); in search_single_leaf()
791 assert_eq!(p.find(25, root, &pool, &comp), None); in search_single_leaf()
800 let mut pool = NodePool::<TF>::new(); in search_single_inner() localVariable
801 let leaf1 = pool.alloc_node(NodeData::leaf(10, 'a')).panic_on_oom(); in search_single_inner()
802 let leaf2 = pool.alloc_node(NodeData::leaf(20, 'b')).panic_on_oom(); in search_single_inner()
803 let root = pool in search_single_inner()
810 assert_eq!(p.find(5, root, &pool, &comp), None); in search_single_inner()
817 assert_eq!(p.find(10, root, &pool, &comp), Some('a')); in search_single_inner()
825 assert_eq!(p.find(15, root, &pool, &comp), None); in search_single_inner()
832 assert_eq!(p.find(20, root, &pool, &comp), Some('b')); in search_single_inner()
839 assert_eq!(p.find(25, root, &pool, &comp), None); in search_single_inner()