Lines Matching +full:10 +full:k
35 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
40 /// assert_eq!(tree.get(&10).unwrap(), &100);
48 /// assert_eq!(iter.next().unwrap(), (&10, &100));
60 /// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?;
65 /// assert_eq!(iter.next().unwrap(), (&10, &1000));
77 /// assert_eq!(iter.next().unwrap(), (&10, &1000));
84 /// tree.remove(&10);
106 /// let node = RBTreeNode::new(10, 100, flags::GFP_KERNEL)?;
126 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
132 /// assert_eq!(iter.next().unwrap(), (&10, &100));
144 /// assert_eq!(iter.next().unwrap(), (&10, &100));
159 /// assert_eq!(iter.next().unwrap(), (&10, &100));
172 pub struct RBTree<K, V> {
174 _p: PhantomData<Node<K, V>>,
178 // fields, so we use the same Send condition as would be used for a struct with K and V fields.
179 unsafe impl<K: Send, V: Send> Send for RBTree<K, V> {}
182 // fields, so we use the same Sync condition as would be used for a struct with K and V fields.
183 unsafe impl<K: Sync, V: Sync> Sync for RBTree<K, V> {}
185 impl<K, V> RBTree<K, V> {
196 pub fn iter(&self) -> Iter<'_, K, V> { in iter() argument
211 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { in iter_mut() argument
226 pub fn keys(&self) -> impl Iterator<Item = &'_ K> { in keys()
227 self.iter().map(|(k, _)| k) in keys()
241 pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_front() argument
256 pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_back() argument
271 impl<K, V> RBTree<K, V>
273 K: Ord,
283 key: K, in try_create_and_insert() argument
286 ) -> Result<Option<RBTreeNode<K, V>>> { in try_create_and_insert() argument
296 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> { in insert() argument
306 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> { in raw_entry() argument
307 let raw_self: *mut RBTree<K, V> = self; in raw_entry()
332 // SAFETY: All links fields we create are in a `Node<K, V>`. in raw_entry()
333 let node = unsafe { container_of!(curr, Node<K, V>, links) }; in raw_entry()
360 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { in entry() argument
368 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> { in find_mut() argument
376 pub fn get(&self, key: &K) -> Option<&V> { in get()
380 // point to the links field of `Node<K, V>` objects. in get()
381 let this = unsafe { container_of!(node, Node<K, V>, links) }; in get()
396 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { in get_mut()
403 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> { in remove_node() argument
410 pub fn remove(&mut self, key: &K) -> Option<V> { in remove()
419 pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>> in cursor_lower_bound() argument
421 K: Ord, in cursor_lower_bound()
424 let mut best_match: Option<NonNull<Node<K, V>>> = None; in cursor_lower_bound()
427 // point to the links field of `Node<K, V>` objects. in cursor_lower_bound()
428 let this = unsafe { container_of!(node, Node<K, V>, links) }.cast_mut(); in cursor_lower_bound()
476 impl<K, V> Default for RBTree<K, V> {
482 impl<K, V> Drop for RBTree<K, V> {
489 // SAFETY: All links fields we create are in a `Node<K, V>`. in drop()
490 let this = unsafe { container_of!(next, Node<K, V>, links) }; in drop()
519 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
526 /// assert_eq!(current, (&10, &100));
558 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
589 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
621 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
629 /// let (k, v) = cursor.current_mut();
633 /// let updated = tree.get(&10).unwrap();
648 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
655 /// assert_eq!(current, (&10, &100));
687 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
694 /// assert_eq!(current, (&10, &100));
713 /// assert_eq!(current, (&10, &100));
724 pub struct Cursor<'a, K, V> {
725 tree: &'a mut RBTree<K, V>,
729 // SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it is sufficient to require …
732 unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {}
734 // SAFETY: The [`Cursor`] gives out immutable references to K and mutable references to V,
736 unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
738 impl<'a, K, V> Cursor<'a, K, V> {
740 pub fn current(&self) -> (&K, &V) { in current() argument
748 pub fn current_mut(&mut self) -> (&K, &mut V) { in current_mut() argument
760 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) { in remove_current() argument
764 // point to the links field of `Node<K, V>` objects. in remove_current()
765 let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }.cast_mut(); in remove_current()
793 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> { in remove_prev() argument
798 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> { in remove_next() argument
802 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> { in remove_neighbor() argument
809 // point to the links field of `Node<K, V>` objects. in remove_neighbor()
810 let this = unsafe { container_of!(neighbor, Node<K, V>, links) }.cast_mut(); in remove_neighbor()
838 pub fn peek_prev(&self) -> Option<(&K, &V)> { in peek_prev() argument
843 pub fn peek_next(&self) -> Option<(&K, &V)> { in peek_next() argument
847 fn peek(&self, direction: Direction) -> Option<(&K, &V)> { in peek() argument
857 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { in peek_prev_mut() argument
862 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { in peek_next_mut() argument
866 fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> { in peek_mut() argument
890 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) { in to_key_value() argument
892 let (k, v) = unsafe { Self::to_key_value_raw(node) }; in to_key_value()
894 (k, unsafe { &*v }) in to_key_value()
900 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) { in to_key_value_mut() argument
902 let (k, v) = unsafe { Self::to_key_value_raw(node) }; in to_key_value_mut()
904 (k, unsafe { &mut *v }) in to_key_value_mut()
910 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) { in to_key_value_raw() argument
912 // point to the links field of `Node<K, V>` objects. in to_key_value_raw()
913 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) }.cast_mut(); in to_key_value_raw()
916 let k = unsafe { &(*this).key }; in to_key_value_raw() localVariable
920 (k, v) in to_key_value_raw()
932 impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
933 type Item = (&'a K, &'a V);
934 type IntoIter = Iter<'a, K, V>;
944 pub struct Iter<'a, K, V> {
945 _tree: PhantomData<&'a RBTree<K, V>>,
946 iter_raw: IterRaw<K, V>,
949 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
951 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
953 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
955 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
957 impl<'a, K, V> Iterator for Iter<'a, K, V> {
958 type Item = (&'a K, &'a V);
961 // SAFETY: Due to `self._tree`, `k` and `v` are valid for the lifetime of `'a`. in next()
962 self.iter_raw.next().map(|(k, v)| unsafe { (&*k, &*v) }) in next()
966 impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
967 type Item = (&'a K, &'a mut V);
968 type IntoIter = IterMut<'a, K, V>;
978 pub struct IterMut<'a, K, V> {
979 _tree: PhantomData<&'a mut RBTree<K, V>>,
980 iter_raw: IterRaw<K, V>,
983 // SAFETY: The [`IterMut`] has exclusive access to both `K` and `V`, so it is sufficient to require…
986 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
988 // SAFETY: The [`IterMut`] gives out immutable references to K and mutable references to V, so it h…
990 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
992 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
993 type Item = (&'a K, &'a mut V);
996 self.iter_raw.next().map(|(k, v)| in next()
997 … // SAFETY: Due to `&mut self`, we have exclusive access to `k` and `v`, for the lifetime of `'a`. in next()
998 unsafe { (&*k, &mut *v) }) in next()
1007 struct IterRaw<K, V> {
1009 _phantom: PhantomData<fn() -> (K, V)>,
1012 impl<K, V> Iterator for IterRaw<K, V> {
1013 type Item = (*mut K, *mut V);
1021 …// and by the type invariant of `RBTree`, all nodes point to the links field of `Node<K, V>` objec… in next()
1022 let cur = unsafe { container_of!(self.next, Node<K, V>, links) }.cast_mut(); in next()
1037 pub struct RBTreeNodeReservation<K, V> {
1038 node: Box<MaybeUninit<Node<K, V>>>,
1041 impl<K, V> RBTreeNodeReservation<K, V> {
1044 pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> { in new() argument
1051 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation. Those can always
1053 unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
1055 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation.
1056 unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
1058 impl<K, V> RBTreeNodeReservation<K, V> {
1062 pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> { in into_node() argument
1078 pub struct RBTreeNode<K, V> {
1079 node: Box<Node<K, V>>,
1082 impl<K, V> RBTreeNode<K, V> {
1085 pub fn new(key: K, value: V, flags: Flags) -> Result<RBTreeNode<K, V>> { in new() argument
1090 pub fn to_key_value(self) -> (K, V) { in to_key_value() argument
1095 // SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
1097 unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
1099 // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
1101 unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
1103 impl<K, V> RBTreeNode<K, V> {
1111 pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> { in into_reservation() argument
1123 pub enum Entry<'a, K, V> {
1125 Vacant(VacantEntry<'a, K, V>),
1127 Occupied(OccupiedEntry<'a, K, V>),
1131 enum RawEntry<'a, K, V> {
1132 Vacant(RawVacantEntry<'a, K, V>),
1133 Occupied(OccupiedEntry<'a, K, V>),
1137 pub struct VacantEntry<'a, K, V> {
1138 key: K,
1139 raw: RawVacantEntry<'a, K, V>,
1148 struct RawVacantEntry<'a, K, V> {
1149 rbtree: *mut RBTree<K, V>,
1155 _phantom: PhantomData<&'a mut RBTree<K, V>>,
1158 impl<'a, K, V> RawVacantEntry<'a, K, V> {
1163 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V { in insert() argument
1183 impl<'a, K, V> VacantEntry<'a, K, V> {
1185 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V { in insert() argument
1194 pub struct OccupiedEntry<'a, K, V> {
1195 rbtree: &'a mut RBTree<K, V>,
1200 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1206 unsafe { &(*container_of!(self.node_links, Node<K, V>, links)).value } in get()
1214 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value } in get_mut()
1223 …// - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that … in into_mut()
1224 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value } in into_mut()
1228 pub fn remove_node(self) -> RBTreeNode<K, V> { in remove_node() argument
1238 Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) in remove_node()
1251 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { in replace() argument
1268 unsafe { Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; in replace()
1274 struct Node<K, V> {
1276 key: K,