persist_o_vec/

lib.rs

//! The purpose of "persist-o-vec" is to:
//!
//! - prevent reallocation
//! - remove items without shifting right to left
//! - re-use freed slots, pop, push, and remove, fast
//! - iterate over used slots only
//!
//! As such, you must allocate what you need before use up to the maximum determined
//! by the chosen indexer feature. In future there will be an option to increase
//! the capacity if required.
//!
//! Use should be similar to `Vec`.
//!
//! **WIP!**

use std::marker::PhantomData;
use std::ptr;

#[derive(Debug)]
struct Entry<T> {
    index: usize,
    data: Option<T>,
    // The pointer must always be created from mutable
    next: *mut Entry<T>,
    prev: *mut Entry<T>,
    _pin: std::marker::PhantomPinned,
}

/// Iteration will not always be in order
#[derive(Debug)]
pub struct Persist<T> {
    entries: Vec<Entry<T>>,
    /// contains the indexes to `None` slots
    // The pointer must always be created from mutable
    free: Option<*mut Entry<T>>,
    /// contains the indexes to used slots
    // The pointer must always be created from mutable
    used: Option<*mut Entry<T>>,
    length: usize,
}

impl<T> Persist<T> {
    /// Ensure that the current and previous Entry are linked
    #[inline(always)]
    fn link_to_prev(i: usize, entries: &mut Vec<Entry<T>>) {
        entries[i - 1].next = &mut entries[i];
        entries[i].prev = &mut entries[i - 1];
    }

    /// Allocate with capacity.
    ///
    /// This is the only way to create a new persistent vec.
    ///
    /// # Panics
    ///
    /// Will panic if the selected capacity is larger than the ability for
    /// `Persist` to internally index in to
    #[inline]
    pub fn with_capacity(capacity: usize) -> Persist<T> {
        let mut entries = Vec::with_capacity(capacity);
        for i in 0..capacity {
            entries.push(Entry {
                index: i,
                data: None,
                next: ptr::null_mut(),
                prev: ptr::null_mut(),
                _pin: std::marker::PhantomPinned,
            });
            if i > 0 {
                Persist::link_to_prev(i, &mut entries);
            }
        }
        let first = &mut entries[0] as *mut Entry<T>;
        Persist {
            entries,
            free: Some(first),
            used: None,
            length: 0,
        }
    }

    /// Allocate with capacity and fill with values produced by a closure
    ///
    /// This is a secondary way to create a new persistent vec and is a good way
    /// to do so if you know the storage needs to be filled.
    ///
    /// # Panics
    ///
    /// Will panic if the selected capacity is larger than the ability for
    /// `Persist` to internally index in to
    #[inline]
    pub fn with_capacity_filled_by<F>(capacity: usize, func: F) -> Persist<T>
    where
        F: Fn() -> T,
    {
        let mut entries = Vec::with_capacity(capacity);
        for i in 0..capacity {
            entries.push(Entry {
                index: i,
                data: Some(func()),
                next: ptr::null_mut(),
                prev: ptr::null_mut(),
                _pin: std::marker::PhantomPinned,
            });
            if i > 0 {
                Persist::link_to_prev(i, &mut entries);
            }
        }
        let first = &mut entries[0] as *mut Entry<T>;
        Persist {
            entries,
            free: None,
            used: Some(first),
            length: capacity,
        }
    }

    #[inline]
    pub fn from(slice: &[T]) -> Persist<T>
    where
        T: Clone,
    {
        let mut entries = Vec::with_capacity(slice.len());
        for (i, obj) in slice.iter().enumerate() {
            entries.push(Entry {
                index: i,
                data: Some(obj.clone()),
                next: ptr::null_mut(),
                prev: ptr::null_mut(),
                _pin: std::marker::PhantomPinned,
            });
            if i > 0 {
                Persist::link_to_prev(i, &mut entries);
            }
        }
        let first = &mut entries[0] as *mut Entry<T>;
        Persist {
            entries,
            free: None,
            used: Some(first),
            length: slice.len(),
        }
    }

