slot_list/lib.rs
1#![cfg_attr(not(feature = "std"), no_std)]
2#![warn(missing_docs)]
3#![warn(unsafe_op_in_unsafe_fn)]
4
5//! A doubly linked list whose nodes all live in a preallocated contiguous
6//! region: the slot index is the element's identity (`slot`, constant for the
7//! element's lifetime), and deleted slots are reused through a free-list (LIFO).
8//! That is where the name `slot-list` comes from.
9//!
10//! # Two "positions": logical position `pos` and physical slot `slot`
11//!
12//! The code and the docs keep these two terms strictly apart, with no
13//! conversion formula between them:
14//!
15//! | | logical position `pos` | physical slot `slot` |
16//! |---|---|---|
17//! | Meaning | the element's order in the chain (which one) | the element's index in contiguous memory (= identity) |
18//! | Range | `0 .. len()` | `0 .. storage.slots()` |
19//! | Stability | changes on every insert/remove | **constant while the element lives** (usable as a handle) |
20//! | How to get it | walk the chain from an endpoint; `Cursor::index()` | **handle**: `Cursor::slot` / `CursorMut::slot` /
21//! `List::front_slot` / `back_slot` / `iter_slots` (all `O(1)`); the type is [`Slot`] (a raw index,
22//! 8 B, **no generation tag** ⇒ a stale handle is undetectable; for the trade-off vs `fast-list` see `PERFORMANCE.md` §7) |
23//! | Conversion | `slot_at(pos)`: walk the chain, `O(min(pos, len-1-pos))` | `pos_of(slot)`: walk the chain, `O(len)` |
24//!
25//! Any "position" in the public API means the logical position: [`List::at`] /
26//! [`List::remove`] / [`Cursor::index`] (matching std's `Cursor::index`: returns the
27//! logical position, `None` for the ghost position) / [`CursorMut::seek`] /
28//! [`CursorMut::move_steps`].
29//!
30//! Slots are a first-class part of the public surface: once you have a handle you
31//! can call `cursor_at(_mut)` / `remove_slot` / `move_to_front` / `move_to_back` /
32//! `pos_of` without knowing the logical position first; the invariants guarantee the
33//! handle stays valid while the element lives and that inserts/removes do not move
34//! other elements. After an element is removed its slot is reused, so an old handle
35//! does not become invalid: it may point at the new element (classic ABA; for the
36//! same-machine comparison and trade-offs see `PERFORMANCE.md` §7). The indices in
37//! `head` / `tail` / `free_head` / `free_tail` and `storage` remain private.
38//!
39//! The three memory layouts share one implementation; the only difference is
40//! "which fields sit together":
41//!
42//! | alias | layout | arrangement | slot size for an 8 B / 64 B element |
43//! |---|---|---|---|
44//! | [`SplitList`] | [`Split`] | `data` / `prev` / `next` **as three separate `Vec`s** | 24 / 80 B = 8 / 64 B payload + 16 B links (`u32` index: 16 / 72 B) |
45//! | [`PackedLinksList`] | [`PackedLinks`] | `data` in one `Vec`, `prev`/`next` **paired** into a single `Link` | 24 / 80 B (`u32`: 16 / 72 B) |
46//! | [`NodesList`] | [`Nodes`] | `data` + `prev` + `next` **as a whole node** in one `Node` | 24 / 80 B (`u32`: 16 / 72 B) |
47//!
48//! The alias's second parameter is the index width ([`Ix`]), defaulting to
49//! [`DefaultIx`] = `usize`; enabling the `u32-index` feature switches it to `u32`: a
50//! third less per slot and `append` ~32% faster, at the cost of a 2.1G slot limit
51//! (see [`Ix::MAX_SLOTS`]). `PERFORMANCE.md` is measured with this default.
52//!
53//! All three are aliases of [`List<T, S>`]: the logic is written once, and the layout
54//! differences come from the [`Storage`] strategy.
55//!
56//! # `no_std`
57//!
58//! Turning off the default `std` feature gives `no_std` + `alloc`:
59//!
60//! ```text
61//! cargo check --no-default-features # no_std is only verified with check
62//! ```
63//!
64//! `std` is also a prerequisite for benches and tests (criterion, `std::rc` in
65//! the tests): under this combination the bench target is skipped via
66//! `required-features` and the test module is not compiled. The library itself only
67//! uses `core` and `alloc::vec::Vec`, with no other dependencies.
68//!
69//! # State is transportable (serializable / shared memory)
70//!
71//! The whole chain's state = the slot arrays plus five numbers, no pointers, so it
72//! can be written to disk or placed in shared memory directly. The public entry points
73//! are [`List::into_raw`] / [`List::from_raw`] (with [`RawList`]'s accessors) and each
74//! layout's `as_parts` / `into_parts` / `from_parts`; for per-slot state there is also
75//! [`List::iter_slots`] (live) and [`List::free_slots`] (the free chain, LIFO).
76//!
77//! # Alignment with `std::collections::LinkedList`
78//!
79//! Both the public API and the semantics align with `LinkedList`:
80//!
81//! - `new` (`const fn`), `Default`, `len`, `is_empty`, `clear`
82//! - `push_front` / `push_back` (returning `()`), `push_front_mut` / `push_back_mut`
83//! - `pop_front` / `pop_back`
84//! - `front` / `back` / `front_mut` / `back_mut`
85//! - `cursor_front` / `cursor_front_mut` / `cursor_back` / `cursor_back_mut`
86//! - `iter` / `iter_mut` / `IntoIterator` (`&`, `&mut`, and owned)
87//! - `contains`, `retain`, `append`, `split_off`, `remove`
88//! - the std-aligned cursor methods: `remove_current_as_list` / `splice_before` /
89//! `splice_after` / `split_before` / `split_after` (complexity differs from std, see below)
90//! - `Clone`, `Debug`, `PartialEq`, `Eq`, `FromIterator`, `Extend`
91//! - cursors: [`Cursor`] / [`CursorMut`], including the "ghost" position, wrap-around
92//! movement, `insert_before` / `insert_after` / `remove_current` / `push_*` / `pop_*`
93//! / `peek_*` / `as_cursor` / `as_list`
94//!
95//! Semantic differences (all stemming from the single fact that "slots are one
96//! contiguous storage"):
97//!
98//! | operation | std | this library |
99//! |---|---|---|
100//! | `append` | O(1) pointer splice | O(other's slot count): move the whole run over + add an offset to the indices (the invariant lets each index be written once) |
101//! | `split_before` / `split_after` / `split_off` | O(1) pointer split | **O(N) element moves**, and the **moved elements get new slots** (old `Slot` handles become stale) |
102//! | `splice_before` / `splice_after` | O(1) | O(number of elements spliced in), inserting one by one |
103//! | `remove_current_as_list` | O(1) node move | O(1), but the element **gets a new slot** |
104//!
105//! `append` in detail:
106//!
107//! It moves the other list's whole run of slots over (adding the offset as it moves,
108//! so each index is written once), O(other's total slot count); the other list's free
109//! slots come along too. For
110//! "move element by element to the back, preferring to reuse free slots we already
111//! have" (billed by live elements, especially worthwhile when the other list is
112//! sparse), use [`List::append_elementwise`]. See that method and [`Storage::append`]
113//! for the trade-offs between the two paths.
114//!
115//! # Implementation notes: no sentinel values in the arrays
116//!
117//! Every value in the `next` array is a valid slot index (the "dummy" fields at the
118//! ends of the two chains are never read, but are still valid indices); `NIL` is used
119//! only as a scalar argument (the "empty" value of `head`/`tail`/`free_head`/
120//! `free_tail`) and as the cursor's ghost-position tag. This is exactly why
121//! [`List::append`] can unconditionally `+= base` the whole run of moved indices: the
122//! free bit rides along. It sits in the top bit of `prev`, and `2^63 | v` plus `base`
123//! is still `2^63 | (v + base)` (as long as `u64` does not overflow).
124//!
125//! `prev` is a "valid index" only on live slots; a free slot's `prev` is a stale
126//! value plus the mark bit. Hence the contract: read `prev` only on live slots
127//! ([`Storage::prev`] does not mask; debug builds pin this with `debug_assert`, release
128//! pays nothing).
129//!
130//! To decide whether a slot is live, look only at that mark bit, never read `data`:
131//! a free slot's `data` is uninitialized, and touching it is UB.
132//!
133//! This yields two disciplines:
134//!
135//! - walking a chain must be by count (the end dummies are not NIL): [`Iter`] /
136//! [`IterMut`] count with `remaining`, and `retain` / `clear` finish by `len`;
137//! - all four endpoint fields reset to `NIL` when a chain becomes empty
138//! (`head`/`tail` when `len == 0`, `free_head`/`free_tail` when the free chain empties):
139//! that way "is it empty" is a single field read instead of computing
140//! `storage.slots() - len`, which would run on every free/alloc (measured ~3-6% slower
141//! `churn`); the reset writes two fields only on the transition to empty.
142//!
143//! # Extensions (not in std)
144//!
145//! - [`List::at`]: O(min(pos, len-1-pos)) random access; std has no random access at all
146//! - [`List::with_capacity`] / [`List::reserve`]: preallocate slot capacity
147//! (nodes live in contiguous memory, so std's list has no such need, but ours does)
148//! - [`CursorMut::seek`] / [`CursorMut::move_steps`]: move a cursor by position/stride
149//! - [`CursorMut::is_head`] / [`CursorMut::is_tail`]: O(1) endpoint checks
150//!
151//! # Performance
152//!
153//! Numbers, the choice matrix for `append`'s two APIs, and the comparisons against
154//! `std`'s containers and `fast-list` are in `PERFORMANCE.md` at the repository root; the
155//! benchmarks themselves are in `benches/list.rs`, whose header spells out the reading
156//! discipline (one run at a time, alternating A/B). Variants that were measured and
157//! rejected are not kept as documentation: the reason a piece of state is the way it is
158//! sits next to it in the source, and the measurements that picked it are in the commit
159//! messages.
160//!
161//! # Intentionally not implemented
162//!
163//! `PartialOrd` / `Ord` / `Hash`, `extract_if` / `retain_mut`,
164//! `CursorMut::splice_before` / `splice_after` / `split_before` /
165//! `split_after` / `remove_current_as_list`, and the allocator APIs (`new_in`).
166
167extern crate alloc;
168mod cursor;
169mod iter;
170mod list;
171mod slot;
172pub mod storage;
173
174#[cfg(all(test, feature = "std"))]
175mod tests;
176
177pub use cursor::{Cursor, CursorMut};
178pub use iter::{IntoIter, Iter, IterMut};
179pub use list::{List, RawList};
180pub use slot::Slot;
181pub use storage::{DefaultIx, Ix, Nodes, PackedLinks, Split, Storage};
182
183/// `Split` layout: `data` / `prev` / `next` as three independent `Vec`s.
184///
185/// The second parameter is the index width ([`Ix`]: `u8` / `u16` / `u32` / `u64` /
186/// `usize`), which directly determines the bytes per slot: for an 8-byte element (`usize`),
187/// the default `usize` index gives 24 B/slot (8 B payload + 2×8 B links), `u32` is 16 B,
188/// and `u16` is 12 B. The cost is a slot-count limit
189/// (`u32` ⇒ 2.1G, `u16` ⇒ 32k, `u8` ⇒ 128; exceeding it panics).
190pub type SplitList<T, I = DefaultIx> = List<T, Split<T, I>>;
191
192/// PackedLinks layout: `data` in one `Vec`, `prev`/`next` interleaved in another `Vec`.
193/// The second parameter is the index width (same as [`SplitList`]).
194pub type PackedLinksList<T, I = DefaultIx> = List<T, PackedLinks<T, I>>;
195
196/// Nodes layout: `data` / `prev` / `next` in a single `Node`.
197/// The second parameter is the index width (same as [`SplitList`]).
198pub type NodesList<T, I = DefaultIx> = List<T, Nodes<T, I>>;