Lines Matching defs:RBTree
27 /// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode, RBTreeNodeReservation}};
30 /// let mut tree = RBTree::new();
101 /// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode}, sync::SpinLock};
103 /// fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
118 /// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNodeReservation}};
121 /// let mut tree = RBTree::new();
171 pub struct RBTree<K, V> {
176 // SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
178 unsafe impl<K: Send, V: Send> Send for RBTree<K, V> {}
180 // SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
182 unsafe impl<K: Sync, V: Sync> Sync for RBTree<K, V> {}
184 impl<K, V> RBTree<K, V> {
252 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
267 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
282 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
297 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
306 impl<K, V> RBTree<K, V>
342 let raw_self: *mut RBTree<K, V> = self;
363 // SAFETY: `raw_self` is a valid pointer to the `RBTree` (created from `self` above).
465 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
486 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
535 impl<K, V> Default for RBTree<K, V> {
541 impl<K, V> Drop for RBTree<K, V> {
572 /// use kernel::{alloc::flags, rbtree::RBTree};
575 /// let mut tree = RBTree::new();
611 /// use kernel::{alloc::flags, rbtree::RBTree};
614 /// let mut tree = RBTree::new();
631 /// use kernel::rbtree::RBTree;
633 /// let mut tree: RBTree<u16, u16> = RBTree::new();
639 /// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary node in the tree.
642 /// use kernel::{alloc::flags, rbtree::RBTree};
645 /// let mut tree = RBTree::new();
674 /// use kernel::{alloc::flags, rbtree::RBTree};
677 /// let mut tree = RBTree::new();
701 /// use kernel::{alloc::flags, rbtree::RBTree};
704 /// let mut tree = RBTree::new();
740 /// use kernel::{alloc::flags, rbtree::RBTree};
743 /// let mut tree = RBTree::new();
782 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
784 tree: &'a mut RBTree<K, V>,
797 /// use kernel::{alloc::flags, rbtree::RBTree};
800 /// let mut tree = RBTree::new();
815 _tree: PhantomData<&'a RBTree<K, V>>,
838 /// - `node` must be a valid pointer to a node in an [`RBTree`].
932 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`.
979 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`.
1038 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1041 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`.
1049 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1052 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`.
1060 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1084 impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
1093 /// An iterator over the nodes of a [`RBTree`].
1095 /// Instances are created by calling [`RBTree::iter`].
1097 _tree: PhantomData<&'a RBTree<K, V>>,
1118 impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
1127 /// A mutable iterator over the nodes of a [`RBTree`].
1129 /// Instances are created by calling [`RBTree::iter_mut`].
1131 _tree: PhantomData<&'a mut RBTree<K, V>>,
1154 /// A raw iterator over the nodes of a [`RBTree`].
1158 /// - `self.next` points to a node stored inside of a valid `RBTree`.
1172 // SAFETY: By the type invariant of `IterRaw`, `self.next` is a valid node in an `RBTree`,
1173 // and by the type invariant of `RBTree`, all nodes point to the links field of `Node<K, V>` objects.
1195 /// call to [`RBTree::insert`].
1237 /// [`RBTree::insert`].
1275 /// This enum is constructed from the [`RBTree::entry`].
1277 /// [`entry`]: fn@RBTree::entry
1279 /// This [`RBTree`] does not have a node with this key.
1281 /// This [`RBTree`] already has a node with this key.
1291 /// A view into a vacant entry in a [`RBTree`]. It is part of the [`Entry`] enum.
1302 /// null, it is a pointer to the root of the [`RBTree`].
1304 rbtree: *mut RBTree<K, V>,
1310 _phantom: PhantomData<&'a mut RBTree<K, V>>,
1314 /// Inserts the given node into the [`RBTree`] at this entry.
1317 /// [`RBTree`].
1339 /// Inserts the given node into the [`RBTree`] at this entry.
1345 /// A view into an occupied entry in a [`RBTree`]. It is part of the [`Entry`] enum.
1350 rbtree: &'a mut RBTree<K, V>,
1378 // - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that lives for `'a`.
1382 /// Remove this entry from the [`RBTree`].