Lines Matching refs:V
171 pub struct RBTree<K, V> {
173 _p: PhantomData<Node<K, V>>,
178 unsafe impl<K: Send, V: Send> Send for RBTree<K, V> {}
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> { in iter() argument
210 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { in iter_mut() argument
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() argument
255 pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_back() argument
270 impl<K, V> RBTree<K, V>
283 value: V, in try_create_and_insert() argument
285 ) -> Result<Option<RBTreeNode<K, V>>> { in try_create_and_insert() argument
295 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> { in insert() argument
305 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> { in raw_entry() argument
306 let raw_self: *mut RBTree<K, V> = self; in raw_entry()
332 let node = unsafe { container_of!(curr, Node<K, V>, links) }; in raw_entry()
359 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { in entry() argument
367 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> { in find_mut() argument
375 pub fn get(&self, key: &K) -> Option<&V> { in get() argument
380 let this = unsafe { container_of!(node, Node<K, V>, links) }; in get()
395 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { in get_mut() argument
402 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> { in remove_node() argument
409 pub fn remove(&mut self, key: &K) -> Option<V> { in remove() argument
418 pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>> in cursor_lower_bound()
423 let mut best_match: Option<NonNull<Node<K, V>>> = None; in cursor_lower_bound()
427 let this = unsafe { container_of!(node, Node<K, V>, links) }.cast_mut(); in cursor_lower_bound()
475 impl<K, V> Default for RBTree<K, V> {
481 impl<K, V> Drop for RBTree<K, V> {
489 let this = unsafe { container_of!(next, Node<K, V>, links) }; in drop()
723 pub struct Cursor<'a, K, V> {
724 tree: &'a mut RBTree<K, V>,
731 unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, 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) { in current() argument
747 pub fn current_mut(&mut self) -> (&K, &mut V) { in current_mut() argument
759 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) { in remove_current() argument
764 let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }.cast_mut(); in remove_current()
792 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> { in remove_prev() argument
797 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> { in remove_next() argument
801 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> { in remove_neighbor() argument
809 let this = unsafe { container_of!(neighbor, Node<K, V>, links) }.cast_mut(); in remove_neighbor()
837 pub fn peek_prev(&self) -> Option<(&K, &V)> { in peek_prev() argument
842 pub fn peek_next(&self) -> Option<(&K, &V)> { in peek_next() argument
846 fn peek(&self, direction: Direction) -> Option<(&K, &V)> { in peek() argument
856 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { in peek_prev_mut() argument
861 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { in peek_next_mut() argument
865 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
901 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) { in to_key_value_mut() argument
912 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) { in to_key_value_raw() argument
915 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) }.cast_mut(); in to_key_value_raw()
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>,
953 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
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>,
988 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
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);
1024 let cur = unsafe { container_of!(self.next, Node<K, V>, links) }.cast_mut(); in next()
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>> { in new() argument
1055 unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
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> { in into_node() argument
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>> { in new() argument
1093 pub fn to_key_value(self) -> (K, V) { in to_key_value() argument
1102 unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
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> { in into_reservation() argument
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 { in insert() argument
1188 impl<'a, K, V> VacantEntry<'a, K, V> {
1190 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V { in insert() argument
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 { in get() argument
1211 unsafe { &(*container_of!(self.node_links, Node<K, V>, links)).value } in get()
1215 pub fn get_mut(&mut self) -> &mut V { in get_mut() argument
1219 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value } in get_mut()
1225 pub fn into_mut(self) -> &'a mut V { in into_mut() argument
1229 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links).cast_mut())).value } in into_mut()
1233 pub fn remove_node(self) -> RBTreeNode<K, V> { in remove_node() argument
1243 KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) in remove_node()
1249 pub fn remove(self) -> V { in remove() argument
1259 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { in replace() argument
1276 unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; in replace()
1282 struct Node<K, V> {
1285 value: V,