use core::cmp::Ordering;
use core::marker::PhantomData;
use core::ptr;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Color {
Red,
Black,
}
#[repr(C)]
pub struct RbNode {
parent: *mut RbNode,
left: *mut RbNode,
right: *mut RbNode,
color: Color,
}
impl RbNode {
pub const fn new() -> Self {
Self {
parent: ptr::null_mut(),
left: ptr::null_mut(),
right: ptr::null_mut(),
color: Color::Red,
}
}
pub fn reset_links(&mut self) {
self.parent = ptr::null_mut();
self.left = ptr::null_mut();
self.right = ptr::null_mut();
self.color = Color::Red;
}
#[allow(dead_code)]
pub fn is_linked(&self) -> bool {
!self.parent.is_null() || !self.left.is_null() || !self.right.is_null()
}
}
impl Default for RbNode {
fn default() -> Self {
Self::new()
}
}
pub(crate) unsafe trait RBTreeNode: Sized {
fn node(entity: *mut Self) -> *mut RbNode;
fn entity_of(node: *mut RbNode) -> *mut Self;
fn entity_of_const(node: *const RbNode) -> *const Self;
unsafe fn cmp(a: *const Self, b: *const Self) -> Ordering;
}
pub(crate) struct RBTree<T: RBTreeNode> {
root: *mut RbNode,
len: usize,
_entity: PhantomData<T>,
}
impl<T: RBTreeNode> Default for RBTree<T> {
fn default() -> Self {
Self::new()
}
}
impl<T: RBTreeNode> RBTree<T> {
pub const fn new() -> Self {
Self {
root: ptr::null_mut(),
len: 0,
_entity: PhantomData,
}
}
#[allow(dead_code)]
pub fn is_empty(&self) -> bool {
self.root.is_null()
}
#[allow(dead_code)]
pub fn len(&self) -> usize {
self.len
}
#[allow(dead_code)]
pub fn root(&self) -> *mut T {
T::entity_of(self.root)
}
pub fn first(&self) -> *mut T {
T::entity_of(Self::minimum(self.root))
}
#[allow(dead_code)]
pub fn last(&self) -> *mut T {
T::entity_of(Self::maximum(self.root))
}
pub fn next(&self, entity: *mut T) -> *mut T {
if entity.is_null() {
return ptr::null_mut();
}
unsafe {
let mut node = T::node(entity);
if !(*node).right.is_null() {
return T::entity_of(Self::minimum((*node).right));
}
let mut parent = (*node).parent;
while !parent.is_null() && node == (*parent).right {
node = parent;
parent = (*parent).parent;
}
T::entity_of(parent)
}
}
pub unsafe fn upper_bound(&self, entity: *const T) -> *mut T {
let mut current = self.root;
let mut candidate = ptr::null_mut();
unsafe {
while !current.is_null() {
if T::cmp(entity, T::entity_of_const(current)) == Ordering::Less {
candidate = current;
current = (*current).left;
} else {
current = (*current).right;
}
}
}
T::entity_of(candidate)
}
pub fn contains(&self, entity: *const T) -> bool {
let mut current = self.first();
while !current.is_null() {
if ptr::eq(current.cast_const(), entity) {
return true;
}
current = self.next(current);
}
false
}
pub unsafe fn insert(&mut self, entity: *mut T) {
debug_assert!(!entity.is_null());
debug_assert!(
!self.contains(entity.cast_const()),
"entity is already linked into this tree"
);
unsafe {
let node = T::node(entity);
(*node).reset_links();
let mut parent = ptr::null_mut();
let mut current = self.root;
while !current.is_null() {
parent = current;
match Self::cmp_nodes(node, current) {
Ordering::Less => current = (*current).left,
Ordering::Greater => current = (*current).right,
Ordering::Equal => unreachable!("entity ordering must be strict"),
}
}
(*node).parent = parent;
if parent.is_null() {
self.root = node;
} else if Self::cmp_nodes(node, parent) == Ordering::Less {
(*parent).left = node;
} else {
(*parent).right = node;
}
self.insert_fixup(node);
self.len += 1;
}
}
pub unsafe fn remove(&mut self, entity: *mut T) -> *mut T {
if entity.is_null() {
return ptr::null_mut();
}
unsafe {
let node = T::node(entity);
let mut y = node;
let mut y_original_color = (*y).color;
let x;
let x_parent;
if (*node).left.is_null() {
x = (*node).right;
x_parent = (*node).parent;
self.transplant(node, (*node).right);
} else if (*node).right.is_null() {
x = (*node).left;
x_parent = (*node).parent;
self.transplant(node, (*node).left);
} else {
y = Self::minimum((*node).right);
y_original_color = (*y).color;
x = (*y).right;
if (*y).parent == node {
x_parent = y;
if !x.is_null() {
(*x).parent = y;
}
} else {
x_parent = (*y).parent;
self.transplant(y, (*y).right);
(*y).right = (*node).right;
(*(*y).right).parent = y;
}
self.transplant(node, y);
(*y).left = (*node).left;
(*(*y).left).parent = y;
(*y).color = (*node).color;
}
if y_original_color == Color::Black {
self.remove_fixup(x, x_parent);
}
(*node).reset_links();
self.len -= 1;
entity
}
}
pub unsafe fn pop_first(&mut self) -> Option<&mut T> {
let first = self.first();
if first.is_null() {
return None;
}
unsafe {
self.remove(first);
Some(&mut *first)
}
}
fn color_of(node: *mut RbNode) -> Color {
if node.is_null() {
Color::Black
} else {
unsafe { (*node).color }
}
}
fn minimum(mut node: *mut RbNode) -> *mut RbNode {
unsafe {
while !node.is_null() && !(*node).left.is_null() {
node = (*node).left;
}
}
node
}
#[allow(dead_code)]
fn maximum(mut node: *mut RbNode) -> *mut RbNode {
unsafe {
while !node.is_null() && !(*node).right.is_null() {
node = (*node).right;
}
}
node
}
fn cmp_nodes(a: *const RbNode, b: *const RbNode) -> Ordering {
unsafe { T::cmp(T::entity_of_const(a), T::entity_of_const(b)) }
}
unsafe fn left_rotate(&mut self, x: *mut RbNode) {
unsafe {
let y = (*x).right;
debug_assert!(!y.is_null());
(*x).right = (*y).left;
if !(*y).left.is_null() {
(*(*y).left).parent = x;
}
(*y).parent = (*x).parent;
if (*x).parent.is_null() {
self.root = y;
} else if x == (*(*x).parent).left {
(*(*x).parent).left = y;
} else {
(*(*x).parent).right = y;
}
(*y).left = x;
(*x).parent = y;
}
}
unsafe fn right_rotate(&mut self, y: *mut RbNode) {
unsafe {
let x = (*y).left;
debug_assert!(!x.is_null());
(*y).left = (*x).right;
if !(*x).right.is_null() {
(*(*x).right).parent = y;
}
(*x).parent = (*y).parent;
if (*y).parent.is_null() {
self.root = x;
} else if y == (*(*y).parent).right {
(*(*y).parent).right = x;
} else {
(*(*y).parent).left = x;
}
(*x).right = y;
(*y).parent = x;
}
}
unsafe fn insert_fixup(&mut self, mut z: *mut RbNode) {
unsafe {
while Self::color_of((*z).parent) == Color::Red {
let parent = (*z).parent;
let grandparent = (*parent).parent;
if parent == (*grandparent).left {
let uncle = (*grandparent).right;
if Self::color_of(uncle) == Color::Red {
(*parent).color = Color::Black;
(*uncle).color = Color::Black;
(*grandparent).color = Color::Red;
z = grandparent;
} else {
if z == (*parent).right {
z = parent;
self.left_rotate(z);
}
let parent = (*z).parent;
let grandparent = (*parent).parent;
(*parent).color = Color::Black;
(*grandparent).color = Color::Red;
self.right_rotate(grandparent);
}
} else {
let uncle = (*grandparent).left;
if Self::color_of(uncle) == Color::Red {
(*parent).color = Color::Black;
(*uncle).color = Color::Black;
(*grandparent).color = Color::Red;
z = grandparent;
} else {
if z == (*parent).left {
z = parent;
self.right_rotate(z);
}
let parent = (*z).parent;
let grandparent = (*parent).parent;
(*parent).color = Color::Black;
(*grandparent).color = Color::Red;
self.left_rotate(grandparent);
}
}
}
if !self.root.is_null() {
(*self.root).color = Color::Black;
}
}
}
unsafe fn transplant(&mut self, u: *mut RbNode, v: *mut RbNode) {
unsafe {
if (*u).parent.is_null() {
self.root = v;
} else if u == (*(*u).parent).left {
(*(*u).parent).left = v;
} else {
(*(*u).parent).right = v;
}
if !v.is_null() {
(*v).parent = (*u).parent;
}
}
}
unsafe fn remove_fixup(&mut self, mut x: *mut RbNode, mut parent: *mut RbNode) {
unsafe {
while x != self.root && Self::color_of(x) == Color::Black {
if x == parent_left(parent) {
let mut w = parent_right(parent);
if Self::color_of(w) == Color::Red {
(*w).color = Color::Black;
(*parent).color = Color::Red;
self.left_rotate(parent);
w = parent_right(parent);
}
if Self::color_of(left_of(w)) == Color::Black
&& Self::color_of(right_of(w)) == Color::Black
{
if !w.is_null() {
(*w).color = Color::Red;
}
x = parent;
parent = parent_of(x);
} else {
if Self::color_of(right_of(w)) == Color::Black {
let left = left_of(w);
if !left.is_null() {
(*left).color = Color::Black;
}
if !w.is_null() {
(*w).color = Color::Red;
self.right_rotate(w);
}
w = parent_right(parent);
}
if !w.is_null() {
(*w).color = (*parent).color;
}
(*parent).color = Color::Black;
let right = right_of(w);
if !right.is_null() {
(*right).color = Color::Black;
}
self.left_rotate(parent);
x = self.root;
parent = ptr::null_mut();
}
} else {
let mut w = parent_left(parent);
if Self::color_of(w) == Color::Red {
(*w).color = Color::Black;
(*parent).color = Color::Red;
self.right_rotate(parent);
w = parent_left(parent);
}
if Self::color_of(right_of(w)) == Color::Black
&& Self::color_of(left_of(w)) == Color::Black
{
if !w.is_null() {
(*w).color = Color::Red;
}
x = parent;
parent = parent_of(x);
} else {
if Self::color_of(left_of(w)) == Color::Black {
let right = right_of(w);
if !right.is_null() {
(*right).color = Color::Black;
}
if !w.is_null() {
(*w).color = Color::Red;
self.left_rotate(w);
}
w = parent_left(parent);
}
if !w.is_null() {
(*w).color = (*parent).color;
}
(*parent).color = Color::Black;
let left = left_of(w);
if !left.is_null() {
(*left).color = Color::Black;
}
self.right_rotate(parent);
x = self.root;
parent = ptr::null_mut();
}
}
}
if !x.is_null() {
(*x).color = Color::Black;
}
}
}
}
fn parent_of(node: *mut RbNode) -> *mut RbNode {
if node.is_null() {
ptr::null_mut()
} else {
unsafe { (*node).parent }
}
}
fn left_of(node: *mut RbNode) -> *mut RbNode {
if node.is_null() {
ptr::null_mut()
} else {
unsafe { (*node).left }
}
}
fn right_of(node: *mut RbNode) -> *mut RbNode {
if node.is_null() {
ptr::null_mut()
} else {
unsafe { (*node).right }
}
}
fn parent_left(node: *mut RbNode) -> *mut RbNode {
left_of(node)
}
fn parent_right(node: *mut RbNode) -> *mut RbNode {
right_of(node)
}
#[cfg(feature = "host")]
#[path = "../tests/support/rbtree.rs"]
pub mod test_support;