Lines Matching +full:non +full:- +full:safety
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.
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
176 // SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
180 // SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
186 pub fn new() -> Self { in new()
195 pub fn iter(&self) -> Iter<'_, K, V> { in iter()
199 // - `self.root` is a valid pointer to a tree root. in iter()
200 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid. in iter()
202 // SAFETY: by the invariants, all pointers are valid. in iter()
210 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { in iter_mut()
214 // - `self.root` is a valid pointer to a tree root. in iter_mut()
215 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid. in iter_mut()
217 // SAFETY: by the invariants, all pointers are valid. in iter_mut()
225 pub fn keys(&self) -> impl Iterator<Item = &'_ K> { in keys()
230 pub fn values(&self) -> impl Iterator<Item = &'_ V> { in values()
235 pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> { in values_mut()
240 pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_front()
242 // SAFETY: `self.root` is always a valid root node in cursor_front()
246 // - `current` is a valid node in the [`RBTree`] pointed to by `self`. in cursor_front()
255 pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_back()
257 // SAFETY: `self.root` is always a valid root node in cursor_back()
261 // - `current` is a valid node in the [`RBTree`] pointed to by `self`. in cursor_back()
285 ) -> Result<Option<RBTreeNode<K, V>>> { in try_create_and_insert()
295 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> { in insert()
305 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> { in raw_entry()
309 // - `node`: A pointer to an uninitialized node being inserted. in raw_entry()
310 // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be in raw_entry()
313 // - `rb_link`: A pointer to either the left-child or right-child field of `parent`. This in raw_entry()
327 // SAFETY: `raw_self` is a valid pointer to the `RBTree` (created from `self` above). in raw_entry()
331 // SAFETY: All links fields we create are in a `Node<K, V>`. in raw_entry()
334 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in raw_entry()
336 // SAFETY: `curr` is a non-null node so it is valid by the type invariants. in raw_entry()
338 // SAFETY: `curr` is a non-null node so it is valid by the type invariants. in raw_entry()
358 /// Gets the given key's corresponding entry in the map for in-place manipulation.
359 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { in entry()
367 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> { in find_mut()
375 pub fn get(&self, key: &K) -> Option<&V> { in get()
378 … // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self` in get()
381 // SAFETY: `this` is a non-null node so it is valid by the type invariants. in get()
383 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in get()
385 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in get()
387 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in get()
395 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { in get_mut()
402 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> { in remove_node()
409 pub fn remove(&mut self, key: &K) -> Option<V> { in remove()
418 pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>> in cursor_lower_bound()
425 … // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self` in cursor_lower_bound()
428 // SAFETY: `this` is a non-null node so it is valid by the type invariants. in cursor_lower_bound()
430 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in cursor_lower_bound()
432 // SAFETY: `node` is a non-null node so it is valid by the type invariants. in cursor_lower_bound()
446 … // SAFETY: `best` is a non-null node so it is valid by the type invariants. in cursor_lower_bound()
461 // SAFETY: `best` is a non-null node so it is valid by the type invariants. in cursor_lower_bound()
466 // - `current` is a valid node in the [`RBTree`] pointed to by `self`. in cursor_lower_bound()
476 fn default() -> Self { in default()
483 // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`. in drop()
488 // SAFETY: All links fields we create are in a `Node<K, V>`. in drop()
492 // SAFETY: `next` and all nodes in postorder are still valid. in drop()
495 // INVARIANT: This is the destructor, so we break the type invariant during clean-up, in drop()
498 // SAFETY: `this` is valid per the loop invariant. in drop()
722 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
728 // SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it is sufficient to require …
733 // SAFETY: The [`Cursor`] gives out immutable references to K and mutable references to V,
734 // so it has the same thread safety requirements as mutable references.
739 pub fn current(&self) -> (&K, &V) { in current()
740 // SAFETY: in current()
741 // - `self.current` is a valid node by the type invariants. in current()
742 // - We have an immutable reference by the function signature. in current()
747 pub fn current_mut(&mut self) -> (&K, &mut V) { in current_mut()
748 // SAFETY: in current_mut()
749 // - `self.current` is a valid node by the type invariants. in current_mut()
750 // - We have an mutable reference by the function signature. in current_mut()
759 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) { in remove_current()
762 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self` in remove_current()
765 // SAFETY: `this` is valid by the type invariants as described above. in remove_current()
768 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_current()
782 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`. in remove_current()
792 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> { in remove_prev()
797 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> { in remove_next()
801 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> { in remove_neighbor()
804 // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so in remove_neighbor()
807 … // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self` in remove_neighbor()
810 // SAFETY: `this` is valid by the type invariants as described above. in remove_neighbor()
818 pub fn move_prev(self) -> Option<Self> { in move_prev()
823 pub fn move_next(self) -> Option<Self> { in move_next()
827 fn mv(self, direction: Direction) -> Option<Self> { in mv()
829 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`. in mv()
837 pub fn peek_prev(&self) -> Option<(&K, &V)> { in peek_prev()
842 pub fn peek_next(&self) -> Option<(&K, &V)> { in peek_next()
846 fn peek(&self, direction: Direction) -> Option<(&K, &V)> { in peek()
848 // SAFETY: in peek()
849 // - `neighbor` is a valid tree node. in peek()
850 // - By the function signature, we have an immutable reference to `self`. in peek()
856 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { in peek_prev_mut()
861 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { in peek_next_mut()
865 fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> { in peek_mut()
867 // SAFETY: in peek_mut()
868 // - `neighbor` is a valid tree node. in peek_mut()
869 // - By the function signature, we have a mutable reference to `self`. in peek_mut()
874 fn get_neighbor_raw(&self, direction: Direction) -> Option<NonNull<bindings::rb_node>> { in get_neighbor_raw()
875 // SAFETY: `self.current` is valid by the type invariants. in get_neighbor_raw()
886 /// # Safety
888 /// - `node` must be a valid pointer to a node in an [`RBTree`].
889 /// - The caller has immutable access to `node` for the duration of 'b.
890 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) { in to_key_value()
891 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`. in to_key_value()
893 // SAFETY: the caller guarantees immutable access to `node`. in to_key_value()
897 /// # Safety
899 /// - `node` must be a valid pointer to a node in an [`RBTree`].
900 /// - The caller has mutable access to `node` for the duration of 'b.
901 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) { in to_key_value_mut()
902 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`. in to_key_value_mut()
904 // SAFETY: the caller guarantees mutable access to `node`. in to_key_value_mut()
908 /// # Safety
910 /// - `node` must be a valid pointer to a node in an [`RBTree`].
911 /// - The caller has immutable access to the key for the duration of 'b.
912 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) { in to_key_value_raw()
913 // SAFETY: By the type invariant of `Self`, all non-null `rb_node` pointers stored in `self` in to_key_value_raw()
916 // SAFETY: The passed `node` is the current node or a non-null neighbor, in to_key_value_raw()
919 // SAFETY: The passed `node` is the current node or a non-null neighbor, in to_key_value_raw()
938 fn into_iter(self) -> Self::IntoIter { in into_iter()
951 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
952 // thread safety requirements as immutable references.
955 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
956 // thread safety requirements as immutable references.
962 fn next(&mut self) -> Option<Self::Item> { in next()
963 // SAFETY: Due to `self._tree`, `k` and `v` are valid for the lifetime of `'a`. in next()
972 fn into_iter(self) -> Self::IntoIter { in into_iter()
985 // SAFETY: The [`IterMut`] has exclusive access to both `K` and `V`, so it is sufficient to require…
990 // SAFETY: The [`IterMut`] gives out immutable references to K and mutable references to V, so it h…
991 // thread safety requirements as mutable references.
997 fn next(&mut self) -> Option<Self::Item> { in next()
999 … // SAFETY: Due to `&mut self`, we have exclusive access to `k` and `v`, for the lifetime of `'a`. in next()
1007 /// - `self.next` is a valid pointer.
1008 /// - `self.next` points to a node stored inside of a valid `RBTree`.
1011 _phantom: PhantomData<fn() -> (K, V)>,
1017 fn next(&mut self) -> Option<Self::Item> { in next()
1022 // SAFETY: By the type invariant of `IterRaw`, `self.next` is a valid node in an `RBTree`, in next()
1026 // SAFETY: `self.next` is a valid tree node by the type invariants. in next()
1029 // SAFETY: By the same reasoning above, it is safe to dereference the node. 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
1046 pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> { in new()
1053 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation. Those can always
1057 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation.
1064 pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> { in into_node()
1077 /// A red-black tree node.
1088 pub fn new(key: K, value: V, flags: Flags) -> Result<RBTreeNode<K, V>> { in new()
1093 pub fn to_key_value(self) -> (K, V) { in to_key_value()
1100 // SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
1104 // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
1111 /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
1114 /// The existing key and value are dropped in-place as part of this operation, that is, memory
1116 pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> { in into_reservation()
1150 /// - `parent` may be null if the new node becomes the root.
1151 /// - `child_field_of_parent` is a valid pointer to the left-child or right-child of `parent`. If `…
1157 /// This points to the left-child or right-child field of `parent`, or `root` if `parent` is
1168 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V { in insert()
1171 // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when in insert()
1177 …// SAFETY: The type invariants of `RawVacantEntry` are exactly the safety requirements of `rb_link… in insert()
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()
1190 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V { in insert()
1198 /// - `node_links` is a valid, non-null pointer to a tree node in `self.rbtree`
1207 pub fn get(&self) -> &V { in get()
1208 // SAFETY: in get()
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()
1215 pub fn get_mut(&mut self) -> &mut V { in get_mut()
1216 // SAFETY: in get_mut()
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()
1225 pub fn into_mut(self) -> &'a mut V { in into_mut()
1226 // SAFETY: in into_mut()
1227 // - `self.node_links` is a valid pointer to a node in the tree. in into_mut()
1228 …// - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that … in into_mut()
1233 pub fn remove_node(self) -> RBTreeNode<K, V> { in remove_node()
1234 // SAFETY: The node is a node in the tree, so it is valid. 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()
1249 pub fn remove(self) -> V { in remove()
1259 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { in replace()
1262 // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when in replace()
1266 // SAFETY: This updates the pointers so that `new_node_links` is in the tree where in replace()
1272 // SAFETY: 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()