use crate::Bound::{self, Excluded, Included, Unbounded};
use crate::IntrusivePointer;
use crate::{Adapter, KeyAdapter};
use core::borrow::Borrow;
use core::cell::Cell;
use core::cmp::Ordering;
use core::fmt;
use core::mem;
use core::ptr;
pub struct Link {
left: Cell<NodePtr>,
right: Cell<NodePtr>,
parent_color: Cell<usize>,
}
impl Link {
#[inline]
pub const fn new() -> Link {
Link {
left: Cell::new(NodePtr(ptr::null())),
right: Cell::new(NodePtr(ptr::null())),
parent_color: Cell::new(UNLINKED_MARKER),
}
}
#[inline]
pub fn is_linked(&self) -> bool {
self.parent_color.get() != UNLINKED_MARKER
}
#[inline]
pub unsafe fn force_unlink(&self) {
self.parent_color.set(UNLINKED_MARKER);
}
}
unsafe impl Send for Link {}
impl Clone for Link {
#[inline]
fn clone(&self) -> Link {
Link::new()
}
}
impl Default for Link {
#[inline]
fn default() -> Link {
Link::new()
}
}
impl fmt::Debug for Link {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_linked() {
write!(f, "linked")
} else {
write!(f, "unlinked")
}
}
}
#[derive(Copy, Clone, PartialEq, Eq)]
enum Color {
Red,
Black,
}
#[derive(Copy, Clone, PartialEq, Eq)]
struct NodePtr(*const Link);
const UNLINKED_MARKER: usize = 0;
impl NodePtr {
#[inline]
fn null() -> NodePtr {
NodePtr(ptr::null())
}
#[inline]
fn is_null(self) -> bool {
self.0.is_null()
}
#[inline]
unsafe fn unlink(self) {
(*self.0).parent_color.set(UNLINKED_MARKER);
}
#[inline]
unsafe fn parent(self) -> NodePtr {
NodePtr(((*self.0).parent_color.get() & !1) as *const _)
}
#[inline]
unsafe fn color(self) -> Color {
if (*self.0).parent_color.get() & 1 == 1 {
Color::Black
} else {
Color::Red
}
}
#[inline]
unsafe fn set_parent_color(self, parent: NodePtr, color: Color) {
assert!(mem::align_of::<Link>() >= 2);
let bit = match color {
Color::Red => 0,
Color::Black => 1,
};
(*self.0).parent_color.set((parent.0 as usize & !1) | bit);
}
#[inline]
unsafe fn set_parent(self, parent: NodePtr) {
self.set_parent_color(parent, self.color());
}
#[inline]
unsafe fn set_color(self, color: Color) {
self.set_parent_color(self.parent(), color);
}
#[inline]
unsafe fn left(self) -> NodePtr {
(*self.0).left.get()
}
#[inline]
unsafe fn right(self) -> NodePtr {
(*self.0).right.get()
}
#[inline]
unsafe fn set_left(self, left: NodePtr) {
(*self.0).left.set(left);
}
#[inline]
unsafe fn set_right(self, right: NodePtr) {
(*self.0).right.set(right);
}
#[inline]
unsafe fn is_left_child(self) -> bool {
self.parent().left() == self
}
#[inline]
unsafe fn first_child(self) -> NodePtr {
if self.is_null() {
NodePtr::null()
} else {
let mut x = self;
while !x.left().is_null() {
x = x.left();
}
x
}
}
#[inline]
unsafe fn last_child(self) -> NodePtr {
if self.is_null() {
NodePtr::null()
} else {
let mut x = self;
while !x.right().is_null() {
x = x.right();
}
x
}
}
unsafe fn next(self) -> NodePtr {
if !self.right().is_null() {
self.right().first_child()
} else {
let mut x = self;
loop {
if x.parent().is_null() {
return NodePtr::null();
}
if x.is_left_child() {
return x.parent();
}
x = x.parent();
}
}
}
unsafe fn prev(self) -> NodePtr {
if !self.left().is_null() {
self.left().last_child()
} else {
let mut x = self;
loop {
if x.parent().is_null() {
return NodePtr::null();
}
if !x.is_left_child() {
return x.parent();
}
x = x.parent();
}
}
}
unsafe fn replace_with(self, new: NodePtr, root: &mut NodePtr) {
if self.parent().is_null() {
*root = new;
} else if self.is_left_child() {
self.parent().set_left(new);
} else {
self.parent().set_right(new);
}
if !self.left().is_null() {
self.left().set_parent(new);
}
if !self.right().is_null() {
self.right().set_parent(new);
}
new.set_left(self.left());
new.set_right(self.right());
new.set_parent_color(self.parent(), self.color());
self.unlink();
}
#[inline]
unsafe fn insert_left(self, new: NodePtr, root: &mut NodePtr) {
new.set_parent_color(self, Color::Red);
new.set_left(NodePtr::null());
new.set_right(NodePtr::null());
self.set_left(new);
new.post_insert(root);
}
#[inline]
unsafe fn insert_right(self, new: NodePtr, root: &mut NodePtr) {
new.set_parent_color(self, Color::Red);
new.set_left(NodePtr::null());
new.set_right(NodePtr::null());
self.set_right(new);
new.post_insert(root);
}
unsafe fn rotate_left(self, root: &mut NodePtr) {
let y = self.right();
self.set_right(y.left());
if !self.right().is_null() {
self.right().set_parent(self);
}
y.set_parent(self.parent());
if self.parent().is_null() {
*root = y;
} else if self.is_left_child() {
self.parent().set_left(y);
} else {
self.parent().set_right(y);
}
y.set_left(self);
self.set_parent(y);
}
unsafe fn rotate_right(self, root: &mut NodePtr) {
let y = self.left();
self.set_left(y.right());
if !self.left().is_null() {
self.left().set_parent(self);
}
y.set_parent(self.parent());
if self.parent().is_null() {
*root = y;
} else if self.is_left_child() {
self.parent().set_left(y);
} else {
self.parent().set_right(y);
}
y.set_right(self);
self.set_parent(y);
}
unsafe fn post_insert(self, root: &mut NodePtr) {
let mut x = self;
while !x.parent().is_null() && x.parent().color() == Color::Red {
if x.parent().is_left_child() {
let y = x.parent().parent().right();
if !y.is_null() && y.color() == Color::Red {
x = x.parent();
x.set_color(Color::Black);
x = x.parent();
if x.parent().is_null() {
x.set_color(Color::Black);
} else {
x.set_color(Color::Red);
}
y.set_color(Color::Black);
} else {
if !x.is_left_child() {
x = x.parent();
x.rotate_left(root);
}
x = x.parent();
x.set_color(Color::Black);
x = x.parent();
x.set_color(Color::Red);
x.rotate_right(root);
break;
}
} else {
let y = x.parent().parent().left();
if !y.is_null() && y.color() == Color::Red {
x = x.parent();
x.set_color(Color::Black);
x = x.parent();
if x.parent().is_null() {
x.set_color(Color::Black);
} else {
x.set_color(Color::Red);
}
y.set_color(Color::Black);
} else {
if x.is_left_child() {
x = x.parent();
x.rotate_right(root);
}
x = x.parent();
x.set_color(Color::Black);
x = x.parent();
x.set_color(Color::Red);
x.rotate_left(root);
break;
}
}
}
}
unsafe fn remove(self, root: &mut NodePtr) {
let y = if self.left().is_null() || self.right().is_null() {
self
} else {
self.next()
};
let mut x = if !y.left().is_null() {
y.left()
} else {
y.right()
};
let mut w = NodePtr::null();
if !x.is_null() {
x.set_parent(y.parent());
}
if y.parent().is_null() {
*root = x;
} else if y.is_left_child() {
y.parent().set_left(x);
w = y.parent().right();
} else {
y.parent().set_right(x);
w = y.parent().left();
}
let removed_black = y.color() == Color::Black;
if y != self {
y.set_parent(self.parent());
if self.parent().is_null() {
*root = y;
} else if self.is_left_child() {
y.parent().set_left(y);
} else {
y.parent().set_right(y);
}
y.set_left(self.left());
y.left().set_parent(y);
y.set_right(self.right());
if !y.right().is_null() {
y.right().set_parent(y);
}
y.set_color(self.color());
}
if removed_black && !root.is_null() {
if !x.is_null() {
x.set_color(Color::Black);
} else {
loop {
if !w.is_left_child() {
if w.color() == Color::Red {
w.set_color(Color::Black);
w.parent().set_color(Color::Red);
w.parent().rotate_left(root);
w = w.left().right();
}
if (w.left().is_null() || w.left().color() == Color::Black)
&& (w.right().is_null() || w.right().color() == Color::Black)
{
w.set_color(Color::Red);
x = w.parent();
if x.parent().is_null() || x.color() == Color::Red {
x.set_color(Color::Black);
break;
}
w = if x.is_left_child() {
x.parent().right()
} else {
x.parent().left()
};
} else {
if w.right().is_null() || w.right().color() == Color::Black {
w.left().set_color(Color::Black);
w.set_color(Color::Red);
w.rotate_right(root);
w = w.parent();
}
w.set_color(w.parent().color());
w.parent().set_color(Color::Black);
w.right().set_color(Color::Black);
w.parent().rotate_left(root);
break;
}
} else {
if w.color() == Color::Red {
w.set_color(Color::Black);
w.parent().set_color(Color::Red);
w.parent().rotate_right(root);
w = w.right().left();
}
if (w.left().is_null() || w.left().color() == Color::Black)
&& (w.right().is_null() || w.right().color() == Color::Black)
{
w.set_color(Color::Red);
x = w.parent();
if x.parent().is_null() || x.color() == Color::Red {
x.set_color(Color::Black);
break;
}
w = if x.is_left_child() {
x.parent().right()
} else {
x.parent().left()
};
} else {
if w.left().is_null() || w.left().color() == Color::Black {
w.right().set_color(Color::Black);
w.set_color(Color::Red);
w.rotate_left(root);
w = w.parent();
}
w.set_color(w.parent().color());
w.parent().set_color(Color::Black);
w.left().set_color(Color::Black);
w.parent().rotate_right(root);
break;
}
}
}
}
}
self.unlink();
}
}
pub struct Cursor<'a, A: Adapter<Link = Link>> {
current: NodePtr,
tree: &'a RBTree<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> Clone for Cursor<'a, A> {
#[inline]
fn clone(&self) -> Cursor<'a, A> {
Cursor {
current: self.current,
tree: self.tree,
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> Cursor<'a, A> {
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_null()
}
#[inline]
pub fn get(&self) -> Option<&'a A::Value> {
if self.is_null() {
None
} else {
Some(unsafe { &*self.tree.adapter.get_value(self.current.0) })
}
}
#[inline]
pub fn clone_pointer(&self) -> Option<A::Pointer>
where
A::Pointer: Clone,
{
let raw_pointer = self.get()? as *const A::Value;
Some(unsafe { crate::intrusive_pointer::clone_pointer_from_raw(raw_pointer) })
}
#[inline]
pub fn move_next(&mut self) {
if self.is_null() {
self.current = unsafe { self.tree.root.first_child() };
} else {
self.current = unsafe { self.current.next() };
}
}
#[inline]
pub fn move_prev(&mut self) {
if self.is_null() {
self.current = unsafe { self.tree.root.last_child() };
} else {
self.current = unsafe { self.current.prev() };
}
}
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.clone();
next.move_next();
next
}
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.clone();
prev.move_prev();
prev
}
}
pub struct CursorMut<'a, A: Adapter<Link = Link>> {
current: NodePtr,
tree: &'a mut RBTree<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> CursorMut<'a, A> {
#[inline]
pub fn is_null(&self) -> bool {
self.current.is_null()
}
#[inline]
pub fn get(&self) -> Option<&A::Value> {
if self.is_null() {
None
} else {
Some(unsafe { &*self.tree.adapter.get_value(self.current.0) })
}
}
#[inline]
pub fn as_cursor(&self) -> Cursor<'_, A> {
Cursor {
current: self.current,
tree: self.tree,
}
}
#[inline]
pub fn move_next(&mut self) {
if self.is_null() {
self.current = unsafe { self.tree.root.first_child() };
} else {
self.current = unsafe { self.current.next() };
}
}
#[inline]
pub fn move_prev(&mut self) {
if self.is_null() {
self.current = unsafe { self.tree.root.last_child() };
} else {
self.current = unsafe { self.current.prev() };
}
}
#[inline]
pub fn peek_next(&self) -> Cursor<'_, A> {
let mut next = self.as_cursor();
next.move_next();
next
}
#[inline]
pub fn peek_prev(&self) -> Cursor<'_, A> {
let mut prev = self.as_cursor();
prev.move_prev();
prev
}
#[inline]
pub fn remove(&mut self) -> Option<A::Pointer> {
unsafe {
if self.is_null() {
return None;
}
let next = self.current.next();
let result = self.current.0;
self.current.remove(&mut self.tree.root);
self.current = next;
Some(A::Pointer::from_raw(self.tree.adapter.get_value(result)))
}
}
#[inline]
pub fn replace_with(&mut self, val: A::Pointer) -> Result<A::Pointer, A::Pointer> {
if self.is_null() {
return Err(val);
}
unsafe {
let new = self.tree.node_from_value(val);
let result = self.current.0;
self.current.replace_with(new, &mut self.tree.root);
self.current = new;
Ok(A::Pointer::from_raw(self.tree.adapter.get_value(result)))
}
}
#[inline]
pub fn insert_after(&mut self, val: A::Pointer) {
unsafe {
let new = self.tree.node_from_value(val);
if self.tree.is_empty() {
self.tree.insert_root(new);
} else if self.is_null() {
self.tree
.root
.first_child()
.insert_left(new, &mut self.tree.root);
} else if self.current.right().is_null() {
self.current.insert_right(new, &mut self.tree.root);
} else {
self.current.next().insert_left(new, &mut self.tree.root);
}
}
}
#[inline]
pub fn insert_before(&mut self, val: A::Pointer) {
unsafe {
let new = self.tree.node_from_value(val);
if self.tree.is_empty() {
self.tree.insert_root(new);
} else if self.is_null() {
self.tree
.root
.last_child()
.insert_right(new, &mut self.tree.root);
} else if self.current.left().is_null() {
self.current.insert_left(new, &mut self.tree.root);
} else {
self.current.prev().insert_right(new, &mut self.tree.root);
}
}
}
}
impl<'a, A: for<'b> KeyAdapter<'b, Link = Link>> CursorMut<'a, A> {
#[inline]
pub fn insert<'c>(&'c mut self, val: A::Pointer)
where
<A as KeyAdapter<'c>>::Key: Ord,
{
self.tree.insert(val);
}
}
pub struct RBTree<A: Adapter<Link = Link>> {
root: NodePtr,
adapter: A,
}
impl<A: Adapter<Link = Link>> RBTree<A> {
#[inline]
fn node_from_value(&self, val: A::Pointer) -> NodePtr {
unsafe {
assert!(
!(*self.adapter.get_link(&*val)).is_linked(),
"attempted to insert an object that is already linked"
);
NodePtr(self.adapter.get_link(val.into_raw()))
}
}
#[cfg(feature = "nightly")]
#[inline]
pub const fn new(adapter: A) -> RBTree<A> {
RBTree {
root: NodePtr(ptr::null()),
adapter,
}
}
#[cfg(not(feature = "nightly"))]
#[inline]
pub fn new(adapter: A) -> RBTree<A> {
RBTree {
root: NodePtr::null(),
adapter,
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.root.is_null()
}
#[inline]
pub fn cursor(&self) -> Cursor<'_, A> {
Cursor {
current: NodePtr::null(),
tree: self,
}
}
#[inline]
pub fn cursor_mut(&mut self) -> CursorMut<'_, A> {
CursorMut {
current: NodePtr::null(),
tree: self,
}
}
#[inline]
pub unsafe fn cursor_from_ptr(&self, ptr: *const A::Value) -> Cursor<'_, A> {
Cursor {
current: NodePtr(self.adapter.get_link(ptr)),
tree: self,
}
}
#[inline]
pub unsafe fn cursor_mut_from_ptr(&mut self, ptr: *const A::Value) -> CursorMut<'_, A> {
CursorMut {
current: NodePtr(self.adapter.get_link(ptr)),
tree: self,
}
}
#[inline]
pub fn front(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_next();
cursor
}
#[inline]
pub fn front_mut(&mut self) -> CursorMut<'_, A> {
let mut cursor = self.cursor_mut();
cursor.move_next();
cursor
}
#[inline]
pub fn back(&self) -> Cursor<'_, A> {
let mut cursor = self.cursor();
cursor.move_prev();
cursor
}
#[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: NodePtr) {
node.set_parent_color(NodePtr::null(), Color::Black);
node.set_left(NodePtr::null());
node.set_right(NodePtr::null());
self.root = node;
}
#[inline]
pub fn iter(&self) -> Iter<'_, A> {
if self.root.is_null() {
Iter {
head: NodePtr::null(),
tail: NodePtr::null(),
tree: self,
}
} else {
Iter {
head: unsafe { self.root.first_child() },
tail: unsafe { self.root.last_child() },
tree: self,
}
}
}
#[inline]
fn clear_recurse(&mut self, current: NodePtr) {
if !current.is_null() {
unsafe {
self.clear_recurse(current.left());
self.clear_recurse(current.right());
current.unlink();
A::Pointer::from_raw(self.adapter.get_value(current.0));
}
}
}
#[inline]
pub fn clear(&mut self) {
let root = self.root;
self.root = NodePtr::null();
self.clear_recurse(root);
}
#[inline]
pub fn fast_clear(&mut self) {
self.root = NodePtr::null();
}
#[inline]
pub fn take(&mut self) -> RBTree<A>
where
A: Clone,
{
let tree = RBTree {
root: self.root,
adapter: self.adapter.clone(),
};
self.root = NodePtr::null();
tree
}
}
impl<A: for<'a> KeyAdapter<'a, Link = Link>> RBTree<A> {
#[inline]
fn find_internal<'a, Q: ?Sized + Ord>(&self, key: &Q) -> NodePtr
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
A::Value: 'a,
{
let mut tree = self.root;
while !tree.is_null() {
let current = unsafe { &*self.adapter.get_value(tree.0) };
match key.cmp(self.adapter.get_key(current).borrow()) {
Ordering::Less => tree = unsafe { tree.left() },
Ordering::Equal => return tree,
Ordering::Greater => tree = unsafe { tree.right() },
}
}
NodePtr::null()
}
#[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,
}
}
#[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>) -> NodePtr
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
A::Value: 'a,
{
let mut tree = self.root;
let mut result = NodePtr::null();
while !tree.is_null() {
let current = unsafe { &*self.adapter.get_value(tree.0) };
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 { tree.left() };
} else {
tree = unsafe { tree.right() };
}
}
result
}
#[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,
}
}
#[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>) -> NodePtr
where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
A::Value: 'a,
{
let mut tree = self.root;
let mut result = NodePtr::null();
while !tree.is_null() {
let current = unsafe { &*self.adapter.get_value(tree.0) };
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 { tree.left() };
} else {
result = tree;
tree = unsafe { tree.right() };
}
}
result
}
#[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,
}
}
#[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,
}
}
#[inline]
pub fn insert<'a>(&'a mut self, val: A::Pointer) -> CursorMut<'_, A>
where
<A as KeyAdapter<'a>>::Key: Ord,
{
unsafe {
let raw = &*val as *const _;
let new = self.node_from_value(val);
if self.is_empty() {
self.insert_root(new);
} else {
let key = self.adapter.get_key(&*raw);
let mut tree = self.root;
loop {
let current = &*self.adapter.get_value(tree.0);
if key < self.adapter.get_key(current) {
if tree.left().is_null() {
tree.insert_left(new, &mut self.root);
break;
} else {
tree = tree.left();
}
} else {
if tree.right().is_null() {
tree.insert_right(new, &mut self.root);
break;
} else {
tree = tree.right();
}
}
}
}
CursorMut {
current: new,
tree: self,
}
}
}
#[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 self.is_empty() {
Entry::Vacant(InsertCursor {
parent: NodePtr::null(),
insert_left: false,
tree: self,
})
} else {
let mut tree = self.root;
loop {
let current = &*self.adapter.get_value(tree.0);
match key.cmp(self.adapter.get_key(current).borrow()) {
Ordering::Less => {
if tree.left().is_null() {
return Entry::Vacant(InsertCursor {
parent: tree,
insert_left: true,
tree: self,
});
} else {
tree = tree.left();
}
}
Ordering::Equal => {
return Entry::Occupied(CursorMut {
current: tree,
tree: self,
});
}
Ordering::Greater => {
if tree.right().is_null() {
return Entry::Vacant(InsertCursor {
parent: tree,
insert_left: false,
tree: self,
});
} else {
tree = tree.right();
}
}
}
}
}
}
}
#[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 !lower.is_null() && !upper.is_null() {
let lower_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(lower.0)) };
let upper_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(upper.0)) };
if upper_key >= lower_key {
return Iter {
head: lower,
tail: upper,
tree: self,
};
}
}
Iter {
head: NodePtr::null(),
tail: NodePtr::null(),
tree: self,
}
}
}
unsafe impl<A: Adapter<Link = Link> + Sync> Sync for RBTree<A> where A::Value: Sync {}
unsafe impl<A: Adapter<Link = Link> + Send> Send for RBTree<A> where A::Pointer: Send {}
impl<A: Adapter<Link = Link>> Drop for RBTree<A> {
#[inline]
fn drop(&mut self) {
self.clear();
}
}
impl<A: Adapter<Link = Link>> IntoIterator for RBTree<A> {
type Item = A::Pointer;
type IntoIter = IntoIter<A>;
#[inline]
fn into_iter(self) -> IntoIter<A> {
if self.root.is_null() {
IntoIter {
head: NodePtr::null(),
tail: NodePtr::null(),
tree: self,
}
} else {
IntoIter {
head: unsafe { self.root.first_child() },
tail: unsafe { self.root.last_child() },
tree: self,
}
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> IntoIterator for &'a RBTree<A> {
type Item = &'a A::Value;
type IntoIter = Iter<'a, A>;
#[inline]
fn into_iter(self) -> Iter<'a, A> {
self.iter()
}
}
impl<A: Adapter<Link = Link> + Default> Default for RBTree<A> {
fn default() -> RBTree<A> {
RBTree::new(A::default())
}
}
impl<A: Adapter<Link = Link>> fmt::Debug for RBTree<A>
where
A::Value: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
pub struct InsertCursor<'a, A: Adapter<Link = Link>> {
parent: NodePtr,
insert_left: bool,
tree: &'a mut RBTree<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> InsertCursor<'a, A> {
pub fn insert(self, val: A::Pointer) -> CursorMut<'a, A> {
unsafe {
let new = self.tree.node_from_value(val);
if self.parent.is_null() {
self.tree.insert_root(new);
} else if self.insert_left {
self.parent.insert_left(new, &mut self.tree.root);
} else {
self.parent.insert_right(new, &mut self.tree.root);
}
CursorMut {
current: new,
tree: self.tree,
}
}
}
}
pub enum Entry<'a, A: Adapter<Link = Link> + 'a> {
Occupied(CursorMut<'a, A>),
Vacant(InsertCursor<'a, A>),
}
impl<'a, A: Adapter<Link = Link> + 'a> Entry<'a, A> {
pub fn or_insert(self, val: A::Pointer) -> CursorMut<'a, A> {
match self {
Entry::Occupied(entry) => entry,
Entry::Vacant(entry) => entry.insert(val),
}
}
pub fn or_insert_with<F>(self, default: F) -> CursorMut<'a, A>
where
F: FnOnce() -> A::Pointer,
{
match self {
Entry::Occupied(entry) => entry,
Entry::Vacant(entry) => entry.insert(default()),
}
}
}
pub struct Iter<'a, A: Adapter<Link = Link>> {
head: NodePtr,
tail: NodePtr,
tree: &'a RBTree<A>,
}
impl<'a, A: Adapter<Link = Link> + 'a> Iterator for Iter<'a, A> {
type Item = &'a A::Value;
#[inline]
fn next(&mut self) -> Option<&'a A::Value> {
if self.head.is_null() {
None
} else {
let head = self.head;
if head == self.tail {
self.head = NodePtr::null();
self.tail = NodePtr::null();
} else {
self.head = unsafe { head.next() };
}
Some(unsafe { &*self.tree.adapter.get_value(head.0) })
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> DoubleEndedIterator for Iter<'a, A> {
#[inline]
fn next_back(&mut self) -> Option<&'a A::Value> {
if self.tail.is_null() {
None
} else {
let tail = self.tail;
if self.head == tail {
self.tail = NodePtr::null();
self.head = NodePtr::null();
} else {
self.tail = unsafe { tail.prev() };
}
Some(unsafe { &*self.tree.adapter.get_value(tail.0) })
}
}
}
impl<'a, A: Adapter<Link = Link> + 'a> Clone for Iter<'a, A> {
#[inline]
fn clone(&self) -> Iter<'a, A> {
Iter {
head: self.head,
tail: self.tail,
tree: self.tree,
}
}
}
pub struct IntoIter<A: Adapter<Link = Link>> {
head: NodePtr,
tail: NodePtr,
tree: RBTree<A>,
}
impl<A: Adapter<Link = Link>> Iterator for IntoIter<A> {
type Item = A::Pointer;
#[inline]
fn next(&mut self) -> Option<A::Pointer> {
if self.head.is_null() {
None
} else {
unsafe {
let head = self.head;
let parent = head.parent();
let right = head.right();
if parent.is_null() {
self.tree.root = right;
if right.is_null() {
self.tail = NodePtr::null();
}
} else {
parent.set_left(right);
}
if right.is_null() {
self.head = parent;
} else {
right.set_parent(parent);
self.head = right.first_child();
}
head.unlink();
Some(A::Pointer::from_raw(self.tree.adapter.get_value(head.0)))
}
}
}
}
impl<A: Adapter<Link = Link>> DoubleEndedIterator for IntoIter<A> {
#[inline]
fn next_back(&mut self) -> Option<A::Pointer> {
if self.tail.is_null() {
None
} else {
unsafe {
let tail = self.tail;
let parent = tail.parent();
let left = tail.left();
if parent.is_null() {
self.tree.root = left;
if left.is_null() {
self.head = NodePtr::null();
}
} else {
parent.set_right(left);
}
if left.is_null() {
self.tail = parent;
} else {
left.set_parent(parent);
self.tail = left.last_child();
}
tail.unlink();
Some(A::Pointer::from_raw(self.tree.adapter.get_value(tail.0)))
}
}
}
}
#[cfg(test)]
mod tests {
use self::rand::{Rng, XorShiftRng};
use super::{Entry, Link, RBTree};
use crate::Bound::*;
use crate::{KeyAdapter, UnsafeRef};
use rand;
use std::boxed::Box;
use std::fmt;
use std::vec::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 = UnsafeRef<Obj>: Obj { link: Link });
impl<'a> KeyAdapter<'a> for ObjAdapter {
type Key = i32;
fn get_key(&self, value: &'a Self::Value) -> i32 {
value.value
}
}
fn make_obj(value: i32) -> UnsafeRef<Obj> {
UnsafeRef::from_box(Box::new(Obj {
link: Link::new(),
value: 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 _
);
}
#[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::new_unseeded();
{
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<_>>();
rng.shuffle(&mut indices);
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<_>>();
rng.shuffle(&mut indices);
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<_>>();
rng.shuffle(&mut indices);
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);
}
}
}
#[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);
}
}