Lines Matching +full:reference +full:- +full:sync
1 // SPDX-License-Identifier: GPL-2.0
3 //! Red-black trees.
7 //! Reference: <https://docs.kernel.org/core-api/rbtree.html>
17 /// A red-black tree with owned nodes.
19 /// It is backed by the kernel C red-black trees.
101 /// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode}, sync::SpinLock};
103 /// fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
104 /// // Pre-allocate node. This may fail (as it allocates memory).
148 /// // Create a preallocated reservation that we can re-use later.
169 /// Non-null parent/children pointers stored in instances of the `rb_node` C struct are always
181 // fields, so we use the same Sync condition as would be used for a struct with K and V fields.
182 unsafe impl<K: Sync, V: Sync> Sync for RBTree<K, V> {}
186 pub fn new() -> Self {
196 pub fn is_empty(&self) -> bool {
201 pub fn iter(&self) -> Iter<'_, K, V> {
205 // - `self.root` is a valid pointer to a tree root.
206 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid.
216 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
220 // - `self.root` is a valid pointer to a tree root.
221 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid.
231 pub fn keys(&self) -> impl Iterator<Item = &'_ K> {
236 pub fn values(&self) -> impl Iterator<Item = &'_ V> {
241 pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
246 pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K, V>> {
252 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
261 pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {
267 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
276 pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>> {
282 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
291 pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {
297 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
321 ) -> Result<Option<RBTreeNode<K, V>>> {
331 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
341 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> {
345 // - `node`: A pointer to an uninitialized node being inserted.
346 // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be
349 // - `rb_link`: A pointer to either the left-child or right-child field of `parent`. This
370 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
372 // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
374 // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
394 /// Gets the given key's corresponding entry in the map for in-place manipulation.
395 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
403 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {
410 /// Returns a reference to the value corresponding to the key.
411 pub fn get(&self, key: &K) -> Option<&V> {
414 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
418 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
421 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
433 /// Returns a mutable reference to the value corresponding to the key.
434 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
441 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
448 pub fn remove(&mut self, key: &K) -> Option<V> {
457 pub fn cursor_lower_bound_mut(&mut self, key: &K) -> Option<CursorMut<'_, K, V>>
465 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
478 pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_, K, V>>
486 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
494 fn find_best_match(&self, key: &K) -> Option<NonNull<bindings::rb_node>> {
499 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
502 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
505 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
510 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
524 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
536 fn default() -> Self {
555 // INVARIANT: This is the destructor, so we break the type invariant during clean-up,
687 /// // Get a mutable reference to the current value.
782 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
821 unsafe impl<'a, K: Sync, V: Sync> Send for Cursor<'a, K, V> {}
825 unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
829 pub fn current(&self) -> (&K, &V) {
831 // - `self.current` is a valid node by the type invariants.
832 // - We have an immutable reference by the function signature.
838 /// - `node` must be a valid pointer to a node in an [`RBTree`].
839 /// - The caller has immutable access to `node` for the duration of `'b`.
840 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
841 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
844 // SAFETY: The passed `node` is the current node or a non-null neighbor,
847 // SAFETY: The passed `node` is the current node or a non-null neighbor,
854 pub fn peek_prev(&self) -> Option<(&K, &V)> {
859 pub fn peek_next(&self) -> Option<(&K, &V)> {
863 fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
866 // - `neighbor` is a valid tree node.
867 // - By the function signature, we have an immutable reference to `self`.
872 fn get_neighbor_raw(&self, direction: Direction) -> Option<NonNull<bindings::rb_node>> {
888 // those same keys, `Send` is sufficient. `Sync` would be okay, but it is more restrictive to the
894 unsafe impl<'a, K: Sync, V: Sync> Sync for CursorMut<'a, K, V> {}
898 pub fn current(&self) -> (&K, &V) {
900 // - `self.current` is a valid node by the type invariants.
901 // - We have an immutable reference by the function signature.
906 pub fn current_mut(&mut self) -> (&K, &mut V) {
908 // - `self.current` is a valid node by the type invariants.
909 // - We have an mutable reference by the function signature.
918 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) {
921 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
927 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
932 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`.
942 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> {
947 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> {
951 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> {
954 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so
957 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
968 pub fn move_prev(self) -> Option<Self> {
973 pub fn move_next(self) -> Option<Self> {
977 fn mv(self, direction: Direction) -> Option<Self> {
979 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`.
987 pub fn peek_prev(&self) -> Option<(&K, &V)> {
992 pub fn peek_next(&self) -> Option<(&K, &V)> {
996 fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
999 // - `neighbor` is a valid tree node.
1000 // - By the function signature, we have an immutable reference to `self`.
1006 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> {
1011 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> {
1015 fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> {
1018 // - `neighbor` is a valid tree node.
1019 // - By the function signature, we have a mutable reference to `self`.
1024 fn get_neighbor_raw(&self, direction: Direction) -> Option<NonNull<bindings::rb_node>> {
1038 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1039 /// - The caller has immutable access to `node` for the duration of `'b`.
1040 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
1049 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1050 /// - The caller has mutable access to `node` for the duration of `'b`.
1051 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) {
1060 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1061 /// - The caller has immutable access to the key for the duration of `'b`.
1062 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) {
1063 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self`
1066 // SAFETY: The passed `node` is the current node or a non-null neighbor,
1069 // SAFETY: The passed `node` is the current node or a non-null neighbor,
1088 fn into_iter(self) -> Self::IntoIter {
1103 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
1107 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
1112 fn next(&mut self) -> Option<Self::Item> {
1122 fn into_iter(self) -> Self::IntoIter {
1137 // keys, `Send` is sufficient. `Sync` would be okay, but it is more restrictive to the user.
1142 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
1147 fn next(&mut self) -> Option<Self::Item> {
1157 /// - `self.next` is a valid pointer.
1158 /// - `self.next` points to a node stored inside of a valid `RBTree`.
1161 _phantom: PhantomData<fn() -> (K, V)>,
1167 fn next(&mut self) -> Option<Self::Item> {
1184 /// A memory reservation for a red-black tree node.
1187 /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
1196 pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> {
1208 unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
1214 pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> {
1227 /// A red-black tree node.
1238 pub fn new(key: K, value: V, flags: Flags) -> Result<RBTreeNode<K, V>> {
1243 pub fn to_key_value(self) -> (K, V) {
1256 unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
1261 /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
1264 /// The existing key and value are dropped in-place as part of this operation, that is, memory
1266 pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {
1300 /// - `parent` may be null if the new node becomes the root.
1301 /// - `child_field_of_parent` is a valid pointer to the left-child or right-child of `parent`. If `parent` is
1307 /// This points to the left-child or right-child field of `parent`, or `root` if `parent` is
1318 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
1340 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {
1348 /// - `node_links` is a valid, non-null pointer to a tree node in `self.rbtree`
1356 /// Gets a reference to the value in the entry.
1357 pub fn get(&self) -> &V {
1359 // - `self.node_links` is a valid pointer to a node in the tree.
1360 // - We have shared access to the underlying tree, and can thus give out a shared reference.
1364 /// Gets a mutable reference to the value in the entry.
1365 pub fn get_mut(&mut self) -> &mut V {
1367 // - `self.node_links` is a valid pointer to a node in the tree.
1368 // - We have exclusive access to the underlying tree, and can thus give out a mutable reference.
1372 /// Converts the entry into a mutable reference to its value.
1375 pub fn into_mut(self) -> &'a mut V {
1377 // - `self.node_links` is a valid pointer to a node in the tree.
1378 // - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that lives for `'a`.
1383 pub fn remove_node(self) -> RBTreeNode<K, V> {
1397 pub fn remove(self) -> V {
1407 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> {
1421 // - `self.node_ptr` produces a valid pointer to a node in the tree.
1422 // - Now that we removed this entry from the tree, we can convert the node to a box.