// SPDX-License-Identifier: GPL-2.0
//! Red-black trees.
//!
//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h)
//!
//! Reference: <https://docs.kernel.org/core-api/rbtree.html>
use crate::{alloc::Flags, bindings, container_of, error::Result, prelude::*};
use core::{
cmp::{Ord, Ordering},
marker::PhantomData,
mem::MaybeUninit,
ptr::{addr_of_mut, from_mut, NonNull},
};
/// A red-black tree with owned nodes.
///
/// It is backed by the kernel C red-black trees.
///
/// # Examples
///
/// In the example below we do several operations on a tree. We note that insertions may fail if
/// the system is out of memory.
///
/// ```
/// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode, RBTreeNodeReservation}};
///
/// // Create a new tree.
/// let mut tree = RBTree::new();
///
/// // Insert three elements.
/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
///
/// // Check the nodes we just inserted.
/// {
/// assert_eq!(tree.get(&10), Some(&100));
/// assert_eq!(tree.get(&20), Some(&200));
/// assert_eq!(tree.get(&30), Some(&300));
/// }
///
/// // Iterate over the nodes we just inserted.
/// {
/// let mut iter = tree.iter();
/// assert_eq!(iter.next(), Some((&10, &100)));
/// assert_eq!(iter.next(), Some((&20, &200)));
/// assert_eq!(iter.next(), Some((&30, &300)));
/// assert!(iter.next().is_none());
/// }
///
/// // Print all elements.
/// for (key, value) in &tree {
/// pr_info!("{} = {}\n", key, value);
/// }
///
/// // Replace one of the elements.
/// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?;
///
/// // Check that the tree reflects the replacement.
/// {
/// let mut iter = tree.iter();
/// assert_eq!(iter.next(), Some((&10, &1000)));
/// assert_eq!(iter.next(), Some((&20, &200)));
/// assert_eq!(iter.next(), Some((&30, &300)));
/// assert!(iter.next().is_none());
/// }
///
/// // Change the value of one of the elements.
/// *tree.get_mut(&30).unwrap() = 3000;
///
/// // Check that the tree reflects the update.
/// {
/// let mut iter = tree.iter();
/// assert_eq!(iter.next(), Some((&10, &1000)));
/// assert_eq!(iter.next(), Some((&20, &200)));
/// assert_eq!(iter.next(), Some((&30, &3000)));
/// assert!(iter.next().is_none());
/// }
///
/// // Remove an element.
/// tree.remove(&10);
///
/// // Check that the tree reflects the removal.
/// {
/// let mut iter = tree.iter();
/// assert_eq!(iter.next(), Some((&20, &200)));
/// assert_eq!(iter.next(), Some((&30, &3000)));
/// assert!(iter.next().is_none());
/// }
///
/// # Ok::<(), Error>(())
/// ```
///
/// In the example below, we first allocate a node, acquire a spinlock, then insert the node into
/// the tree. This is useful when the insertion context does not allow sleeping, for example, when
/// ho