23101968992

Committed 15 Mar 2026 02:53AM UTC coverage: 83.495% (+0.7%) from 82.752%

Build # 23101968992

Build Type

push

github

Committed by

macthecadillac

Commit Message

Documentation and tests. Fixed a "memory leak" with the internal
function `Arena::set`

Coverage Stats

3 of 3 new or added lines in 1 file covered. (100.0%)

43 existing lines in 4 files now uncovered.

430 of 515 relevant lines covered (83.5%)

27.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.15

/src/alloc.rs

//! Core arena allocator used to back the tree structure.
//!
//! The [`Allocator`] manages a flat `Vec` of [`Cell`]s. Free slots form an
//! intrusive singly-linked free-list: each `Cell::Nothing` holds the
//! one-based index of the next free slot (or `None` if it is the last).
//! `head` always points to the first free slot, so allocation and
//! deallocation are O(1). When no free slots remain the backing `Vec` is
//! doubled via [`Allocator::reserve`].
//!
//! Slots are addressed through [`Token`]s, which use one-based indexing so
//! that the null / invalid state can be represented by `Option<NonZeroUsize>`
//! without a separate tag word.
#![allow(clippy::new_without_default)]
#![allow(unused)]
use std::mem;
use std::num::NonZeroUsize;

#[cfg(feature = "serde")]
use serde::{Serialize, Deserialize};

use crate::token::Token;

/// A slot-map / arena allocator whose entries are addressed by [`Token`].
///
/// Internally the storage is a `Vec<Cell<T>>`. Live entries are
/// `Cell::Just(value)`; free entries are `Cell::Nothing(next)` where `next`
/// is the one-based index of the following free slot in the free-list
/// (or `None` for the tail).
///
/// # Indexing convention
/// All indices stored inside [`Token`] and inside the free-list links are
/// **one-based** so they can be stored as `NonZeroUsize`. The implementation
/// subtracts 1 when indexing into `data`.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Allocator<T> {
    /// Backing storage. `data[0]` is the slot with one-based index 1.
    data: Vec<Cell<T>>,
    /// One-based index of the first free slot, or `None` when fully occupied.
    head: Option<NonZeroUsize>,
    /// Number of occupied (live) slots.
    len: usize
}

/// A single storage slot inside an [`Allocator`].
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
enum Cell<T> {
    /// The slot is occupied and holds a value.
    Just(T),
    /// The slot is free. The payload is the one-based index of the next free
    /// slot in the intrusive free-list, or `None` if this is the last free
    /// slot.
    Nothing(Option<NonZeroUsize>)
}

impl<T> Default for Allocator<T> {
    /// Creates an allocator with a single pre-allocated free slot.
    fn default() -> Self {
        Allocator {
            data: vec![Cell::Nothing(None)],
            head: Some(NonZeroUsize::new(1).unwrap()),
            len: 0
        }
    }
}

impl<T> Allocator<T> {
    /// Creates a new, empty allocator with a single pre-allocated free slot.
    pub fn new() -> Self {
        Allocator {
            data: vec![Cell::Nothing(None)],
            head: Some(NonZeroUsize::new(1).unwrap()),
            len: 0
        }
    }

    /// Returns a [`Token`] pointing to the next free slot, growing the
    /// allocator if necessary.
    ///
    /// The returned token is **not** yet occupied; it is only a hint about
    /// where the *next* [`insert`](Self::insert) will land.
    pub fn head(&mut self) -> Token {
        match self.head {
            Some(head) => Token{ index: head },
            None => {
                self.reserve(self.len());
                self.head()
            }
        }
    }

    /// Returns the number of occupied (live) slots.
    pub fn len(&self) -> usize { self.len }

    /// Returns `true` if there are no occupied slots.
    pub fn is_empty(&self) -> bool { self.len == 0 }

    /// Returns the total number of slots (occupied + free) in the backing
    /// storage. Equivalent to `self.data.len()`.
    pub fn capacity(&self) -> usize { self.data.len() }

    /// Returns `true` if `token` refers to a currently-occupied slot.
    pub fn is_valid_token(&self, token: Token) -> bool {
        self.get(token).is_some()
    }

