Lines Matching full:k
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> {
201 pub fn iter(&self) -> Iter<'_, K, V> { in iter() argument
216 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { in iter_mut() argument
231 pub fn keys(&self) -> impl Iterator<Item = &'_ K> { in keys()
232 self.iter().map(|(k, _)| k) in keys()
246 pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_front() argument
261 pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> { in cursor_back() argument
276 impl<K, V> RBTree<K, V>
278 K: Ord,
288 key: K, in try_create_and_insert() argument
291 ) -> Result<Option<RBTreeNode<K, V>>> { in try_create_and_insert() argument
301 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> { in insert() argument
311 fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> { in raw_entry() argument
312 let raw_self: *mut RBTree<K, V> = self; in raw_entry()
337 // SAFETY: All links fields we create are in a `Node<K, V>`. in raw_entry()
338 let node = unsafe { container_of!(curr, Node<K, V>, links) }; in raw_entry()
365 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { in entry() argument
373 pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> { in find_mut() argument
381 pub fn get(&self, key: &K) -> Option<&V> { in get()
385 // point to the links field of `Node<K, V>` objects. in get()
386 let this = unsafe { container_of!(node, Node<K, V>, links) }; in get()
401 pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { in get_mut()
408 pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> { in remove_node() argument
415 pub fn remove(&mut self, key: &K) -> Option<V> { in remove()
424 pub fn cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>> in cursor_lower_bound() argument
426 K: Ord, in cursor_lower_bound()
429 let mut best_match: Option<NonNull<Node<K, V>>> = None; in cursor_lower_bound()
432 // point to the links field of `Node<K, V>` objects. in cursor_lower_bound()
433 let this = unsafe { container_of!(node, Node<K, V>, links) }; in cursor_lower_bound()
481 impl<K, V> Default for RBTree<K, V> {
487 impl<K, V> Drop for RBTree<K, V> {
494 // SAFETY: All links fields we create are in a `Node<K, V>`. in drop()
495 let this = unsafe { container_of!(next, Node<K, V>, links) }; in drop()
634 /// let (k, v) = cursor.current_mut();
729 pub struct Cursor<'a, K, V> {
730 tree: &'a mut RBTree<K, V>,
734 // SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it is sufficient to require …
737 unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {}
739 // SAFETY: The [`Cursor`] gives out immutable references to K and mutable references to V,
741 unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
743 impl<'a, K, V> Cursor<'a, K, V> {
745 pub fn current(&self) -> (&K, &V) { in current() argument
753 pub fn current_mut(&mut self) -> (&K, &mut V) { in current_mut() argument
765 pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) { in remove_current() argument
769 // point to the links field of `Node<K, V>` objects. in remove_current()
770 let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }; in remove_current()
789 pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> { in remove_prev() argument
794 pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> { in remove_next() argument
798 fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> { in remove_neighbor() argument
805 // point to the links field of `Node<K, V>` objects. in remove_neighbor()
806 let this = unsafe { container_of!(neighbor, Node<K, V>, links) }; in remove_neighbor()
834 pub fn peek_prev(&self) -> Option<(&K, &V)> { in peek_prev() argument
839 pub fn peek_next(&self) -> Option<(&K, &V)> { in peek_next() argument
843 fn peek(&self, direction: Direction) -> Option<(&K, &V)> { in peek() argument
853 pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { in peek_prev_mut() argument
858 pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { in peek_next_mut() argument
862 fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> { in peek_mut() argument
887 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) { in to_key_value() argument
889 let (k, v) = unsafe { Self::to_key_value_raw(node) }; in to_key_value()
891 (k, unsafe { &*v }) in to_key_value()
898 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) { in to_key_value_mut() argument
900 let (k, v) = unsafe { Self::to_key_value_raw(node) }; in to_key_value_mut()
902 (k, unsafe { &mut *v }) in to_key_value_mut()
909 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) { in to_key_value_raw() argument
911 // point to the links field of `Node<K, V>` objects. in to_key_value_raw()
912 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) }; in to_key_value_raw()
915 let k = unsafe { &(*this).key }; in to_key_value_raw() localVariable
919 (k, v) in to_key_value_raw()
931 impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
932 type Item = (&'a K, &'a V);
933 type IntoIter = Iter<'a, K, V>;
943 pub struct Iter<'a, K, V> {
944 _tree: PhantomData<&'a RBTree<K, V>>,
945 iter_raw: IterRaw<K, V>,
948 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
950 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
952 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it has the same
954 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
956 impl<'a, K, V> Iterator for Iter<'a, K, V> {
957 type Item = (&'a K, &'a V);
960 // SAFETY: Due to `self._tree`, `k` and `v` are valid for the lifetime of `'a`. in next()
961 self.iter_raw.next().map(|(k, v)| unsafe { (&*k, &*v) }) in next()
965 impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
966 type Item = (&'a K, &'a mut V);
967 type IntoIter = IterMut<'a, K, V>;
977 pub struct IterMut<'a, K, V> {
978 _tree: PhantomData<&'a mut RBTree<K, V>>,
979 iter_raw: IterRaw<K, V>,
982 // SAFETY: The [`IterMut`] has exclusive access to both `K` and `V`, so it is sufficient to require…
985 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
987 // SAFETY: The [`IterMut`] gives out immutable references to K and mutable references to V, so it h…
989 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
991 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
992 type Item = (&'a K, &'a mut V);
995 self.iter_raw.next().map(|(k, v)| in next()
996 … // SAFETY: Due to `&mut self`, we have exclusive access to `k` and `v`, for the lifetime of `'a`. in next()
997 unsafe { (&*k, &mut *v) }) in next()
1006 struct IterRaw<K, V> {
1008 _phantom: PhantomData<fn() -> (K, V)>,
1011 impl<K, V> Iterator for IterRaw<K, V> {
1012 type Item = (*mut K, *mut V);
1020 …// and by the type invariant of `RBTree`, all nodes point to the links field of `Node<K, V>` objec… in next()
1021 let cur = unsafe { container_of!(self.next, Node<K, V>, links) }; in next()
1036 pub struct RBTreeNodeReservation<K, V> {
1037 node: KBox<MaybeUninit<Node<K, V>>>,
1040 impl<K, V> RBTreeNodeReservation<K, V> {
1043 pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> { in new() argument
1050 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation. Those can always
1052 unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
1054 // SAFETY: This doesn't actually contain K or V, and is just a memory allocation.
1055 unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
1057 impl<K, V> RBTreeNodeReservation<K, V> {
1061 pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> { in into_node() argument
1078 pub struct RBTreeNode<K, V> {
1079 node: KBox<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
1097 // SAFETY: If K and V can be sent across threads, then it's also okay to send [`RBTreeNode`] across
1099 unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
1101 // SAFETY: If K and V can be accessed without synchronization, then it's also okay to access
1103 unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
1105 impl<K, V> RBTreeNode<K, V> {
1113 pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> { in into_reservation() argument
1125 pub enum Entry<'a, K, V> {
1127 Vacant(VacantEntry<'a, K, V>),
1129 Occupied(OccupiedEntry<'a, K, V>),
1133 enum RawEntry<'a, K, V> {
1134 Vacant(RawVacantEntry<'a, K, V>),
1135 Occupied(OccupiedEntry<'a, K, V>),
1139 pub struct VacantEntry<'a, K, V> {
1140 key: K,
1141 raw: RawVacantEntry<'a, K, V>,
1150 struct RawVacantEntry<'a, K, V> {
1151 rbtree: *mut RBTree<K, V>,
1157 _phantom: PhantomData<&'a mut RBTree<K, V>>,
1160 impl<'a, K, V> RawVacantEntry<'a, K, V> {
1165 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V { in insert() argument
1185 impl<'a, K, V> VacantEntry<'a, K, V> {
1187 pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V { in insert() argument
1196 pub struct OccupiedEntry<'a, K, V> {
1197 rbtree: &'a mut RBTree<K, V>,
1202 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1208 unsafe { &(*container_of!(self.node_links, Node<K, V>, links)).value } in get()
1216 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links))).value } in get_mut()
1225 …// - This consumes the `&'a mut RBTree<K, V>`, therefore it can give out a mutable reference that … in into_mut()
1226 unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links))).value } in into_mut()
1230 pub fn remove_node(self) -> RBTreeNode<K, V> { in remove_node() argument
1239 node: unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links)) }, in remove_node()
1254 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { in replace() argument
1270 let old_node = unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links)) }; in replace()
1276 struct Node<K, V> {
1278 key: K,