intrusive-collections 0.8.3

// Copyright 2016 Amanieu d'Antras
//
// 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 collections for Rust.
//!
//! This library provides a set of high-performance intrusive collections which
//! can offer better performance and more flexibility than standard collections.
//!
//! The main difference between an intrusive collection and a normal one is that
//! while normal collections allocate memory behind your back to keep track of a
//! set of *values*, intrusive collections never allocate memory themselves and
//! instead keep track of a set of *objects*. Such collections are called
//! intrusive because they requires explicit support in objects to allow them to
//! be inserted into a collection.
//!
//! # Example
//!
//! ```
//! #[macro_use]
//! extern crate intrusive_collections;
//! use intrusive_collections::{LinkedList, LinkedListLink};
//! use std::cell::Cell;
//!
//! // A simple struct containing an instrusive link and a value
//! struct Test {
//!     link: LinkedListLink,
//!     value: Cell<i32>,
//! }
//!
//! // The adapter describes how an object can be inserted into an intrusive
//! // collection. This is automatically generated using a macro.
//! intrusive_adapter!(TestAdapter = Box<Test>: Test { link: LinkedListLink });
//!
//! fn main() {
//!     // Create a list and some objects
//!     let mut list = LinkedList::new(TestAdapter::new());
//!     let a = Box::new(Test {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(1),
//!     });
//!     let b = Box::new(Test {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(2),
//!     });
//!     let c = Box::new(Test {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(3),
//!     });
//!
//!     // Insert the objects at the front of the list
//!     list.push_front(a);
//!     list.push_front(b);
//!     list.push_front(c);
//!     assert_eq!(list.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [3, 2, 1]);
//!
//!     // At this point, the objects are owned by the list, and we can modify
//!     // them through the list.
//!     list.front().get().unwrap().value.set(4);
//!     assert_eq!(list.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [4, 2, 1]);
//!
//!     // Removing an object from an instrusive collection gives us back the
//!     // Box<Test> that we originally inserted into it.
//!     let a = list.pop_front().unwrap();
//!     assert_eq!(a.value.get(), 4);
//!     assert_eq!(list.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [2, 1]);
//!
//!     // Dropping the collection will automatically free b and c by
//!     // transforming them back into Box<Test> and dropping them.
//!     drop(list);
//! }
//! ```
//!
//! # Links and adapters
//!
//! Intrusive collections track objects through links which are embedded within
//! the objects themselves. It also allows a single object to be part of
//! multiple intrusive collections at once by having multiple links in it.
//!
//! The relationship between an object and a link inside it is described by the
//! `Adapter` trait. Intrusive collections use an implementation of this trait
//! to determine which link in an object should be used by the collection. In
//! most cases you do not need to write an implementation manually: the
//! `intrusive_adapter!` macro will automatically generate the necessary code.
//!
//! For red-black trees, the adapter must also implement the `KeyAdapter` trait
//! which allows a key to be extracted from an object. This key is then used to
//! keep all elements in the tree in ascending order.
//!
//! ```
//! #[macro_use]
//! extern crate intrusive_collections;
//! use intrusive_collections::{SinglyLinkedListLink, SinglyLinkedList};
//! use intrusive_collections::{LinkedListLink, LinkedList};
//! use intrusive_collections::{RBTreeLink, RBTree, KeyAdapter};
//! use std::rc::Rc;
//!
//! // This struct can be inside two lists and one tree simultaneously
//! #[derive(Default)]
//! struct Test {
//!     link: LinkedListLink,
//!     link2: SinglyLinkedListLink,
//!     link3: RBTreeLink,
//!     value: i32,
//! }
//!
//! intrusive_adapter!(MyAdapter = Rc<Test>: Test { link: LinkedListLink });
//! intrusive_adapter!(MyAdapter2 = Rc<Test>: Test { link2: SinglyLinkedListLink });
//! intrusive_adapter!(MyAdapter3 = Rc<Test>: Test { link3: RBTreeLink });
//! impl<'a> KeyAdapter<'a> for MyAdapter3 {
//!     type Key = i32;
//!     fn get_key(&self, x: &'a Test) -> i32 { x.value }
//! }
//!
//! fn main() {
//!     let mut a = LinkedList::new(MyAdapter::new());
//!     let mut b = SinglyLinkedList::new(MyAdapter2::new());
//!     let mut c = RBTree::new(MyAdapter3::new());
//!
//!     let test = Rc::new(Test::default());
//!     a.push_front(test.clone());
//!     b.push_front(test.clone());
//!     c.insert(test);
//! }
//! ```
//!
//! # Cursors
//!
//! Intrusive collections are manipulated using cursors. A cursor is similar to
//! an iterator, except that it can freely seek back-and-forth, and can safely
//! mutate the list during iteration. This is similar to how a C++ iterator
//! works.
//!
//! A cursor views an intrusive collection as a circular list, with a special
//! null object between the last and first elements of the collection. A cursor
//! will either point to a valid object in the collection or to this special
//! null object.
//!
//! Cursors come in two forms: `Cursor` and `CursorMut`. A `Cursor` gives a
//! read-only view of a collection, but you are allowed to use multiple `Cursor`
//! objects simultaneously on the same collection. On the other hand,
//! `CursorMut` can be used to mutate the collection, but you may only use one
//! of them at a time.
//!
//! Cursors are a very powerful abstraction since they allow a collection to be
//! mutated safely while it is being iterated on. For example, here is a
//! function which removes all values within a given range from a `RBTree`:
//!
//! ```
//! #[macro_use]
//! extern crate intrusive_collections;
//! use intrusive_collections::{RBTreeLink, RBTree, KeyAdapter, Bound};
//!
//! struct Element {
//!     link: RBTreeLink,
//!     value: i32,
//! }
//!
//! intrusive_adapter!(ElementAdapter = Box<Element>: Element { link: RBTreeLink });
//! impl<'a> KeyAdapter<'a> for ElementAdapter {
//!     type Key = i32;
//!     fn get_key(&self, e: &'a Element) -> i32 { e.value }
//! }
//!
//! fn remove_range(tree: &mut RBTree<ElementAdapter>, min: i32, max: i32) {
//!     // Find the first element which is greater than or equal to min
//!     let mut cursor = tree.lower_bound_mut(Bound::Included(&min));
//!
//!     // Iterate over all elements in the range [min, max]
//!     while cursor.get().map_or(false, |e| e.value <= max) {
//!         // CursorMut::remove will return a Some(<Box<Element>), which we
//!         // simply drop here. This will also advance the cursor to the next
//!         // element.
//!         cursor.remove();
//!     }
//! }
//! # fn main() {}
//! ```
//!
//! # Scoped collections
//!
//! Instead of taking ownership of objects inserted into them, intrusive
//! collections can also work with borrowed values. This works by using
//! lifetimes and the borrow checker to ensure that any objects inserted into an
//! intrusive collection will outlive the collection itself.
//!
//! ```
//! #[macro_use]
//! extern crate intrusive_collections;
//! extern crate typed_arena;
//!
//! use intrusive_collections::{LinkedListLink, LinkedList};
//! use typed_arena::Arena;
//! use std::cell::Cell;
//!
//! struct Value {
//!     link: LinkedListLink,
//!     value: Cell<i32>,
//! }
//!
//! // Note that we use a plain reference as the pointer type for the collection.
//! intrusive_adapter!(ValueAdapter<'a> = &'a Value: Value { link: LinkedListLink });
//!
//! fn main() {
//!     // Create an arena and a list. Note that since stack objects are dropped in
//!     // reverse order, the Arena must be created before the LinkedList. This
//!     // ensures that the list is dropped before the values are freed by the
//!     // arena. This is enforced by the Rust lifetime system.
//!     let arena = Arena::new();
//!     let mut list = LinkedList::new(ValueAdapter::new());
//!
//!     // We can now insert values allocated from the arena into the linked list
//!     list.push_back(arena.alloc(Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(1),
//!     }));
//!     list.push_back(arena.alloc(Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(2),
//!     }));
//!     list.push_back(arena.alloc(Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(3),
//!     }));
//!     assert_eq!(list.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [1, 2, 3]);
//!
//!     // We can also insert stack allocated values into an intrusive list.
//!     // Again, the values must outlive the LinkedList.
//!     let a = Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(4),
//!     };
//!     let b = Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(5),
//!     };
//!     let c = Value {
//!         link: LinkedListLink::new(),
//!         value: Cell::new(6),
//!     };
//!     let mut list2 = LinkedList::new(ValueAdapter::new());
//!     list2.push_back(&a);
//!     list2.push_back(&b);
//!     list2.push_back(&c);
//!     assert_eq!(list2.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [4, 5, 6]);
//!
//!     // Since these are shared references, any changes in the values are reflected in
//!     // the list.
//!     a.value.set(7);
//!     assert_eq!(list2.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [7, 5, 6]);
//! }
//! ```
//!
//! # Safety
//!
//! While it is possible to use intrusive collections without any unsafe code,
//! this crate also exposes a few unsafe features.
//!
//! The `cursor_from_ptr` and `cursor_mut_from_ptr` allow you to create a
//! cursor pointing to a specific element in the collection from a pointer to
//! that element. This is unsafe because it assumes that the objected pointed to
//! is currently inserted in the collection.
//!
//! The `UnsafeRef` type acts like `Rc`, except without the reference count.
//! Instead, you are responsible for keeping track of the number of active
//! references to an object and for freeing it once the last reference is
//! dropped. The advantage of `UnsafeRef` over `Rc` is that it reduces the size
//! of the allocation by two `usize` and avoids the overhead of maintaining
//! reference counts.