    /// Walks the free-list from `head` and returns the one-based index of the
    /// **last** free slot (i.e., the tail of the list), or `None` if the
    /// allocator is full.
    fn find_last_available(&self) -> Option<NonZeroUsize> {
        fn aux<T>(data: &[Cell<T>], indx: NonZeroUsize) -> Option<NonZeroUsize> {
            match data.get(indx.get() - 1) {  // get back to zero-based indexing
                // Dead code: corrupt-arena sentinel; unreachable via public API
                Some(Cell::Just(_)) | None => panic!("corrpt arena"),
                Some(Cell::Nothing(next_head)) => match next_head {
                    Some(n) => aux(data, *n),
                    None => Some(indx)
                }
            }
        }
        match self.head {
            None => None,
            Some(head) => aux(&self.data[..], head) // walk the heap til the end
        }
    }

    /// Appends `additional` new free slots to the backing storage and links
    /// them into the free-list.
    ///
    /// If the allocator is currently full (`head` is `None`) the new head is
    /// set to the first newly-allocated slot; otherwise the tail of the
    /// existing free-list is linked to the first new slot.
    pub fn reserve(&mut self, additional: usize) {
        self.data.reserve_exact(additional);
        let head_indx = NonZeroUsize::new(self.data.len() + 1).unwrap();
        match self.find_last_available() {
            None => self.head = Some(head_indx),
            Some(n) => self.data[n.get() - 1] = Cell::Nothing(Some(head_indx)),
        };
        // Build a chain: each new slot points to the next, the last points to None.
        let new_cells = (head_indx.get()..)  // already bigger by 1
            .take(additional - 1)
            .map(|i| Cell::Nothing(Some(NonZeroUsize::new(i + 1).unwrap())))
            .chain(std::iter::once(Cell::Nothing(None)));
        self.data.extend(new_cells);
    }

    /// Inserts `data` into the next free slot and returns a [`Token`] that
    /// can later be used to retrieve or remove the value.
    ///
    /// If no free slots are available the allocator doubles its capacity via
    /// [`reserve`](Self::reserve) before inserting.
    pub fn insert(&mut self, data: T) -> Token {
        match self.head {
            None => {
                self.reserve(self.capacity());
                self.insert(data)
            },
            Some(index) => {
                let i = index.get() - 1;  // zero-based index
                let next_head = match self.data.get(i) {
                    // Dead code: corrupt-arena sentinel; unreachable via public API
                    Some(Cell::Just(_)) | None => panic!("corrupt arena"),
                    Some(Cell::Nothing(next_head)) => next_head
                };
                self.head = *next_head;
                self.len += 1;
                self.data[i] = Cell::Just(data);
                Token { index }
            }
        }
    }

    /// Replaces the value at `token` with `data`, returning the old value.
    ///
    /// Returns `None` if `token` does not refer to a live slot. Note that the
    /// replacement is always inserted at the *next* free slot, which may
    /// differ from the original position of `token` if other slots are free.
    pub fn set(&mut self, token: Token, data: T) -> Option<T> {
        let out = self.remove(token);
        self.insert(data);
        out
    }

    /// Removes the value at `token`, freeing the slot for future use.
    ///
    /// Returns the removed value, or `None` if `token` does not refer to a
    /// live slot (already removed, never inserted, or out of range).
    pub fn remove(&mut self, token: Token) -> Option<T> {
        match self.data.get_mut(token.index.get() - 1) {  // zero-based index
            Some(Cell::Nothing(_)) | None => None,
            Some(mut cell) => {
                let mut x = Cell::Nothing(self.head);
                mem::swap(&mut x, cell);
                self.head = Some(token.index);
                self.len -= 1;
                match x {
                    Cell::Just(data) => Some(data),
                    // Dead code: corrupt-arena sentinel; unreachable via public API
                    _ => panic!("something is wrong with the code")
                }
            }
        }
    }

