fffl/
lib.rs

1#![doc = include_str!("../doc/lib.md")]
2
3use std::{hint::unreachable_unchecked, ops::{Index, IndexMut}, mem::replace};
4
5
6#[derive(PartialEq, Debug, Clone)]
7enum Slot<T> {
8    Value(T),
9    Next(usize),
10    Empty
11}
12
13impl <T>Slot<T> {
14
15    #[inline(always)]
16    const fn from_value(value: T) -> Self {
17        Self::Value(value)
18    }
19
20    #[inline(always)]
21    unsafe fn to_some_unchecked(self) -> Option<T> {
22        match self {
23            Slot::Value(value) => Some(value),
24            _ => unsafe { unreachable_unchecked() }
25        }
26    }
27
28    #[inline(always)]
29    unsafe fn as_value_unchecked(&self) -> &T {
30        match self {
31            Slot::Value(value) => value,
32            _ => unsafe { unreachable_unchecked() }
33        }
34    }
35
36    #[inline(always)]
37    unsafe fn as_value_unchecked_mut(&mut self) -> &mut T {
38        match self {
39            Slot::Value(value) => value,
40            _ => unsafe { unreachable_unchecked() }
41        }
42    }
43
44}
45
46#[doc = include_str!("../doc/freelist.md")]
47#[derive(Debug, Clone)]
48pub struct Freelist<T> {
49    slots: Vec<Slot<T>>,
50    next: Slot<T>,
51    filled_length: usize,
52}
53
54
55impl<T> Freelist<T> {
56
57    #[inline]
58    pub const fn new() -> Self { 
59        Self { 
60            slots: Vec::new(),
61            next: Slot::Empty,
62            filled_length: 0
63        }
64    }
65
66    /// Appends an element to the first free slot or back of the list
67    /// and returns the index of insertion.
68    #[inline]
69    pub fn push(&mut self, value: T) -> usize {
70        self.filled_length += 1;
71        let item = Slot::Value(value);
72        match self.next {
73            Slot::Next(index) => unsafe {
74                self.next = replace(self.slots.get_unchecked_mut(index), item);
75                index
76            },
77            _ => {
78                self.slots.push(item);
79                self.filled_length - 1
80            }
81        }
82    }
83
84    /// Returns the next available index OR total length of the list if full.
85    #[inline]
86    pub fn next_available(&self) -> usize {
87        match self.next {
88            Slot::Next(index) => index,
89            _ => self.filled_length
90        }
91    }
92
93    /// Removes and returns the value at the given index or None if the index is empty.
94    /// 
95    /// This operation preserves ordering and is always *O*(1).
96    #[inline]
97    pub fn remove(&mut self, index: usize) -> Option<T> {
98
99        // The data struture guarantees the following operations are valid.
100        // Next(index) -> self.next -> Value(value) -> return Some(value)
101        match &mut self.slots[index] {
102            value @ Slot::Value(_) => unsafe {
103                self.filled_length -= 1;
104                replace(value, replace(&mut self.next, Slot::Next(index)))
105                    .to_some_unchecked()
106            },
107            _ => None
108        }
109    }
110
111    #[inline]
112    /// Returns the number of filled slots in the list.
113    pub const fn filled(&self) -> usize {
114        self.filled_length
115    }
116
117    #[inline]
118    /// Returns the length of the list, including empty slots.
119    pub fn size(&self) -> usize {
120        self.slots.len()
121    }
122
123    #[inline]
124    /// Returns the number of free slots in the list.
125    pub fn free(&self) -> usize {
126        self.slots.len() - self.filled_length
127    }
128
129    #[inline]
130    /// Clears the freelist, removing all values.
131    pub fn clear(&mut self) {
132        self.slots.clear();
133        self.next = Slot::Empty;
134        self.filled_length = 0;
135    }
136
137    #[inline]
138    /// Reserves the minimum capacity for at least `n` more elements.  This function will
139    /// take into account any free slots within the underlying list.
140    pub fn reserve(&mut self, n: usize) {
141        self.slots.reserve_exact(n - self.free());
142    }
143
144
145    /// Returns a reference to the element at the given index,
146    /// or `None` if the index is a free slot.
147    #[inline]
148    pub fn get(&self, index: usize) -> Option<&T> {
149        match self.slots[index] {
150            Slot::Value(ref value) => Some(value),
151            _ => None,
152        }
153    }
154
155    /// Returns a mutable reference to the element at the given index,
156    /// or `None` if the index is a free slot.
157    #[inline]
158    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
159        match self.slots[index] {
160            Slot::Value(ref mut value) => Some(value),
161            _ => None,
162        }
163    }
164
165    /// Returns a reference to the element at the given index, without
166    /// doing bounds checking or asserting the status of the slot.
167    /// 
168    /// See [`get`](Freelist::get) for a safe alternative.
169    /// 
170    /// # Safety
171    /// Calling this method with an out-of-bounds index OR on an index that
172    /// is already empty is [undefined behavior]: <https://doc.rust-lang.org/reference/behavior-considered-undefined.html>
173    #[inline]
174    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
175        unsafe { self.slots.get_unchecked(index).as_value_unchecked() }
176    }
177
178    /// Returns a mutable reference to the element at the given index, without
179    /// doing bounds checking or asserting the slot contains a value.
180    /// 
181    /// See [`get_mut`](Freelist::get_mut) for a safe alternative.
182    /// 
183    /// # Safety
184    /// Calling this method with an out-of-bounds index OR on an index that
185    /// is already empty is [undefined behavior]: <https://doc.rust-lang.org/reference/behavior-considered-undefined.html>
186    #[inline]
187    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
188        unsafe { self.slots.get_unchecked_mut(index).as_value_unchecked_mut() }
189
190    }
191
192
193    /// Returns an iterator over the freelist.
194    pub fn iter(&self) -> impl Iterator<Item = &T> {
195        self.slots.iter().filter_map(|c| match c {
196            Slot::Value(value) => Some(value),
197            _ => None
198        })
199    }
200
201    /// Returns a mutable iterator over the freelist.
202    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
203        self.slots.iter_mut().filter_map(|c| match c {
204            Slot::Value(value) => Some(value),
205            _ => None
206        })
207    }
208
209    /// Converts the freelist into an iterator, dropping any empty slots.
210    pub fn into_iter(self)  -> impl Iterator<Item = T> {
211        self.slots.into_iter().filter_map(|c| match c {
212            Slot::Value(value) => Some(value),
213            _ => None
214        })
215    }
216
217}
218
219impl<T> Default for Freelist<T> {
220    fn default() -> Self {
221        Self { slots: Vec::new(), next: Slot::Empty, filled_length: 0 }
222    }
223}
224
225impl<T> Index<usize> for Freelist<T> {
226    type Output = T;
227
228    #[inline]
229    fn index(&self, index: usize) -> &Self::Output {
230        match &self.slots[index] {
231            Slot::Value(element) => element,
232            _ => panic!("attempted to access an empty slot")
233        }
234    }
235}
236
237impl<T> IndexMut<usize> for Freelist<T> {
238
239    #[inline]
240    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
241        match &mut self.slots[index] {
242            Slot::Value(element) => element,
243            _ => panic!("attempted to access an empty slot")
244        }
245    }
246}
247
248impl<T> From<Vec<T>> for Freelist<T> {
249    fn from(data: Vec<T>) -> Self {
250        Self {
251            filled_length: data.len(),
252            next: Slot::Empty,
253            slots: data.into_iter()
254                .map(Slot::from_value)
255                .collect(),
256        }
257    }
258}
259
260impl<T, const N: usize> From<[T; N]> for Freelist<T> {
261    fn from(data: [T; N]) -> Self {
262        Self {
263            filled_length: N,
264            next: Slot::Empty,
265            slots: data.into_iter()
266                .map(Slot::from_value)
267                .collect(),
268        }
269    }
270}
271
272impl<T> FromIterator<T> for Freelist<T> {
273    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
274        let mut len = 0;
275        let data = iter.into_iter()
276            .inspect(|_| len += 1)
277            .map(Slot::from_value)
278            .collect();
279        
280        Self {
281            slots: data,
282            filled_length: len,
283            next: Slot::Empty
284        }
285    }
286}
287
288
289#[cfg(test)]
290mod tests {
291    use super::{
292        Slot::*,
293        Freelist
294    };
295    
296
297    #[test]
298    fn push() {
299        let mut list = Freelist::<f32>::new();
300
301        list.push(0.0);
302        list.push(1.0);
303        list.push(2.0);
304
305        assert_eq!(list.slots, vec![Value(0.0), Value(1.0), Value(2.0)]);
306
307        println!("{:?}", list.slots);
308
309    }
310
311    #[test]
312    fn remove() {
313        let mut list = Freelist::<f32> {
314            slots: vec![Value(0.0), Value(1.0), Value(2.0)],
315            next: Empty,
316            filled_length: 3,
317        };
318
319        let removed = list.remove(1);
320
321        assert_eq!(removed, Some(1.0));
322        assert_eq!(list.next, Next(1));
323        assert_eq!(list.slots, vec![Value(0.0), Empty, Value(2.0)]);
324    }
325
326    #[test]
327    fn remove_then_push() {
328        let mut list = Freelist::<f32> {
329            slots: vec![Value(0.0), Value(1.0), Value(2.0)],
330            next: Empty,
331            filled_length: 3,
332        };
333
334        list.remove(1);
335        list.push(3.0);
336
337        assert_eq!(list.next, Empty);
338        assert_eq!(list.slots, vec![Value(0.0), Value(3.0), Value(2.0)]);
339    }
340
341    #[test]
342    fn remove_then_push_multiple() {
343        let mut list = Freelist::<f32> {
344            slots: vec![Value(0.0), Value(1.0), Value(2.0)],
345            next: Empty,
346            filled_length: 3,
347        };
348
349        list.remove(1);
350        list.remove(2);
351        list.push(3.0);
352        list.push(4.0);
353        list.push(5.0);
354
355        assert_eq!(list.next, Empty);
356        assert_eq!(list.slots, vec![Value(0.0), Value(4.0), Value(3.0), Value(5.0)]);
357    }
358
359    #[test]
360    fn clear() {
361        let mut list = Freelist::<f32> {
362            slots: vec![Value(0.0), Value(1.0), Value(2.0)],
363            next: Empty,
364            filled_length: 3,
365        };
366
367        list.clear();
368        assert_eq!(list.next, Empty);
369        assert_eq!(list.slots, vec![]);
370    }
371
372}
fffl/lib.rs

fffl/
lib.rs
