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