Crate intrusive_collections

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

use intrusive_collections::intrusive_adapter;
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 });

// 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.

use intrusive_collections::intrusive_adapter;
use intrusive_collections::{SinglyLinkedListLink, SinglyLinkedList};
use intrusive_collections::{LinkedListLink, LinkedList};
use intrusive_collections::{XorLinkedList, XorLinkedListLink};
use intrusive_collections::{RBTreeLink, RBTree, KeyAdapter};
use std::rc::Rc;

// This struct can be inside three lists and one tree simultaneously
#[derive(Default)]
struct Test {
    link: LinkedListLink,
    link2: SinglyLinkedListLink,
    link3: XorLinkedListLink,
    link4: 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: XorLinkedListLink });
intrusive_adapter!(MyAdapter4 = Rc<Test>: Test { link4: RBTreeLink });
impl<'a> KeyAdapter<'a> for MyAdapter4 {
    type Key = i32;
    fn get_key(&self, x: &'a Test) -> i32 { x.value }
}

let mut a = LinkedList::new(MyAdapter::new());
let mut b = SinglyLinkedList::new(MyAdapter2::new());
let mut c = XorLinkedList::new(MyAdapter3::new());
let mut d = RBTree::new(MyAdapter4::new());

let test = Rc::new(Test::default());
a.push_front(test.clone());
b.push_front(test.clone());
c.push_front(test.clone());
d.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:

use intrusive_collections::intrusive_adapter;
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();
    }
}

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.

use intrusive_collections::intrusive_adapter;
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 });

// 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.

Re-exports

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::xor_linked_list::Link as XorLinkedListLink;

pub use crate::xor_linked_list::XorLinkedList;

Modules

linked_list	Intrusive doubly-linked list.
rbtree	Intrusive red-black tree.
singly_linked_list	Intrusive singly-linked list.
xor_linked_list	Intrusive xor doubly-linked list which uses less memory than a regular doubly linked list.

Macros

container_of	Unsafe macro to get a raw pointer to an outer object from a pointer to one of its fields.
intrusive_adapter	Macro to generate an implementation of Adapter for a given set of types. In particular this will automatically generate implementations of the get_value and get_link methods for a given named field in a struct.
offset_of	Calculates the offset of the specified field from the start of the struct.

Structs

DefaultPointerOps	The PointerOps type used by an Adapter generated by intrusive_adapter!.
UnsafeRef	Unchecked shared pointer

Enums

Bound

An endpoint of a range of keys.

Traits

Adapter	Trait for a adapter which allows a type to be inserted into an intrusive collection.
DefaultLinkOps	The default implementation of LinkOps associated with a link type.
KeyAdapter	Extension of the Adapter trait to provide a way of extracting a key from an object. This key can then be used as an index in certain intrusive collections (currently only RBTree uses this).
LinkOps	Base trait for link operations.
PointerOps	Trait for pointer conversion operations.