use rkyv::{Archive, Deserialize, Serialize};
use std::collections::btree_map::Entry;
use std::collections::BTreeMap;
use std::fmt::Debug;
use crate::page::PageId;
use crate::{align, align_to, Persistable, SizeMeasurable, INNER_PAGE_SIZE};
pub const EMPTY_TABLE_OF_CONTENTS_PAGE_SIZE: usize = std::mem::size_of::<usize>() + 12;
#[derive(Debug)]
pub struct TableOfContentsOverflowError<T> {
pub key: T,
pub record_size: usize,
pub estimated_size: usize,
pub capacity: usize,
}
impl<T> TableOfContentsOverflowError<T> {
pub fn into_key(self) -> T {
self.key
}
pub fn fits_empty_page(&self) -> bool {
EMPTY_TABLE_OF_CONTENTS_PAGE_SIZE + self.record_size <= self.capacity
}
}
impl<T> std::fmt::Display for TableOfContentsOverflowError<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"table of contents record of {} bytes does not fit the page \
(estimated size {} of {} bytes)",
self.record_size, self.estimated_size, self.capacity
)
}
}
impl<T: Debug> std::error::Error for TableOfContentsOverflowError<T> {}
#[derive(Archive, Clone, Deserialize, Debug, Serialize)]
pub struct TableOfContentsPage<T: Ord + Eq> {
records: BTreeMap<T, PageId>,
empty_pages: Vec<PageId>,
estimated_size: usize,
}
impl<T> Default for TableOfContentsPage<T>
where
T: SizeMeasurable + Ord + Eq,
{
fn default() -> Self {
Self {
records: BTreeMap::new(),
empty_pages: vec![],
estimated_size: EMPTY_TABLE_OF_CONTENTS_PAGE_SIZE,
}
}
}
#[derive(Archive, Clone, Deserialize, Debug, Serialize)]
struct TableOfContentsPagePersisted<T: Ord + Eq> {
records: Vec<(T, PageId)>,
empty_pages: Vec<PageId>,
estimated_size: usize,
}
impl<T: Ord + Eq> Persistable for TableOfContentsPage<T>
where
T: Clone
+ SizeMeasurable
+ rkyv::Archive
+ for<'a> rkyv::Serialize<
rkyv::rancor::Strategy<
rkyv::ser::Serializer<
rkyv::util::AlignedVec,
rkyv::ser::allocator::ArenaHandle<'a>,
rkyv::ser::sharing::Share,
>,
rkyv::rancor::Error,
>,
>,
<T as rkyv::Archive>::Archived:
rkyv::Deserialize<T, rkyv::api::high::HighDeserializer<rkyv::rancor::Error>> + Ord,
<TableOfContentsPagePersisted<T> as rkyv::Archive>::Archived:
for<'a> rkyv::bytecheck::CheckBytes<
rkyv::api::high::HighValidator<'a, rkyv::rancor::Error>,
>,
{
fn as_bytes(&self) -> impl AsRef<[u8]> {
let records = self
.records
.iter()
.map(|(k, v)| (k.clone(), *v))
.collect::<Vec<_>>();
let model = TableOfContentsPagePersisted {
records,
empty_pages: self.empty_pages.clone(),
estimated_size: self.estimated_size,
};
rkyv::to_bytes::<rkyv::rancor::Error>(&model).unwrap()
}
fn from_bytes(bytes: &[u8], _version: u32) -> Self {
let archived =
crate::access_archived::<<TableOfContentsPagePersisted<T> as Archive>::Archived>(bytes)
.expect("torn or corrupt table of contents page: the bytes fail validation");
let model: TableOfContentsPagePersisted<T> =
rkyv::deserialize::<_, rkyv::rancor::Error>(archived).expect("data should be valid");
let records = BTreeMap::from_iter(model.records);
let estimated_size = Self::recompute_estimated_size(&records, &model.empty_pages);
Self {
records,
estimated_size,
empty_pages: model.empty_pages,
}
}
}
impl<T: Ord + Eq> TableOfContentsPage<T> {
fn record_size(key: &T) -> usize
where
T: SizeMeasurable,
{
let len = key.aligned_size() + PageId::default().0.aligned_size();
if let Some(key_align) = T::align() {
if key_align % 8 == 0 {
return align_to(len, key_align);
}
}
align(len)
}
fn recompute_estimated_size(records: &BTreeMap<T, PageId>, empty_pages: &[PageId]) -> usize
where
T: SizeMeasurable,
{
let mut estimated_size = EMPTY_TABLE_OF_CONTENTS_PAGE_SIZE;
for key in records.keys() {
estimated_size += Self::record_size(key);
}
estimated_size += empty_pages.len() * PageId::default().0.aligned_size();
estimated_size
}
}
impl<T> TableOfContentsPage<T>
where
T: Debug + Ord + Eq,
{
pub fn estimated_size(&self) -> usize {
self.estimated_size
}
pub fn insert(&mut self, val: T, page_id: PageId)
where
T: SizeMeasurable,
{
let record_size = Self::record_size(&val);
match self.records.entry(val) {
Entry::Occupied(mut entry) => {
entry.insert(page_id);
}
Entry::Vacant(entry) => {
entry.insert(page_id);
self.estimated_size += record_size;
}
}
}
pub fn try_insert(
&mut self,
val: T,
page_id: PageId,
) -> Result<(), TableOfContentsOverflowError<T>>
where
T: SizeMeasurable,
{
let record_size = Self::record_size(&val);
match self.records.entry(val) {
Entry::Occupied(mut entry) => {
entry.insert(page_id);
Ok(())
}
Entry::Vacant(entry) => {
if self.estimated_size + record_size > INNER_PAGE_SIZE {
return Err(TableOfContentsOverflowError {
key: entry.into_key(),
record_size,
estimated_size: self.estimated_size,
capacity: INNER_PAGE_SIZE,
});
}
entry.insert(page_id);
self.estimated_size += record_size;
Ok(())
}
}
}
pub fn pop_empty_page(&mut self) -> Option<PageId>
where
T: SizeMeasurable,
{
if self.empty_pages.is_empty() {
return None;
}
let val = self
.empty_pages
.pop()
.expect("should not be empty as checked before");
self.estimated_size -= val.aligned_size();
Some(val)
}
pub fn get(&self, val: &T) -> Option<PageId> {
self.records.get(val).copied()
}
pub fn remove(&mut self, val: &T) -> PageId
where
T: SizeMeasurable,
{
let id = self.remove_without_record(val);
self.estimated_size += id.aligned_size();
self.empty_pages.push(id);
id
}
pub fn remove_without_record(&mut self, val: &T) -> PageId
where
T: SizeMeasurable,
{
self.estimated_size -= Self::record_size(val);
self.records
.remove(val)
.expect("value should be available if remove is called")
}
pub fn update_key(&mut self, old_key: &T, new_key: T) -> Option<()>
where
T: SizeMeasurable,
{
let id = self.records.remove(old_key)?;
self.estimated_size -= Self::record_size(old_key);
let new_record_size = Self::record_size(&new_key);
match self.records.entry(new_key) {
Entry::Occupied(mut entry) => {
entry.insert(id);
}
Entry::Vacant(entry) => {
entry.insert(id);
self.estimated_size += new_record_size;
}
}
Some(())
}
pub fn try_update_key(
&mut self,
old_key: &T,
new_key: T,
) -> Result<bool, TableOfContentsOverflowError<T>>
where
T: SizeMeasurable,
{
let Some((old_entry_key, id)) = self.records.remove_entry(old_key) else {
return Ok(false);
};
let old_record_size = Self::record_size(old_key);
let new_record_size = Self::record_size(&new_key);
match self.records.entry(new_key) {
Entry::Occupied(mut entry) => {
entry.insert(id);
self.estimated_size -= old_record_size;
Ok(true)
}
Entry::Vacant(entry) => {
let projected = self.estimated_size - old_record_size + new_record_size;
if projected > INNER_PAGE_SIZE {
let key = entry.into_key();
self.records.insert(old_entry_key, id);
return Err(TableOfContentsOverflowError {
key,
record_size: new_record_size,
estimated_size: self.estimated_size,
capacity: INNER_PAGE_SIZE,
});
}
entry.insert(id);
self.estimated_size = projected;
Ok(true)
}
}
}
pub fn contains(&self, val: &T) -> bool {
self.records.contains_key(val)
}
pub fn iter(&self) -> impl Iterator<Item = (&T, &PageId)> {
self.records.iter()
}
}
impl<T> IntoIterator for TableOfContentsPage<T>
where
T: Ord + Eq,
{
type Item = (T, PageId);
type IntoIter = <BTreeMap<T, PageId> as IntoIterator>::IntoIter;
fn into_iter(self) -> Self::IntoIter {
self.records.into_iter()
}
}
#[cfg(test)]
mod test {
use crate::{Link, Persistable, TableOfContentsPage, INNER_PAGE_SIZE};
fn link(offset: u32) -> Link {
Link {
page_id: 1.into(),
offset,
length: 32,
}
}
#[test]
fn test_from_bytes_recomputes_stale_persisted_estimated_size() {
for bogus_estimated in [0usize, 3, 100_000] {
let stale = super::TableOfContentsPagePersisted {
records: vec![
((1u64, link(0)), crate::page::PageId::from(6)),
((2u64, link(64)), crate::page::PageId::from(7)),
],
empty_pages: vec![9.into()],
estimated_size: bogus_estimated,
};
let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&stale).unwrap();
let loaded = TableOfContentsPage::<(u64, Link)>::from_bytes(&bytes, 0);
assert_ne!(loaded.estimated_size(), bogus_estimated);
assert_eq!(loaded.estimated_size(), loaded.as_bytes().as_ref().len());
let mut fresh = TableOfContentsPage::<(u64, Link)>::default();
fresh.insert((1, link(0)), 6.into());
fresh.insert((2, link(64)), 7.into());
fresh.insert((3, link(128)), 9.into());
fresh.remove(&(3, link(128)));
assert_eq!(loaded.estimated_size(), fresh.estimated_size());
}
}
#[test]
fn test_try_insert_bounds_real_serialized_size_for_16_aligned_keys() {
let mut toc_page = TableOfContentsPage::<u128>::default();
let mut i = 0u128;
while toc_page.try_insert(i, 1.into()).is_ok() {
i += 1;
assert!(i < 4096, "the page must eventually report itself full");
}
let serialized = toc_page.as_bytes().as_ref().len();
assert_eq!(serialized, toc_page.estimated_size());
assert!(serialized <= INNER_PAGE_SIZE);
let mut toc_page = TableOfContentsPage::<(u128, Link)>::default();
let mut i = 0u128;
while toc_page.try_insert((i, link(i as u32)), 1.into()).is_ok() {
i += 1;
assert!(i < 4096, "the page must eventually report itself full");
}
let serialized = toc_page.as_bytes().as_ref().len();
assert_eq!(serialized, toc_page.estimated_size());
assert!(serialized <= INNER_PAGE_SIZE);
}
#[test]
fn test_estimated_size_is_an_upper_bound_under_adversarial_churn() {
let mut state = 0x2545F4914F6CDD1Du64;
let mut next = move || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(state >> 33) as u32
};
let mut toc_page = TableOfContentsPage::<(String, Link)>::default();
let mut keys: Vec<(String, Link)> = vec![];
let mut record_count = 0usize;
for step in 0..600u32 {
let op = next() % 4;
if op < 2 || keys.is_empty() {
let len = (next() % 48) as usize;
let key = (format!("{step:0>len$}"), link(step));
if toc_page.try_insert(key.clone(), (step + 1).into()).is_ok() {
keys.push(key);
record_count += 1;
}
} else if op == 2 {
let key = keys.swap_remove((next() as usize) % keys.len());
toc_page.remove(&key);
record_count -= 1;
} else {
let old = keys.swap_remove((next() as usize) % keys.len());
let len = (next() % 48) as usize;
let new_key = (format!("{step:0>len$}"), link(step));
match toc_page.try_update_key(&old, new_key.clone()) {
Ok(true) => keys.push(new_key),
Ok(false) => unreachable!("old key is always present"),
Err(_) => keys.push(old),
}
}
let serialized = toc_page.as_bytes().as_ref().len();
let estimated = toc_page.estimated_size();
assert!(
serialized <= estimated,
"under-estimate at step {step}: serialized {serialized} > estimated {estimated}"
);
assert!(
estimated - serialized <= 4 * (record_count + 2),
"slack blew past the documented bound at step {step}: \
serialized {serialized}, estimated {estimated}, records {record_count}"
);
}
}
#[test]
fn test_try_update_key_onto_existing_key_replaces_in_place() {
let mut toc_page = TableOfContentsPage::<(u32, Link)>::default();
toc_page.insert((1, link(0)), 6.into());
toc_page.insert((2, link(64)), 7.into());
assert!(toc_page
.try_update_key(&(1, link(0)), (2, link(64)))
.unwrap());
assert!(!toc_page.contains(&(1, link(0))));
assert_eq!(toc_page.get(&(2, link(64))), Some(6.into()));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert!(toc_page
.try_update_key(&(2, link(64)), (2, link(64)))
.unwrap());
assert_eq!(toc_page.get(&(2, link(64))), Some(6.into()));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
#[test]
fn test_remove_without_record_keeps_estimated_size_exact() {
let mut toc_page = TableOfContentsPage::<(u32, Link)>::default();
let empty_size = toc_page.as_bytes().as_ref().len();
assert_eq!(empty_size, toc_page.estimated_size());
toc_page.insert((1, link(0)), 6.into());
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
toc_page.remove_without_record(&(1, link(0)));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert_eq!(toc_page.estimated_size(), empty_size);
}
#[test]
fn test_remove_keeps_estimated_size_exact() {
let mut toc_page = TableOfContentsPage::<(u32, Link)>::default();
toc_page.insert((1, link(0)), 6.into());
toc_page.insert((2, link(64)), 7.into());
toc_page.remove(&(1, link(0)));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert_eq!(toc_page.pop_empty_page(), Some(6.into()));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
#[test]
fn test_insert_over_existing_key_keeps_estimated_size_exact() {
let mut toc_page = TableOfContentsPage::<(u32, Link)>::default();
toc_page.insert((1, link(0)), 6.into());
let size_after_first = toc_page.estimated_size();
toc_page.insert((1, link(0)), 7.into());
assert_eq!(toc_page.get(&(1, link(0))), Some(7.into()));
assert_eq!(toc_page.estimated_size(), size_after_first);
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
#[test]
fn test_remove_accounts_8_aligned_keys_like_insert() {
let mut toc_page = TableOfContentsPage::<(u64, Link)>::default();
let empty_size = toc_page.as_bytes().as_ref().len();
toc_page.insert((128, link(0)), 6.into());
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
toc_page.remove_without_record(&(128, link(0)));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert_eq!(toc_page.estimated_size(), empty_size);
}
#[test]
fn test_update_key_keeps_estimated_size_exact() {
fn assert_exact(toc_page: &TableOfContentsPage<(String, Link)>) {
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
let mut toc_page = TableOfContentsPage::<(String, Link)>::default();
toc_page.insert(("key_0001".to_string(), link(0)), 6.into());
assert_exact(&toc_page);
let grown = "key_0001_grown_by_a_long_suffix_0001".to_string();
toc_page
.update_key(&("key_0001".to_string(), link(0)), (grown.clone(), link(0)))
.unwrap();
assert_exact(&toc_page);
toc_page
.update_key(&(grown, link(0)), ("key_0001".to_string(), link(0)))
.unwrap();
assert_exact(&toc_page);
toc_page.insert(("key_0002".to_string(), link(64)), 7.into());
toc_page
.update_key(
&("key_0001".to_string(), link(0)),
("key_0002".to_string(), link(64)),
)
.unwrap();
assert_exact(&toc_page);
assert_eq!(
toc_page.get(&("key_0002".to_string(), link(64))),
Some(6.into())
);
let before = toc_page.estimated_size();
assert!(toc_page
.update_key(
&("missing".to_string(), link(0)),
("whatever".to_string(), link(0)),
)
.is_none());
assert_eq!(toc_page.estimated_size(), before);
assert_exact(&toc_page);
}
#[test]
fn test_estimated_size_stays_exact_across_churn() {
fn assert_exact(toc_page: &TableOfContentsPage<(String, Link)>) {
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
let mut toc_page = TableOfContentsPage::<(String, Link)>::default();
for i in 0..32u32 {
toc_page.insert((format!("key_{i:04}"), link(i)), (i + 1).into());
assert_exact(&toc_page);
}
for i in 0..16u32 {
toc_page
.update_key(
&(format!("key_{i:04}"), link(i)),
(format!("key_{i:04}_grown_by_a_long_suffix_"), link(i)),
)
.unwrap();
assert_exact(&toc_page);
}
for i in 0..16u32 {
toc_page
.update_key(
&(format!("key_{i:04}_grown_by_a_long_suffix_"), link(i)),
(format!("key_{i:04}"), link(i)),
)
.unwrap();
assert_exact(&toc_page);
}
for i in 0..8u32 {
toc_page.remove(&(format!("key_{i:04}"), link(i)));
assert_exact(&toc_page);
}
for i in 8..16u32 {
toc_page.remove_without_record(&(format!("key_{i:04}"), link(i)));
assert_exact(&toc_page);
}
while toc_page.pop_empty_page().is_some() {
assert_exact(&toc_page);
}
}
#[test]
fn test_try_insert_never_reports_success_past_the_page_slot() {
let mut toc_page = TableOfContentsPage::<(u32, Link)>::default();
let mut rejected_at = None;
for i in 0..2048u32 {
match toc_page.try_insert((i, link(i)), (i + 1).into()) {
Ok(()) => {
assert!(toc_page.estimated_size() <= INNER_PAGE_SIZE);
}
Err(err) => {
rejected_at = Some((i, err));
break;
}
}
}
let (i, err) = rejected_at.expect("the page must eventually report itself full");
let serialized = toc_page.as_bytes().as_ref().len();
assert_eq!(serialized, toc_page.estimated_size());
assert!(serialized <= INNER_PAGE_SIZE);
assert!(!toc_page.contains(&(i, link(i))));
assert!(err.fits_empty_page());
assert_eq!(err.into_key(), (i, link(i)));
let size_before = toc_page.estimated_size();
toc_page
.try_insert((0, link(0)), 999.into())
.expect("replacement must fit");
assert_eq!(toc_page.estimated_size(), size_before);
assert_eq!(toc_page.get(&(0, link(0))), Some(999.into()));
}
#[test]
fn test_try_insert_rejects_record_that_can_never_fit() {
let mut toc_page = TableOfContentsPage::<(String, Link)>::default();
let oversized = "x".repeat(INNER_PAGE_SIZE);
let err = toc_page
.try_insert((oversized.clone(), link(0)), 6.into())
.expect_err("a record larger than the page slot must be rejected");
assert!(!err.fits_empty_page());
assert!(!toc_page.contains(&(oversized, link(0))));
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
}
#[test]
fn test_try_update_key_rejects_growth_past_the_page_slot() {
let mut toc_page = TableOfContentsPage::<(String, Link)>::default();
toc_page.insert(("key_0001".to_string(), link(0)), 6.into());
let grown = "x".repeat(INNER_PAGE_SIZE);
let err = toc_page
.try_update_key(&("key_0001".to_string(), link(0)), (grown.clone(), link(0)))
.expect_err("growth past the page slot must be rejected");
assert!(!err.fits_empty_page());
assert_eq!(err.into_key(), (grown, link(0)));
assert_eq!(
toc_page.get(&("key_0001".to_string(), link(0))),
Some(6.into())
);
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert!(toc_page
.try_update_key(
&("key_0001".to_string(), link(0)),
("key_0002".to_string(), link(0)),
)
.unwrap());
assert_eq!(
toc_page.as_bytes().as_ref().len(),
toc_page.estimated_size()
);
assert!(!toc_page
.try_update_key(
&("missing".to_string(), link(0)),
("whatever".to_string(), link(0)),
)
.unwrap());
}
#[test]
fn test_sizes() {
let mut toc_page = TableOfContentsPage::<(u64, Link)>::default();
assert_eq!(toc_page.as_bytes().as_ref().len(), toc_page.estimated_size);
toc_page.insert(
(
128,
Link {
page_id: 1.into(),
offset: 40,
length: 80,
},
),
6.into(),
);
assert_eq!(toc_page.as_bytes().as_ref().len(), toc_page.estimated_size);
}
}