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 crate::ffi;
12use std::mem;
13
14/// Represents a slot of a [`PyObjectFreeList`].
15enum PyObjectSlot {
16 /// A free slot.
17 Empty,
18 /// An allocated slot.
19 Filled(*mut ffi::PyObject),
20}
21
22// safety: access is guarded by a per-pyclass mutex
23unsafe impl Send for PyObjectSlot {}
24
25/// A free allocation list for PyObject ffi pointers.
26///
27/// See [the parent module](crate::impl_::freelist) for more details.
28pub struct PyObjectFreeList {
29 entries: Box<[PyObjectSlot]>,
30 split: usize,
31 capacity: usize,
32}
33
34impl PyObjectFreeList {
35 /// Creates a new `PyObjectFreeList` instance with specified capacity.
36 pub fn with_capacity(capacity: usize) -> PyObjectFreeList {
37 let entries = (0..capacity)
38 .map(|_| PyObjectSlot::Empty)
39 .collect::<Box<[_]>>();
40
41 PyObjectFreeList {
42 entries,
43 split: 0,
44 capacity,
45 }
46 }
47
48 /// Pops the first non empty item.
49 pub fn pop(&mut self) -> Option<*mut ffi::PyObject> {
50 let idx = self.split;
51 if idx == 0 {
52 None
53 } else {
54 match mem::replace(&mut self.entries[idx - 1], PyObjectSlot::Empty) {
55 PyObjectSlot::Filled(v) => {
56 self.split = idx - 1;
57 Some(v)
58 }
59 _ => panic!("PyObjectFreeList is corrupt"),
60 }
61 }
62 }
63
64 /// Inserts a value into the list. Returns `Some(val)` if the `PyObjectFreeList` is full.
65 pub fn insert(&mut self, val: *mut ffi::PyObject) -> Option<*mut ffi::PyObject> {
66 let next = self.split + 1;
67 if next < self.capacity {
68 self.entries[self.split] = PyObjectSlot::Filled(val);
69 self.split = next;
70 None
71 } else {
72 Some(val)
73 }
74 }
75}
76