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));