    // TODO: need to rebuilt the linked list after to ensure that
    //  it is still valid
    //
    //    /// Reserve extra capacity. This may move the allocations and invalidate any
    //    /// pointers that are held to stored data.
    //    #[inline]
    //    pub fn reserve(&mut self, additional: usize) {
    //        let old_cap = self.entries.len();
    //        let new_cap = self.entries.len() + additional;
    //        self.entries.reserve_exact(additional);
    //        for i in old_cap..new_cap {
    //            self.entries.push(Entry {
    //                data: None,
    //                next: ptr::null_mut(),
    //                prev: ptr::null_mut(),
    //            });
    //            if i > old_cap {
    //                Persist::link_to_prev(i, &mut self.entries);
    //            }
    //        }
    //        // If there is a free, append it to the end of the new alloc
    //        unsafe {
    //            if let Some(mut free) = self.free.as_mut() {
    //                free.prev = &mut self.entries[new_cap - 1];
    //                self.entries[new_cap - 1].next = free;
    //            }
    //        }
    //        self.free = &mut self.entries[old_cap];
    //    }

    /// Returns the actual used length regardless of capacity
    #[inline]
    pub fn len(&self) -> usize {
        self.length
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    /// Returns the storage capacity
    #[inline]
    pub fn capacity(&self) -> usize {
        self.entries.capacity()
    }

    /// Clear the storage out while keeping allocated memory
    ///
    /// Should not ever panic
    #[inline]
    pub fn clear(&mut self) {
        for i in 0..self.entries.len() {
            self.entries[i].data = None;
            if i > 0 {
                self.entries[i - 1].next = &mut self.entries[i];
                self.entries[i].prev = &mut self.entries[i - 1];
            }
            // make sure head and tail are reset
            if i == 0 {
                self.entries[i].prev = ptr::null_mut();
            }
            if i == self.entries.len() - 1 {
                self.entries[i].next = ptr::null_mut();
            }
        }
        self.free = Some(&mut self.entries[0]);
        self.used = None;
        self.length = 0;
    }

    #[inline]
    pub fn get(&self, index: usize) -> Option<&T> {
        if let Some(entry) = self.entries.get(index) {
            return entry.data.as_ref();
        }
        None
    }

    #[inline]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if let Some(entry) = self.entries.get_mut(index) {
            return entry.data.as_mut();
        }
        None
    }

    /// Check if there is a value at this index
    #[inline]
    pub fn is_index_live(&self, index: usize) -> bool {
        if let Some(entry) = self.entries.get(index) {
            if entry.data.is_some() {
                return true;
            }
        }
        false
    }

    // TODO: Push top, push bottom
    /// Push `T` on to storage.
    ///
    /// A push is not guaranteed to push in any
    /// particular order if the internal storage has empty locations (typical after
    /// many `remove`). For this reason it will return the index pushed to.
    ///
    /// Returns `None` if there are no free slots left
    #[inline]
    pub fn push(&mut self, value: T) -> Option<usize> {
        unsafe {
            if let Some(into_used) = self.free.as_ref() {
                if let Some(mut into_used) = into_used.as_mut() {
                    into_used.data = Some(value);
                    // move next free to head
                    let next_free = into_used.next;
                    Persist::disassociate_entry(into_used);
                    self.free = Some(next_free);
                    // make it head
                    if let Some(head_free) = self.free {
                        if let Some(head_free) = head_free.as_mut() {
                            head_free.prev = ptr::null_mut();
                        }
                    }

                    if let Some(used) = self.used {
                        into_used.next = used;
                        (*used).prev = into_used;
                    }
                    self.used = Some(into_used);
                    self.length += 1;
                    return Some(into_used.index);
                }
            }
        }
        None
    }

    /// Pulls the entry out of the linked list it is in and nulls its next/prev
    #[inline(always)]
    fn disassociate_entry(slot: &mut Entry<T>) {
        unsafe {
            if let Some(mut prev) = slot.prev.as_mut() {
                if let Some(mut next) = slot.next.as_mut() {
                    prev.next = next;
                    next.prev = prev;
                } else {
                    // only prev?
                    prev.next = ptr::null_mut();
                }
            } else if let Some(mut next) = slot.next.as_mut() {
                // only next?
                next.prev = ptr::null_mut();
            }
        }
        slot.next = ptr::null_mut();
        slot.prev = ptr::null_mut();
    }

    /// Insert `T` at location. Returns existing value in that location or `None`.
    ///
    /// # Panics
    ///
    /// Will panic is the index is out of range
    #[inline]
    pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
        // check if used first
        if self.entries[index].data.is_none() {
            let mut slot = &mut self.entries[index];
            // remove it out of links
            Persist::disassociate_entry(slot);
            // make it the head
            slot.prev = ptr::null_mut();
            // add it to used
            unsafe {
                if let Some(first_used) = self.used {
                    slot.next = first_used;
                    (*first_used).prev = slot
                }
            }

            self.used = Some(&mut self.entries[index]);
        }

        let mut data: Option<T> = Some(value);
        std::mem::swap(&mut self.entries[index].data, &mut data);
        self.length += 1;
        data
    }

    // TODO: pop top, pop bottom
    /// Pop the last value in the `Persist`
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        unsafe {
            if let Some(slot) = self.used {
                // Shift next to head
                if let Some(mut next) = (*slot).next.as_mut() {
                    next.prev = ptr::null_mut();
                    self.used = Some(next);
                }
                self.length -= 1;
                // Yeet!
                return std::mem::take(&mut (*slot).data);
            }
        }
        None
    }

    /// Remove the item at this index and return it if it exists. Does not shift
    /// elements after it to the left.
    #[inline]
    pub fn remove(&mut self, index: usize) -> Option<T> {
        let mut slot = &mut self.entries[index];
        // remove it out of links
        Persist::disassociate_entry(slot);
        // make it the head
        slot.prev = ptr::null_mut();
        // add it to used
        unsafe {
            if let Some(first_free) = self.free {
                if let Some(first_free) = first_free.as_mut() {
                    slot.next = first_free;
                    (*first_free).prev = slot;
                }
            }
        }

        self.length -= 1;
        self.free = Some(&mut self.entries[index]);
        // Yeet!
        std::mem::take(&mut self.entries[index].data)
    }

    #[inline]
    pub fn iter(&self) -> Iter<T> {
        if let Some(entry) = self.used {
            return Iter {
                entry,
                n_entries: self.length,
                phantom: PhantomData,
            };
        };

        Iter {
            entry: &self.entries[0],
            n_entries: self.length,
            phantom: PhantomData,
        }
    }

    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<T> {
        if let Some(entry) = self.used {
            return IterMut {
                entry,
                n_entries: self.length,
                phantom: PhantomData,
            };
        };
        IterMut {
            entry: &mut self.entries[0],
            n_entries: self.length,
            phantom: PhantomData,
        }
    }
}

