Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / rust / crates / intrusive-collections / 2a99f22e4e19a2989ac2eb2aa0aa7465b70f43c8 / . / src / rbtree.rs
blob: ad8f861baf0fe887ce85b3fee69577cb27ebd6c6 [file] [log] [blame]
// Copyright 2016 Amanieu d'Antras
// Copyright 2020 Amari Robinson
//
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
// http://opensource.org/licenses/MIT>, at your option. This file may not be
// copied, modified, or distributed except according to those terms.
//! Intrusive red-black tree.
use core::borrow::Borrow;
use core::cell::Cell;
use core::cmp::Ordering;
use core::fmt;
use core::mem;
use core::ptr::NonNull;
use crate::Bound::{self, Excluded, Included, Unbounded};
use crate::link_ops::{self, DefaultLinkOps};
use crate::linked_list::LinkedListOps;
use crate::pointer_ops::PointerOps;
use crate::singly_linked_list::SinglyLinkedListOps;
use crate::unchecked_option::UncheckedOptionExt;
use crate::xor_linked_list::XorLinkedListOps;
use crate::Adapter;
use crate::KeyAdapter;
// =============================================================================
// RBTreeOps
// =============================================================================
/// The color of a red-black tree node.
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
#[allow(missing_docs)]
pub enum Color {
Red,
Black,
}
/// Link operations for `RBTree`.
pub unsafe trait RBTreeOps: link_ops::LinkOps {
/// Returns the left child of `ptr`.
///
/// # Safety
/// An implementation of `left` must not panic.
unsafe fn left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
/// Returns the right child of `ptr`.
///
/// # Safety
/// An implementation of `right` must not panic.
unsafe fn right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
/// Returns the parent of `ptr`.
///
/// # Safety
/// An implementation of `parent` must not panic.
unsafe fn parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
/// Returns the color of `ptr`.
///
/// # Safety
/// An implementation of `color` must not panic.
unsafe fn color(&self, ptr: Self::LinkPtr) -> Color;
/// Sets the left child of `ptr`.
///
/// # Safety
/// An implementation of `set_left` must not panic.
unsafe fn set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>);
/// Sets the right child of `ptr`.
///
/// # Safety
/// An implementation of `set_right` must not panic.
unsafe fn set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>);
/// Sets the parent of `ptr`.
///
/// # Safety
/// An implementation of `set_parent` must not panic.
unsafe fn set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>);
/// Sets the color of `ptr`.
///
/// # Safety
/// An implementation of `set_color` must not panic.
unsafe fn set_color(&mut self, ptr: Self::LinkPtr, color: Color);
}
// =============================================================================
// Link
// =============================================================================
/// Intrusive link that allows an object to be inserted into a
/// `RBTree`.
#[repr(align(2))]
pub struct Link {
left: Cell<Option<NonNull<Link>>>,
right: Cell<Option<NonNull<Link>>>,
parent_color: Cell<usize>,
}
// Use a special value to indicate an unlinked node. This value represents a
// red root node, which is impossible in a valid red-black tree.
const UNLINKED_MARKER: usize = 0;
impl Link {
/// Creates a new `Link`.
#[inline]
pub const fn new() -> Link {
Link {
left: Cell::new(None),
right: Cell::new(None),
parent_color: Cell::new(UNLINKED_MARKER),
}
}
/// Checks whether the `Link` is linked into a `RBTree`.
#[inline]
pub fn is_linked(&self) -> bool {
self.parent_color.get() != UNLINKED_MARKER
}
/// Forcibly unlinks an object from a `RBTree`.
///
/// # Safety
///
/// It is undefined behavior to call this function while still linked into a
/// `RBTree`. The only situation where this function is useful is
/// after calling `fast_clear` on a `RBTree`, since this clears
/// the collection without marking the nodes as unlinked.
#[inline]
pub unsafe fn force_unlink(&self) {
self.parent_color.set(UNLINKED_MARKER);
}
}
impl DefaultLinkOps for Link {
type Ops = LinkOps;
const NEW: Self::Ops = LinkOps;
}
// An object containing a link can be sent to another thread if it is unlinked.
unsafe impl Send for Link {}
// Provide an implementation of Clone which simply initializes the new link as
// unlinked. This allows structs containing a link to derive Clone.
impl Clone for Link {
#[inline]
fn clone(&self) -> Link {
Link::new()
}
}
// Same as above
impl Default for Link {
#[inline]
fn default() -> Link {
Link::new()
}
}
// Provide an implementation of Debug so that structs containing a link can
// still derive Debug.
impl fmt::Debug for Link {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// There isn't anything sensible to print here except whether the link
// is currently in a tree.
if self.is_linked() {
write!(f, "linked")
} else {
write!(f, "unlinked")
}
}
}
// =============================================================================
// LinkOps
// =============================================================================
/// Default `LinkOps` implementation for `RBTree`.
#[derive(Clone, Copy, Default)]
pub struct LinkOps;
impl LinkOps {
#[inline]
unsafe fn set_parent_color(
self,
ptr: <Self as link_ops::LinkOps>::LinkPtr,
parent: Option<<Self as link_ops::LinkOps>::LinkPtr>,
color: Color,
) {
assert!(mem::align_of::<Link>() >= 2);
let bit = match color {
Color::Red => 0,
Color::Black => 1,
};
let parent_usize = parent.map(|x| x.as_ptr() as usize).unwrap_or(0);
ptr.as_ref().parent_color.set((parent_usize & !1) | bit);
}
}
unsafe impl link_ops::LinkOps for LinkOps {
type LinkPtr = NonNull<Link>;
#[inline]
unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
if ptr.as_ref().is_linked() {
false
} else {
self.set_parent_color(ptr, None, Color::Black);
true
}
}
#[inline]
unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
ptr.as_ref().parent_color.set(UNLINKED_MARKER);
}
}
unsafe impl RBTreeOps for LinkOps {
#[inline]
unsafe fn left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
ptr.as_ref().left.get()
}
#[inline]
unsafe fn right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
ptr.as_ref().right.get()
}
#[inline]
unsafe fn parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
let parent_usize = ptr.as_ref().parent_color.get() & !1;
NonNull::new(parent_usize as *mut Link)
}
#[inline]
unsafe fn color(&self, ptr: Self::LinkPtr) -> Color {
if ptr.as_ref().parent_color.get() & 1 == 1 {
Color::Black
} else {
Color::Red
}
}
#[inline]
unsafe fn set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>) {
ptr.as_ref().left.set(left);
}
#[inline]
unsafe fn set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>) {
ptr.as_ref().right.set(right);
}
#[inline]
unsafe fn set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>) {
self.set_parent_color(ptr, parent, self.color(ptr));
}
#[inline]
unsafe fn set_color(&mut self, ptr: Self::LinkPtr, color: Color) {
self.set_parent_color(ptr, self.parent(ptr), color);
}
}
unsafe impl SinglyLinkedListOps for LinkOps {
#[inline]
unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
self.right(ptr)
}
#[inline]
unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
self.set_right(ptr, next);
}
}
unsafe impl LinkedListOps for LinkOps {
#[inline]
unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
self.right(ptr)
}
#[inline]
unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
self.left(ptr)
}
#[inline]
unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
self.set_right(ptr, next);
}
#[inline]
unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
self.set_left(ptr, prev);
}
}
unsafe impl XorLinkedListOps for LinkOps {
#[inline]
unsafe fn next(
&self,
ptr: Self::LinkPtr,
prev: Option<Self::LinkPtr>,
) -> Option<Self::LinkPtr> {
let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
NonNull::new(raw as *mut _)
}
#[inline]
unsafe fn prev(
&self,
ptr: Self::LinkPtr,
next: Option<Self::LinkPtr>,
) -> Option<Self::LinkPtr> {
let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
NonNull::new(raw as *mut _)
}
#[inline]
unsafe fn set(
&mut self,
ptr: Self::LinkPtr,
prev: Option<Self::LinkPtr>,
next: Option<Self::LinkPtr>,
) {
let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
let new_next = NonNull::new(new_packed as *mut _);
self.set_right(ptr, new_next);
}
#[inline]
unsafe fn replace_next_or_prev(
&mut self,
ptr: Self::LinkPtr,
old: Option<Self::LinkPtr>,
new: Option<Self::LinkPtr>,
) {
let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
let new_packed = packed
^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
let new_next = NonNull::new(new_packed as *mut _);
self.set_right(ptr, new_next);
}
}
#[inline]
unsafe fn is_left_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr, parent: T::LinkPtr) -> bool {
link_ops.left(parent) == Some(ptr)
}
#[inline]
unsafe fn first_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr {
let mut x = ptr;
while let Some(y) = link_ops.left(x) {
x = y;
}
x
}
#[inline]
unsafe fn last_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr {
let mut x = ptr;
while let Some(y) = link_ops.right(x) {
x = y;
}
x
}
#[inline]
unsafe fn next<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> {
if let Some(right) = link_ops.right(ptr) {
Some(first_child(link_ops, right))
} else {
let mut x = ptr;
loop {
if let Some(parent) = link_ops.parent(x) {
if is_left_child(link_ops, x, parent) {
return Some(parent);
}
x = parent;
} else {
return None;
}
}
}
}
#[inline]
unsafe fn prev<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> {
if let Some(left) = link_ops.left(ptr) {
Some(last_child(link_ops, left))
} else {
let mut x = ptr;
loop {
if let Some(parent) = link_ops.parent(x) {
if !is_left_child(link_ops, x, parent) {
return Some(parent);
}
x = parent;
} else {
return None;
}
}
}
}
#[inline]
unsafe fn replace_with<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
new: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
if let Some(parent) = link_ops.parent(ptr) {
if is_left_child(link_ops, ptr, parent) {
link_ops.set_left(parent, Some(new));
} else {
link_ops.set_right(parent, Some(new));
}
} else {
*root = Some(new);
}
if let Some(left) = link_ops.left(ptr) {
link_ops.set_parent(left, Some(new));
}
if let Some(right) = link_ops.right(ptr) {
link_ops.set_parent(right, Some(new));
}
link_ops.set_left(new, link_ops.left(ptr));
link_ops.set_right(new, link_ops.right(ptr));
link_ops.set_parent(new, link_ops.parent(ptr));
link_ops.set_color(new, link_ops.color(ptr));
link_ops.release_link(ptr);
}
#[inline]
unsafe fn insert_left<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
new: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
link_ops.set_parent(new, Some(ptr));
link_ops.set_color(new, Color::Red);
link_ops.set_left(new, None);
link_ops.set_right(new, None);
link_ops.set_left(ptr, Some(new));
post_insert(link_ops, new, root);
}
#[inline]
unsafe fn insert_right<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
new: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
link_ops.set_parent(new, Some(ptr));
link_ops.set_color(new, Color::Red);
link_ops.set_left(new, None);
link_ops.set_right(new, None);
link_ops.set_right(ptr, Some(new));
post_insert(link_ops, new, root);
}
unsafe fn rotate_left<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
let y = link_ops.right(ptr).unwrap_unchecked();
link_ops.set_right(ptr, link_ops.left(y));
if let Some(right) = link_ops.right(ptr) {
link_ops.set_parent(right, Some(ptr));
}
link_ops.set_parent(y, link_ops.parent(ptr));
if let Some(parent) = link_ops.parent(ptr) {
if is_left_child(link_ops, ptr, parent) {
link_ops.set_left(parent, Some(y));
} else {
link_ops.set_right(parent, Some(y));
}
} else {
*root = Some(y);
}
link_ops.set_left(y, Some(ptr));
link_ops.set_parent(ptr, Some(y));
}
unsafe fn rotate_right<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
let y = link_ops.left(ptr).unwrap_unchecked();
link_ops.set_left(ptr, link_ops.right(y));
if let Some(left) = link_ops.left(ptr) {
link_ops.set_parent(left, Some(ptr));
}
link_ops.set_parent(y, link_ops.parent(ptr));
if let Some(parent) = link_ops.parent(ptr) {
if is_left_child(link_ops, ptr, parent) {
link_ops.set_left(parent, Some(y));
} else {
link_ops.set_right(parent, Some(y));
}
} else {
*root = Some(y);
}
link_ops.set_right(y, Some(ptr));
link_ops.set_parent(ptr, Some(y));
}
// This code is based on the red-black tree implementation in libc++
unsafe fn post_insert<T: RBTreeOps>(
link_ops: &mut T,
ptr: T::LinkPtr,
root: &mut Option<T::LinkPtr>,
) {
let mut x = ptr;
while let Some(parent) = link_ops.parent(x) {
if link_ops.color(parent) != Color::Red {
break;
}
// SAFETY: The root of the tree must be black, and `parent` cannot be the root if it is red.
let grandparent = link_ops.parent(parent).unwrap_unchecked();
if is_left_child(link_ops, parent, grandparent) {
let y = link_ops.right(grandparent);
if let Some(y) = y {
if link_ops.color(y) == Color::Red {
x = parent;
link_ops.set_color(x, Color::Black);
x = grandparent;
if link_ops.parent(x).is_none() {
link_ops.set_color(x, Color::Black);
} else {
link_ops.set_color(x, Color::Red);
}
link_ops.set_color(y, Color::Black);
continue;
}
}
if !is_left_child(link_ops, x, parent) {
x = parent;
rotate_left(link_ops, x, root);
}
x = link_ops.parent(x).unwrap_unchecked();
link_ops.set_color(x, Color::Black);
x = link_ops.parent(x).unwrap_unchecked();
link_ops.set_color(x, Color::Red);
rotate_right(link_ops, x, root);
break;
} else {
let y = link_ops.left(grandparent);
if let Some(y) = y {
if link_ops.color(y) == Color::Red {
x = parent;
link_ops.set_color(x, Color::Black);
x = grandparent;
if link_ops.parent(x).is_none() {
link_ops.set_color(x, Color::Black);
} else {
link_ops.set_color(x, Color::Red);
}
link_ops.set_color(y, Color::Black);
continue;
}
}
if is_left_child(link_ops, x, parent) {
x = parent;
rotate_right(link_ops, x, root);
}
x = link_ops.parent(x).unwrap_unchecked();
link_ops.set_color(x, Color::Black);
x = link_ops.parent(x).unwrap_unchecked();
link_ops.set_color(x, Color::Red);
rotate_left(link_ops, x, root);
break;
}
}
}
// This code is based on the red-black tree implementation in libc++
unsafe fn remove<T: RBTreeOps>(link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>) {
let y = if link_ops.left(ptr).is_none() || link_ops.right(ptr).is_none() {
ptr
} else {
next(link_ops, ptr).unwrap_unchecked()
};
let x = if link_ops.left(y).is_some() {
link_ops.left(y)
} else {
link_ops.right(y)
};
let mut w = None;
if let Some(x) = x {
link_ops.set_parent(x, link_ops.parent(y));
}
if let Some(y_parent) = link_ops.parent(y) {
if is_left_child(link_ops, y, y_parent) {
link_ops.set_left(y_parent, x);
w = link_ops.right(y_parent);
} else {
link_ops.set_right(y_parent, x);
w = link_ops.left(y_parent);
}
} else {
*root = x;
}
let removed_black = link_ops.color(y) == Color::Black;
if y != ptr {
if let Some(parent) = link_ops.parent(ptr) {
link_ops.set_parent(y, Some(parent));
if is_left_child(link_ops, ptr, parent) {
link_ops.set_left(parent, Some(y));
} else {
link_ops.set_right(parent, Some(y));
}
} else {
link_ops.set_parent(y, None);
*root = Some(y);
}
link_ops.set_left(y, link_ops.left(ptr));
link_ops.set_parent(link_ops.left(y).unwrap_unchecked(), Some(y));
link_ops.set_right(y, link_ops.right(ptr));
if let Some(y_right) = link_ops.right(y) {
link_ops.set_parent(y_right, Some(y));
}
link_ops.set_color(y, link_ops.color(ptr));
}
if removed_black && !root.is_none() {
if let Some(x) = x {
link_ops.set_color(x, Color::Black);
} else {
let mut w = w.unwrap_unchecked();
loop {
let mut w_parent = link_ops.parent(w).unwrap_unchecked();
if !is_left_child(link_ops, w, w_parent) {
if link_ops.color(w) == Color::Red {
link_ops.set_color(w, Color::Black);
link_ops.set_color(w_parent, Color::Red);
rotate_left(link_ops, w_parent, root);
w = link_ops
.right(link_ops.left(w).unwrap_unchecked())
.unwrap_unchecked();
w_parent = link_ops.parent(w).unwrap_unchecked();
}
let left_color = link_ops.left(w).map(|x| link_ops.color(x));
let right_color = link_ops.right(w).map(|x| link_ops.color(x));
if (left_color != Some(Color::Red)) && (right_color != Some(Color::Red)) {
link_ops.set_color(w, Color::Red);
if link_ops.parent(w_parent).is_none()
|| link_ops.color(w_parent) == Color::Red
{
link_ops.set_color(w_parent, Color::Black);
break;
}
let w_grandparent = link_ops.parent(w_parent).unwrap_unchecked();
w = if is_left_child(link_ops, w_parent, w_grandparent) {
link_ops.right(w_grandparent).unwrap_unchecked()
} else {
link_ops.left(w_grandparent).unwrap_unchecked()
};
} else {
if link_ops.right(w).map(|x| link_ops.color(x)) != Some(Color::Red) {
link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black);
link_ops.set_color(w, Color::Red);
rotate_right(link_ops, w, root);
w = link_ops.parent(w).unwrap_unchecked();
w_parent = link_ops.parent(w).unwrap_unchecked();
}
link_ops.set_color(w, link_ops.color(w_parent));
link_ops.set_color(w_parent, Color::Black);
link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black);
rotate_left(link_ops, w_parent, root);
break;
}
} else {
if link_ops.color(w) == Color::Red {
link_ops.set_color(w, Color::Black);
link_ops.set_color(w_parent, Color::Red);
rotate_right(link_ops, w_parent, root);
w = link_ops
.left(link_ops.right(w).unwrap_unchecked())
.unwrap_unchecked();
w_parent = link_ops.parent(w).unwrap_unchecked();
}
let left_color = link_ops.left(w).map(|x| link_ops.color(x));
let right_color = link_ops.right(w).map(|x| link_ops.color(x));
if (left_color != Some(Color::Red)) && (right_color != Some(Color::Red)) {
link_ops.set_color(w, Color::Red);
if link_ops.parent(w_parent).is_none()
|| link_ops.color(w_parent) == Color::Red
{
link_ops.set_color(w_parent, Color::Black);
break;
}
w = if is_left_child(
link_ops,
w_parent,
link_ops.parent(w_parent).unwrap_unchecked(),
) {
link_ops
.right(link_ops.parent(w_parent).unwrap_unchecked())
.unwrap_unchecked()
} else {
link_ops
.left(link_ops.parent(w_parent).unwrap_unchecked())
.unwrap_unchecked()
};
} else {
if link_ops.left(w).map(|x| link_ops.color(x)) != Some(Color::Red) {
link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black);
link_ops.set_color(w, Color::Red);
rotate_left(link_ops, w, root);
w = link_ops.parent(w).unwrap_unchecked();
w_parent = link_ops.parent(w).unwrap_unchecked();
}
link_ops.set_color(w, link_ops.color(w_parent));
link_ops.set_color(w_parent, Color::Black);
link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black);
rotate_right(link_ops, w_parent, root);
break;
}
}
}
}
}
link_ops.release_link(ptr);
}
// =============================================================================
// Cursor, CursorMut
// =============================================================================
/// A cursor which provides read-only access to a `RBTree`.
pub struct Cursor<'a, A: Adapter>
where
A::LinkOps: RBTreeOps,
{
current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tree: &'a RBTree<A>,
}
impl<'a, A: Adapter> Clone for Cursor<'a, A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn clone(&self) -> Cursor<'a, A> {
Cursor {
current: self.current,
tree: self.tree,
}
}
}
impl<'a, A: Adapter> Cursor<'a, A>
where
A::LinkOps: RBTreeOps,
{
/// Checks if the cursor is currently pointing to the null object.
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_none()
}
/// Returns a reference to the object that the cursor is currently
/// pointing to.
///
/// This returns `None` if the cursor is currently pointing to the null
/// object.
#[inline]
pub fn get(&self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
Some(unsafe { &*self.tree.adapter.get_value(self.current?) })
}
/// Clones and returns the pointer that points to the element that the
/// cursor is referencing.
///
/// This returns `None` if the cursor is currently pointing to the null
/// object.
#[inline]
pub fn clone_pointer(&self) -> Option<<A::PointerOps as PointerOps>::Pointer>
where
<A::PointerOps as PointerOps>::Pointer: Clone,
{
let raw_pointer = self.get()? as *const <A::PointerOps as PointerOps>::Value;
Some(unsafe {
crate::pointer_ops::clone_pointer_from_raw(self.tree.adapter.pointer_ops(), raw_pointer)
})
}
/// Moves the cursor to the next element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will move it to
/// the first element of the `RBTree`. If it is pointing to the last
/// element of the `RBTree` then this will move it to the null object.
#[inline]
pub fn move_next(&mut self) {
if let Some(current) = self.current {
self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
} else if let Some(root) = self.tree.root {
self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
} else {
self.current = None;
}
}
/// Moves the cursor to the previous element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will move it to
/// the last element of the `RBTree`. If it is pointing to the first
/// element of the `RBTree` then this will move it to the null object.
#[inline]
pub fn move_prev(&mut self) {
if let Some(current) = self.current {
self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
} else if let Some(root) = self.tree.root {
self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
} else {
self.current = None;
}
}
/// Returns a cursor pointing to the next element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will return the
/// first element of the `RBTree`. If it is pointing to the last
/// element of the `RBTree` then this will return a null cursor.
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.clone();
next.move_next();
next
}
/// Returns a cursor pointing to the previous element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will return the
/// last element of the `RBTree`. If it is pointing to the first
/// element of the `RBTree` then this will return a null cursor.
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.clone();
prev.move_prev();
prev
}
}
/// A cursor which provides mutable access to a `RBTree`.
pub struct CursorMut<'a, A: Adapter>
where
A::LinkOps: RBTreeOps,
{
current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tree: &'a mut RBTree<A>,
}
impl<'a, A: Adapter> CursorMut<'a, A>
where
A::LinkOps: RBTreeOps,
{
/// Checks if the cursor is currently pointing to the null object.
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_none()
}
/// Returns a reference to the object that the cursor is currently
/// pointing to.
///
/// This returns None if the cursor is currently pointing to the null
/// object.
#[inline]
pub fn get(&self) -> Option<&<A::PointerOps as PointerOps>::Value> {
Some(unsafe { &*self.tree.adapter.get_value(self.current?) })
}
/// Returns a read-only cursor pointing to the current element.
///
/// The lifetime of the returned `Cursor` is bound to that of the
/// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
/// `CursorMut` is frozen for the lifetime of the `Cursor`.
#[inline]
pub fn as_cursor(&self) -> Cursor<'_, A> {
Cursor {
current: self.current,
tree: self.tree,
}
}
/// Moves the cursor to the next element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will move it to
/// the first element of the `RBTree`. If it is pointing to the last
/// element of the `RBTree` then this will move it to the null object.
#[inline]
pub fn move_next(&mut self) {
if let Some(current) = self.current {
self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
} else if let Some(root) = self.tree.root {
self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
} else {
self.current = None;
}
}
/// Moves the cursor to the previous element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will move it to
/// the last element of the `RBTree`. If it is pointing to the first
/// element of the `RBTree` then this will move it to the null object.
#[inline]
pub fn move_prev(&mut self) {
if let Some(current) = self.current {
self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
} else if let Some(root) = self.tree.root {
self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
} else {
self.current = None;
}
}
/// Returns a cursor pointing to the next element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will return the
/// first element of the `RBTree`. If it is pointing to the last
/// element of the `RBTree` then this will return a null cursor.
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.as_cursor();
next.move_next();
next
}
/// Returns a cursor pointing to the previous element of the `RBTree`.
///
/// If the cursor is pointer to the null object then this will return the
/// last element of the `RBTree`. If it is pointing to the first
/// element of the `RBTree` then this will return a null cursor.
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.as_cursor();
prev.move_prev();
prev
}
/// Removes the current element from the `RBTree`.
///
/// A pointer to the element that was removed is returned, and the cursor is
/// moved to point to the next element in the `RBTree`.
///
/// If the cursor is currently pointing to the null object then no element
/// is removed and `None` is returned.
#[inline]
pub fn remove(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
unsafe {
if let Some(current) = self.current {
let next = next(self.tree.adapter.link_ops(), current);
let result = current;
remove(
self.tree.adapter.link_ops_mut(),
current,
&mut self.tree.root,
);
self.current = next;
Some(
self.tree
.adapter
.pointer_ops()
.from_raw(self.tree.adapter.get_value(result)),
)
} else {
None
}
}
}
/// Removes the current element from the `RBTree` and inserts another
/// object in its place.
///
/// A pointer to the element that was removed is returned, and the cursor is
/// modified to point to the newly added element.
///
/// When using this function you must ensure that the elements in the
/// collection are maintained in increasing order. Failure to do this may
/// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
/// incorrect results.
///
/// If the cursor is currently pointing to the null object then an error is
/// returned containing the given `val` parameter.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
#[inline]
pub fn replace_with(
&mut self,
val: <A::PointerOps as PointerOps>::Pointer,
) -> Result<<A::PointerOps as PointerOps>::Pointer, <A::PointerOps as PointerOps>::Pointer>
{
unsafe {
if let Some(current) = self.current {
let new = self.tree.node_from_value(val);
let result = current;
replace_with(
self.tree.adapter.link_ops_mut(),
current,
new,
&mut self.tree.root,
);
self.current = Some(new);
Ok(self
.tree
.adapter
.pointer_ops()
.from_raw(self.tree.adapter.get_value(result)))
} else {
Err(val)
}
}
}
/// Inserts a new element into the `RBTree` after the current one.
///
/// When using this function you must ensure that the elements in the
/// collection are maintained in increasing order. Failure to do this may
/// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
/// incorrect results.
///
/// If the cursor is pointing at the null object then the new element is
/// inserted at the start of the `RBTree`.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
#[inline]
pub fn insert_after(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
unsafe {
let new = self.tree.node_from_value(val);
let link_ops = self.tree.adapter.link_ops_mut();
if let Some(root) = self.tree.root {
if let Some(current) = self.current {
if link_ops.right(current).is_some() {
let next = next(link_ops, current).unwrap_unchecked();
insert_left(link_ops, next, new, &mut self.tree.root);
} else {
insert_right(link_ops, current, new, &mut self.tree.root);
}
} else {
insert_left(
link_ops,
first_child(link_ops, root),
new,
&mut self.tree.root,
);
}
} else {
self.tree.insert_root(new);
}
}
}
/// Inserts a new element into the `RBTree` before the current one.
///
/// When using this function you must ensure that the elements in the
/// collection are maintained in increasing order. Failure to do this may
/// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
/// incorrect results.
///
/// If the cursor is pointing at the null object then the new element is
/// inserted at the end of the `RBTree`.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
#[inline]
pub fn insert_before(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
unsafe {
let new = self.tree.node_from_value(val);
let link_ops = self.tree.adapter.link_ops_mut();
if let Some(root) = self.tree.root {
if let Some(current) = self.current {
if link_ops.left(current).is_some() {
let prev = prev(link_ops, current).unwrap_unchecked();
insert_right(link_ops, prev, new, &mut self.tree.root);
} else {
insert_left(link_ops, current, new, &mut self.tree.root);
}
} else {
insert_right(
link_ops,
last_child(link_ops, root),
new,
&mut self.tree.root,
);
}
} else {
self.tree.insert_root(new);
}
}
}
}
impl<'a, A: for<'b> KeyAdapter<'b>> CursorMut<'a, A>
where
<A as Adapter>::LinkOps: RBTreeOps,
{
/// Inserts a new element into the `RBTree`.
///
/// The new element will be inserted at the correct position in the tree
/// based on its key, regardless of the current cursor position.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
#[inline]
pub fn insert<'c>(&'c mut self, val: <A::PointerOps as PointerOps>::Pointer)
where
<A as KeyAdapter<'c>>::Key: Ord,
{
// We explicitly drop the returned CursorMut here, otherwise we would
// end up with multiple CursorMut in the same collection.
self.tree.insert(val);
}
}
// =============================================================================
// RBTree
// =============================================================================
/// An intrusive red-black tree.
///
/// When this collection is dropped, all elements linked into it will be
/// converted back to owned pointers and dropped.
///
/// Note that you are responsible for ensuring that the elements in a `RBTree`
/// remain in ascending key order. This property can be violated, either because
/// the key of an element was modified, or because the
/// `insert_before`/`insert_after` methods of `CursorMut` were incorrectly used.
/// If this situation occurs, memory safety will not be violated but the `find`,
/// `upper_bound`, `lower_bound` and `range` may return incorrect results.
pub struct RBTree<A: Adapter>
where
A::LinkOps: RBTreeOps,
{
root: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
adapter: A,
}
impl<A: Adapter> RBTree<A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn node_from_value(
&mut self,
val: <A::PointerOps as PointerOps>::Pointer,
) -> <A::LinkOps as link_ops::LinkOps>::LinkPtr {
use link_ops::LinkOps;
unsafe {
let raw = self.adapter.pointer_ops().into_raw(val);
let link = self.adapter.get_link(raw);
if !self.adapter.link_ops_mut().acquire_link(link) {
// convert the node back into a pointer
self.adapter.pointer_ops().from_raw(raw);
panic!("attempted to insert an object that is already linked");
}
link
}
}
/// Creates an empty `RBTree`.
#[cfg(not(feature = "nightly"))]
#[inline]
pub fn new(adapter: A) -> RBTree<A> {
RBTree {
root: None,
adapter,
}
}
/// Creates an empty `RBTree`.
#[cfg(feature = "nightly")]
#[inline]
pub const fn new(adapter: A) -> RBTree<A> {
RBTree {
root: None,
adapter,
}
}
/// Returns `true` if the `RBTree` is empty.
#[inline]
pub fn is_empty(&self) -> bool {
self.root.is_none()
}
/// Returns a null `Cursor` for this tree.
#[inline]
pub fn cursor(&self) -> Cursor<'_, A> {
Cursor {
current: None,
tree: self,
}
}
/// Returns a null `CursorMut` for this tree.
#[inline]
pub fn cursor_mut(&mut self) -> CursorMut<'_, A> {
CursorMut {
current: None,
tree: self,
}
}
/// Creates a `Cursor` from a pointer to an element.
///
/// # Safety
///
/// `ptr` must be a pointer to an object that is part of this tree.
#[inline]
pub unsafe fn cursor_from_ptr(
&self,
ptr: *const <A::PointerOps as PointerOps>::Value,
) -> Cursor<'_, A> {
Cursor {
current: Some(self.adapter.get_link(ptr)),
tree: self,
}
}
/// Creates a `CursorMut` from a pointer to an element.
///
/// # Safety
///
/// `ptr` must be a pointer to an object that is part of this tree.
#[inline]
pub unsafe fn cursor_mut_from_ptr(
&mut self,
ptr: *const <A::PointerOps as PointerOps>::Value,
) -> CursorMut<'_, A> {
CursorMut {
current: Some(self.adapter.get_link(ptr)),
tree: self,
}
}
/// Returns a `Cursor` pointing to the first element of the tree. If the
/// tree is empty then a null cursor is returned.
#[inline]
pub fn front(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_next();
cursor
}
/// Returns a `CursorMut` pointing to the first element of the tree. If the
/// the tree is empty then a null cursor is returned.
#[inline]
pub fn front_mut(&mut self) -> CursorMut<'_, A> {
let mut cursor = self.cursor_mut();
cursor.move_next();
cursor
}
/// Returns a `Cursor` pointing to the last element of the tree. If the tree
/// is empty then a null cursor is returned.
#[inline]
pub fn back(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_prev();
cursor
}
/// Returns a `CursorMut` pointing to the last element of the tree. If the
/// tree is empty then a null cursor is returned.
#[inline]
pub fn back_mut(&mut self) -> CursorMut<'_, A> {
let mut cursor = self.cursor_mut();
cursor.move_prev();
cursor
}
#[inline]
unsafe fn insert_root(&mut self, node: <A::LinkOps as link_ops::LinkOps>::LinkPtr) {
self.adapter.link_ops_mut().set_parent(node, None);
self.adapter.link_ops_mut().set_color(node, Color::Black);
self.adapter.link_ops_mut().set_left(node, None);
self.adapter.link_ops_mut().set_right(node, None);
self.root = Some(node);
}
/// Gets an iterator over the objects in the `RBTree`.
#[inline]
pub fn iter(&self) -> Iter<'_, A> {
let link_ops = self.adapter.link_ops();
if let Some(root) = self.root {
Iter {
head: Some(unsafe { first_child(link_ops, root) }),
tail: Some(unsafe { last_child(link_ops, root) }),
tree: self,
}
} else {
Iter {
head: None,
tail: None,
tree: self,
}
}
}
#[inline]
fn clear_recurse(&mut self, current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>) {
use link_ops::LinkOps;
// If adapter.get_value or Pointer::from_raw panic here, it will leak
// the nodes and keep them linked. However this is harmless since there
// is nothing you can do with just a Link.
if let Some(current) = current {
unsafe {
let left = self.adapter.link_ops_mut().left(current);
let right = self.adapter.link_ops_mut().right(current);
self.clear_recurse(left);
self.clear_recurse(right);
self.adapter.link_ops_mut().release_link(current);
self.adapter
.pointer_ops()
.from_raw(self.adapter.get_value(current));
}
}
}
/// Removes all elements from the `RBTree`.
///
/// This will unlink all object currently in the tree, which requires
/// iterating through all elements in the `RBTree`. Each element is
/// converted back to an owned pointer and then dropped.
#[inline]
pub fn clear(&mut self) {
let root = self.root.take();
self.clear_recurse(root);
}
/// Empties the `RBTree` without unlinking or freeing objects in it.
///
/// Since this does not unlink any objects, any attempts to link these
/// objects into another `RBTree` will fail but will not cause any
/// memory unsafety. To unlink those objects manually, you must call the
/// `force_unlink` function on them.
#[inline]
pub fn fast_clear(&mut self) {
self.root = None;
}
/// Takes all the elements out of the `RBTree`, leaving it empty. The
/// taken elements are returned as a new `RBTree`.
#[inline]
pub fn take(&mut self) -> RBTree<A>
where
A: Clone,
{
let tree = RBTree {
root: self.root,
adapter: self.adapter.clone(),
};
self.root = None;
tree
}
}
impl<A: for<'a> KeyAdapter<'a>> RBTree<A>
where
<A as Adapter>::LinkOps: RBTreeOps,
{
#[inline]
fn find_internal<'a, Q: ?Sized + Ord>(
&self,
key: &Q,
) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
<A::PointerOps as PointerOps>::Value: 'a,
{
let link_ops = self.adapter.link_ops();
let mut tree = self.root;
while let Some(x) = tree {
let current = unsafe { &*self.adapter.get_value(x) };
match key.cmp(self.adapter.get_key(current).borrow()) {
Ordering::Less => tree = unsafe { link_ops.left(x) },
Ordering::Equal => return tree,
Ordering::Greater => tree = unsafe { link_ops.right(x) },
}
}
None
}
/// Returns a `Cursor` pointing to an element with the given key. If no such
/// element is found then a null cursor is returned.
///
/// If multiple elements with an identical key are found then an arbitrary
/// one is returned.
#[inline]
pub fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
Cursor {
current: self.find_internal(key),
tree: self,
}
}
/// Returns a `CursorMut` pointing to an element with the given key. If no
/// such element is found then a null cursor is returned.
///
/// If multiple elements with an identical key are found then an arbitrary
/// one is returned.
#[inline]
pub fn find_mut<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
CursorMut {
current: self.find_internal(key),
tree: self,
}
}
#[inline]
fn lower_bound_internal<'a, Q: ?Sized + Ord>(
&self,
bound: Bound<&Q>,
) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
<A::PointerOps as PointerOps>::Value: 'a,
{
let link_ops = self.adapter.link_ops();
let mut tree = self.root;
let mut result = None;
while let Some(x) = tree {
let current = unsafe { &*self.adapter.get_value(x) };
let cond = match bound {
Unbounded => true,
Included(key) => key <= self.adapter.get_key(current).borrow(),
Excluded(key) => key < self.adapter.get_key(current).borrow(),
};
if cond {
result = tree;
tree = unsafe { link_ops.left(x) };
} else {
tree = unsafe { link_ops.right(x) };
}
}
result
}
/// Returns a `Cursor` pointing to the lowest element whose key is above
/// the given bound. If no such element is found then a null cursor is
/// returned.
#[inline]
pub fn lower_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
Cursor {
current: self.lower_bound_internal(bound),
tree: self,
}
}
/// Returns a `CursorMut` pointing to the first element whose key is
/// above the given bound. If no such element is found then a null
/// cursor is returned.
#[inline]
pub fn lower_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
CursorMut {
current: self.lower_bound_internal(bound),
tree: self,
}
}
#[inline]
fn upper_bound_internal<'a, Q: ?Sized + Ord>(
&self,
bound: Bound<&Q>,
) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
<A::PointerOps as PointerOps>::Value: 'a,
{
let link_ops = self.adapter.link_ops();
let mut tree = self.root;
let mut result = None;
while let Some(x) = tree {
let current = unsafe { &*self.adapter.get_value(x) };
let cond = match bound {
Unbounded => false,
Included(key) => key < self.adapter.get_key(current).borrow(),
Excluded(key) => key <= self.adapter.get_key(current).borrow(),
};
if cond {
tree = unsafe { link_ops.left(x) };
} else {
result = tree;
tree = unsafe { link_ops.right(x) };
}
}
result
}
/// Returns a `Cursor` pointing to the last element whose key is below
/// the given bound. If no such element is found then a null cursor is
/// returned.
#[inline]
pub fn upper_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
Cursor {
current: self.upper_bound_internal(bound),
tree: self,
}
}
/// Returns a `CursorMut` pointing to the last element whose key is
/// below the given bound. If no such element is found then a null
/// cursor is returned.
#[inline]
pub fn upper_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
CursorMut {
current: self.upper_bound_internal(bound),
tree: self,
}
}
/// Inserts a new element into the `RBTree`.
///
/// The new element will be inserted at the correct position in the tree
/// based on its key.
///
/// Returns a mutable cursor pointing to the newly added element.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
#[inline]
pub fn insert<'a>(&'a mut self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'_, A>
where
<A as KeyAdapter<'a>>::Key: Ord,
{
unsafe {
let new = self.node_from_value(val);
let raw = self.adapter.get_value(new);
if let Some(root) = self.root {
let key = self.adapter.get_key(&*raw);
let mut tree = root;
loop {
let current = &*self.adapter.get_value(tree);
if key < self.adapter.get_key(current) {
if let Some(left) = self.adapter.link_ops().left(tree) {
tree = left;
} else {
insert_left(self.adapter.link_ops_mut(), tree, new, &mut self.root);
break;
}
} else {
if let Some(right) = self.adapter.link_ops().right(tree) {
tree = right;
} else {
insert_right(self.adapter.link_ops_mut(), tree, new, &mut self.root);
break;
}
}
}
} else {
self.insert_root(new);
}
CursorMut {
current: Some(new),
tree: self,
}
}
}
/// Returns an `Entry` for the given key which contains a `CursorMut` to an
/// element with the given key or an `InsertCursor` which points to a place
/// in which to insert a new element with the given key.
///
/// This is more efficient than calling `find` followed by `insert` since
/// the tree does not have to be searched a second time to find a place to
/// insert the new element.
///
/// If multiple elements with an identical key are found then an arbitrary
/// one is returned.
#[inline]
pub fn entry<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> Entry<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
{
unsafe {
if let Some(root) = self.root {
let mut tree = root;
loop {
let current = &*self.adapter.get_value(tree);
match key.cmp(self.adapter.get_key(current).borrow()) {
Ordering::Less => {
if let Some(left) = self.adapter.link_ops().left(tree) {
tree = left;
} else {
return Entry::Vacant(InsertCursor {
parent: Some(tree),
insert_left: true,
tree: self,
});
}
}
Ordering::Equal => {
return Entry::Occupied(CursorMut {
current: Some(tree),
tree: self,
});
}
Ordering::Greater => {
if let Some(right) = self.adapter.link_ops().right(tree) {
tree = right;
} else {
return Entry::Vacant(InsertCursor {
parent: Some(tree),
insert_left: false,
tree: self,
});
}
}
}
}
} else {
Entry::Vacant(InsertCursor {
parent: None,
insert_left: false,
tree: self,
})
}
}
}
/// Constructs a double-ended iterator over a sub-range of elements in the
/// tree, starting at min, and ending at max. If min is `Unbounded`, then it
/// will be treated as "negative infinity", and if max is `Unbounded`, then
/// it will be treated as "positive infinity". Thus
/// `range(Unbounded, Unbounded)` will yield the whole collection.
#[inline]
pub fn range<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(
&'a self,
min: Bound<&Min>,
max: Bound<&Max>,
) -> Iter<'a, A>
where
<A as KeyAdapter<'a>>::Key: Borrow<Min> + Borrow<Max>,
<A as KeyAdapter<'a>>::Key: Ord,
{
let lower = self.lower_bound_internal(min);
let upper = self.upper_bound_internal(max);
if let (Some(lower), Some(upper)) = (lower, upper) {
let lower_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(lower)) };
let upper_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(upper)) };
if upper_key >= lower_key {
return Iter {
head: Some(lower),
tail: Some(upper),
tree: self,
};
}
}
Iter {
head: None,
tail: None,
tree: self,
}
}
}
// Allow read-only access to values from multiple threads
unsafe impl<A: Adapter + Sync> Sync for RBTree<A>
where
<A::PointerOps as PointerOps>::Value: Sync,
A::LinkOps: RBTreeOps,
{
}
// Allow sending to another thread if the ownership (represented by the <A::PointerOps as PointerOps>::Pointer owned
// pointer type) can be transferred to another thread.
unsafe impl<A: Adapter + Send> Send for RBTree<A>
where
<A::PointerOps as PointerOps>::Pointer: Send,
A::LinkOps: RBTreeOps,
{
}
// Drop all owned pointers if the collection is dropped
impl<A: Adapter> Drop for RBTree<A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn drop(&mut self) {
self.clear();
}
}
impl<A: Adapter> IntoIterator for RBTree<A>
where
A::LinkOps: RBTreeOps,
{
type Item = <A::PointerOps as PointerOps>::Pointer;
type IntoIter = IntoIter<A>;
#[inline]
fn into_iter(self) -> IntoIter<A> {
let link_ops = self.adapter.link_ops();
if let Some(root) = self.root {
IntoIter {
head: Some(unsafe { first_child(link_ops, root) }),
tail: Some(unsafe { last_child(link_ops, root) }),
tree: self,
}
} else {
IntoIter {
head: None,
tail: None,
tree: self,
}
}
}
}
impl<'a, A: Adapter + 'a> IntoIterator for &'a RBTree<A>
where
A::LinkOps: RBTreeOps,
{
type Item = &'a <A::PointerOps as PointerOps>::Value;
type IntoIter = Iter<'a, A>;
#[inline]
fn into_iter(self) -> Iter<'a, A> {
self.iter()
}
}
impl<A: Adapter + Default> Default for RBTree<A>
where
A::LinkOps: RBTreeOps,
{
fn default() -> RBTree<A> {
RBTree::new(A::default())
}
}
impl<A: Adapter> fmt::Debug for RBTree<A>
where
A::LinkOps: RBTreeOps,
<A::PointerOps as PointerOps>::Value: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
// =============================================================================
// InsertCursor, Entry
// =============================================================================
/// A cursor pointing to a slot in which an element can be inserted into a
/// `RBTree`.
pub struct InsertCursor<'a, A: Adapter>
where
A::LinkOps: RBTreeOps,
{
parent: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
insert_left: bool,
tree: &'a mut RBTree<A>,
}
impl<'a, A: Adapter + 'a> InsertCursor<'a, A>
where
A::LinkOps: RBTreeOps,
{
/// Inserts a new element into the `RBTree` at the location indicated by
/// this `InsertCursor`.
///
/// # Panics
///
/// Panics if the new element is already linked to a different intrusive
/// collection.
pub fn insert(self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'a, A> {
unsafe {
let new = self.tree.node_from_value(val);
let link_ops = self.tree.adapter.link_ops_mut();
if let Some(parent) = self.parent {
if self.insert_left {
insert_left(link_ops, parent, new, &mut self.tree.root);
} else {
insert_right(link_ops, parent, new, &mut self.tree.root);
}
} else {
self.tree.insert_root(new);
}
CursorMut {
current: Some(new),
tree: self.tree,
}
}
}
}
/// An entry in a `RBTree`.
///
/// See the documentation for `RBTree::entry`.
pub enum Entry<'a, A: Adapter>
where
A::LinkOps: RBTreeOps,
{
/// An occupied entry.
Occupied(CursorMut<'a, A>),
/// A vacant entry.
Vacant(InsertCursor<'a, A>),
}
impl<'a, A: Adapter + 'a> Entry<'a, A>
where
A::LinkOps: RBTreeOps,
{
/// Inserts an element into the `RBTree` if the entry is vacant, returning
/// a `CursorMut` to the resulting value. If the entry is occupied then a
/// `CursorMut` pointing to the element is returned.
///
/// # Panics
///
/// Panics if the `Entry` is vacant and the new element is already linked to
/// a different intrusive collection.
pub fn or_insert(self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'a, A> {
match self {
Entry::Occupied(entry) => entry,
Entry::Vacant(entry) => entry.insert(val),
}
}
/// Calls the given function and inserts the result into the `RBTree` if the
/// entry is vacant, returning a `CursorMut` to the resulting value. If the
/// entry is occupied then a `CursorMut` pointing to the element is
/// returned and the function is not executed.
///
/// # Panics
///
/// Panics if the `Entry` is vacant and the new element is already linked to
/// a different intrusive collection.
pub fn or_insert_with<F>(self, default: F) -> CursorMut<'a, A>
where
F: FnOnce() -> <A::PointerOps as PointerOps>::Pointer,
{
match self {
Entry::Occupied(entry) => entry,
Entry::Vacant(entry) => entry.insert(default()),
}
}
}
// =============================================================================
// Iter
// =============================================================================
/// An iterator over references to the items of a `RBTree`.
pub struct Iter<'a, A: Adapter>
where
A::LinkOps: RBTreeOps,
{
head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tree: &'a RBTree<A>,
}
impl<'a, A: Adapter + 'a> Iterator for Iter<'a, A>
where
A::LinkOps: RBTreeOps,
{
type Item = &'a <A::PointerOps as PointerOps>::Value;
#[inline]
fn next(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
let head = self.head?;
if Some(head) == self.tail {
self.head = None;
self.tail = None;
} else {
self.head = unsafe { next(self.tree.adapter.link_ops(), head) };
}
Some(unsafe { &*self.tree.adapter.get_value(head) })
}
}
impl<'a, A: Adapter + 'a> DoubleEndedIterator for Iter<'a, A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn next_back(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
let tail = self.tail?;
if Some(tail) == self.head {
self.head = None;
self.tail = None;
} else {
self.tail = unsafe { prev(self.tree.adapter.link_ops(), tail) };
}
Some(unsafe { &*self.tree.adapter.get_value(tail) })
}
}
impl<'a, A: Adapter + 'a> Clone for Iter<'a, A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn clone(&self) -> Iter<'a, A> {
Iter {
head: self.head,
tail: self.tail,
tree: self.tree,
}
}
}
// =============================================================================
// IntoIter
// =============================================================================
/// An iterator which consumes a `RBTree`.
pub struct IntoIter<A: Adapter>
where
A::LinkOps: RBTreeOps,
{
head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
tree: RBTree<A>,
}
impl<A: Adapter> Iterator for IntoIter<A>
where
A::LinkOps: RBTreeOps,
{
type Item = <A::PointerOps as PointerOps>::Pointer;
#[inline]
fn next(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
use link_ops::LinkOps;
let head = self.head?;
let link_ops = self.tree.adapter.link_ops_mut();
unsafe {
// Remove the node from the tree. Since head is always the
// left-most node, we can infer the following:
// - head.left is null.
// - head is a left child of its parent (or the root node).
if let Some(parent) = link_ops.parent(head) {
link_ops.set_left(parent, link_ops.right(head));
} else {
self.tree.root = link_ops.right(head);
if link_ops.right(head).is_none() {
self.tail = None;
}
}
if let Some(right) = link_ops.right(head) {
link_ops.set_parent(right, link_ops.parent(head));
self.head = Some(first_child(link_ops, right));
} else {
self.head = link_ops.parent(head);
}
link_ops.release_link(head);
Some(
self.tree
.adapter
.pointer_ops()
.from_raw(self.tree.adapter.get_value(head)),
)
}
}
}
impl<A: Adapter> DoubleEndedIterator for IntoIter<A>
where
A::LinkOps: RBTreeOps,
{
#[inline]
fn next_back(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
use link_ops::LinkOps;
let tail = self.tail?;
let link_ops = self.tree.adapter.link_ops_mut();
unsafe {
// Remove the node from the tree. Since tail is always the
// right-most node, we can infer the following:
// - tail.right is null.
// - tail is a right child of its parent (or the root node).
if let Some(parent) = link_ops.parent(tail) {
link_ops.set_right(parent, link_ops.left(tail));
} else {
self.tree.root = link_ops.left(tail);
if link_ops.left(tail).is_none() {
self.tail = None;
}
}
if let Some(left) = link_ops.left(tail) {
link_ops.set_parent(left, link_ops.parent(tail));
self.tail = Some(last_child(link_ops, left));
} else {
self.tail = link_ops.parent(tail);
}
link_ops.release_link(tail);
Some(
self.tree
.adapter
.pointer_ops()
.from_raw(self.tree.adapter.get_value(tail)),
)
}
}
}
// =============================================================================
// Tests
// =============================================================================
#[cfg(test)]
mod tests {
use super::{Entry, KeyAdapter, Link, PointerOps, RBTree};
use crate::Bound::*;
use rand::prelude::*;
use rand_xorshift::XorShiftRng;
use std::fmt;
use std::rc::Rc;
use std::vec::Vec;
use std::{format, vec};
#[derive(Clone)]
struct Obj {
link: Link,
value: i32,
}
impl fmt::Debug for Obj {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.value)
}
}
intrusive_adapter!(ObjAdapter = Rc<Obj>: Obj { link: Link });
impl<'a> KeyAdapter<'a> for ObjAdapter {
type Key = i32;
fn get_key(&self, value: &'a <Self::PointerOps as PointerOps>::Value) -> i32 {
value.value
}
}
fn make_obj(value: i32) -> Rc<Obj> {
Rc::new(Obj {
link: Link::new(),
value,
})
}
#[test]
fn test_link() {
let a = make_obj(1);
assert!(!a.link.is_linked());
assert_eq!(format!("{:?}", a.link), "unlinked");
let mut b = RBTree::<ObjAdapter>::default();
assert!(b.is_empty());
assert_eq!(b.insert(a.clone()).get().unwrap().value, 1);
assert!(!b.is_empty());
assert!(a.link.is_linked());
assert_eq!(format!("{:?}", a.link), "linked");
let c = a.as_ref().clone();
assert!(!c.link.is_linked());
unsafe {
assert_eq!(b.cursor_from_ptr(a.as_ref()).get().unwrap().value, 1);
assert_eq!(b.cursor_mut_from_ptr(a.as_ref()).get().unwrap().value, 1);
}
assert_eq!(
b.front_mut().remove().unwrap().as_ref() as *const _,
a.as_ref() as *const _
);
assert!(b.is_empty());
assert!(!a.link.is_linked());
}
#[test]
fn test_cursor() {
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let mut t = RBTree::new(ObjAdapter::new());
let mut cur = t.cursor_mut();
assert!(cur.is_null());
assert!(cur.get().is_none());
assert!(cur.remove().is_none());
cur.insert_before(a.clone());
cur.insert_before(c.clone());
cur.move_prev();
cur.insert(b.clone());
assert!(cur.peek_next().is_null());
cur.move_next();
assert!(cur.is_null());
cur.move_next();
assert!(cur.peek_prev().is_null());
assert!(!cur.is_null());
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
{
let mut cur2 = cur.as_cursor();
assert_eq!(cur2.get().unwrap() as *const _, a.as_ref() as *const _);
assert_eq!(cur2.peek_next().get().unwrap().value, 2);
cur2.move_next();
assert_eq!(cur2.get().unwrap().value, 2);
cur2.move_next();
assert_eq!(cur2.peek_prev().get().unwrap().value, 2);
assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
cur2.move_prev();
assert_eq!(cur2.get().unwrap() as *const _, b.as_ref() as *const _);
cur2.move_next();
assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
cur2.move_next();
assert!(cur2.is_null());
assert!(cur2.clone().get().is_none());
}
assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
let a2 = make_obj(1);
let b2 = make_obj(2);
let c2 = make_obj(3);
assert_eq!(
cur.replace_with(a2.clone()).unwrap().as_ref() as *const _,
a.as_ref() as *const _
);
assert!(!a.link.is_linked());
cur.move_next();
assert_eq!(
cur.replace_with(b2.clone()).unwrap().as_ref() as *const _,
b.as_ref() as *const _
);
assert!(!b.link.is_linked());
cur.move_next();
assert_eq!(
cur.replace_with(c2.clone()).unwrap().as_ref() as *const _,
c.as_ref() as *const _
);
assert!(!c.link.is_linked());
cur.move_next();
assert_eq!(
cur.replace_with(c.clone()).unwrap_err().as_ref() as *const _,
c.as_ref() as *const _
);
}
#[cfg(not(miri))]
#[test]
fn test_insert_remove() {
let v = (0..100).map(make_obj).collect::<Vec<_>>();
assert!(v.iter().all(|x| !x.link.is_linked()));
let mut t = RBTree::new(ObjAdapter::new());
assert!(t.is_empty());
let mut rng = XorShiftRng::seed_from_u64(0);
{
let mut expected = Vec::new();
for x in v.iter() {
t.insert(x.clone());
expected.push(x.value);
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
while let Some(x) = t.front_mut().remove() {
assert_eq!(x.value, expected.remove(0));
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
assert!(expected.is_empty());
assert!(t.is_empty());
}
{
let mut expected = Vec::new();
for x in v.iter().rev() {
t.insert(x.clone());
expected.insert(0, x.value);
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
while let Some(x) = t.back_mut().remove() {
assert_eq!(x.value, expected.pop().unwrap());
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
assert!(expected.is_empty());
assert!(t.is_empty());
}
{
let mut indices = (0..v.len()).collect::<Vec<_>>();
indices.shuffle(&mut rng);
let mut expected = Vec::new();
for i in indices {
t.insert(v[i].clone());
expected.push(v[i].value);
expected[..].sort();
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
while !expected.is_empty() {
{
let index = rng.gen_range(0..expected.len());
let mut c = t.cursor_mut();
for _ in 0..(index + 1) {
c.move_next();
}
assert_eq!(c.remove().unwrap().value, expected.remove(index));
}
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
assert!(t.is_empty());
}
{
let mut indices = (0..v.len()).collect::<Vec<_>>();
indices.shuffle(&mut rng);
let mut expected = Vec::new();
for i in indices {
{
let mut c = t.front_mut();
loop {
if let Some(x) = c.get() {
if x.value > v[i].value {
break;
}
} else {
break;
}
c.move_next();
}
c.insert_before(v[i].clone());
}
expected.push(v[i].value);
expected[..].sort();
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
t.clear();
assert!(t.is_empty());
}
{
let mut indices = (0..v.len()).collect::<Vec<_>>();
indices.shuffle(&mut rng);
let mut expected = Vec::new();
for i in indices {
{
let mut c = t.back_mut();
loop {
if let Some(x) = c.get() {
if x.value < v[i].value {
break;
}
} else {
break;
}
c.move_prev();
}
c.insert_after(v[i].clone());
}
expected.push(v[i].value);
expected[..].sort();
assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
}
}
}
#[cfg(not(miri))]
#[test]
fn test_iter() {
let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>();
let mut t = RBTree::new(ObjAdapter::new());
for x in v.iter() {
t.insert(x.clone());
}
assert_eq!(
format!("{:?}", t),
"{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}"
);
assert_eq!(
t.iter().clone().map(|x| x.value).collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
(&t).into_iter().rev().map(|x| x.value).collect::<Vec<_>>(),
vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0]
);
assert_eq!(
t.range(Unbounded, Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Included(&0), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Excluded(&0), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![10, 20, 30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Included(&25), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Excluded(&25), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Included(&70), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![70, 80, 90]
);
assert_eq!(
t.range(Excluded(&70), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![80, 90]
);
assert_eq!(
t.range(Included(&100), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&100), Unbounded)
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Unbounded, Included(&90))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
);
assert_eq!(
t.range(Unbounded, Excluded(&90))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70, 80]
);
assert_eq!(
t.range(Unbounded, Included(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20]
);
assert_eq!(
t.range(Unbounded, Excluded(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20]
);
assert_eq!(
t.range(Unbounded, Included(&70))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60, 70]
);
assert_eq!(
t.range(Unbounded, Excluded(&70))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![0, 10, 20, 30, 40, 50, 60]
);
assert_eq!(
t.range(Unbounded, Included(&-1))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Unbounded, Excluded(&-1))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Included(&25), Included(&80))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70, 80]
);
assert_eq!(
t.range(Included(&25), Excluded(&80))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70]
);
assert_eq!(
t.range(Excluded(&25), Included(&80))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70, 80]
);
assert_eq!(
t.range(Excluded(&25), Excluded(&80))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![30, 40, 50, 60, 70]
);
assert_eq!(
t.range(Included(&25), Included(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Included(&25), Excluded(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&25), Included(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&25), Excluded(&25))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Included(&50), Included(&50))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![50]
);
assert_eq!(
t.range(Included(&50), Excluded(&50))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&50), Included(&50))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&50), Excluded(&50))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Included(&100), Included(&-2))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Included(&100), Excluded(&-2))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&100), Included(&-2))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
assert_eq!(
t.range(Excluded(&100), Excluded(&-2))
.map(|x| x.value)
.collect::<Vec<_>>(),
vec![]
);
let mut v2 = Vec::new();
for x in t.take() {
v2.push(x.value);
}
assert_eq!(v2, vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]);
assert!(t.is_empty());
for _ in t.take() {
unreachable!();
}
for x in v.iter() {
t.insert(x.clone());
}
v2.clear();
for x in t.into_iter().rev() {
v2.push(x.value);
}
assert_eq!(v2, vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0]);
}
#[test]
fn test_find() {
let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>();
let mut t = RBTree::new(ObjAdapter::new());
for x in v.iter() {
t.insert(x.clone());
}
for i in -9..100 {
fn mod10(x: i32) -> i32 {
if x < 0 {
10 + x % 10
} else {
x % 10
}
}
{
let c = t.find(&i);
assert_eq!(
c.get().map(|x| x.value),
if i % 10 == 0 { Some(i) } else { None }
);
}
{
let c = t.find_mut(&i);
assert_eq!(
c.get().map(|x| x.value),
if i % 10 == 0 { Some(i) } else { None }
);
}
{
let c = t.upper_bound(Unbounded);
assert_eq!(c.get().map(|x| x.value), Some(90));
}
{
let c = t.upper_bound_mut(Unbounded);
assert_eq!(c.get().map(|x| x.value), Some(90));
}
{
let c = t.upper_bound(Included(&i));
assert_eq!(
c.get().map(|x| x.value),
if i >= 0 { Some(i - mod10(i)) } else { None }
);
}
{
let c = t.upper_bound_mut(Included(&i));
assert_eq!(
c.get().map(|x| x.value),
if i >= 0 { Some(i - mod10(i)) } else { None }
);
}
{
let c = t.upper_bound(Excluded(&i));
assert_eq!(
c.get().map(|x| x.value),
if i > 0 {
Some(i - 1 - mod10(i - 1))
} else {
None
}
);
}
{
let c = t.upper_bound_mut(Excluded(&i));
assert_eq!(
c.get().map(|x| x.value),
if i > 0 {
Some(i - 1 - mod10(i - 1))
} else {
None
}
);
}
{
let c = t.lower_bound(Unbounded);
assert_eq!(c.get().map(|x| x.value), Some(0));
}
{
let c = t.lower_bound_mut(Unbounded);
assert_eq!(c.get().map(|x| x.value), Some(0));
}
{
let c = t.lower_bound(Included(&i));
assert_eq!(
c.get().map(|x| x.value),
if i <= 90 {
Some((i + 9) - mod10(i + 9))
} else {
None
}
);
}
{
let c = t.lower_bound_mut(Included(&i));
assert_eq!(
c.get().map(|x| x.value),
if i <= 90 {
Some((i + 9) - mod10(i + 9))
} else {
None
}
);
}
{
let c = t.lower_bound(Excluded(&i));
assert_eq!(
c.get().map(|x| x.value),
if i < 90 {
Some((i + 10) - mod10(i + 10))
} else {
None
}
);
}
{
let c = t.lower_bound_mut(Excluded(&i));
assert_eq!(
c.get().map(|x| x.value),
if i < 90 {
Some((i + 10) - mod10(i + 10))
} else {
None
}
);
}
}
}
#[test]
fn test_fast_clear() {
let mut t = RBTree::new(ObjAdapter::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
t.insert(a.clone());
t.insert(b.clone());
t.insert(c.clone());
t.fast_clear();
assert!(t.is_empty());
assert!(a.link.is_linked());
assert!(b.link.is_linked());
assert!(c.link.is_linked());
unsafe {
a.link.force_unlink();
b.link.force_unlink();
c.link.force_unlink();
}
assert!(t.is_empty());
assert!(!a.link.is_linked());
assert!(!b.link.is_linked());
assert!(!c.link.is_linked());
}
#[test]
fn test_entry() {
let mut t = RBTree::new(ObjAdapter::new());
let a = make_obj(1);
let b = make_obj(2);
let c = make_obj(3);
let d = make_obj(4);
let e = make_obj(5);
let f = make_obj(6);
t.entry(&3).or_insert(c.clone());
t.entry(&2).or_insert(b.clone());
t.entry(&1).or_insert(a.clone());
match t.entry(&2) {
Entry::Vacant(_) => unreachable!(),
Entry::Occupied(c) => assert_eq!(c.get().unwrap().value, 2),
}
assert_eq!(t.entry(&2).or_insert(b.clone()).get().unwrap().value, 2);
assert_eq!(
t.entry(&2)
.or_insert_with(|| b.clone())
.get()
.unwrap()
.value,
2
);
match t.entry(&5) {
Entry::Vacant(c) => assert_eq!(c.insert(e.clone()).get().unwrap().value, 5),
Entry::Occupied(_) => unreachable!(),
}
assert!(e.link.is_linked());
assert_eq!(t.entry(&4).or_insert(d.clone()).get().unwrap().value, 4);
assert!(d.link.is_linked());
assert_eq!(
t.entry(&6)
.or_insert_with(|| f.clone())
.get()
.unwrap()
.value,
6
);
assert!(f.link.is_linked());
}
#[test]
fn test_non_static() {
#[derive(Clone)]
struct Obj<'a, T> {
link: Link,
value: &'a T,
}
intrusive_adapter!(ObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a);
impl<'a, 'b, T: 'a + 'b> KeyAdapter<'a> for ObjAdapter<'b, T> {
type Key = &'a T;
fn get_key(&self, value: &'a Obj<'b, T>) -> &'a T {
value.value
}
}
let v = 5;
let a = Obj {
link: Link::default(),
value: &v,
};
let b = a.clone();
let mut l = RBTree::new(ObjAdapter::new());
l.insert(&a);
l.insert(&b);
assert_eq!(*l.front().get().unwrap().value, 5);
assert_eq!(*l.back().get().unwrap().value, 5);
}
macro_rules! test_clone_pointer {
($ptr: ident, $ptr_import: path) => {
use $ptr_import;
#[derive(Clone)]
struct Obj {
link: Link,
value: usize,
}
intrusive_adapter!(ObjAdapter = $ptr<Obj>: Obj { link: Link });
impl<'a> KeyAdapter<'a> for ObjAdapter {
type Key = usize;
fn get_key(&self, value: &'a Obj) -> usize {
value.value
}
}
let a = $ptr::new(Obj {
link: Link::new(),
value: 5,
});
let mut l = RBTree::new(ObjAdapter::new());
l.insert(a.clone());
assert_eq!(2, $ptr::strong_count(&a));
let pointer = l.front().clone_pointer().unwrap();
assert_eq!(pointer.value, 5);
assert_eq!(3, $ptr::strong_count(&a));
l.front_mut().remove();
assert!(l.front().clone_pointer().is_none());
};
}
#[test]
fn test_clone_pointer_rc() {
test_clone_pointer!(Rc, std::rc::Rc);
}
#[test]
fn test_clone_pointer_arc() {
test_clone_pointer!(Arc, std::sync::Arc);
}
}