use alloc::{alloc::Global, vec::Vec};
use core::alloc::Allocator;
mod checkpoint;
pub mod paged;
mod table;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
Limit,
Allocation,
NativeImage,
Poisoned,
Checkpoint,
Integrity,
Epoch,
}
pub use checkpoint::{ExportError, ImportError, export_records};
#[repr(C)]
#[derive(Clone, Copy)]
pub struct Slot {
occupied: u64,
key: u64,
value: u64,
}
impl Slot {
pub const EMPTY: Self = Self {
occupied: 0,
key: 0,
value: 0,
};
}
pub struct AdmissionError<A: Allocator> {
pub error: Error,
pub slots: Vec<Slot, A>,
}
pub struct Map<A: Allocator + Clone = Global> {
slots: Vec<Slot, A>,
len: usize,
limit: usize,
poisoned: bool,
}
impl Map {
#[must_use]
pub fn new(limit: usize) -> Self {
Self::new_in(limit, Global)
}
}
impl<A: Allocator + Clone> Map<A> {
#[must_use]
pub fn new_in(limit: usize, allocator: A) -> Self {
Self {
slots: Vec::new_in(allocator),
len: 0,
limit,
poisoned: false,
}
}
pub fn admit(slots: Vec<Slot, A>, len: usize, limit: usize) -> Result<Self, AdmissionError<A>> {
if let Err(error) = table::validate(&slots, len, limit) {
return Err(AdmissionError { error, slots });
}
Ok(Self {
slots,
len,
limit,
poisoned: false,
})
}
pub fn release(self) -> Result<(Vec<Slot, A>, usize), Error> {
self.healthy()?;
Ok((self.slots, self.len))
}
pub fn rebuild_in<B: Allocator + Clone>(
&self,
minimum_capacity: usize,
allocator: B,
) -> Result<Map<B>, Error> {
self.healthy()?;
let mut candidate = Map::new_in(self.limit, allocator);
candidate.reserve(minimum_capacity.max(self.len))?;
for slot in &self.slots {
if slot.occupied == 1 {
table::place(&mut candidate.slots, *slot);
}
}
candidate.len = self.len;
Ok(candidate)
}
pub fn with<R>(
&mut self,
operation: impl for<'scope> FnOnce(View<'scope, A>) -> R,
) -> Result<R, Error> {
self.healthy()?;
self.poisoned = true;
let result = operation(View { map: self });
self.poisoned = false;
Ok(result)
}
pub fn len(&self) -> Result<usize, Error> {
self.healthy()?;
Ok(self.len)
}
pub fn is_empty(&self) -> Result<bool, Error> {
self.len().map(|len| len == 0)
}
pub fn capacity(&self) -> Result<usize, Error> {
self.healthy()?;
Ok(table::capacity(self.slots.len()).min(self.limit))
}
pub fn allocated_bytes(&self) -> Result<usize, Error> {
self.healthy()?;
Ok(self.slots.capacity() * size_of::<Slot>())
}
fn healthy(&self) -> Result<(), Error> {
if self.poisoned {
Err(Error::Poisoned)
} else {
Ok(())
}
}
fn reserve(&mut self, additional: usize) -> Result<(), Error> {
let required = self.len.checked_add(additional).ok_or(Error::Limit)?;
if required > self.limit {
return Err(Error::Limit);
}
if required <= table::capacity(self.slots.len()) {
return Ok(());
}
let buckets = table::buckets_for(required)?;
let mut candidate = Vec::new_in(self.slots.allocator().clone());
candidate
.try_reserve_exact(buckets)
.map_err(|_| Error::Allocation)?;
candidate.resize(buckets, Slot::EMPTY);
for slot in &self.slots {
if slot.occupied == 1 {
table::place(&mut candidate, *slot);
}
}
self.slots = candidate;
Ok(())
}
}
pub struct View<'scope, A: Allocator + Clone> {
map: &'scope mut Map<A>,
}
impl<A: Allocator + Clone> View<'_, A> {
#[must_use]
pub fn len(&self) -> usize {
self.map.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.map.len == 0
}
#[must_use]
pub fn get(&self, key: u64) -> Option<u64> {
table::find(&self.map.slots, key).map(|index| self.map.slots[index].value)
}
pub fn reserve(&mut self, additional: usize) -> Result<(), Error> {
self.map.reserve(additional)
}
pub fn insert(&mut self, key: u64, value: u64) -> Result<Option<u64>, Error> {
if let Some(index) = table::find(&self.map.slots, key) {
return Ok(Some(core::mem::replace(
&mut self.map.slots[index].value,
value,
)));
}
self.map.reserve(1)?;
table::place(
&mut self.map.slots,
Slot {
occupied: 1,
key,
value,
},
);
self.map.len += 1;
Ok(None)
}
pub fn remove(&mut self, key: u64) -> Option<u64> {
let index = table::find(&self.map.slots, key)?;
let value = self.map.slots[index].value;
table::remove(&mut self.map.slots, index);
self.map.len -= 1;
Some(value)
}
pub fn for_each(&self, mut visit: impl FnMut(u64, u64)) {
for slot in &self.map.slots {
if slot.occupied == 1 {
visit(slot.key, slot.value);
}
}
}
pub fn clear(&mut self) {
self.map.slots.fill(Slot::EMPTY);
self.map.len = 0;
}
}
#[cfg(test)]
mod tests;