Lines Matching full:tree
17 /// A red-black tree with owned nodes.
23 /// In the example below we do several operations on a tree. We note that insertions may fail if
29 /// // Create a new tree.
30 /// let mut tree = RBTree::new();
33 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
34 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
35 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
39 /// assert_eq!(tree.get(&10), Some(&100));
40 /// assert_eq!(tree.get(&20), Some(&200));
41 /// assert_eq!(tree.get(&30), Some(&300));
46 /// let mut iter = tree.iter();
54 /// for (key, value) in &tree {
59 /// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?;
61 /// // Check that the tree reflects the replacement.
63 /// let mut iter = tree.iter();
71 /// *tree.get_mut(&30).unwrap() = 3000;
73 /// // Check that the tree reflects the update.
75 /// let mut iter = tree.iter();
83 /// tree.remove(&10);
85 /// // Check that the tree reflects the removal.
87 /// let mut iter = tree.iter();
97 /// the tree. This is useful when the insertion context does not allow sleeping, for example, when
103 /// fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
109 /// let mut guard = tree.lock();
120 /// // Create a new tree.
121 /// let mut tree = RBTree::new();
124 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
125 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
126 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
130 /// let mut iter = tree.iter();
138 /// let existing = tree.remove(&30);
140 /// // Check that the tree reflects the removal.
142 /// let mut iter = tree.iter();
151 /// // Insert a new node into the tree, reusing the previous allocation. This is guaranteed to
153 /// tree.insert(reservation.into_node(15, 150));
155 /// // Check that the tree reflect the new insertion.
157 /// let mut iter = tree.iter();
185 /// Creates a new and empty tree.
188 // INVARIANT: There are no nodes in the tree, so the invariant holds vacuously. in new()
194 /// Returns an iterator over the tree nodes, sorted by key.
199 // - `self.root` is a valid pointer to a tree root. in iter()
209 /// Returns a mutable iterator over the tree nodes, sorted by key.
214 // - `self.root` is a valid pointer to a tree root. in iter_mut()
224 /// Returns an iterator over the keys of the nodes in the tree, in sorted order.
229 /// Returns an iterator over the values of the nodes in the tree, sorted by key.
234 /// Returns a mutable iterator over the values of the nodes in the tree, sorted by key.
239 /// Returns a cursor over the tree nodes, starting with the smallest key.
249 tree: self, in cursor_front()
254 /// Returns a cursor over the tree nodes, starting with the largest key.
264 tree: self, in cursor_back()
274 /// Tries to insert a new value into the tree.
289 /// Inserts a new node into the tree.
310 // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be in raw_entry()
316 // red/black tree is empty, then it’s also possible for `parent` to be null. In in raw_entry()
317 // this case, `rb_link` is a pointer to the `root` field of the red/black tree. in raw_entry()
319 // We will traverse the tree looking for a node that has a null pointer as its child, in raw_entry()
321 // that we preserve the ordering of the nodes in the tree. In each iteration of the loop in raw_entry()
399 /// Removes the node with the given key from the tree.
406 /// Removes the node with the given key from the tree.
413 /// Returns a cursor over the tree nodes based on the given key.
469 tree: self, in cursor_lower_bound()
486 // INVARIANT: The loop invariant is that all tree nodes from `next` in postorder are valid. in drop()
504 /// A bidirectional cursor over the tree nodes, sorted by key.
508 /// In the following example, we obtain a cursor to the first element in the tree.
509 /// The cursor allows us to iterate bidirectionally over key/value pairs in the tree.
514 /// // Create a new tree.
515 /// let mut tree = RBTree::new();
518 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
519 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
520 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
523 /// let mut cursor = tree.cursor_front().unwrap();
548 /// A cursor can also be obtained at the last element in the tree.
553 /// // Create a new tree.
554 /// let mut tree = RBTree::new();
557 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
558 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
559 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
561 /// let mut cursor = tree.cursor_back().unwrap();
568 /// Obtaining a cursor returns [`None`] if the tree is empty.
573 /// let mut tree: RBTree<u16, u16> = RBTree::new();
574 /// assert!(tree.cursor_front().is_none());
579 /// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary node in the tree.
584 /// // Create a new tree.
585 /// let mut tree = RBTree::new();
588 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
589 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
590 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
591 /// tree.try_create_and_insert(40, 400, flags::GFP_KERNEL)?;
592 /// tree.try_create_and_insert(50, 500, flags::GFP_KERNEL)?;
595 /// let cursor = tree.cursor_lower_bound(&20).unwrap();
600 /// let cursor = tree.cursor_lower_bound(&25).unwrap();
605 /// let cursor = tree.cursor_lower_bound(&55);
611 /// The cursor allows mutation of values in the tree.
616 /// // Create a new tree.
617 /// let mut tree = RBTree::new();
620 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
621 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
622 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
625 /// let mut cursor = tree.cursor_front().unwrap();
631 /// // The updated value is reflected in the tree.
632 /// let updated = tree.get(&10).unwrap();
643 /// // Create a new tree.
644 /// let mut tree = RBTree::new();
647 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
648 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
649 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
652 /// let mut cursor = tree.cursor_front().unwrap();
662 /// cursor = tree.cursor_back().unwrap();
671 /// // Removing the last element in the tree returns [`None`].
682 /// // Create a new tree.
683 /// let mut tree = RBTree::new();
686 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
687 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
688 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
691 /// let mut cursor = tree.cursor_front().unwrap();
699 /// cursor = tree.cursor_back().unwrap();
722 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
724 tree: &'a mut RBTree<K, V>, field
754 /// Remove the current node from the tree.
757 /// else the previous node, else [`None`] (if the tree becomes empty). The second element
768 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_current()
769 // the tree cannot change. By the tree invariant, all nodes are valid. in remove_current()
770 unsafe { bindings::rb_erase(&mut (*this).links, addr_of_mut!(self.tree.root)) }; in remove_current()
782 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`. in remove_current()
785 tree: self.tree, in remove_current()
804 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_neighbor()
805 // the tree cannot change. By the tree invariant, all nodes are valid. in remove_neighbor()
806 unsafe { bindings::rb_erase(neighbor, addr_of_mut!(self.tree.root)) }; in remove_neighbor()
829 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`. in mv()
831 tree: self.tree, in mv()
849 // - `neighbor` is a valid tree node. in peek()
868 // - `neighbor` is a valid tree node. in peek_mut()
1026 // SAFETY: `self.next` is a valid tree node by the type invariants. in next()
1034 /// A memory reservation for a red-black tree node.
1037 /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
1044 /// Allocates memory for a node to be eventually initialised and inserted into the tree via a
1063 /// It then becomes an [`RBTreeNode`] that can be inserted into a tree.
1077 /// A red-black tree node.
1079 /// The node is fully initialised (with key and value) and can be inserted into a tree without any
1086 /// Allocates and initialises a node that can be inserted into the tree via
1180 // SAFETY: All pointers are valid. `node` has just been inserted into the tree. in insert()
1183 // SAFETY: The node is valid until we remove it from the tree. in insert()
1198 /// - `node_links` is a valid, non-null pointer to a tree node in `self.rbtree`
1209 // - `self.node_links` is a valid pointer to a node in the tree. in get()
1210 // - We have shared access to the underlying tree, and can thus give out a shared reference. in get()
1217 // - `self.node_links` is a valid pointer to a node in the tree. in get_mut()
1218 … // - We have exclusive access to the underlying tree, and can thus give out a mutable reference. in get_mut()
1227 // - `self.node_links` is a valid pointer to a node in the tree. in into_mut()
1234 // SAFETY: The node is a node in the tree, so it is valid. in remove_node()
1238 // removed from the tree. So the invariants still hold. in remove_node()
1240 // SAFETY: The node was a node in the tree, but we removed it, so we can convert it in remove_node()
1266 // SAFETY: This updates the pointers so that `new_node_links` is in the tree where in replace()
1273 // - `self.node_ptr` produces a valid pointer to a node in the tree. in replace()
1274 // - Now that we removed this entry from the tree, we can convert the node to a box. in replace()