    /// Returns a shared reference to the value at `token`, or `None` if the
    /// slot is free or the token is out of range.
    pub fn get(&self, token: Token) -> Option<&T> {
        match self.data.get(token.index.get() - 1) {  // zero-based index
            Some(Cell::Nothing(_)) | None => None,
            Some(Cell::Just(data)) => Some(data)
        }
    }

    /// Returns an exclusive reference to the value at `token`, or `None` if
    /// the slot is free or the token is out of range.
    pub fn get_mut(&mut self, token: Token) -> Option<&mut T> {
        match self.data.get_mut(token.index.get() - 1) {  // zero-based index
            Some(Cell::Nothing(_)) | None => None,
            Some(Cell::Just(data)) => Some(data)
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn default_creates_valid_allocator() {
        let alloc: Allocator<usize> = Allocator::default();
        assert_eq!(alloc.len(), 0);
        assert!(alloc.is_empty());
        assert!(alloc.capacity() > 0);
    }

    #[test]
    fn capacity_returns_correct_value() {
        let alloc: Allocator<usize> = Allocator::new();
        assert_eq!(alloc.capacity(), alloc.data.len());
    }

    #[test]
    fn is_valid_token_true_and_false() {
        let mut alloc: Allocator<usize> = Allocator::new();
        let token = alloc.insert(42);
        assert!(alloc.is_valid_token(token));

        alloc.remove(token);
        assert!(!alloc.is_valid_token(token));
    }

    #[test]
    fn get_returns_none_for_free_slot() {
        let mut alloc: Allocator<usize> = Allocator::new();
        let token = alloc.insert(99);
        alloc.remove(token);
        assert!(alloc.get(token).is_none());
    }

    #[test]
    fn get_mut_returns_none_for_free_slot() {
        let mut alloc: Allocator<usize> = Allocator::new();
        let token = alloc.insert(99);
        alloc.remove(token);
        assert!(alloc.get_mut(token).is_none());
    }

    #[test]
    fn reserve_extends_capacity() {
        let mut alloc: Allocator<usize> = Allocator::new();
        let initial_capacity = alloc.capacity();
        alloc.reserve(8);
        assert!(alloc.capacity() >= initial_capacity + 8);
    }

    #[test]
    fn insert_after_exhaustion_triggers_reserve() {
        let mut alloc: Allocator<usize> = Allocator::new();
        // Fill until the allocator must grow
        let initial_capacity = alloc.capacity();
        for i in 0..initial_capacity {
            alloc.insert(i);
        }
        // This insert should trigger reserve internally
        let token = alloc.insert(999);
        assert!(alloc.is_valid_token(token));
        assert_eq!(*alloc.get(token).unwrap(), 999);
    }

    #[test]
    fn find_last_available_recursive_case() {
        let mut alloc: Allocator<usize> = Allocator::new();
        alloc.reserve(2);
        alloc.reserve(1);
        assert!(alloc.capacity() >= 4);
        assert_eq!(alloc.len(), 0);
        let t = alloc.insert(42);
        assert_eq!(*alloc.get(t).unwrap(), 42);
    }

    #[test]
    fn head_when_full_triggers_reserve() {
        let mut alloc: Allocator<usize> = Allocator::new();
        let capacity = alloc.capacity();
        for i in 0..capacity {
            alloc.insert(i);
        }
        // head() when allocator is full should call reserve and return a valid token
        let token = alloc.head();
        assert!(alloc.capacity() > capacity);
        // head token should be a free slot pointing to a Nothing cell
        assert!(alloc.get(token).is_none());
    }
}

1	//! Core arena allocator used to back the tree structure.
2	//!
3	//! The [`Allocator`] manages a flat `Vec` of [`Cell`]s. Free slots form an
4	//! intrusive singly-linked free-list: each `Cell::Nothing` holds the
5	//! one-based index of the next free slot (or `None` if it is the last).
6	//! `head` always points to the first free slot, so allocation and
7	//! deallocation are O(1). When no free slots remain the backing `Vec` is
8	//! doubled via [`Allocator::reserve`].
9	//!
10	//! Slots are addressed through [`Token`]s, which use one-based indexing so
11	//! that the null / invalid state can be represented by `Option<NonZeroUsize>`
12	//! without a separate tag word.
13	#![allow(clippy::new_without_default)]
14	#![allow(unused)]
15	use std::mem;
16	use std::num::NonZeroUsize;
17
18	#[cfg(feature = "serde")]
19	use serde::{Serialize, Deserialize};
20
21	use crate::token::Token;
22
23	/// A slot-map / arena allocator whose entries are addressed by [`Token`].
24	///
25	/// Internally the storage is a `Vec<Cell<T>>`. Live entries are
26	/// `Cell::Just(value)`; free entries are `Cell::Nothing(next)` where `next`
27	/// is the one-based index of the following free slot in the free-list
28	/// (or `None` for the tail).
29	///
30	/// # Indexing convention
31	/// All indices stored inside [`Token`] and inside the free-list links are
32	/// one-based so they can be stored as `NonZeroUsize`. The implementation
33	/// subtracts 1 when indexing into `data`.
34	#[derive(Clone, Debug)]
35	#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
36	pub struct Allocator<T> {
37	/// Backing storage. `data[0]` is the slot with one-based index 1.
38	data: Vec<Cell<T>>,
39	/// One-based index of the first free slot, or `None` when fully occupied.
40	head: Option<NonZeroUsize>,
41	/// Number of occupied (live) slots.
42	len: usize
43	}
44
45	/// A single storage slot inside an [`Allocator`].
46	#[derive(Clone, Debug)]
47	#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
48	enum Cell<T> {
49	/// The slot is occupied and holds a value.
50	Just(T),
51	/// The slot is free. The payload is the one-based index of the next free
52	/// slot in the intrusive free-list, or `None` if this is the last free
53	/// slot.
54	Nothing(Option<NonZeroUsize>)
55	}
56
57	impl<T> Default for Allocator<T> {
58	/// Creates an allocator with a single pre-allocated free slot.
59	fn default() -> Self {	8✔
60	Allocator {
61	data: vec![Cell::Nothing(None)],	8✔
62	head: Some(NonZeroUsize::new(1).unwrap()),	10✔
63	len: 0
64	}
65	}
66	}
67
68	impl<T> Allocator<T> {
69	/// Creates a new, empty allocator with a single pre-allocated free slot.
70	pub fn new() -> Self {	114✔
71	Allocator {
72	data: vec![Cell::Nothing(None)],	114✔
73	head: Some(NonZeroUsize::new(1).unwrap()),	130✔
74	len: 0
75	}
76	}
77
78	/// Returns a [`Token`] pointing to the next free slot, growing the
79	/// allocator if necessary.
80	///
81	/// The returned token is not yet occupied; it is only a hint about
82	/// where the next [`insert`](Self::insert) will land.
83	pub fn head(&mut self) -> Token {	110✔
84	match self.head {	110✔
85	Some(head) => Token{ index: head },
UNCOV 86	None => {	×
87	self.reserve(self.len());	104✔
88	self.head()	102✔
89	}
90	}
91	}
92
93	/// Returns the number of occupied (live) slots.
94	pub fn len(&self) -> usize { self.len }	220✔
95
96	/// Returns `true` if there are no occupied slots.
97	pub fn is_empty(&self) -> bool { self.len == 0 }	24✔
98
99	/// Returns the total number of slots (occupied + free) in the backing
100	/// storage. Equivalent to `self.data.len()`.
101	pub fn capacity(&self) -> usize { self.data.len() }	8✔
102
103	/// Returns `true` if `token` refers to a currently-occupied slot.
104	pub fn is_valid_token(&self, token: Token) -> bool {	2✔
105	self.get(token).is_some()	2✔
106	}
107
108	/// Walks the free-list from `head` and returns the one-based index of the
109	/// last free slot (i.e., the tail of the list), or `None` if the
110	/// allocator is full.
111	fn find_last_available(&self) -> Option<NonZeroUsize> {	104✔
112	fn aux<T>(data: &[Cell<T>], indx: NonZeroUsize) -> Option<NonZeroUsize> {	2✔
113	match data.get(indx.get() - 1) { // get back to zero-based indexing	2✔
114	// Dead code: corrupt-arena sentinel; unreachable via public API
UNCOV 115	Some(Cell::Just(_)) \| None => panic!("corrpt arena"),	×
116	Some(Cell::Nothing(next_head)) => match next_head {	2✔
117	Some(n) => aux(data, *n),	2✔
118	None => Some(indx)	2✔
119	}
120	}
121	}
122	match self.head {	104✔
123	None => None,	102✔
124	Some(head) => aux(&self.data[..], head) // walk the heap til the end	2✔
125	}
126	}
127
128	/// Appends `additional` new free slots to the backing storage and links
129	/// them into the free-list.
130	///
131	/// If the allocator is currently full (`head` is `None`) the new head is
132	/// set to the first newly-allocated slot; otherwise the tail of the
133	/// existing free-list is linked to the first new slot.
134	pub fn reserve(&mut self, additional: usize) {	104✔
135	self.data.reserve_exact(additional);	104✔
136	let head_indx = NonZeroUsize::new(self.data.len() + 1).unwrap();	196✔
137	match self.find_last_available() {	104✔
138	None => self.head = Some(head_indx),	103✔
139	Some(n) => self.data[n.get() - 1] = Cell::Nothing(Some(head_indx)),	2✔
140	};
141	// Build a chain: each new slot points to the next, the last points to None.
142	let new_cells = (head_indx.get()..) // already bigger by 1	102✔
143	.take(additional - 1)	205✔
144	.map(\|i\| Cell::Nothing(Some(NonZeroUsize::new(i + 1).unwrap())))	379✔
145	.chain(std::iter::once(Cell::Nothing(None)));	104✔
146	self.data.extend(new_cells);	105✔
147	}
148
149	/// Inserts `data` into the next free slot and returns a [`Token`] that
150	/// can later be used to retrieve or remove the value.
151	///
152	/// If no free slots are available the allocator doubles its capacity via
153	/// [`reserve`](Self::reserve) before inserting.
154	pub fn insert(&mut self, data: T) -> Token {	114✔
155	match self.head {	114✔
UNCOV 156	None => {	×
157	self.reserve(self.capacity());	4✔
158	self.insert(data)	2✔
159	},
160	Some(index) => {	114✔
161	let i = index.get() - 1; // zero-based index	232✔
162	let next_head = match self.data.get(i) {	236✔
163	// Dead code: corrupt-arena sentinel; unreachable via public API
UNCOV 164	Some(Cell::Just(_)) \| None => panic!("corrupt arena"),	×
165	Some(Cell::Nothing(next_head)) => next_head	118✔
166	};
167	self.head = *next_head;	118✔
168	self.len += 1;	118✔
169	self.data[i] = Cell::Just(data);	118✔
170	Token { index }
171	}
172	}
173	}
174
175	/// Replaces the value at `token` with `data`, returning the old value.
176	///
177	/// Returns `None` if `token` does not refer to a live slot. Note that the
178	/// replacement is always inserted at the next free slot, which may
179	/// differ from the original position of `token` if other slots are free.
180	pub fn set(&mut self, token: Token, data: T) -> Option<T> {	106✔
181	let out = self.remove(token);	107✔
182	self.insert(data);	107✔
183	out	106✔
184	}
185
186	/// Removes the value at `token`, freeing the slot for future use.
187	///
188	/// Returns the removed value, or `None` if `token` does not refer to a
189	/// live slot (already removed, never inserted, or out of range).
190	pub fn remove(&mut self, token: Token) -> Option<T> {	110✔
191	match self.data.get_mut(token.index.get() - 1) { // zero-based index	111✔
192	Some(Cell::Nothing(_)) \| None => None,	106✔
193	Some(mut cell) => {	22✔
194	let mut x = Cell::Nothing(self.head);	23✔
195	mem::swap(&mut x, cell);	23✔
196	self.head = Some(token.index);	23✔
197	self.len -= 1;	23✔
198	match x {	24✔
199	Cell::Just(data) => Some(data),	24✔
200	// Dead code: corrupt-arena sentinel; unreachable via public API
UNCOV 201	_ => panic!("something is wrong with the code")	×
202	}
203	}
204	}
205	}
206
207	/// Returns a shared reference to the value at `token`, or `None` if the
208	/// slot is free or the token is out of range.
209	pub fn get(&self, token: Token) -> Option<&T> {	105✔
210	match self.data.get(token.index.get() - 1) { // zero-based index	106✔
211	Some(Cell::Nothing(_)) \| None => None,	105✔
212	Some(Cell::Just(data)) => Some(data)	105✔
213	}
214	}
215
216	/// Returns an exclusive reference to the value at `token`, or `None` if
217	/// the slot is free or the token is out of range.
218	pub fn get_mut(&mut self, token: Token) -> Option<&mut T> {	103✔
219	match self.data.get_mut(token.index.get() - 1) { // zero-based index	102✔
220	Some(Cell::Nothing(_)) \| None => None,	2✔
221	Some(Cell::Just(data)) => Some(data)	101✔
222	}
223	}
224	}
225
226	#[cfg(test)]
227	mod test {
228	use super::*;
229
230	#[test]
231	fn default_creates_valid_allocator() {
232	let alloc: Allocator<usize> = Allocator::default();
233	assert_eq!(alloc.len(), 0);
234	assert!(alloc.is_empty());
235	assert!(alloc.capacity() > 0);
236	}
237
238	#[test]
239	fn capacity_returns_correct_value() {
240	let alloc: Allocator<usize> = Allocator::new();
241	assert_eq!(alloc.capacity(), alloc.data.len());
242	}
243
244	#[test]
245	fn is_valid_token_true_and_false() {
246	let mut alloc: Allocator<usize> = Allocator::new();
247	let token = alloc.insert(42);
248	assert!(alloc.is_valid_token(token));
249
250	alloc.remove(token);
251	assert!(!alloc.is_valid_token(token));
252	}
253
254	#[test]
255	fn get_returns_none_for_free_slot() {
256	let mut alloc: Allocator<usize> = Allocator::new();
257	let token = alloc.insert(99);
258	alloc.remove(token);
259	assert!(alloc.get(token).is_none());
260	}
261
262	#[test]
263	fn get_mut_returns_none_for_free_slot() {
264	let mut alloc: Allocator<usize> = Allocator::new();
265	let token = alloc.insert(99);
266	alloc.remove(token);
267	assert!(alloc.get_mut(token).is_none());
268	}
269
270	#[test]
271	fn reserve_extends_capacity() {
272	let mut alloc: Allocator<usize> = Allocator::new();
273	let initial_capacity = alloc.capacity();
274	alloc.reserve(8);
275	assert!(alloc.capacity() >= initial_capacity + 8);
276	}
277
278	#[test]
279	fn insert_after_exhaustion_triggers_reserve() {
280	let mut alloc: Allocator<usize> = Allocator::new();
281	// Fill until the allocator must grow
282	let initial_capacity = alloc.capacity();
283	for i in 0..initial_capacity {
284	alloc.insert(i);
285	}
286	// This insert should trigger reserve internally
287	let token = alloc.insert(999);
288	assert!(alloc.is_valid_token(token));
289	assert_eq!(*alloc.get(token).unwrap(), 999);
290	}
291
292	#[test]
293	fn find_last_available_recursive_case() {
294	let mut alloc: Allocator<usize> = Allocator::new();
295	alloc.reserve(2);
296	alloc.reserve(1);
297	assert!(alloc.capacity() >= 4);
298	assert_eq!(alloc.len(), 0);
299	let t = alloc.insert(42);
300	assert_eq!(*alloc.get(t).unwrap(), 42);
301	}
302
303	#[test]
304	fn head_when_full_triggers_reserve() {
305	let mut alloc: Allocator<usize> = Allocator::new();
306	let capacity = alloc.capacity();
307	for i in 0..capacity {
308	alloc.insert(i);
309	}
310	// head() when allocator is full should call reserve and return a valid token
311	let token = alloc.head();
312	assert!(alloc.capacity() > capacity);
313	// head token should be a free slot pointing to a Nothing cell
314	assert!(alloc.get(token).is_none());
315	}
316	}

macthecadillac / atree / 23101968992

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous