use std::marker::PhantomData;
use std::ptr;
use std::ptr::null_mut;
#[derive(Debug)]
struct Entry<T> {
index: usize,
data: Option<T>,
next: *mut Entry<T>,
prev: *mut Entry<T>,
}
#[derive(Debug)]
pub struct Persist<T> {
entries: Vec<Entry<T>>,
free: *mut Entry<T>,
used: *mut Entry<T>,
length: usize,
}
impl<T> Persist<T> {
#[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];
}
#[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(),
});
if i > 0 {
Persist::link_to_prev(i, &mut entries);
}
}
let first = &mut entries[0] as *mut Entry<T>;
Persist {
entries,
free: first,
used: ptr::null_mut(),
length: 0,
}
}
#[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(),
});
if i > 0 {
Persist::link_to_prev(i, &mut entries);
}
}
let first = &mut entries[0] as *mut Entry<T>;
Persist {
entries,
free: ptr::null_mut(),
used: first,
length: capacity,
}
}
#[inline]
pub fn from(slice: &[T]) -> Persist<T>
where
T: Clone,
{
let mut entries = Vec::with_capacity(slice.len());
for i in 0..slice.len() {
entries.push(Entry {
index: i,
data: Some(slice[i].clone()),
next: ptr::null_mut(),
prev: ptr::null_mut(),
});
if i > 0 {
Persist::link_to_prev(i, &mut entries);
}
}
let first = &mut entries[0] as *mut Entry<T>;
Persist {
entries,
free: ptr::null_mut(),
used: first,
length: slice.len(),
}
}
#[inline]
pub fn len(&self) -> usize {
self.length
}
#[inline]
pub fn capacity(&self) -> usize {
self.entries.capacity()
}
#[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];
}
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 = &mut self.entries[0];
self.used = null_mut();
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
}
#[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
}
#[inline]
pub fn push(&mut self, value: T) -> Option<usize> {
unsafe {
if let Some(mut into_used) = self.free.as_mut() {
into_used.data = Some(value);
let next_free = into_used.next;
Persist::disassociate_entry(into_used);
self.free = next_free;
if let Some(head_free) = self.free.as_mut() {
head_free.prev = ptr::null_mut();
}
if let Some(mut used) = self.used.as_mut() {
into_used.next = used;
used.prev = into_used;
}
self.used = into_used;
self.length += 1;
return Some((&*self.used).index);
}
}
None
}
#[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 {
prev.next = ptr::null_mut();
}
} else if let Some(mut next) = slot.next.as_mut() {
next.prev = ptr::null_mut();
}
}
slot.next = ptr::null_mut();
slot.prev = ptr::null_mut();
}
#[inline]
pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
if self.entries[index].data.is_none() {
let mut slot = &mut self.entries[index];
Persist::disassociate_entry(slot);
slot.prev = ptr::null_mut();
unsafe {
if let Some(mut first_used) = self.used.as_mut() {
slot.next = first_used;
first_used.prev = slot
}
}
self.used = &mut self.entries[index];
}
let mut data: Option<T> = Some(value);
std::mem::swap(&mut self.entries[index].data, &mut data);
self.length += 1;
return data;
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
unsafe {
if let Some(slot) = self.used.as_mut() {
if let Some(mut next) = slot.next.as_mut() {
next.prev = ptr::null_mut();
self.used = next;
}
self.length -= 1;
return std::mem::take(&mut slot.data);
}
}
None
}
#[inline]
pub fn remove(&mut self, index: usize) -> Option<T> {
let mut slot = &mut self.entries[index];
Persist::disassociate_entry(slot);
slot.prev = ptr::null_mut();
unsafe {
if let Some(mut first_free) = self.free.as_mut() {
slot.next = first_free;
first_free.prev = slot;
}
}
self.length -= 1;
self.free = &mut self.entries[index];
return std::mem::take(&mut self.entries[index].data);
}
#[inline]
pub fn iter(&self) -> Iter<T> {
unsafe {
if let Some(entry) = self.used.as_ref() {
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> {
unsafe {
if let Some(entry) = self.used.as_mut() {
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.clone();
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.clone();
self.n_entries -= 1;
data
}
}
}
impl<T: Clone> From<&[T]> for Persist<T> {
fn from(s: &[T]) -> Persist<T> {
Persist::from(s)
}
}
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 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;
struct Velocity(f32);
let mut persist = Persist::with_capacity(LIMIT);
for _ in 0..LIMIT {
persist.push(Velocity(1.0));
}
let mut accum = 0.0;
for x in persist.iter() {
accum += x.0;
}
assert_eq!(accum, LIMIT as f32);
}
#[test]
fn from_slice_reserve() {
let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let persist = Persist::from(&ar[..]);
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);
}
}