Lines Matching defs:root
29246 // We are at the top, create a new root node and push there.
29812 /// Minimum number of elements in nodes that are not a root.
29818 // - If the root node is internal, it must contain at least 1 element.
29819 // - Every non-root node contains at least MIN_LEN elements.
29821 // An empty map may be represented both by the absence of a root node or by a
29822 // root node that is an empty leaf.
29936 root: Option<Root<K, V>>,
29943 if let Some(root) = self.root.take() {
29944 Dropper { front: root.into_dying().first_leaf_edge(), remaining_length: self.length };
29961 let mut out_tree = BTreeMap { root: Some(Root::new()), length: 0 };
29964 let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
29965 let mut out_node = match root.borrow_mut().force() {
29986 let out_root = BTreeMap::ensure_is_owned(&mut out_tree.root);
30001 let root = ptr::read(&subtree.root);
30003 (root, length)
30019 BTreeMap { root: None, length: 0 }
30021 clone_subtree(self.root.as_ref().unwrap().reborrow()) // unwrap succeeds because not empty
30034 let root_node = self.root.as_ref()?.reborrow();
30043 let root_node = map.root.as_mut()?.borrow_mut();
30054 let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
30286 BTreeMap { root: None, length: 0 }
30305 *self = BTreeMap { root: None, length: 0 };
30331 let root_node = self.root.as_ref()?.reborrow();
30359 let root_node = self.root.as_ref()?.reborrow();
30388 let root_node = self.root.as_ref()?.reborrow();
30418 let root_node = map.root.as_mut()?.borrow_mut();
30471 let root_node = self.root.as_ref()?.reborrow();
30501 let root_node = map.root.as_mut()?.borrow_mut();
30585 let root_node = self.root.as_mut()?.borrow_mut();
30719 let root_node = map.root.as_mut()?.borrow_mut();
30798 let root = BTreeMap::ensure_is_owned(&mut self.root);
30799 root.append_from_sorted_iters(self_iter, other_iter, &mut self.length)
30838 if let Some(root) = &self.root {
30839 Range { inner: root.reborrow().range_search(range) }
30882 if let Some(root) = &mut self.root {
30883 RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData }
30914 let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
30962 let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty
30969 BTreeMap { root: Some(right_root), length: right_len }
31017 if let Some(root) = self.root.as_mut() {
31018 let (root, dormant_root) = DormantMutRef::new(root);
31019 let front = root.borrow_mut().first_leaf_edge();
31223 if let Some(root) = me.root.take() {
31224 let full_range = root.into_dying().full_range();
31419 /// Buried reference to the root field in the borrowed map.
31423 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
31483 // SAFETY: we will touch the root in a way that will not
31485 let root = unsafe { self.dormant_root.take().unwrap().awaken() };
31486 root.pop_internal_level();
31487 self.dormant_root = Some(DormantMutRef::new(root).1);
31848 if let Some(root) = &self.root {
31849 let full_range = root.reborrow().full_range();
31880 if let Some(root) = &mut self.root {
31881 let full_range = root.borrow_valmut().full_range();
32004 /// If the root node is the empty (non-allocated) root node, allocate our
32006 fn ensure_is_owned(root: &mut Option<Root<K, V>>) -> &mut Root<K, V> {
32007 root.get_or_insert_with(Root::new)
32160 let mut root = Root::new();
32162 root.push_internal_level();
32164 root
33896 // We duplicate the root NodeRef here -- we will never visit the same KV
33908 // We duplicate the root NodeRef here -- we will never access it in a way
33909 // that overlaps references obtained from the root.
33920 /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
33933 Err(root) => return Err(root),
33941 /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
33954 Err(root) => return Err(root),
33966 /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
33979 Err(root) => return Err(root),
34043 /// Deallocates a pile of nodes from the leaf up to the root.
35370 let root = map.root.as_mut().unwrap();
35371 root.push_internal_level().push(ins.kv.0, ins.kv.1, ins.right);
35548 // SAFETY: we consumed the intermediate root borrow, `self.handle`.
35552 let root = map.root.as_mut().unwrap();
35553 root.pop_internal_level();
35578 // i.e., a tree who's root is a leaf node at height 0.
35582 // i.e., a tree who's root is an internal node at height 1, with edges to leaf nodes.
35587 // i.e., a tree who's root is an internal node at height 2, with edges to more internal nodes.
35608 if let Some(root) = &self.root {
35609 let root_node = root.reborrow();
35641 // Returns the height of the root, if any.
35643 self.root.as_ref().map(node::Root::height)
35650 if let Some(root) = self.root.as_ref() {
35651 root.reborrow().dump_keys()
35679 let root = BTreeMap::ensure_is_owned(&mut self.root);
35680 root.bulk_push(iter, &mut self.length);
35713 // - 1 element in internal root node with 2 children
35725 // - 1 element in internal root node with 2 children
35810 // Empty, root is absent (None):
35875 // Empty but root is owned (Some(...)):
36198 // Tests tree with a root and 2 leaves. The single key in the root node is
36203 for root in middle - 2..=middle + 2 {
36204 assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]);
36205 assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]);
36206 assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]);
36207 assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]);
36209 assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]);
36210 assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]);
36211 assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]);
36212 assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]);
37432 let root_node = map.root.as_ref().unwrap().reborrow();
37484 // Two leafs where the second one ends up empty because the insertion finished at the root.
37486 // Three levels; insertion finished at the root.
37739 /// a root node that is internal, which the caller should pop from the map
37927 // root: Option<Box<Node<K, V, height>>>
38106 /// the node itself does not store. We only need to store the height of the root
38116 /// The root node of an owned tree.
38203 /// root on top, the number says at which elevation the node appears.
38232 /// The method name assumes you picture trees with the root node on top.
38460 /// Clears the root's link to its parent edge.
38469 /// Returns a new owned tree, with its own root node that is initially empty.
38474 /// Adds a new internal node with a single edge pointing to the previous root node,
38475 /// make that new node the root node, and return it. This increases the height by 1
38484 /// Removes the internal root node, using its first child as the new root node.
38485 /// As it is intended only to be called when the root node has only one child,
38489 /// Requires exclusive access to the `Root` object but not to the root node;
38490 /// it will not invalidate other handles or references to the root node.
38492 /// Panics if there is no internal level, i.e., if the root node is a leaf.
38514 /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe
38515 /// because the return value cannot be used to destroy the root, and there
38521 /// Slightly mutably borrows the owned root node.
38866 /// insert the split off portion into the parent node recursively, until the root is reached.
38869 /// If the returned result is a `Split`, the `left` field will be the root node.
38891 Err(root) => {
38892 return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr);
38904 /// The method name assumes you picture trees with the root node on top.
39109 Err(root) => Err(root),
39552 // we know that every reference of the `Owned` type is to a root node.
39649 // picturing the tree growing sideways from its root on the left to its
39738 /// an empty root.
39765 Err(root) => {
39769 Err(root)
39781 /// root node became empty.
39805 /// tree. The other nodes, those that are not the root nor a rightmost edge,
39825 /// The other nodes, those that are not the root nor a rightmost edge,