Lines Matching defs:child
29591 /// pair of bounds for continuing the search in the child nodes, in case
29662 /// the matching child node, if `self` is an internal node.
29740 /// the matching child node, if `self` is an internal node.
34192 /// internal nodes precede their individual KVs and their child nodes.
35714 // - 6 elements in left leaf child
35715 // - 5 elements in right leaf child
35726 // - 6 elements in left internal child with 7 grandchildren
35727 // - 42 elements in left child's 7 grandchildren with 6 elements each
35728 // - 5 elements in right internal child with 6 grandchildren
35729 // - 30 elements in right child's 5 first grandchildren with 6 elements each
35730 // - 5 elements in right child's last grandchild
36053 // Descend into first child.
36055 // Descend into first child again, after running through second child.
37761 // We have to temporarily forget the child type, because there is no
37953 // an edge both identifies a position and contains a pointer to a child node.
38147 fn new_internal(child: Root<K, V>) -> Self {
38149 new_node.edges[0].write(child.node);
38150 unsafe { NodeRef::from_new_internal(new_node, child.height + 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,
38623 /// a child node, these represent the spaces where child pointers would go between the key-value
38738 /// the keys, values and edges to the left of the split point become the left child;
38739 /// the keys, values and edges to the right of the split point become the right child.
38800 /// Fixes the parent pointer and index in the child node that this edge
38806 let mut child = self.descend();
38807 child.set_parent_link(ptr, idx);
39078 /// Chooses a balancing context involving the node as a child, thus between
39132 /// in a node to combine the central KV with both adjacent child nodes.
39201 /// Merges the parent's key-value pair and both adjacent child nodes into
39202 /// the left child node and returns the shrunk parent node.
39209 /// Merges the parent's key-value pair and both adjacent child nodes into
39210 /// the left child node and returns that child node.
39214 self.do_merge(|_parent, child| child)
39217 /// Merges the parent's key-value pair and both adjacent child nodes into
39218 /// the left child node and returns the edge handle in that child node
39219 /// where the tracked child edge ended up,
39232 let child = self.merge_tracking_child();
39237 unsafe { Handle::new_edge(child, new_idx) }
39240 /// Removes a key-value pair from the left child and places it in the key-value storage
39241 /// of the parent, while pushing the old parent key-value pair into the right child.
39242 /// Returns a handle to the edge in the right child corresponding to where the original
39252 /// Removes a key-value pair from the right child and places it in the key-value storage
39253 /// of the parent, while pushing the old parent key-value pair onto the left child.
39254 /// Returns a handle to the edge in the left child specified by `track_left_edge_idx`,
39284 // Make room for stolen elements in the right child.
39288 // Move elements from the left child to the right one.
39303 // Move parent's key-value pair to the right child.
39352 // Move parent's key-value pair to the left child.
39356 // Move elements from the right child to the left one.
39641 let child = edge.descend();
39642 assert!(child.ascend().ok() == Some(edge));
39643 child.assert_back_pointers();
39830 // Check if right-most child is underfull.
39862 /// Stocks up the left child, assuming the right child isn't underfull, and
39865 /// Returns the left child.
39882 /// Stocks up the right child, assuming the left child isn't underfull, and
39885 /// Returns wherever the right child ended up.
44833 let mut child = 2 * hole.pos() + 1;
44835 // Loop invariant: child == 2 * hole.pos() + 1.
44836 while child <= end.saturating_sub(2) {
44838 // SAFETY: child < end - 1 < self.len() and
44839 // child + 1 < end <= self.len(), so they're valid indexes.
44840 // child == 2 * hole.pos() + 1 != hole.pos() and
44841 // child + 1 == 2 * hole.pos() + 2 != hole.pos().
44844 child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
44847 // SAFETY: child is now either the old child or the old child+1
44849 if hole.element() >= unsafe { hole.get(child) } {
44854 unsafe { hole.move_to(child) };
44855 child = 2 * hole.pos() + 1;
44859 // second condition it's already true that child == end - 1 < self.len().
44860 if child == end - 1 && hole.element() < unsafe { hole.get(child) } {
44861 // SAFETY: child is already proven to be a valid index and
44862 // child == 2 * hole.pos() + 1 != hole.pos().
44863 unsafe { hole.move_to(child) };
44892 let mut child = 2 * hole.pos() + 1;
44894 // Loop invariant: child == 2 * hole.pos() + 1.
44895 while child <= end.saturating_sub(2) {
44896 // SAFETY: child < end - 1 < self.len() and
44897 // child + 1 < end <= self.len(), so they're valid indexes.
44898 // child == 2 * hole.pos() + 1 != hole.pos() and
44899 // child + 1 == 2 * hole.pos() + 2 != hole.pos().
44902 child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
44905 unsafe { hole.move_to(child) };
44906 child = 2 * hole.pos() + 1;
44909 if child == end - 1 {
44910 // SAFETY: child == end - 1 < self.len(), so it's a valid index
44911 // and child == 2 * hole.pos() + 1 != hole.pos().
44912 unsafe { hole.move_to(child) };