use std::cmp::Ordering;
use std::mem::size_of;
#[cfg(feature = "capacity_u8_len")]
type INDEXER = u8;
#[cfg(feature = "capacity_u16_len")]
type INDEXER = u16;
#[cfg(feature = "capacity_u32_len")]
type INDEXER = u32;
#[cfg(feature = "capacity_u64_len")]
type INDEXER = u64;
#[derive(Clone, Default)]
pub struct Persist<T> {
entries: Vec<Option<T>>,
free: Vec<INDEXER>,
used: Vec<INDEXER>,
}
impl<T> Persist<T> {
#[inline]
pub fn with_capacity(capacity: usize) -> Persist<T> {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
if capacity > limit {
panic!("Selected capacity is larger than ability to index");
}
Persist {
entries: (0..capacity).map(|_| None).collect(),
free: (0..capacity as INDEXER).rev().collect(),
used: Vec::with_capacity(capacity),
}
}
#[inline]
pub fn with_capacity_filled_by<F>(capacity: usize, func: F) -> Persist<T>
where
F: Fn() -> T,
{
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
if capacity > limit {
panic!("Selected capacity is larger than ability to index");
}
Persist {
entries: (0..capacity).map(|_| Some(func())).collect(),
free: Vec::with_capacity(capacity),
used: (0..capacity as INDEXER).collect(),
}
}
#[inline]
pub fn with_capacity_from(capacity: usize, slice: &[T]) -> Persist<T>
where
T: Clone,
{
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
if capacity > limit {
panic!("Selected capacity is larger than ability to index");
}
Persist {
entries: (0..capacity).map(|i| Some(slice[i].clone())).collect(),
free: (slice.len() as INDEXER..capacity as INDEXER)
.rev()
.collect(),
used: (0..slice.len() as INDEXER).collect(),
}
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
if self.entries.len() + additional > limit {
panic!("Additional capacity is larger than ability to index");
}
let old_cap = self.entries.len();
let new_cap = self.entries.len() + additional;
self.entries.reserve_exact(additional);
for _ in old_cap..new_cap {
self.entries.push(None)
}
for i in old_cap..new_cap {
self.insert_free_record(i as INDEXER);
}
}
#[inline]
pub fn len(&self) -> usize {
self.used.len()
}
#[inline]
pub fn clear(&mut self) {
let capacity = self.entries.capacity();
for entry in self.entries.iter_mut() {
*entry = None;
}
self.free = (0..capacity as INDEXER).rev().collect();
self.used.clear();
}
#[inline]
pub fn get(&self, index: usize) -> Option<&T> {
if let Some(value) = self.entries.get(index) {
return value.as_ref();
}
None
}
#[inline]
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
if let Some(value) = self.entries.get_mut(index) {
return value.as_mut();
}
None
}
#[inline]
pub fn is_index_live(&self, index: usize) -> bool {
if let Some(value) = self.entries.get(index) {
if value.is_some() {
return true;
}
}
false
}
#[inline]
pub fn push(&mut self, value: T) -> Option<usize> {
if let Some(free_idx) = self.free.pop() {
self.entries[free_idx as usize] = Some(value);
self.insert_used_record(free_idx);
return Some(free_idx as usize);
}
None
}
#[inline]
pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
if self.entries[index].is_none() {
if let Ok(free_idx) = self.free.binary_search_by(|probe| {
if *probe > index as INDEXER {
return Ordering::Less;
} else if *probe < index as INDEXER {
return Ordering::Greater;
}
Ordering::Equal
}) {
let loc = self.free.remove(free_idx);
self.insert_used_record(loc);
}
}
let mut entry = Some(value);
std::mem::swap(&mut self.entries[index], &mut entry);
return entry;
}
fn insert_free_record(&mut self, index: INDEXER) {
if let Some(idx) = self
.free
.binary_search_by(|probe| {
if *probe > index {
return Ordering::Less;
}
Ordering::Greater
})
.err()
{
self.free.insert(idx, index);
};
}
fn insert_used_record(&mut self, index: INDEXER) {
if let Some(idx) = self.used.binary_search(&index).err() {
self.used.insert(idx, index);
};
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
if let Some(index) = self.used.pop() {
let value = std::mem::take(&mut self.entries[index as usize]);
self.insert_free_record(index);
return value;
}
None
}
#[inline]
pub fn remove(&mut self, index: usize) -> Option<T> {
if self.entries[index].is_some() {
if let Ok(pos) = self.used.binary_search(&(index as INDEXER)) {
let i = self.used.remove(pos);
self.insert_free_record(i);
}
}
return std::mem::take(&mut self.entries[index]);
}
#[inline]
pub fn iter(&self) -> Iter<T> {
Iter {
entries: &self.entries,
used: &self.used,
used_index: 0,
}
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut {
entries: &mut self.entries,
used: &self.used,
used_index: 0,
}
}
}
#[derive(Debug)]
pub struct Iter<'a, T> {
entries: &'a [Option<T>],
used: &'a [INDEXER],
used_index: usize,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
if self.used_index == self.used.len() {
return None;
}
unsafe {
let index = *self.used.get_unchecked(self.used_index) as usize;
let value = self.entries.get_unchecked(index).as_ref();
self.used_index += 1;
value
}
}
}
#[derive(Debug)]
pub struct IterMut<'a, T> {
entries: &'a mut [Option<T>],
used: &'a [INDEXER],
used_index: usize,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
#[inline]
fn next(&mut self) -> Option<&'a mut T> {
if self.used_index == self.used.len() {
return None;
}
unsafe {
let index = *self.used.get_unchecked(self.used_index) as usize;
let value = self.entries.get_unchecked_mut(index) as *mut Option<T>;
self.used_index += 1;
(*value).as_mut()
}
}
}
impl<T: Clone> From<&[T]> for Persist<T> {
fn from(s: &[T]) -> Persist<T> {
let capacity = s.len();
Persist::with_capacity_from(capacity, s)
}
}
impl<T: Clone> From<&mut [T]> for Persist<T> {
fn from(s: &mut [T]) -> Persist<T> {
let capacity = s.len();
Persist::with_capacity_from(capacity, s)
}
}
#[cfg(test)]
mod tests {
use crate::{Persist, INDEXER};
use std::mem::size_of;
#[test]
fn with_capacity() {
let p: Persist<u32> = Persist::with_capacity(10);
assert_eq!(p.entries.capacity(), 10);
}
#[test]
fn return_none_if_push_when_full() {
let mut p: Persist<u32> = Persist::with_capacity(30);
for i in 0..30 {
assert!(p.push(i).is_some());
}
assert!(p.push(31).is_none());
}
#[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.free.len(), 7);
assert_eq!(p.entries.len(), 10);
p.reserve(10);
assert_eq!(p.free.len(), 17);
assert_eq!(p.entries.len(), 20);
}
#[test]
fn clear() {
let p: Persist<u32> = Persist::with_capacity(10);
assert_eq!(p.free.len(), 10);
assert_eq!(p.free[9], 0);
assert_eq!(p.free[0], 9);
}
#[test]
fn pop() {
let mut p: Persist<u32> = Persist::with_capacity(10);
p.push(13);
p.push(14);
p.push(15);
assert_eq!(p.used.len(), 3);
assert_eq!(p.free.len(), 7);
p.pop();
assert_eq!(p.used.len(), 2);
assert_eq!(p.free.len(), 8);
}
#[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 });
}
assert_eq!(p.used.len(), 50);
let r = p.remove(10);
assert_eq!(r, Some(Heading { x: 10 }));
assert!(p.entries[10].is_none());
assert_eq!(p.used.len(), 49);
assert_eq!(p.free.len(), 1);
let r = p.remove(20);
assert_eq!(r, Some(Heading { x: 20 }));
assert!(p.entries[20].is_none());
assert_eq!(p.used.len(), 48);
assert_eq!(p.free.len(), 2);
let r = p.remove(30);
assert_eq!(r, Some(Heading { x: 30 }));
assert!(p.entries[30].is_none());
assert_eq!(p.used.len(), 47);
assert_eq!(p.free.len(), 3);
let r = p.remove(22);
assert_eq!(r, Some(Heading { x: 22 }));
assert!(p.entries[22].is_none());
assert_eq!(p.used.len(), 46);
assert_eq!(p.free.len(), 4);
}
#[test]
fn insert() {
let mut p: Persist<u32> = Persist::with_capacity(10);
p.push(13);
p.push(14);
p.push(15);
assert_eq!(p.used.len(), 3);
assert_eq!(p.free.len(), 7);
let previous = p.insert(0, 16).unwrap();
assert_eq!(previous, 13);
assert_eq!(p.get(0), Some(&16));
assert_eq!(p.free.len(), 7);
assert_eq!(p.used.len(), 3);
assert!(p.insert(5, 17).is_none());
assert_eq!(p.get(5), Some(&17));
assert_eq!(p.free.len(), 6);
assert_eq!(p.used.len(), 4);
}
#[test]
fn iter() {
#[derive(Debug)]
struct Heading {
x: usize,
}
let mut p: Persist<Heading> = Persist::with_capacity(10);
p.push(Heading { x: 13 });
p.push(Heading { x: 14 });
p.push(Heading { x: 15 });
assert_eq!(p.used.len(), 3);
let mut accum = 0;
for (i, x) in p.iter().enumerate() {
assert_eq!(x.x, 13 + i);
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 });
assert_eq!(p.used.len(), 3);
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 });
}
assert_eq!(p.used.len(), 50);
let r = p.remove(10);
assert_eq!(r, Some(Heading { x: 10 }));
assert!(p.entries[10].is_none());
let r = p.remove(20);
assert_eq!(r, Some(Heading { x: 20 }));
assert!(p.entries[20].is_none());
let r = p.remove(30);
assert_eq!(r, Some(Heading { x: 30 }));
assert!(p.entries[30].is_none());
for head in p.iter() {
assert_ne!(head.x, 10);
assert_ne!(head.x, 20);
assert_ne!(head.x, 30);
}
}
#[cfg(feature = "capacity_u8_len")]
#[test]
#[should_panic]
fn panic_if_cap_gt_u8() {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
let _: Persist<u8> = Persist::with_capacity(limit + 1);
}
#[cfg(feature = "capacity_u16_len")]
#[test]
#[should_panic]
fn panic_if_cap_gt_u16() {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
let _: Persist<u8> = Persist::with_capacity(limit + 1);
}
#[cfg(feature = "capacity_u32_len")]
#[test]
#[should_panic]
fn panic_if_cap_gt_u32() {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
let _: Persist<u8> = Persist::with_capacity(limit + 1);
}
#[cfg(feature = "capacity_u64_len")]
#[test]
#[should_panic]
fn panic_if_cap_gt_u64() {
let limit = (255 as INDEXER).pow(size_of::<INDEXER>() as u32) as usize;
let _: Persist<u8> = Persist::with_capacity(limit + 1);
}
#[cfg(feature = "capacity_u16_len")]
#[test]
fn populate() {
const LIMIT: usize = 65025;
let mut persist = Persist::with_capacity(LIMIT);
for _ in 0..LIMIT {
persist.push(10);
}
for i in 0..LIMIT {
persist.remove(i);
}
}
#[test]
fn pst_remove_and_push() {
#[cfg(feature = "capacity_u8_len")]
const LIMIT: usize = 255;
#[cfg(any(
feature = "capacity_u16_len",
feature = "capacity_u32_len",
feature = "capacity_u64_len"
))]
const LIMIT: usize = 10_000;
struct Velocity(f32);
let mut persist = Persist::with_capacity(LIMIT);
assert_eq!(persist.free.len(), LIMIT);
for _ in 0..LIMIT {
persist.push(Velocity(1.0));
}
assert_eq!(persist.used.len(), LIMIT);
let mut a = 0.0;
for _ in 0..100 {
let b = persist.remove(9).unwrap();
a += b.0;
let b = persist.remove(20).unwrap();
a += b.0;
let b = persist.remove(77).unwrap();
a += b.0;
let b = persist.remove(4).unwrap();
a += b.0;
let b = persist.remove(100).unwrap();
a += b.0;
let b = persist.remove(200).unwrap();
a += b.0;
let b = persist.remove(222).unwrap();
a += b.0;
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
persist.push(Velocity(1.0));
}
}
#[test]
fn from_slice_reserve() {
let ar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let mut persist = Persist::from(&ar[..]);
assert_eq!(persist.len(), 10);
persist.reserve(10);
assert_eq!(persist.len(), 10);
assert_eq!(persist.entries.len(), 20);
}
#[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[..]);
assert_eq!(persist.len(), 10);
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);
}
}