#[derive(Debug)]
pub struct Iter<'a, T> {
    entry: *const Entry<T>,
    n_entries: usize,
    phantom: PhantomData<&'a T>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        if self.n_entries == 0 {
            return None;
        }

        unsafe {
            let data: Option<&'a T> = (*self.entry).data.as_ref();
            self.entry = (*self.entry).next;
            self.n_entries -= 1;
            data
        }
    }
}

#[derive(Debug)]
pub struct IterMut<'a, T> {
    entry: *mut Entry<T>,
    n_entries: usize,
    phantom: PhantomData<&'a mut T>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        if self.n_entries == 0 {
            return None;
        }

        unsafe {
            let data: Option<&'a mut T> = (*self.entry).data.as_mut();
            self.entry = (*self.entry).next;
            self.n_entries -= 1;
            data
        }
    }
}

/// Total capacity will be set from the length of the slice
impl<T: Clone> From<&[T]> for Persist<T> {
    fn from(s: &[T]) -> Persist<T> {
        Persist::from(s)
    }
}

/// Total capacity will be set from the length of the slice
impl<T: Clone> From<&mut [T]> for Persist<T> {
    fn from(s: &mut [T]) -> Persist<T> {
        Persist::from(s)
    }
}

#[cfg(test)]
mod tests {
    use crate::{Entry, Persist};

    #[test]
    fn with_capacity() {
        let p: Persist<u32> = Persist::with_capacity(10);
        assert_eq!(p.entries.capacity(), 10);
    }

