mod arena;
mod batch;
mod bytes;
mod checkpoint;
#[cfg(test)]
mod db_tests;
pub mod paged;
#[cfg(test)]
mod payload_tests;
mod range;
pub mod session;
#[cfg(test)]
mod tests;
mod tree;
pub use batch::Mutation;
pub use bytes::{ByteSlice, Bytes};
pub use range::{Entries, Entry, Range};
use alloc::{alloc::Global, vec::Vec};
use core::{alloc::Allocator, ops::Bound};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
Limit,
Allocation,
NativeImage,
Poisoned,
Checkpoint,
Epoch,
}
#[repr(C)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Node<const K: usize, const V: usize> {
left: u64,
right: u64,
height: u64,
key: arena::Span,
value: arena::Span,
}
impl<const K: usize, const V: usize> Node<K, V> {
pub const EMPTY: Self = Self {
left: 0,
right: 0,
height: 0,
key: arena::Span::EMPTY,
value: arena::Span::EMPTY,
};
}
pub struct Image<const K: usize, const V: usize, A: Allocator = Global, P: Allocator = A> {
pub nodes: Vec<Node<K, V>, A>,
pub payload: Vec<u8, P>,
pub root: u64,
pub free: u64,
pub len: usize,
}
pub struct AdmissionError<const K: usize, const V: usize, A: Allocator, P: Allocator> {
pub error: Error,
pub image: Image<K, V, A, P>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AllocationUsage {
pub initialized_bytes: usize,
pub allocated_bytes: usize,
}
pub struct Map<
const K: usize,
const V: usize,
A: Allocator + Clone = Global,
P: Allocator + Clone = A,
> {
image: Image<K, V, A, P>,
limit: usize,
poisoned: bool,
}
impl<const K: usize, const V: usize> Map<K, V> {
#[must_use]
pub fn new(limit: usize) -> Self {
Self::new_in(limit, Global)
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone> Map<K, V, A> {
#[must_use]
pub fn new_in(limit: usize, allocator: A) -> Self {
Self::new_in_allocators(limit, allocator.clone(), allocator)
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> Map<K, V, A, P> {
pub fn allocation_usage(&self) -> Result<AllocationUsage, Error> {
self.healthy()?;
Ok(AllocationUsage {
initialized_bytes: self.image.nodes.len() * size_of::<Node<K, V>>()
+ self.image.payload.len(),
allocated_bytes: self.image.nodes.capacity() * size_of::<Node<K, V>>()
+ self.image.payload.capacity(),
})
}
#[must_use]
pub fn new_in_allocators(limit: usize, allocator: A, payload_allocator: P) -> Self {
Self {
image: Image {
nodes: Vec::new_in(allocator),
payload: Vec::new_in(payload_allocator),
root: 0,
free: 0,
len: 0,
},
limit,
poisoned: false,
}
}
pub fn admit(
image: Image<K, V, A, P>,
limit: usize,
) -> Result<Self, AdmissionError<K, V, A, P>> {
if let Err(error) = tree::validate(&image, limit) {
return Err(AdmissionError { error, image });
}
Ok(Self {
image,
limit,
poisoned: false,
})
}
pub fn release(self) -> Result<Image<K, V, A, P>, Error> {
self.healthy()?;
Ok(self.image)
}
pub fn with<R>(
&mut self,
operation: impl for<'a> FnOnce(View<'a, K, V, A, P>) -> R,
) -> Result<R, Error> {
self.healthy()?;
self.poisoned = true;
let result = operation(View { map: self });
self.poisoned = false;
Ok(result)
}
fn healthy(&self) -> Result<(), Error> {
if self.poisoned {
Err(Error::Poisoned)
} else {
Ok(())
}
}
}
pub struct View<
'a,
const K: usize,
const V: usize,
A: Allocator + Clone = Global,
P: Allocator + Clone = A,
> {
map: &'a mut Map<K, V, A, P>,
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone>
View<'_, K, V, A, P>
{
#[must_use]
pub fn len(&self) -> usize {
self.map.image.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[must_use]
pub fn get(&self, key: &[u8]) -> Option<ByteSlice<'_>> {
let id = self.map.find(key);
(id != 0).then(|| ByteSlice(self.map.value(id)))
}
#[must_use]
pub fn contains_key(&self, key: &[u8]) -> bool {
self.map.find(key) != 0
}
pub fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Bytes<V>>, Error> {
if key.len() > K || value.len() > V {
return Err(Error::Limit);
}
let id = self.map.find(key);
if id != 0 {
let previous = Bytes::new(self.map.value(id))?;
let old = self.map.node(id).value;
let span = arena::replace(&mut self.map.image.payload, old, value)?;
self.map.node_mut(id).value = span;
return Ok(Some(previous));
}
if self.len() >= self.map.limit {
return Err(Error::Limit);
}
if self.map.image.free == 0 {
self.map
.image
.nodes
.try_reserve(1)
.map_err(|_| Error::Allocation)?;
}
arena::reserve_pair(&mut self.map.image.payload, key.len(), value.len())?;
let key = arena::allocate(&mut self.map.image.payload, key);
let value = arena::allocate(&mut self.map.image.payload, value);
let id = self.map.allocate(Node {
key,
value,
height: 1,
..Node::EMPTY
});
self.map.image.root = self.map.insert_node(self.map.image.root, id);
self.map.image.len += 1;
Ok(None)
}
pub fn remove(&mut self, key: &[u8]) -> Option<Bytes<V>> {
let id = self.map.find(key);
if id == 0 {
return None;
}
let value = Bytes::copy_admitted(self.map.value(id));
self.map.image.root = self.map.remove_node(self.map.image.root, key);
self.map.image.len -= 1;
Some(value)
}
pub fn remove_discard(&mut self, key: &[u8]) -> bool {
if self.map.find(key) == 0 {
return false;
}
self.map.image.root = self.map.remove_node(self.map.image.root, key);
self.map.image.len -= 1;
true
}
#[must_use]
pub fn range(&self, lower: Bound<&[u8]>, upper: Bound<&[u8]>) -> Range<'_, K, V, A, P> {
Range::new(self.map, lower, upper)
}
#[must_use]
pub fn prefix(&self, prefix: &[u8]) -> Range<'_, K, V, A, P> {
Range::prefix(self.map, prefix)
}
}