Lines Matching refs:V
171 pub struct RBTree<K, V> {
173 _p: PhantomData<Node<K, V>>,
177 // fields, so we use the same Send condition as would be used for a struct with K and V fields.
178 unsafe impl<K: Send, V: Send> Send for RBTree<K, V> {}
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> {}
184 impl<K, V> RBTree<K, V> {
195 pub fn iter(&self) -> Iter<'_, K, V> {
210 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
230 pub fn values(&self) -> impl Iterator<Item = &'_ V> {
235 pub fn values_mut(&mut self) -> impl Iterator<Item = &'_ mut V> {
240 pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> {
255 pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> {
270 impl<K, V> RBTree<K, V>
283 value: V,
285 ) -> Result<Option<RBTreeNode<K, V>>> {
295 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
305 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> {
306 let raw_self: *mut RBTree<K, V> = self;
331 // SAFETY: All links fields we create are in a `Node<K, V>`.
332 let node = unsafe { container_of!(curr, Node<K, V>, links) };
359 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
367 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {
375 pub fn get(&self, key: &K) -> Option<&V> {
379 // point to the links field of `Node<K, V>` objects.
380 let this = unsafe { container_of!(node, Node<K, V>, links) };
395 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
402 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {
409 pub fn remove(&mut self, key: &K) -> Option<V> {
418 pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>>
423 let mut best_match: Option<NonNull<Node<K, V>>> = None;
426 // point to the links field of `Node<K, V>` objects.
427 let this = unsafe { container_of!(node, Node<K, V>, links) }.cast_mut();
475 impl<K, V> Default for RBTree<K, V> {
481 impl<K, V> Drop for RBTree<K, V> {
488 // SAFETY: All links fields we create are in a `Node<K, V>`.
489 let this = unsafe { container_of!(next, Node<K, V>, links) };
723 pub struct Cursor<'a, K, V> {
724 tree: &'a mut RBTree<K, V>,
728 // SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it is sufficient to require them to be `Send`.
731 unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {}
733 // SAFETY: The [`Cursor`] gives out immutable references to K and mutable references to V,
735 unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
737 impl<'a, K, V> Cursor<'a, K, V> {
739 pub fn current(&self) -> (&K, &V) {
747 pub fn current_mut(&mut self) -> (&K, &mut V) {
759 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) {
763 // point to the links field of `Node<K, V>` objects.
764 let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }.cast_mut();
792 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> {
797 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> {
801 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> {
808 // point to the links field of `Node<K, V>` objects.
809 let this = unsafe { container_of!(neighbor, Node<K, V>, links) }.cast_mut();
837 pub fn peek_prev(&self) -> Option<(&K, &V)> {
842 pub fn peek_next(&self) -> Option<(&K, &V)> {
846 fn peek(&self, direction: Direction) -> Option<(&K, &V)> {
856 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> {
861 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> {
865 fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> {
890 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
901 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) {
912 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) {
914 // point to the links field of `Node<K, V>` objects.
915 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) }.cast_mut();
934 impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
935 type Item = (&'a K, &'a V);
936 type IntoIter = Iter<'a, K, V>;
946 pub struct Iter<'a, K, V> {
947 _tree: PhantomData<&'a RBTree<K, V>>,
948 iter_raw: IterRaw<K, V>,
951 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
953 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
955 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
957 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
959 impl<'a, K, V> Iterator for Iter<'a, K, V> {
960 type Item = (&'a K, &'a V);
968 impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
969 type Item = (&'a K, &'a mut V);
970 type IntoIter = IterMut<'a, K, V>;
980 pub struct IterMut<'a, K, V> {
981 _tree: PhantomData<&'a mut RBTree<K, V>>,
982 iter_raw: IterRaw<K, V>,
985 // SAFETY: The [`IterMut`] has exclusive access to both `K` and `V`, so it is sufficient to require them to be `Send`.
988 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
990 // SAFETY: The [`IterMut`] gives out immutable references to K and mutable references to V, so it has the same
992 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
994 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
995 type Item = (&'a K, &'a mut V);
1009 struct IterRaw<K, V> {
1011 _phantom: PhantomData<fn() -> (K, V)>,
1014 impl<K, V> Iterator for IterRaw<K, V> {
1015 type Item = (*mut K, *mut V);
1023 // and by the type invariant of `RBTree`, all nodes point to the links field of `Node<K, V>` objects.
1024 let cur = unsafe { container_of!(self.next, Node<K, V>, links) }.cast_mut();
1039 pub struct RBTreeNodeReservation<K, V> {
1040 node: KBox<MaybeUninit<Node<K, V>>>,
1043 impl<K, V> RBTreeNodeReservation<K, V> {
1046 pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> {
1053 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation. Those can always
1055 unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
1057 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation.
1058 unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
1060 impl<K, V> RBTreeNodeReservation<K, V> {
1064 pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> {
1081 pub struct RBTreeNode<K, V> {
1082 node: KBox<Node<K, V>>,
1085 impl<K, V> RBTreeNode<K, V> {
1088 pub fn new(key: K, value: V, flags: Flags) -> Result<RBTreeNode<K, V>> {
1093 pub fn to_key_value(self) -> (K, V) {
1100 // SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
1102 unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
1104 // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
1106 unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
1108 impl<K, V> RBTreeNode<K, V> {
1116 pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {
1128 pub enum Entry<'a, K, V> {
1130 Vacant(VacantEntry<'a, K, V>),
1132 Occupied(OccupiedEntry<'a, K, V>),
1136 enum RawEntry<'a, K, V> {
1137 Vacant(RawVacantEntry<'a, K, V>),
1138 Occupied(OccupiedEntry<'a, K, V>),
1142 pub struct VacantEntry<'a, K, V> {
1144 raw: RawVacantEntry<'a, K, V>,
1153 struct RawVacantEntry<'a, K, V> {
1154 rbtree: *mut RBTree<K, V>,
1160 _phantom: PhantomData<&'a mut RBTree<K, V>>,
1163 impl<'a, K, V> RawVacantEntry<'a, K, V> {
1168 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
1188 impl<'a, K, V> VacantEntry<'a, K, V> {
1190 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {
1199 pub struct OccupiedEntry<'a, K, V> {
1200 rbtree: &'a mut RBTree<K, V>,
1205 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1207 pub fn get(&self) -> &V {
1211 unsafe { &(*container_of!(self.node_links, Node<K, V>, links)).value }
1215 pub fn get_mut(&mut self) -> &mut V {
1219 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value }
1225 pub fn into_mut(self) -> &'a mut V {
1228 // - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that lives for `'a`.
1229 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value }
1233 pub fn remove_node(self) -> RBTreeNode<K, V> {
1243 KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut())
1249 pub fn remove(self) -> V {
1259 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> {
1276 unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) };
1282 struct Node<K, V> {
1285 value: V,