#![warn(missing_docs)]
#![warn(rust_2018_idioms)]
#![no_std]
#![cfg_attr(feature = "nightly", feature(const_fn, allow_internal_unstable))]

// Use liballoc on nightly to avoid a dependency on libstd
#[cfg(all(feature = "nightly", feature = "alloc"))]
extern crate alloc;
#[cfg(all(not(feature = "nightly"), feature = "alloc"))]
extern crate std as alloc;

#[cfg(test)]
#[macro_use]
extern crate std;

// Re-export core for use by macros
#[doc(hidden)]
pub extern crate core as __core;
// Re-export memoffset for use by macros
#[doc(hidden)]
pub extern crate memoffset as __memoffset;

mod intrusive_pointer;
mod unsafe_ref;
#[macro_use]
mod adapter;
mod key_adapter;
pub mod linked_list;
pub mod rbtree;
pub mod singly_linked_list;

pub use crate::adapter::Adapter;
pub use crate::intrusive_pointer::IntrusivePointer;
pub use crate::key_adapter::KeyAdapter;
pub use crate::linked_list::Link as LinkedListLink;
pub use crate::linked_list::LinkedList;
pub use crate::rbtree::Link as RBTreeLink;
pub use crate::rbtree::RBTree;
pub use crate::singly_linked_list::Link as SinglyLinkedListLink;
pub use crate::singly_linked_list::SinglyLinkedList;
pub use crate::unsafe_ref::UnsafeRef;

/// An endpoint of a range of keys.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
pub enum Bound<T> {
    /// An inclusive bound.
    Included(T),
    /// An exclusive bound.
    Excluded(T),
    /// An infinite endpoint. Indicates that there is no bound in this direction.
    Unbounded,
}