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> {
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()
246     pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K, V>> {  in cursor_front_mut()  argument
261     pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {  in cursor_front()  argument
276     pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>> {  in cursor_back_mut()  argument
291     pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {  in cursor_back()  argument
306 impl<K, V> RBTree<K, V>
308     K: Ord,
318         key: K,  in try_create_and_insert()  argument
321     ) -> Result<Option<RBTreeNode<K, V>>> {  in try_create_and_insert()  argument
331     pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {  in insert()  argument
341     fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> {  in raw_entry()  argument
342         let raw_self: *mut RBTree<K, V> = self;  in raw_entry()
368             let node = unsafe { container_of!(curr, Node<K, V>, links) };  in raw_entry()
395     pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {  in entry()  argument
403     pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {  in find_mut()  argument
411     pub fn get(&self, key: &K) -> Option<&V> {  in get()
416             let this = unsafe { container_of!(node, Node<K, V>, links) };  in get()
431     pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {  in get_mut()
438     pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> {  in remove_node()  argument
445     pub fn remove(&mut self, key: &K) -> Option<V> {  in remove()
454     pub fn cursor_lower_bound_mut(&mut self, key: &K) -> Option<CursorMut<'_, K, V>>  in cursor_lower_bound_mut()  argument
456         K: Ord,  in cursor_lower_bound_mut()
475     pub fn cursor_lower_bound(&self, key: &K) -> Option<Cursor<'_, K, V>>  in cursor_lower_bound()  argument
477         K: Ord,  in cursor_lower_bound()
491     fn find_best_match(&self, key: &K) -> Option<NonNull<bindings::rb_node>> {  in find_best_match()
493         let mut best_key: Option<&K> = None;  in find_best_match()
498             let this = unsafe { container_of!(node, Node<K, V>, links) };  in find_best_match()
532 impl<K, V> Default for RBTree<K, V> {
538 impl<K, V> Drop for RBTree<K, V> {
546             let this = unsafe { container_of!(next, Node<K, V>, links) };  in drop()
780 pub struct CursorMut<'a, K, V> {
781     tree: &'a mut RBTree<K, V>,
811 pub struct Cursor<'a, K, V> {
812     _tree: PhantomData<&'a RBTree<K, V>>,
818 unsafe impl<'a, K: Sync, V: Sync> Send for Cursor<'a, K, V> {}
822 unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {}
824 impl<'a, K, V> Cursor<'a, K, V> {
826     pub fn current(&self) -> (&K, &V) {  in current()  argument
837     unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {  in to_key_value()  argument
840         let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) };  in to_key_value()
851     pub fn peek_prev(&self) -> Option<(&K, &V)> {  in peek_prev()  argument
856     pub fn peek_next(&self) -> Option<(&K, &V)> {  in peek_next()  argument
860     fn peek(&self, direction: Direction) -> Option<(&K, &V)> {  in peek()  argument
887 unsafe impl<'a, K: Send, V: Send> Send for CursorMut<'a, K, V> {}
891 unsafe impl<'a, K: Sync, V: Sync> Sync for CursorMut<'a, K, V> {}
893 impl<'a, K, V> CursorMut<'a, K, V> {
895     pub fn current(&self) -> (&K, &V) {  in current()  argument
903     pub fn current_mut(&mut self) -> (&K, &mut V) {  in current_mut()  argument
915     pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>) {  in remove_current()  argument
920         let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) };  in remove_current()
939     pub fn remove_prev(&mut self) -> Option<RBTreeNode<K, V>> {  in remove_prev()  argument
944     pub fn remove_next(&mut self) -> Option<RBTreeNode<K, V>> {  in remove_next()  argument
948     fn remove_neighbor(&mut self, direction: Direction) -> Option<RBTreeNode<K, V>> {  in remove_neighbor()  argument
956             let this = unsafe { container_of!(neighbor, Node<K, V>, links) };  in remove_neighbor()
984     pub fn peek_prev(&self) -> Option<(&K, &V)> {  in peek_prev()  argument
989     pub fn peek_next(&self) -> Option<(&K, &V)> {  in peek_next()  argument
993     fn peek(&self, direction: Direction) -> Option<(&K, &V)> {  in peek()  argument
1003     pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> {  in peek_prev_mut()  argument
1008     pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> {  in peek_next_mut()  argument
1012     fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> {  in peek_mut()  argument
1037     unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {  in to_key_value()  argument
1048     unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) {  in to_key_value_mut()  argument
1059     unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) {  in to_key_value_raw()  argument
1062         let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) };  in to_key_value_raw()
1081 impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
1082     type Item = (&'a K, &'a V);
1083     type IntoIter = Iter<'a, K, V>;
1093 pub struct Iter<'a, K, V> {
1094     _tree: PhantomData<&'a RBTree<K, V>>,
1095     iter_raw: IterRaw<K, V>,
1100 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
1104 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
1106 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1107     type Item = (&'a K, &'a V);
1115 impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V> {
1116     type Item = (&'a K, &'a mut V);
1117     type IntoIter = IterMut<'a, K, V>;
1127 pub struct IterMut<'a, K, V> {
1128     _tree: PhantomData<&'a mut RBTree<K, V>>,
1129     iter_raw: IterRaw<K, V>,
1135 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
1139 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
1141 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1142     type Item = (&'a K, &'a mut V);
1156 struct IterRaw<K, V> {
1158     _phantom: PhantomData<fn() -> (K, V)>,
1161 impl<K, V> Iterator for IterRaw<K, V> {
1162     type Item = (*mut K, *mut V);
1171         let cur = unsafe { container_of!(self.next, Node<K, V>, links) };  in next()
1186 pub struct RBTreeNodeReservation<K, V> {
1187     node: KBox<MaybeUninit<Node<K, V>>>,
1190 impl<K, V> RBTreeNodeReservation<K, V> {
1193     pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> {  in new()  argument
1202 unsafe impl<K, V> Send for RBTreeNodeReservation<K, V> {}
1205 unsafe impl<K, V> Sync for RBTreeNodeReservation<K, V> {}
1207 impl<K, V> RBTreeNodeReservation<K, V> {
1211     pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> {  in into_node()  argument
1228 pub struct RBTreeNode<K, V> {
1229     node: KBox<Node<K, V>>,
1232 impl<K, V> RBTreeNode<K, V> {
1235     pub fn new(key: K, value: V, flags: Flags) -> Result<RBTreeNode<K, V>> {  in new()  argument
1240     pub fn to_key_value(self) -> (K, V) {  in to_key_value()  argument
1249 unsafe impl<K: Send, V: Send> Send for RBTreeNode<K, V> {}
1253 unsafe impl<K: Sync, V: Sync> Sync for RBTreeNode<K, V> {}
1255 impl<K, V> RBTreeNode<K, V> {
1263     pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> {  in into_reservation()  argument
1275 pub enum Entry<'a, K, V> {
1277     Vacant(VacantEntry<'a, K, V>),
1279     Occupied(OccupiedEntry<'a, K, V>),
1283 enum RawEntry<'a, K, V> {
1284     Vacant(RawVacantEntry<'a, K, V>),
1285     Occupied(OccupiedEntry<'a, K, V>),
1289 pub struct VacantEntry<'a, K, V> {
1290     key: K,
1291     raw: RawVacantEntry<'a, K, V>,
1300 struct RawVacantEntry<'a, K, V> {
1301     rbtree: *mut RBTree<K, V>,
1307     _phantom: PhantomData<&'a mut RBTree<K, V>>,
1310 impl<'a, K, V> RawVacantEntry<'a, K, V> {
1315     fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {  in insert()  argument
1335 impl<'a, K, V> VacantEntry<'a, K, V> {
1337     pub fn insert(self, value: V, reservation: RBTreeNodeReservation<K, V>) -> &'a mut V {  in insert()  argument
1346 pub struct OccupiedEntry<'a, K, V> {
1347     rbtree: &'a mut RBTree<K, V>,
1352 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1358         unsafe { &(*container_of!(self.node_links, Node<K, V>, links)).value }  in get()
1366         unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links))).value }  in get_mut()
1376         unsafe { &mut (*(container_of!(self.node_links, Node<K, V>, links))).value }  in into_mut()
1380     pub fn remove_node(self) -> RBTreeNode<K, V> {  in remove_node()  argument
1389             node: unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links)) },  in remove_node()
1404     fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> {  in replace()  argument
1420         let old_node = unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links)) };  in replace()
1426 struct Node<K, V> {
1428     key: K,