Crate intrusive_collections [] [src]

Intrusive collections for Rust.

Unlike normal colletions, an intrusive collection does not own the objects inside it. Instead it just tracks a set of already-existing objects. Such a collection is called intrusive because it requires explicit support in objects to allow them to be inserted into the collection. However, this allows intrusive collections to work without needed to allocate any memory.

Semantically, intrusive collections are roughly equivalent to a standard collection holding a set of *mut T. However, since intrusive collections store data in the objects themselves, the pointers to these objects must remain valid as long as they are linked into a collection.

Example

#[macro_use]
extern crate intrusive_collections;
use intrusive_collections::{IntrusiveRef, LinkedList, linked_list};

// Define a struct containing an intrusive link, and an adaptor for it
struct Test {
    link: linked_list::Link,
    value: i32,
}
intrusive_adaptor!(TestAdaptor = Test { link: linked_list::Link });

fn main() {
    // Create a list and some objects
    let mut list = LinkedList::new(TestAdaptor);
    let a = IntrusiveRef::from_box(Box::new(Test {
        link: linked_list::Link::new(),
        value: 1,
    }));
    let b = IntrusiveRef::from_box(Box::new(Test {
        link: linked_list::Link::new(),
        value: 2,
    }));
    let mut c = IntrusiveRef::from_box(Box::new(Test {
        link: linked_list::Link::new(),
        value: 3,
    }));

    // Insert the objects at the front of the list.
    list.cursor_mut().insert_after(a);
    list.cursor_mut().insert_after(b);
    list.cursor_mut().insert_after(c);
    assert_eq!(list.iter().map(|x| x.value).collect::<Vec<_>>(), [3, 2, 1]);

    // We can modify the objects and the changes will be reflected in the
    // collection since it references the existing objects. Note that we
    // need an unsafe block here because we need to ensure we do not create
    // multiple mutable references to the object. Alternatively a Cell could
    // be used instead to avoid the unsafe block.
    unsafe {
        c.as_mut().value = 4;
    }
    assert_eq!(list.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 2, 1]);

    // Once we remove objects from one collection, we are free to drop them
    // or insert them into another collection. Note that this isn't checked
    // by the compiler: you need to ensure that an object is not dropped
    // while still linked to an intrusive container.
    list.back_mut().remove();
    unsafe {
        drop(a.into_box());
    }
    assert_eq!(list.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 2]);

    // We can drop the collection at any time, even if it still contains
    // objects. This is safe because the links in an object are only
    // accessed by an intrusive container. However this will leak the
    // objects in the list if they are not freed.
    drop(list);
}

Links and adaptors

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 Adaptor 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_adaptor! macro will automatically generate the necessary code.

For red-black trees, the adaptor must also implement the TreeAdaptor 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::{IntrusiveRef, linked_list, LinkedList, rbtree, RBTree, TreeAdaptor};

// This struct can be inside two lists and one tree simultaneously
#[derive(Default)]
struct Test {
    link: linked_list::Link,
    link2: linked_list::Link,
    link3: rbtree::Link,
    value: i32,
}

intrusive_adaptor!(MyAdaptor = Test { link: linked_list::Link });
intrusive_adaptor!(MyAdaptor2 = Test { link2: linked_list::Link });
intrusive_adaptor!(MyAdaptor3 = Test { link3: rbtree::Link });
impl<'a> TreeAdaptor<'a> for MyAdaptor3 {
    type Key = i32;
    fn get_key(&self, x: &'a Test) -> i32 { x.value }
}

fn main() {
    let mut a = LinkedList::new(MyAdaptor);
    let mut b = LinkedList::new(MyAdaptor2);
    let mut c = RBTree::new(MyAdaptor3);

    let test = IntrusiveRef::from_box(Box::new(Test::default()));
    a.cursor_mut().insert_after(test);
    b.cursor_mut().insert_after(test);
    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.

Safety

Guaranteeing safety in intrusive collections is tricky becauses they do not integrate well with Rust's ownership system, especially in cases where an object is a member of multiple intrusive collections. This library encapsulates all safety concerns using the IntrusiveRef type. An IntrusiveRef is a pointer type that provides several guarantees which must be maintained by unsafe code:

  • An object managed by an IntrusiveRef must not be moved, dropped or accessed through a mutable reference as long as at least one IntrusiveRef is pointing to it.

The only safe way to create a IntrusiveRef is by using the IntrusiveRef::from_box which takes ownership of a boxed object. An IntrusiveRef can also be created using the unsafe IntrusiveRef::from_raw function, however you must ensure that the invariants listed above are maintained.

Destroying an object that is managed by an IntrusiveRef can only be done using unsafe code because you must manually ensure that the object is no longer a member of any intrusive collection and that there are no other IntrusiveRef pointing to it. The object managed by an IntrusiveRef can be retrieved through the IntrusiveRef::into_box and IntrusiveRef::into_raw functions.

Note that while moving an object that is linked into a collection is disallowed, moving the collection itself is perfectly fine. This is possible because the linked objects do not contain any pointers back to the collection object itself.

If an intrusive collection is dropped while still containing objects then the links in those objects are not reset. Attempting to insert one of these objects into another intrusive collection will fail unless its link is manually reset by calling unsafe_unlink on it.

Reexports

pub use linked_list::LinkedList;
pub use rbtree::{RBTree, TreeAdaptor};

Modules

linked_list

Intrusive doubly-linked list.

rbtree

Intrusive red-black tree.

Macros

container_of!

Unsafe macro to get a raw pointer to an outer object from a pointer to one of its fields.

intrusive_adaptor!

Macro to generate an empty type implementing the Adaptor trait for the given container object and field.

offset_of!

Macro to get the offset of a struct field in bytes from the address of the struct.

offset_of_unsafe!

Macro to get the offset of a struct field in bytes from the address of the struct.

Structs

IntrusiveRef

Pointer to an object that may be part of one or more intrusive colllections

Enums

Bound

An endpoint of a range of keys.

Traits

Adaptor

Trait representing a mapping between an object and an intrusive link type which is a member of that object.