use crate::{mvcc::PrivateRecordChanges, read_control::StorageReadControl, StorageBackendResult};
use std::ops::Bound;
use uqa_core::{memory::MemoryBudget, DocId, Value};
mod records;
mod tree;
use records::Records;
pub struct RetainedValueIndex {
records: PrivateRecordChanges,
memory: MemoryBudget,
tier_bytes: usize,
root: Option<DocId>,
len: usize,
}
impl Clone for RetainedValueIndex {
fn clone(&self) -> Self {
Self {
records: self.records.fork(),
memory: self.memory.clone(),
tier_bytes: self.tier_bytes,
root: self.root,
len: self.len,
}
}
}
impl RetainedValueIndex {
pub fn new(bytes: usize) -> Self {
let memory = MemoryBudget::new(bytes.max(64 * 1024));
Self {
records: PrivateRecordChanges::with_memory_tier_limit(&memory, bytes / 4),
memory,
tier_bytes: bytes / 4,
root: None,
len: 0,
}
}
pub fn from_ordered(
bytes: usize,
count: usize,
source: &mut dyn FnMut() -> StorageBackendResult<Option<(DocId, Value)>>,
control: &StorageReadControl,
) -> StorageBackendResult<Self> {
let mut index = Self::new(bytes);
let records = Records::new(&index.records, &index.memory, control);
let mut builder = tree::Builder {
records: &records,
source,
previous: None,
};
index.root = builder.build(count, 0)?.0;
if (builder.source)()?.is_some() {
return Err(records::invalid("long ordered index input"));
}
index.len = count;
Ok(index)
}
pub fn count_range(
&self,
low: Bound<&Value>,
high: Bound<&Value>,
control: &StorageReadControl,
) -> StorageBackendResult<usize> {
let records = Records::new(&self.records, &self.memory, control);
let _scope = records.read_scope()?;
let before = match low {
Bound::Included(value) => tree::rank(&records, self.root, value, false)?,
Bound::Excluded(value) => tree::rank(&records, self.root, value, true)?,
Bound::Unbounded => 0,
};
let through = match high {
Bound::Included(value) => tree::rank(&records, self.root, value, true)?,
Bound::Excluded(value) => tree::rank(&records, self.root, value, false)?,
Bound::Unbounded => self.len as u64,
};
usize::try_from(through.saturating_sub(before))
.map_err(|_| records::invalid("range count outside address space"))
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn clear(&mut self) {
self.records = PrivateRecordChanges::with_memory_tier_limit(&self.memory, self.tier_bytes);
self.root = None;
self.len = 0;
}
pub fn contains(&self, id: DocId, control: &StorageReadControl) -> StorageBackendResult<bool> {
let records = Records::new(&self.records, &self.memory, control);
records
.node_at(&records.snapshot()?, id)
.map(|node| node.is_some())
}
pub fn get(
&self,
id: DocId,
control: &StorageReadControl,
) -> StorageBackendResult<Option<Value>> {
let records = Records::new(&self.records, &self.memory, control);
let _scope = records.read_scope()?;
let snapshot = records.snapshot()?;
records.get(&snapshot, id)
}
pub fn replace(
&mut self,
id: DocId,
value: Option<&Value>,
control: &StorageReadControl,
) -> StorageBackendResult<()> {
control.check()?;
let mut next = self.clone();
let records = Records::new(&next.records, &next.memory, control);
let scope = records.read_scope()?;
let old = records.get(&records.snapshot()?, id)?;
if let Some(old) = &old {
next.root = tree::remove(&records, next.root, id, old, 0)?;
records.remove_value(id)?;
next.len -= 1;
}
if let Some(value) = value {
records.put_value(id, value)?;
next.root = Some(tree::insert(&records, next.root, id, value, 0)?);
next.len = next
.len
.checked_add(1)
.ok_or_else(|| records::invalid("row count overflow"))?;
}
control.check()?;
drop(scope);
*self = next;
Ok(())
}
pub fn visit_range(
&self,
low: Bound<&Value>,
high: Bound<&Value>,
control: &StorageReadControl,
visit: &mut dyn FnMut(DocId) -> StorageBackendResult<bool>,
) -> StorageBackendResult<()> {
let records = Records::new(&self.records, &self.memory, control);
let _scope = records.read_scope()?;
let snapshot = records.snapshot()?;
tree::visit(&records, &snapshot, self.root, low, high, visit, 0).map(|_| ())
}
pub fn visit_values(
&self,
control: &StorageReadControl,
visit: &mut dyn FnMut(DocId, Value) -> StorageBackendResult<bool>,
) -> StorageBackendResult<()> {
let records = Records::new(&self.records, &self.memory, control);
let _scope = records.read_scope()?;
let snapshot = records.snapshot()?;
records.visit_values(&snapshot, visit)
}
}
#[cfg(test)]
mod tests;