    #[test]
    fn get() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        let two = p.get(1).unwrap();
        assert_eq!(*two, 14);
    }

    #[test]
    fn get_mut() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        {
            let two = p.get_mut(1).unwrap();
            *two *= 2;
        }
        let two = p.get(1).unwrap();
        assert_eq!(*two, 28);
    }

    #[test]
    fn index_validation() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);

        assert!(p.is_index_live(0));
        assert!(p.is_index_live(1));
        assert!(!p.is_index_live(3));
    }

    //    #[test]
    //    fn reserve() {
    //        let mut p: Persist<u32> = Persist::with_capacity(10);
    //
    //        p.push(13);
    //        p.push(14);
    //        p.push(15);
    //
    //        assert_eq!(p.entries.len(), 10);
    //        p.reserve(10);
    //        assert_eq!(p.entries.len(), 20);
    //    }

    #[test]
    fn clear() {
        let _p: Persist<u32> = Persist::with_capacity(10);
    }

    #[test]
    fn pop() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        p.pop();
    }

    #[test]
    fn push_to_full_then_pop_all() {
        #[derive(Debug, PartialOrd, PartialEq)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(50_000);

        for i in 0..50_000 {
            p.push(Heading { x: i });
        }

        for i in (0..50_000).rev() {
            assert_eq!(p.pop().unwrap().x, i);
        }
    }

    #[test]
    fn remove() {
        #[derive(Debug, PartialOrd, PartialEq)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(50);

        for i in 0..50 {
            p.push(Heading { x: i });
        }

        let r = p.remove(10);
        assert_eq!(r, Some(Heading { x: 10 }));

        let r = p.remove(20);
        assert_eq!(r, Some(Heading { x: 20 }));

        let r = p.remove(30);
        assert_eq!(r, Some(Heading { x: 30 }));

        let r = p.remove(22);
        assert_eq!(r, Some(Heading { x: 22 }));
    }

    #[test]
    fn insert() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.push(13);
        p.push(14);
        p.push(15);

        let previous = p.insert(0, 16).unwrap();
        assert_eq!(previous, 13);
        assert_eq!(p.get(0), Some(&16));

        assert!(p.insert(5, 17).is_none());
        assert_eq!(p.get(5), Some(&17));
    }

    #[test]
    fn iter() {
        #[derive(Debug)]
        struct Heading {
            x: usize,
        }

        dbg!(std::mem::size_of::<Heading>());
        dbg!(std::mem::size_of::<Option<Heading>>());
        dbg!(std::mem::size_of::<usize>());
        dbg!(std::mem::size_of::<Entry<Heading>>());

        let mut p: Persist<Heading> = Persist::with_capacity(10);

        p.push(Heading { x: 13 });
        p.push(Heading { x: 14 });
        p.push(Heading { x: 15 });

        let mut accum = 0;
        for x in p.iter() {
            accum += x.x;
        }
        assert_eq!(accum, 42);
    }

    #[test]
    fn iter_mut() {
        #[derive(Debug)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(10);

        p.push(Heading { x: 6 });
        p.push(Heading { x: 6 });
        p.push(Heading { x: 6 });
        p.push(Heading { x: 6 });

        for x in p.iter_mut() {
            x.x += 1;
        }

        for x in p.iter() {
            assert_eq!(x.x, 7);
        }
    }

    #[test]
    fn iter_over_removed() {
        #[derive(Debug, PartialOrd, PartialEq)]
        struct Heading {
            x: u32,
        }

        let mut p: Persist<Heading> = Persist::with_capacity(50);

        for i in 0..50 {
            p.push(Heading { x: i });
        }

        let r = p.remove(10);
        assert_eq!(r, Some(Heading { x: 10 }));

        let r = p.remove(20);
        assert_eq!(r, Some(Heading { x: 20 }));

        let r = p.remove(30);
        assert_eq!(r, Some(Heading { x: 30 }));

        for head in p.iter() {
            assert_ne!(head.x, 10);
            assert_ne!(head.x, 20);
            assert_ne!(head.x, 30);
        }
    }

    #[test]
    fn pst_remove_and_push() {
        const LIMIT: usize = 100_000; //65025;

        struct Velocity(u32);

        let mut persist = Persist::with_capacity(LIMIT);

        for _ in 0..LIMIT {
            persist.push(Velocity(1));
        }

        let mut accum = 0;
        for x in persist.iter() {
            accum += x.0;
        }
        assert_eq!(accum, LIMIT as u32);
    }

    #[test]
    fn from_slice_reserve() {
        let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let persist = Persist::from(&ar[..]);
        //persist.reserve(10);
        assert_eq!(persist.entries.len(), 10);
    }

    #[test]
    #[should_panic]
    fn panic_out_of_bounds() {
        let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let mut persist = Persist::from(&ar[..]);
        persist.insert(10, 10);
    }

    #[test]
    fn insert_at_end() {
        let mut p: Persist<u32> = Persist::with_capacity(10);

        p.insert(9, 15);

        let x = p.get(9).unwrap();
        assert_eq!(*x, 15);

        let mut accum = 0;
        for (i, v) in p.iter().enumerate() {
            assert_eq!(i, 0);
            assert_eq!(*v, 15);
            accum += 1;
        }
        assert_eq!(accum, 1);

        let mut accum = 0;
        for (i, v) in p.iter_mut().enumerate() {
            assert_eq!(i, 0);
            assert_eq!(*v, 15);
            accum += 1;
        }
        assert_eq!(accum, 1);
    }
}