use crate::packed_option::ReservedValue;
use crate::EntityRef;
use core::marker::PhantomData;
use core::mem;
use std::vec::Vec;
#[derive(Clone, Debug)]
pub struct EntityList<T: EntityRef + ReservedValue> {
index: u32,
unused: PhantomData<T>,
}
impl<T: EntityRef + ReservedValue> Default for EntityList<T> {
fn default() -> Self {
Self {
index: 0,
unused: PhantomData,
}
}
}
#[derive(Clone, Debug)]
pub struct ListPool<T: EntityRef + ReservedValue> {
data: Vec<T>,
free: Vec<usize>,
}
type SizeClass = u8;
fn sclass_size(sclass: SizeClass) -> usize {
4 << sclass
}
fn sclass_for_length(len: usize) -> SizeClass {
30 - (len as u32 | 3).leading_zeros() as SizeClass
}
fn is_sclass_min_length(len: usize) -> bool {
len > 3 && len.is_power_of_two()
}
impl<T: EntityRef + ReservedValue> ListPool<T> {
pub fn new() -> Self {
Self {
data: Vec::new(),
free: Vec::new(),
}
}
pub fn clear(&mut self) {
self.data.clear();
self.free.clear();
}
fn len_of(&self, list: &EntityList<T>) -> Option<usize> {
let idx = list.index as usize;
self.data.get(idx.wrapping_sub(1)).map(|len| len.index())
}
fn alloc(&mut self, sclass: SizeClass) -> usize {
match self.free.get(sclass as usize).cloned() {
Some(head) if head > 0 => {
self.free[sclass as usize] = self.data[head].index();
head - 1
}
_ => {
let offset = self.data.len();
self.data
.resize(offset + sclass_size(sclass), T::reserved_value());
offset
}
}
}
fn free(&mut self, block: usize, sclass: SizeClass) {
let sclass = sclass as usize;
if self.free.len() <= sclass {
self.free.resize(sclass + 1, 0);
}
self.data[block] = T::new(0);
self.data[block + 1] = T::new(self.free[sclass]);
self.free[sclass] = block + 1
}
fn mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [T], &mut [T]) {
if block0 < block1 {
let (s0, s1) = self.data.split_at_mut(block1);
(&mut s0[block0..], s1)
} else {
let (s1, s0) = self.data.split_at_mut(block0);
(s0, &mut s1[block1..])
}
}
fn realloc(
&mut self,
block: usize,
from_sclass: SizeClass,
to_sclass: SizeClass,
elems_to_copy: usize,
) -> usize {
debug_assert!(elems_to_copy <= sclass_size(from_sclass));
debug_assert!(elems_to_copy <= sclass_size(to_sclass));
let new_block = self.alloc(to_sclass);
if elems_to_copy > 0 {
let (old, new) = self.mut_slices(block, new_block);
(&mut new[0..elems_to_copy]).copy_from_slice(&old[0..elems_to_copy]);
}
self.free(block, from_sclass);
new_block
}
}
impl<T: EntityRef + ReservedValue> EntityList<T> {
pub fn new() -> Self {
Default::default()
}
pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self {
let len = slice.len();
if len == 0 {
return Self::new();
}
let block = pool.alloc(sclass_for_length(len));
pool.data[block] = T::new(len);
pool.data[block + 1..=block + len].copy_from_slice(slice);
Self {
index: (block + 1) as u32,
unused: PhantomData,
}
}
pub fn is_empty(&self) -> bool {
self.index == 0
}
pub fn len(&self, pool: &ListPool<T>) -> usize {
pool.len_of(self).unwrap_or(0)
}
pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
self.is_empty() || pool.len_of(self) != None
}
pub fn as_slice<'a>(&'a self, pool: &'a ListPool<T>) -> &'a [T] {
let idx = self.index as usize;
match pool.len_of(self) {
None => &[],
Some(len) => &pool.data[idx..idx + len],
}
}
pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
self.as_slice(pool).get(index).cloned()
}
pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
if self.is_empty() {
None
} else {
Some(pool.data[self.index as usize])
}
}
pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T] {
let idx = self.index as usize;
match pool.len_of(self) {
None => &mut [],
Some(len) => &mut pool.data[idx..idx + len],
}
}
pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
self.as_mut_slice(pool).get_mut(index)
}
pub fn clear(&mut self, pool: &mut ListPool<T>) {
let idx = self.index as usize;
match pool.len_of(self) {
None => debug_assert_eq!(idx, 0, "Invalid pool"),
Some(len) => pool.free(idx - 1, sclass_for_length(len)),
}
self.index = 0;
}
pub fn take(&mut self) -> Self {
mem::replace(self, Default::default())
}
pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
let idx = self.index as usize;
match pool.len_of(self) {
None => {
debug_assert_eq!(idx, 0, "Invalid pool");
let block = pool.alloc(sclass_for_length(1));
pool.data[block] = T::new(1);
pool.data[block + 1] = element;
self.index = (block + 1) as u32;
0
}
Some(len) => {
let new_len = len + 1;
let block;
if is_sclass_min_length(new_len) {
let sclass = sclass_for_length(len);
block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
self.index = (block + 1) as u32;
} else {
block = idx - 1;
}
pool.data[block + new_len] = element;
pool.data[block] = T::new(new_len);
len
}
}
}
fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
let idx = self.index as usize;
let new_len;
let block;
match pool.len_of(self) {
None => {
debug_assert_eq!(idx, 0, "Invalid pool");
if count == 0 {
return &mut [];
}
new_len = count;
block = pool.alloc(sclass_for_length(new_len));
self.index = (block + 1) as u32;
}
Some(len) => {
let sclass = sclass_for_length(len);
new_len = len + count;
let new_sclass = sclass_for_length(new_len);
if new_sclass != sclass {
block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
self.index = (block + 1) as u32;
} else {
block = idx - 1;
}
}
}
pool.data[block] = T::new(new_len);
&mut pool.data[block + 1..block + 1 + new_len]
}
pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
where
I: IntoIterator<Item = T>,
{
for x in elements {
self.push(x, pool);
}
}
pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
self.push(element, pool);
let seq = self.as_mut_slice(pool);
if index < seq.len() {
let tail = &mut seq[index..];
for i in (1..tail.len()).rev() {
tail[i] = tail[i - 1];
}
tail[0] = element;
} else {
debug_assert_eq!(index, seq.len());
}
}
pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
let len;
{
let seq = self.as_mut_slice(pool);
len = seq.len();
debug_assert!(index < len);
for i in index..len - 1 {
seq[i] = seq[i + 1];
}
}
if len == 1 {
self.clear(pool);
return;
}
let mut block = self.index as usize - 1;
if is_sclass_min_length(len) {
let sclass = sclass_for_length(len);
block = pool.realloc(block, sclass, sclass - 1, len);
self.index = (block + 1) as u32;
}
pool.data[block] = T::new(len - 1);
}
pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
let len = self.len(pool);
debug_assert!(index < len);
if index == len - 1 {
self.remove(index, pool);
} else {
{
let seq = self.as_mut_slice(pool);
seq.swap(index, len - 1);
}
self.remove(len - 1, pool);
}
}
pub fn grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>) {
let data = self.grow(count, pool);
for i in (index + count..data.len()).rev() {
data[i] = data[i - count];
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use super::{sclass_for_length, sclass_size};
use crate::EntityRef;
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Inst(u32);
entity_impl!(Inst, "inst");
#[test]
fn size_classes() {
assert_eq!(sclass_size(0), 4);
assert_eq!(sclass_for_length(0), 0);
assert_eq!(sclass_for_length(1), 0);
assert_eq!(sclass_for_length(2), 0);
assert_eq!(sclass_for_length(3), 0);
assert_eq!(sclass_for_length(4), 1);
assert_eq!(sclass_for_length(7), 1);
assert_eq!(sclass_for_length(8), 2);
assert_eq!(sclass_size(1), 8);
for l in 0..300 {
assert!(sclass_size(sclass_for_length(l)) >= l + 1);
}
}
#[test]
fn block_allocator() {
let mut pool = ListPool::<Inst>::new();
let b1 = pool.alloc(0);
let b2 = pool.alloc(1);
let b3 = pool.alloc(0);
assert_ne!(b1, b2);
assert_ne!(b1, b3);
assert_ne!(b2, b3);
pool.free(b2, 1);
let b2a = pool.alloc(1);
let b2b = pool.alloc(1);
assert_ne!(b2a, b2b);
assert!(b2a == b2 || b2b == b2);
pool.free(b1, 0);
pool.free(b3, 0);
let b1a = pool.alloc(0);
let b3a = pool.alloc(0);
assert_ne!(b1a, b3a);
assert!(b1a == b1 || b1a == b3);
assert!(b3a == b1 || b3a == b3);
}
#[test]
fn empty_list() {
let pool = &mut ListPool::<Inst>::new();
let mut list = EntityList::<Inst>::default();
{
let ilist = &list;
assert!(ilist.is_empty());
assert_eq!(ilist.len(pool), 0);
assert_eq!(ilist.as_slice(pool), &[]);
assert_eq!(ilist.get(0, pool), None);
assert_eq!(ilist.get(100, pool), None);
}
assert_eq!(list.as_mut_slice(pool), &[]);
assert_eq!(list.get_mut(0, pool), None);
assert_eq!(list.get_mut(100, pool), None);
list.clear(pool);
assert!(list.is_empty());
assert_eq!(list.len(pool), 0);
assert_eq!(list.as_slice(pool), &[]);
assert_eq!(list.first(pool), None);
}
#[test]
fn from_slice() {
let pool = &mut ListPool::<Inst>::new();
let list = EntityList::<Inst>::from_slice(&[Inst(0), Inst(1)], pool);
assert!(!list.is_empty());
assert_eq!(list.len(pool), 2);
assert_eq!(list.as_slice(pool), &[Inst(0), Inst(1)]);
assert_eq!(list.get(0, pool), Some(Inst(0)));
assert_eq!(list.get(100, pool), None);
let list = EntityList::<Inst>::from_slice(&[], pool);
assert!(list.is_empty());
assert_eq!(list.len(pool), 0);
assert_eq!(list.as_slice(pool), &[]);
assert_eq!(list.get(0, pool), None);
assert_eq!(list.get(100, pool), None);
}
#[test]
fn push() {
let pool = &mut ListPool::<Inst>::new();
let mut list = EntityList::<Inst>::default();
let i1 = Inst::new(1);
let i2 = Inst::new(2);
let i3 = Inst::new(3);
let i4 = Inst::new(4);
assert_eq!(list.push(i1, pool), 0);
assert_eq!(list.len(pool), 1);
assert!(!list.is_empty());
assert_eq!(list.as_slice(pool), &[i1]);
assert_eq!(list.first(pool), Some(i1));
assert_eq!(list.get(0, pool), Some(i1));
assert_eq!(list.get(1, pool), None);
assert_eq!(list.push(i2, pool), 1);
assert_eq!(list.len(pool), 2);
assert!(!list.is_empty());
assert_eq!(list.as_slice(pool), &[i1, i2]);
assert_eq!(list.first(pool), Some(i1));
assert_eq!(list.get(0, pool), Some(i1));
assert_eq!(list.get(1, pool), Some(i2));
assert_eq!(list.get(2, pool), None);
assert_eq!(list.push(i3, pool), 2);
assert_eq!(list.len(pool), 3);
assert!(!list.is_empty());
assert_eq!(list.as_slice(pool), &[i1, i2, i3]);
assert_eq!(list.first(pool), Some(i1));
assert_eq!(list.get(0, pool), Some(i1));
assert_eq!(list.get(1, pool), Some(i2));
assert_eq!(list.get(2, pool), Some(i3));
assert_eq!(list.get(3, pool), None);
assert_eq!(list.push(i4, pool), 3);
assert_eq!(list.len(pool), 4);
assert!(!list.is_empty());
assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
assert_eq!(list.first(pool), Some(i1));
assert_eq!(list.get(0, pool), Some(i1));
assert_eq!(list.get(1, pool), Some(i2));
assert_eq!(list.get(2, pool), Some(i3));
assert_eq!(list.get(3, pool), Some(i4));
assert_eq!(list.get(4, pool), None);
list.extend([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
assert_eq!(list.len(pool), 12);
assert_eq!(
list.as_slice(pool),
&[i1, i2, i3, i4, i1, i1, i2, i2, i3, i3, i4, i4]
);
}
#[test]
fn insert_remove() {
let pool = &mut ListPool::<Inst>::new();
let mut list = EntityList::<Inst>::default();
let i1 = Inst::new(1);
let i2 = Inst::new(2);
let i3 = Inst::new(3);
let i4 = Inst::new(4);
list.insert(0, i4, pool);
assert_eq!(list.as_slice(pool), &[i4]);
list.insert(0, i3, pool);
assert_eq!(list.as_slice(pool), &[i3, i4]);
list.insert(2, i2, pool);
assert_eq!(list.as_slice(pool), &[i3, i4, i2]);
list.insert(2, i1, pool);
assert_eq!(list.as_slice(pool), &[i3, i4, i1, i2]);
list.remove(3, pool);
assert_eq!(list.as_slice(pool), &[i3, i4, i1]);
list.remove(2, pool);
assert_eq!(list.as_slice(pool), &[i3, i4]);
list.remove(0, pool);
assert_eq!(list.as_slice(pool), &[i4]);
list.remove(0, pool);
assert_eq!(list.as_slice(pool), &[]);
assert!(list.is_empty());
}
#[test]
fn growing() {
let pool = &mut ListPool::<Inst>::new();
let mut list = EntityList::<Inst>::default();
let i1 = Inst::new(1);
let i2 = Inst::new(2);
let i3 = Inst::new(3);
let i4 = Inst::new(4);
list.grow_at(0, 0, pool);
assert_eq!(list.len(pool), 0);
assert!(list.is_empty());
list.grow_at(0, 2, pool);
assert_eq!(list.len(pool), 2);
list.as_mut_slice(pool).copy_from_slice(&[i2, i3]);
list.grow_at(1, 0, pool);
assert_eq!(list.as_slice(pool), &[i2, i3]);
list.grow_at(1, 1, pool);
list.as_mut_slice(pool)[1] = i1;
assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
list.grow_at(3, 0, pool);
assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
list.grow_at(3, 1, pool);
list.as_mut_slice(pool)[3] = i4;
assert_eq!(list.as_slice(pool), &[i2, i1, i3, i4]);
}
}