Lines Matching defs:node
13992 /// Force AST node to an expression to improve diagnostics in pattern position.
19318 //! with boxes because each node often has only one owner, the parent.
27029 // We do *not* exclusively own the entire list here, references to node's `element`
27076 /// Adds the given node to the front of the list.
27078 fn push_front_node(&mut self, mut node: Box<Node<T>>) {
27082 node.next = self.head;
27083 node.prev = None;
27084 let node = Some(Box::leak(node).into());
27087 None => self.tail = node,
27089 Some(head) => (*head.as_ptr()).prev = node,
27092 self.head = node;
27097 /// Removes and returns the node at the front of the list.
27102 self.head.map(|node| unsafe {
27103 let node = Box::from_raw(node.as_ptr());
27104 self.head = node.next;
27113 node
27117 /// Adds the given node to the back of the list.
27119 fn push_back_node(&mut self, mut node: Box<Node<T>>) {
27123 node.next = None;
27124 node.prev = self.tail;
27125 let node = Some(Box::leak(node).into());
27128 None => self.head = node,
27130 Some(tail) => (*tail.as_ptr()).next = node,
27133 self.tail = node;
27138 /// Removes and returns the node at the back of the list.
27143 self.tail.map(|node| unsafe {
27144 let node = Box::from_raw(node.as_ptr());
27145 self.tail = node.prev;
27154 node
27158 /// Unlinks the specified node from the current list.
27160 /// Warning: this will not check that the provided node belongs to the current list.
27165 unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
27166 let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut.
27169 match node.prev {
27170 Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
27171 // this node is the head node
27172 None => self.head = node.next,
27175 match node.next {
27176 Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
27177 // this node is the tail node
27178 None => self.tail = node.prev,
27186 /// Warning: this will not check that the provided node belongs to the two existing lists.
27240 // The split node is the new head node of the second part
27279 // The split node is the new tail node of the first part and owns
27616 unsafe { self.head.as_ref().map(|node| &node.as_ref().element) }
27642 unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) }
27662 unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) }
27688 unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) }
27812 // Below, we iterate towards the `i-1`th node, either from the start or the end,
27862 // Below, we iterate towards the node at the given index, either from
27932 while let Some(node) = self.pop_front_node() {
27934 drop(node);
27949 self.head.map(|node| unsafe {
27951 let node = &*node.as_ptr();
27953 self.head = node.next;
27954 &node.element
27977 self.tail.map(|node| unsafe {
27979 let node = &*node.as_ptr();
27981 self.tail = node.prev;
27982 &node.element
28003 self.head.map(|node| unsafe {
28005 let node = &mut *node.as_ptr();
28007 self.head = node.next;
28008 &mut node.element
28031 self.tail.map(|node| unsafe {
28033 let node = &mut *node.as_ptr();
28035 self.tail = node.prev;
28036 &mut node.element
28320 Some(node) => node.as_ref().next,
28340 Some(node) => node.as_ref().prev,
28365 /// Removes the current element from the `LinkedList` without deallocating the list node.
28367 /// The node that was removed is returned as a new `LinkedList` containing only this node.
28403 Some(node) => node.as_ref().next,
28426 Some(node) => node.as_ref().prev,
28484 while let Some(mut node) = self.it {
28486 self.it = node.as_ref().next;
28489 if (self.pred)(&mut node.as_mut().element) {
28491 self.list.unlink_node(node);
28492 return Some(Box::from_raw(node.as_ptr()).element);
28775 // tail node should also be None.
28780 Some(node) => node_ptr = &*node.as_ptr(),
28804 // verify that the tail node points to the last node.
28805 let tail = list.tail.as_ref().expect("some tail node").as_ref();
29188 use super::node::{self, Root};
29225 // Try to push key-value pair into the current leaf node.
29226 if cur_node.len() < node::CAPACITY {
29236 if parent.len() < node::CAPACITY {
29237 // Found a node with space left, push here.
29246 // We are at the top, create a new root node and push there.
29523 use super::node::{marker, ForceResult::*, Handle, NodeRef};
29560 /// Looks up a given key in a (sub)tree headed by the node, recursively.
29585 /// Descends to the nearest node where the edge matching the lower bound
29587 /// the nearest node that has at least one key contained in the range.
29589 /// If found, returns an `Ok` with that node, the strictly ascending pair of
29590 /// edge indices in the node delimiting the range, and the corresponding
29592 /// the node is internal.
29660 /// Finds an edge in the node delimiting the lower bound of a range.
29662 /// the matching child node, if `self` is an internal node.
29694 /// Looks up a given key in the node, without recursion.
29697 /// (if the node is internal) or where the key can be inserted.
29712 /// Returns either the KV index in the node at which the key (or an equivalent)
29719 /// `start_index` must be a valid edge index for the node.
29725 let node = self.reborrow();
29726 let keys = node.keys();
29738 /// Finds an edge index in the node delimiting the lower bound of a range.
29740 /// the matching child node, if `self` is an internal node.
29769 /// `start_index` must be a valid edge index for the node.
29805 use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root};
29814 pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
29816 // A tree in a `BTreeMap` is a tree in the `node` module with additional invariants:
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.
29831 /// is stored in its own individually heap-allocated node. This means that every single insertion
29836 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
29839 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
29841 /// the node using binary search. As a compromise, one could also perform a linear search
29953 node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
29959 match node.force() {
32004 /// If the root node is the empty (non-allocated) root node, allocate our
32005 /// own node. Is an associated function to avoid borrowing the entire BTreeMap.
32095 use super::node::{ForceResult::*, Root};
32144 (Internal(edge), Internal(node)) => {
32146 right_node = node.first_edge().descend();
33753 use super::node::{marker, ForceResult::*, Handle, NodeRef};
33804 node,
33810 let mut lower_edge = unsafe { Handle::new_edge(ptr::read(&node), lower_edge_idx) };
33811 let mut upper_edge = unsafe { Handle::new_edge(node, upper_edge_idx) };
33919 /// on the right side, which is either in the same leaf node or in an ancestor node.
33920 /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
33940 /// on the left side, which is either in the same leaf node or in an ancestor node.
33941 /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
33965 /// on the right side, which is either in the same internal node or in an ancestor node.
33966 /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
33989 /// in the same leaf node, in an ancestor node, or non-existent.
33991 /// This method also deallocates any node(s) it reaches the end of. This
34017 /// in the same leaf node, in an ancestor node, or non-existent.
34019 /// This method also deallocates any node(s) it reaches the end of. This
34119 /// in between, deallocating any node left behind while leaving the corresponding
34120 /// edge in its parent node dangling.
34137 /// in between, deallocating any node left behind while leaving the corresponding
34138 /// edge in its parent node dangling.
34156 /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
34160 let mut node = self;
34162 match node.force() {
34164 Internal(internal) => node = internal.first_edge().descend(),
34169 /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
34173 let mut node = self;
34175 match node.force() {
34177 Internal(internal) => node = internal.last_edge().descend(),
34228 Position::Leaf(node) => result += node.len(),
34229 Position::Internal(node) => result += node.len(),
34270 mod node;
35051 use super::super::node::{marker, Handle, InsertResult::*, NodeRef};
35578 // i.e., a tree who's root is a leaf node at height 0.
35579 const NODE_CAPACITY: usize = node::CAPACITY;
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.
35643 self.root.as_ref().map(node::Root::height)
35686 assert!(self.len() >= min_len, "node len {} < {}", self.len(), min_len);
35687 if let node::ForceResult::Internal(node) = self.force() {
35688 for idx in 0..=node.len() {
35689 let edge = unsafe { Handle::new_edge(node, idx) };
35697 // adapt that value to match a change in node::CAPACITY or the choices made
35713 // - 1 element in internal root node with 2 children
35725 // - 1 element in internal root node with 2 children
36198 // Tests tree with a root and 2 leaves. The single key in the root node is
37478 // Single node.
37488 // Three levels; insertion finished at leaf while there is an empty node on the second level.
37571 // In a tree with 3 levels, if all but a part of the first leaf node is split off,
37586 // In a tree with 3 levels, if only part of the last leaf node is split off,
37608 // Insertion in non-ascending order creates some variation in node length.
37734 use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef};
37739 /// a root node that is internal, which the caller should pop from the map
37746 Leaf(node) => node.remove_leaf_kv(handle_emptied_internal_root),
37747 Internal(node) => node.remove_internal_kv(handle_emptied_internal_root),
37762 // distinct node type for the immediate parents of a leaf.
37816 // The internal node may have been stolen from or merged. Go back right
37948 // given node has exactly the same length.
37949 // - A node of length `n` has `n` keys, `n` values, and `n + 1` edges.
37950 // This implies that even an empty node has at least one edge.
37951 // For a leaf node, "having an edge" only means we can identify a position in the node,
37952 // since leaf edges are empty and need no data representation. In an internal node,
37953 // an edge both identifies a position and contains a pointer to a child node.
37975 /// This node's index into the parent node's `edges` array.
37976 /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`.
37980 /// The number of keys and values this node stores.
37983 /// The arrays storing the actual data of the node. Only the first `len` elements of each
38014 /// node, allowing code to act on leaf and internal nodes generically without having to even check
38021 /// The pointers to the children of this node. `len + 1` of these are considered
38036 let mut node = Box::<Self>::new_uninit();
38038 LeafNode::init(ptr::addr_of_mut!((*node.as_mut_ptr()).data));
38039 node.assume_init()
38044 /// A managed, non-null pointer to a node. This is either an owned pointer to
38058 /// A reference to a node.
38074 /// effectively applies to the entire tree, not just to the node itself.
38077 /// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
38078 /// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
38079 /// `NodeRef` could be pointing to either type of node.
38104 /// The number of levels that the node and the level of leaves are apart, a
38105 /// constant of the node that cannot be entirely described by `Type`, and that
38106 /// the node itself does not store. We only need to store the height of the root
38107 /// node, and derive every other node's height from it.
38110 /// The pointer to the leaf or internal node. The definition of `InternalNode`
38112 node: NonNull<LeafNode<K, V>>,
38116 /// The root node of an owned tree.
38142 NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData }
38149 new_node.edges[0].write(child.node);
38157 let node = NonNull::from(Box::leak(internal)).cast();
38158 let mut this = NodeRef { height, node, _marker: PhantomData };
38165 /// Unpack a node reference that was packed as `NodeRef::parent`.
38166 fn from_internal(node: NonNull<InternalNode<K, V>>, height: usize) -> Self {
38168 NodeRef { height, node: node.cast(), _marker: PhantomData }
38173 /// Exposes the data of an internal node.
38175 /// Returns a raw ptr to avoid invalidating other references to this node.
38177 // SAFETY: the static node type is `Internal`.
38178 this.node.as_ptr() as *mut InternalNode<K, V>
38183 /// Borrows exclusive access to the data of an internal node.
38191 /// Finds the length of the node. This is the number of keys or values.
38201 /// Returns the number of levels that the node and leaves are apart. Zero
38202 /// height means the node is a leaf itself. If you picture trees with the
38203 /// root on top, the number says at which elevation the node appears.
38205 /// the tree extends above the node.
38210 /// Temporarily takes out another, immutable reference to the same node.
38212 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38215 /// Exposes the leaf portion of any leaf or internal node.
38217 /// Returns a raw ptr to avoid invalidating other references to this node.
38219 // The node must be valid for at least the LeafNode portion.
38222 this.node.as_ptr()
38227 /// Finds the parent of the current node. Returns `Ok(handle)` if the current
38228 /// node actually has a parent, where `handle` points to the edge of the parent
38229 /// that points to the current node. Returns `Err(self)` if the current node has
38232 /// The method name assumes you picture trees with the root node on top.
38234 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
38246 node: NodeRef::from_internal(*parent, self.height + 1),
38280 let Self { node, height, _marker } = self;
38281 if node.eq(&other.node) {
38291 /// Exposes the leaf portion of any leaf or internal node in an immutable tree.
38298 /// Borrows a view into the keys stored in the node.
38308 /// Similar to `ascend`, gets a reference to a node's parent node, but also
38309 /// deallocates the current node in the process. This is unsafe because the
38310 /// current node will still be accessible despite being deallocated.
38315 let node = self.node;
38319 node.cast(),
38332 /// Temporarily takes out another, mutable reference to the same node. Beware, as
38343 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38346 /// Borrows exclusive access to the leaf portion of any leaf or internal node.
38349 // SAFETY: we have exclusive access to the entire node.
38353 /// Offers exclusive access to the leaf portion of any leaf or internal node.
38356 // SAFETY: we have exclusive access to the entire node.
38376 /// Borrows exclusive access to an element or slice of the node's value storage area.
38392 /// Borrows exclusive access to an element or slice of the node's storage area for edge contents.
38409 /// - The node has more than `idx` initialized elements.
38427 /// Borrows exclusive access to the length of the node.
38435 /// Every item returned by `range` is a valid edge index for the node.
38450 /// Sets the node's link to its parent edge,
38451 /// without invalidating other references to the node.
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
38481 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
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.
38496 let top = self.node;
38503 self.node = unsafe { internal_node.edges[0].assume_init_read() };
38514 /// Mutably borrows the owned root node. Unlike `reborrow_mut`, this is safe
38518 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38521 /// Slightly mutably borrows the owned root node.
38523 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38529 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38534 /// Adds a key-value pair to the end of the node.
38549 /// to the end of the node.
38560 self.edge_area_mut(idx + 1).write(edge.node);
38567 /// Removes any static information asserting that this node is a `Leaf` node.
38569 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38574 /// Removes any static information asserting that this node is an `Internal` node.
38576 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38581 /// Checks whether a node is an `Internal` node or a `Leaf` node.
38591 node: self.node,
38597 node: self.node,
38605 /// Unsafely asserts to the compiler the static information that this node is a `Leaf`.
38608 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38611 /// Unsafely asserts to the compiler the static information that this node is an `Internal`.
38614 NodeRef { height: self.height, node: self.node, _marker: PhantomData }
38618 /// A reference to a specific key-value pair or edge within a node. The `Node` parameter
38623 /// a child node, these represent the spaces where child pointers would go between the key-value
38624 /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
38625 /// to the left of the node, one between the two pairs, and one at the right of the node.
38627 node: Node,
38642 /// Retrieves the node that contains the edge or key-value pair this handle points to.
38644 self.node
38647 /// Returns the position of this handle in the node.
38654 /// Creates a new handle to a key-value pair in `node`.
38655 /// Unsafe because the caller must ensure that `idx < node.len()`.
38656 pub unsafe fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
38657 debug_assert!(idx < node.len());
38659 Handle { node, idx, _marker: PhantomData }
38663 unsafe { Handle::new_edge(self.node, self.idx) }
38667 unsafe { Handle::new_edge(self.node, self.idx + 1) }
38675 let Self { node, idx, _marker } = self;
38676 node.eq(&other.node) && *idx == other.idx
38686 Handle { node: self.node.reborrow(), idx: self.idx, _marker: PhantomData }
38700 Handle { node: unsafe { self.node.reborrow_mut() }, idx: self.idx, _marker: PhantomData }
38705 /// Creates a new handle to an edge in `node`.
38706 /// Unsafe because the caller must ensure that `idx <= node.len()`.
38707 pub unsafe fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
38708 debug_assert!(idx <= node.len());
38710 Handle { node, idx, _marker: PhantomData }
38715 Ok(unsafe { Handle::new_kv(self.node, self.idx - 1) })
38722 if self.idx < self.node.len() {
38723 Ok(unsafe { Handle::new_kv(self.node, self.idx) })
38735 /// Given an edge index where we want to insert into a node filled to capacity,
38737 /// The goal of the split point is for its key and value to end up in a parent node;
38753 /// this edge. This method assumes that there is enough space in the node for the new
38758 debug_assert!(self.node.len() < CAPACITY);
38759 let new_len = self.node.len() + 1;
38762 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
38763 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
38764 *self.node.len_mut() = new_len as u16;
38766 self.node.val_area_mut(self.idx).assume_init_mut()
38773 /// this edge. This method splits the node if there isn't enough room.
38777 if self.node.len() < CAPACITY {
38779 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
38783 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
38800 /// Fixes the parent pointer and index in the child node that this edge
38803 // Create backpointer without invalidating other references to the node.
38804 let ptr = unsafe { NonNull::new_unchecked(NodeRef::as_internal_ptr(&self.node)) };
38814 /// that there is enough space in the node for the new pair to fit.
38816 debug_assert!(self.node.len() < CAPACITY);
38817 debug_assert!(edge.height == self.node.height - 1);
38818 let new_len = self.node.len() + 1;
38821 slice_insert(self.node.key_area_mut(..new_len), self.idx, key);
38822 slice_insert(self.node.val_area_mut(..new_len), self.idx, val);
38823 slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
38824 *self.node.len_mut() = new_len as u16;
38826 self.node.correct_childrens_parent_links(self.idx + 1..new_len + 1);
38832 /// the node if there isn't enough room.
38839 assert!(edge.height == self.node.height - 1);
38841 if self.node.len() < CAPACITY {
38843 let kv = unsafe { Handle::new_kv(self.node, self.idx) };
38847 let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) };
38865 /// this edge. This method splits the node if there isn't enough room, and tries to
38866 /// insert the split off portion into the parent node recursively, until the root is reached.
38868 /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor.
38869 /// If the returned result is a `Split`, the `left` field will be the root node.
38902 /// Finds the node pointed to by this edge.
38904 /// The method name assumes you picture trees with the root node on top.
38906 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
38914 // node pointer is dereferenced, we access the edges array with a
38917 let parent_ptr = NodeRef::as_internal_ptr(&self.node);
38918 let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() };
38919 NodeRef { node, height: self.node.height - 1, _marker: PhantomData }
38925 debug_assert!(self.idx < self.node.len());
38926 let leaf = self.node.into_leaf();
38935 unsafe { self.node.key_area_mut(self.idx).assume_init_mut() }
38939 debug_assert!(self.idx < self.node.len());
38940 let leaf = self.node.into_leaf_mut();
38947 unsafe { self.node.into_key_val_mut_at(self.idx) }
38953 debug_assert!(self.idx < self.node.len());
38957 let leaf = self.node.as_leaf_mut();
38975 debug_assert!(self.idx < self.node.len());
38976 let old_len = self.node.len();
38980 let k = self.node.key_area_mut(self.idx).assume_init_read();
38981 let v = self.node.val_area_mut(self.idx).assume_init_read();
38984 self.node.key_area_mut(self.idx + 1..old_len),
38988 self.node.val_area_mut(self.idx + 1..old_len),
38992 *self.node.len_mut() = self.idx as u16;
38999 /// Splits the underlying node into three parts:
39001 /// - The node is truncated to only contain the key-value pairs to the left of
39005 /// allocated node.
39012 SplitResult { left: self.node, kv, right }
39020 let old_len = self.node.len();
39022 let k = slice_remove(self.node.key_area_mut(..old_len), self.idx);
39023 let v = slice_remove(self.node.val_area_mut(..old_len), self.idx);
39024 *self.node.len_mut() = (old_len - 1) as u16;
39031 /// Splits the underlying node into three parts:
39033 /// - The node is truncated to only contain the edges and key-value pairs to the
39037 /// a newly allocated node.
39039 let old_len = self.node.len();
39045 self.node.edge_area_mut(self.idx + 1..old_len + 1),
39049 let height = self.node.height;
39052 SplitResult { left: self.node, kv, right }
39078 /// Chooses a balancing context involving the node as a child, thus between
39079 /// the KV immediately to the left or to the right in the parent node.
39083 /// Prefers the left side, to be optimal if the given node is somehow
39087 /// the node's N elements, instead of shifting them to the right and moving
39089 /// typically faster, since we only need to shift the node's N elements to
39106 Err(_) => unreachable!("empty internal node"),
39132 /// in a node to combine the central KV with both adjacent child nodes.
39150 let Handle { node: mut parent_node, idx: parent_idx, _marker } = self.parent;
39183 // of the node of this edge, thus above zero, so they are internal.
39193 Global.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>());
39195 Global.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>());
39202 /// the left child node and returns the shrunk parent node.
39210 /// the left child node and returns that child node.
39218 /// the left child node and returns the edge handle in that child node
39396 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
39404 unsafe { Handle::new_edge(self.node.forget_type(), self.idx) }
39412 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
39420 unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
39425 /// Checks whether the underlying node is an `Internal` node or a `Leaf` node.
39432 match self.node.force() {
39433 ForceResult::Leaf(node) => {
39434 ForceResult::Leaf(Handle { node, idx: self.idx, _marker: PhantomData })
39436 ForceResult::Internal(node) => {
39437 ForceResult::Internal(Handle { node, idx: self.idx, _marker: PhantomData })
39444 /// Unsafely asserts to the compiler the static information that the handle's node is a `Leaf`.
39448 let node = unsafe { self.node.cast_to_leaf_unchecked() };
39449 Handle { node, idx: self.idx, _marker: PhantomData }
39454 /// Move the suffix after `self` from one node to another one. `right` must be empty.
39504 /// Result of insertion, when a node needed to expand beyond its capacity.
39506 // Altered node in existing tree with elements and edges that belong to the left of `kv`.
39510 // Owned, unattached, new node with elements and edges that belong to the right of `kv`.
39545 // Whether node references of this borrow type allow traversing
39552 // we know that every reference of the `Owned` type is to a root node.
39636 // Asserts that the back pointer in each reachable node points to its parent.
39638 if let ForceResult::Internal(node) = self.force() {
39639 for idx in 0..=node.len() {
39640 let edge = unsafe { Handle::new_edge(node, idx) };
39732 use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef, Root};
39735 /// Stocks up a possibly underfull node by merging with or stealing from a
39736 /// sibling. If succesful but at the cost of shrinking the parent node,
39737 /// returns that shrunk parent node. Returns an `Err` if the node is
39778 /// Stocks up a possibly underfull node, and if that causes its parent node
39781 /// root node became empty.
44316 //! // Each node is represented as an `usize`, for a shorter implementation.
44318 //! node: usize,
44325 //! // to each node. This implementation isn't memory-efficient as it may leave duplicate
44329 //! // dist[node] = current shortest distance from `start` to `node`
44346 //! // For each node we can reach, see if we can find a way with
44347 //! // a lower cost going through this node
44349 //! let next = State { cost: cost + edge.cost, position: edge.node };
44366 //! // The node numbers correspond to the different states,
44368 //! // from one node to another.
44384 //! // corresponding to a node value, has a list of outgoing edges.
44388 //! vec![Edge { node: 2, cost: 10 },
44389 //! Edge { node: 1, cost: 1 }],
44391 //! vec![Edge { node: 3, cost: 2 }],
44393 //! vec![Edge { node: 1, cost: 1 },
44394 //! Edge { node: 3, cost: 3 },
44395 //! Edge { node: 4, cost: 1 }],
44397 //! vec![Edge { node: 0, cost: 7 },
44398 //! Edge { node: 4, cost: 2 }],