1//! Support for [free allocation lists][1].
2//!
3//! This can improve performance for types that are often created and deleted in quick succession.
4//!
5//! Rather than implementing this manually,
6//! implement it by annotating a struct with `#[pyclass(freelist = N)]`,
7//! where `N` is the size of the freelist.
8//!
9//! [1]: https://en.wikipedia.org/wiki/Free_list
10
11use std::mem;
12
13/// Represents a slot of a [`FreeList`].
14pub enum Slot<T> {
15 /// A free slot.
16 Empty,
17 /// An allocated slot.
18 Filled(T),
19}
20
21/// A free allocation list.
22///
23/// See [the parent module](crate::impl_::freelist) for more details.
24pub struct FreeList<T> {
25 entries: Vec<Slot<T>>,
26 split: usize,
27 capacity: usize,
28}
29
30impl<T> FreeList<T> {
31 /// Creates a new `FreeList` instance with specified capacity.
32 pub fn with_capacity(capacity: usize) -> FreeList<T> {
33 let entries = (0..capacity).map(|_| Slot::Empty).collect::<Vec<_>>();
34
35 FreeList {
36 entries,
37 split: 0,
38 capacity,
39 }
40 }
41
42 /// Pops the first non empty item.
43 pub fn pop(&mut self) -> Option<T> {
44 let idx = self.split;
45 if idx == 0 {
46 None
47 } else {
48 match mem::replace(&mut self.entries[idx - 1], Slot::Empty) {
49 Slot::Filled(v) => {
50 self.split = idx - 1;
51 Some(v)
52 }
53 _ => panic!("FreeList is corrupt"),
54 }
55 }
56 }
57
58 /// Inserts a value into the list. Returns `Some(val)` if the `FreeList` is full.
59 pub fn insert(&mut self, val: T) -> Option<T> {
60 let next = self.split + 1;
61 if next < self.capacity {
62 self.entries[self.split] = Slot::Filled(val);
63 self.split = next;
64 None
65 } else {
66 Some(val)
67 }
68 }
69}
70