use crate::histogram::MAX_CHAIN_LEN;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ListHandle {
index: u32,
generation: u32,
len: u32,
}
impl Default for ListHandle {
fn default() -> Self {
Self { index: 0, generation: 0, len: 0 }
}
}
const MAX_SIZE_CLAS: SizeClass = sclass_for_length(super::MAX_CHAIN_LEN - 1);
const NUM_SIZE_CLASS: usize = MAX_SIZE_CLAS as usize + 1;
#[derive(Clone, Debug)]
pub struct ListPool {
data: Vec<u32>,
free: [u32; NUM_SIZE_CLASS],
generation: u32,
}
type SizeClass = u8;
#[inline]
const fn sclass_size(sclass: SizeClass) -> usize {
4 << sclass
}
#[inline]
const fn sclass_for_length(len: u32) -> SizeClass {
30 - (len | 3).leading_zeros() as SizeClass
}
#[inline]
fn is_sclass_max_length(len: u32) -> bool {
len > 3 && len.is_power_of_two()
}
impl ListPool {
pub fn new(capacity: u32) -> Self {
Self {
data: Vec::with_capacity(capacity as usize),
free: [u32::MAX; NUM_SIZE_CLASS],
generation: 1,
}
}
pub fn clear(&mut self) {
self.data.clear();
self.free.fill(u32::MAX);
self.generation += 1;
}
fn alloc(&mut self, sclass: SizeClass) -> usize {
let freelist_head = self.free[sclass as usize];
if freelist_head == u32::MAX {
let offset = self.data.len();
self.data.resize(offset + sclass_size(sclass), u32::MAX);
offset
} else {
self.free[sclass as usize] = self.data[freelist_head as usize];
freelist_head as usize
}
}
fn free(&mut self, block: usize, sclass: SizeClass) {
let sclass = sclass as usize;
self.data[block] = self.free[sclass] as u32;
self.free[sclass] = block as u32
}
fn mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [u32], &mut [u32]) {
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);
let (old, new) = self.mut_slices(block, new_block);
new[0..elems_to_copy].copy_from_slice(&old[0..elems_to_copy]);
self.free(block, from_sclass);
new_block
}
}
impl ListHandle {
#[allow(clippy::len_without_is_empty)]
pub fn len(&self, pool: &ListPool) -> u32 {
if self.generation == pool.generation {
self.len
} else {
0
}
}
pub fn as_slice<'a>(&'a self, pool: &'a ListPool) -> &'a [u32] {
let idx = self.index as usize;
match self.len(pool) {
0 => &[],
1 => std::slice::from_ref(&self.index),
len => &pool.data[idx..idx + len as usize],
}
}
pub fn push(&mut self, element: u32, pool: &mut ListPool) {
let len = self.len(pool);
match len {
0 => {
self.generation = pool.generation;
self.index = element;
self.len = 1;
}
1 => {
let block = pool.alloc(0);
pool.data[block] = self.index;
pool.data[block + 1] = element;
self.index = block as u32;
self.len = 2;
}
2..=MAX_CHAIN_LEN => {
let block;
let idx = self.index as usize;
if is_sclass_max_length(len) {
let sclass = sclass_for_length(len);
block = pool.realloc(idx, sclass - 1, sclass, len as usize);
self.index = block as u32;
} else {
block = idx;
}
pool.data[block + len as usize] = element;
self.len += 1;
}
_ => (),
}
}
}