Skip to main content

Crate xorlist_rs

Crate xorlist_rs 

Source
Expand description

A doubly-linked list that packs both links of every node into a single word, backed by a single Vec instead of per-node allocations.

XorList is a XOR doubly linked list: instead of separate prev and next pointers, each node stores the two folded together, and traversal recovers one from the other. The links here are also self-relative — a node in slot curr stores (prev - curr) ^ (next - curr) (with wrapping arithmetic) rather than prev ^ next, so interior nodes stay valid when a whole run of slots is relocated by a constant offset. XorList::append exploits this to splice another list’s storage in wholesale, rewriting only the three links at the seam.

Decoding a link needs one known neighbor: coming from prev, the next slot is (npx ^ (prev - curr)) + curr. Iterators and cursors therefore track a pair of adjacent slots as they walk, and the list can be traversed equally cheaply in either direction.

Rather than giving each node its own heap allocation, all nodes live in slots of one backing Vec, and links name slots instead of addresses — pushes fill the Vec left to right, while the XOR links define the logical order on top of it. This raises the question of what to do when a node is removed from the middle of the Vec: shifting or swapping the remaining nodes would invalidate the links that name their slots. The opinionated answer here is to not move anything — the vacated slot is unlinked, marked dirty, and left in place. Subsequent pushes pop a dirty slot and construct the new node in it, growing the Vec only when no dirty slot is available, so removal never disturbs other nodes and the capacity is recycled. XorList::compact rebuilds the buffer in traversal order to shed accumulated dirty slots.

Because a node stays in its slot for as long as its element lives, the slot doubles as a stable handle to the element. Pushes return the slot they filled, and XorList::slot / XorList::slot_mut turn a saved slot back into the element in O(1) — no traversal — which is what makes patterns like an LRU cache (a map from key to slot, with the recency order kept in the list) practical. See the slots section on XorList for the rules on when a slot stays valid.

§Examples

use xorlist_rs::XorList;

let mut list: XorList<u32> = (1..=3).collect();
list.push_front(0);
list.push_back(4);

assert_eq!(list.len(), 5);
assert!(list.iter().eq(&[0, 1, 2, 3, 4]));
assert_eq!(list.pop_back(), Some(4));

Re-exports§

pub use cursor::Cursor;
pub use cursor::CursorMut;

Modules§

cursor
Cursors over a XorList: iterator-like views that can freely seek back and forth.

Structs§

IntoIter
An owning iterator over the elements of a XorList.
Iter
An iterator over the elements of a XorList.
IterMut
A mutable iterator over the elements of a XorList.
XorList
A doubly-linked list with XOR-compressed links, backed by a single contiguous buffer.