Lines Matching full:tree
18 /// A red-black tree with owned nodes.
24 /// In the example below we do several operations on a tree. We note that insertions may fail if
30 /// // Create a new tree.
31 /// let mut tree = RBTree::new();
34 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
35 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
36 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
40 /// assert_eq!(tree.get(&10).unwrap(), &100);
41 /// assert_eq!(tree.get(&20).unwrap(), &200);
42 /// assert_eq!(tree.get(&30).unwrap(), &300);
47 /// let mut iter = tree.iter();
55 /// for (key, value) in &tree {
60 /// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?;
62 /// // Check that the tree reflects the replacement.
64 /// let mut iter = tree.iter();
72 /// *tree.get_mut(&30).unwrap() = 3000;
74 /// // Check that the tree reflects the update.
76 /// let mut iter = tree.iter();
84 /// tree.remove(&10);
86 /// // Check that the tree reflects the removal.
88 /// let mut iter = tree.iter();
98 /// the tree. This is useful when the insertion context does not allow sleeping, for example, when
104 /// fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
110 /// let mut guard = tree.lock();
121 /// // Create a new tree.
122 /// let mut tree = RBTree::new();
125 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
126 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
127 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
131 /// let mut iter = tree.iter();
139 /// let existing = tree.remove(&30).unwrap();
141 /// // Check that the tree reflects the removal.
143 /// let mut iter = tree.iter();
152 /// // Insert a new node into the tree, reusing the previous allocation. This is guaranteed to
154 /// tree.insert(reservation.into_node(15, 150));
156 /// // Check that the tree reflect the new insertion.
158 /// let mut iter = tree.iter();
186 /// Creates a new and empty tree.
189 // INVARIANT: There are no nodes in the tree, so the invariant holds vacuously. in new()
195 /// Returns an iterator over the tree nodes, sorted by key.
200 // - `self.root` is a valid pointer to a tree root. in iter()
210 /// Returns a mutable iterator over the tree nodes, sorted by key.
215 // - `self.root` is a valid pointer to a tree root. in iter_mut()
225 /// Returns an iterator over the keys of the nodes in the tree, in sorted order.
230 /// Returns an iterator over the values of the nodes in the tree, sorted by key.
235 /// Returns a mutable iterator over the values of the nodes in the tree, sorted by key.
240 /// Returns a cursor over the tree nodes, starting with the smallest key.
250 tree: self, in cursor_front()
255 /// Returns a cursor over the tree nodes, starting with the largest key.
265 tree: self, in cursor_back()
275 /// Tries to insert a new value into the tree.
290 /// Inserts a new node into the tree.
311 // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be in raw_entry()
317 // red/black tree is empty, then it’s also possible for `parent` to be null. In in raw_entry()
318 // this case, `rb_link` is a pointer to the `root` field of the red/black tree. in raw_entry()
320 // We will traverse the tree looking for a node that has a null pointer as its child, in raw_entry()
322 // that we preserve the ordering of the nodes in the tree. In each iteration of the loop in raw_entry()
400 /// Removes the node with the given key from the tree.
407 /// Removes the node with the given key from the tree.
414 /// Returns a cursor over the tree nodes based on the given key.
470 tree: self, in cursor_lower_bound()
487 // INVARIANT: The loop invariant is that all tree nodes from `next` in postorder are valid. in drop()
505 /// A bidirectional cursor over the tree nodes, sorted by key.
509 /// In the following example, we obtain a cursor to the first element in the tree.
510 /// The cursor allows us to iterate bidirectionally over key/value pairs in the tree.
515 /// // Create a new tree.
516 /// let mut tree = RBTree::new();
519 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
520 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
521 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
524 /// let mut cursor = tree.cursor_front().unwrap();
549 /// A cursor can also be obtained at the last element in the tree.
554 /// // Create a new tree.
555 /// let mut tree = RBTree::new();
558 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
559 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
560 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
562 /// let mut cursor = tree.cursor_back().unwrap();
569 /// Obtaining a cursor returns [`None`] if the tree is empty.
574 /// let mut tree: RBTree<u16, u16> = RBTree::new();
575 /// assert!(tree.cursor_front().is_none());
580 /// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary node in the tree.
585 /// // Create a new tree.
586 /// let mut tree = RBTree::new();
589 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
590 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
591 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
592 /// tree.try_create_and_insert(40, 400, flags::GFP_KERNEL)?;
593 /// tree.try_create_and_insert(50, 500, flags::GFP_KERNEL)?;
596 /// let cursor = tree.cursor_lower_bound(&20).unwrap();
601 /// let cursor = tree.cursor_lower_bound(&25).unwrap();
606 /// let cursor = tree.cursor_lower_bound(&55);
612 /// The cursor allows mutation of values in the tree.
617 /// // Create a new tree.
618 /// let mut tree = RBTree::new();
621 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
622 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
623 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
626 /// let mut cursor = tree.cursor_front().unwrap();
632 /// // The updated value is reflected in the tree.
633 /// let updated = tree.get(&10).unwrap();
644 /// // Create a new tree.
645 /// let mut tree = RBTree::new();
648 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
649 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
650 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
653 /// let mut cursor = tree.cursor_front().unwrap();
663 /// cursor = tree.cursor_back().unwrap();
672 /// // Removing the last element in the tree returns [`None`].
683 /// // Create a new tree.
684 /// let mut tree = RBTree::new();
687 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
688 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
689 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
692 /// let mut cursor = tree.cursor_front().unwrap();
700 /// cursor = tree.cursor_back().unwrap();
723 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
725 tree: &'a mut RBTree<K, V>, field
755 /// Remove the current node from the tree.
758 /// else the previous node, else [`None`] (if the tree becomes empty). The second element
769 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_current()
770 // the tree cannot change. By the tree invariant, all nodes are valid. in remove_current()
771 unsafe { bindings::rb_erase(&mut (*this).links, addr_of_mut!(self.tree.root)) }; in remove_current()
783 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`. in remove_current()
786 tree: self.tree, in remove_current()
805 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_neighbor()
806 // the tree cannot change. By the tree invariant, all nodes are valid. in remove_neighbor()
807 unsafe { bindings::rb_erase(neighbor, addr_of_mut!(self.tree.root)) }; in remove_neighbor()
830 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`. in mv()
832 tree: self.tree, in mv()
850 // - `neighbor` is a valid tree node. in peek()
869 // - `neighbor` is a valid tree node. in peek_mut()
1024 // SAFETY: `self.next` is a valid tree node by the type invariants. in next()
1032 /// A memory reservation for a red-black tree node.
1035 /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
1042 /// Allocates memory for a node to be eventually initialised and inserted into the tree via a
1061 /// It then becomes an [`RBTreeNode`] that can be inserted into a tree.
1074 /// A red-black tree node.
1076 /// The node is fully initialised (with key and value) and can be inserted into a tree without any
1083 /// Allocates and initialises a node that can be inserted into the tree via
1175 // SAFETY: All pointers are valid. `node` has just been inserted into the tree. in insert()
1178 // SAFETY: The node is valid until we remove it from the tree. in insert()
1193 /// - `node_links` is a valid, non-null pointer to a tree node in `self.rbtree`
1204 // - `self.node_links` is a valid pointer to a node in the tree. in get()
1205 // - We have shared access to the underlying tree, and can thus give out a shared reference. in get()
1212 // - `self.node_links` is a valid pointer to a node in the tree. in get_mut()
1213 … // - We have exclusive access to the underlying tree, and can thus give out a mutable reference. in get_mut()
1222 // - `self.node_links` is a valid pointer to a node in the tree. in into_mut()
1229 // SAFETY: The node is a node in the tree, so it is valid. in remove_node()
1233 // removed from the tree. So the invariants still hold. in remove_node()
1235 // SAFETY: The node was a node in the tree, but we removed it, so we can convert it in remove_node()
1258 // SAFETY: This updates the pointers so that `new_node_links` is in the tree where in replace()
1265 // - `self.node_ptr` produces a valid pointer to a node in the tree. in replace()
1266 // - Now that we removed this entry from the tree, we can convert the node to a box. in replace()