use anyhow::{Context, Result};
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::path::PathBuf;
use crate::fcm::{self, DEFAULT_BLOCK_SIZE, Fcm, FcmReader, Record, path_cmp};
pub struct Lsm {
dir: PathBuf,
}
impl Lsm {
pub fn new(dir: impl Into<PathBuf>) -> Self {
Self { dir: dir.into() }
}
fn base_path(&self) -> PathBuf {
self.dir.join("base.fcm")
}
fn seg_path(&self, n: u64) -> PathBuf {
self.dir.join(format!("seg-{n:05}.fcm"))
}
pub fn has_base(&self) -> bool {
self.base_path().exists()
}
pub fn segments(&self) -> Result<Vec<u64>> {
let mut segs = Vec::new();
if !self.dir.exists() {
return Ok(segs);
}
for entry in std::fs::read_dir(&self.dir)
.with_context(|| format!("reading manifest dir {}", self.dir.display()))?
{
let name = entry?.file_name();
let name = name.to_string_lossy();
if let Some(mid) = name
.strip_prefix("seg-")
.and_then(|s| s.strip_suffix(".fcm"))
&& let Ok(n) = mid.parse::<u64>()
{
segs.push(n);
}
}
segs.sort_unstable();
Ok(segs)
}
pub fn segment_count(&self) -> Result<usize> {
Ok(self.segments()?.len())
}
pub fn is_empty(&self) -> Result<bool> {
Ok(!self.has_base() && self.segments()?.is_empty())
}
pub fn current(&self) -> Result<LsmMerge> {
let mut readers: Vec<FcmReader> = Vec::new();
if self.has_base() {
readers.push(Fcm::open(&self.base_path())?.iter()?);
}
for n in self.segments()? {
readers.push(Fcm::open(&self.seg_path(n))?.iter()?);
}
LsmMerge::new(readers)
}
pub fn append_segment(&self, records: &mut [Record], zstd_level: i32) -> Result<()> {
std::fs::create_dir_all(&self.dir)?;
let next = self.segments()?.last().copied().unwrap_or(0) + 1;
fcm::write(
&self.seg_path(next),
records,
DEFAULT_BLOCK_SIZE,
zstd_level,
)?;
Ok(())
}
pub fn compact(&self, zstd_level: i32) -> Result<()> {
let segs = self.segments()?;
if segs.is_empty() && self.has_base() {
return Ok(()); }
std::fs::create_dir_all(&self.dir)?;
let tmp = self.dir.join("base.fcm.tmp");
{
let mut writer = fcm::FcmWriter::create(&tmp, DEFAULT_BLOCK_SIZE, zstd_level)?;
for rec in self.current()? {
writer.push(rec?)?;
}
writer.finish()?;
}
std::fs::rename(&tmp, self.base_path())?;
for n in segs {
std::fs::remove_file(self.seg_path(n))?;
}
Ok(())
}
pub fn install_base(&self, fcm_bytes: &[u8]) -> Result<()> {
std::fs::create_dir_all(&self.dir)?;
for n in self.segments()? {
std::fs::remove_file(self.seg_path(n))?;
}
std::fs::write(self.base_path(), fcm_bytes)
.with_context(|| format!("writing base {}", self.base_path().display()))?;
Ok(())
}
pub fn base_file(&self) -> PathBuf {
self.base_path()
}
}
struct HeapItem {
rec: Record,
priority: usize,
}
impl PartialEq for HeapItem {
fn eq(&self, other: &Self) -> bool {
self.priority == other.priority && self.rec.path == other.rec.path
}
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
fn cmp(&self, other: &Self) -> Ordering {
match path_cmp(&self.rec.path, &other.rec.path) {
Ordering::Less => Ordering::Greater,
Ordering::Greater => Ordering::Less,
Ordering::Equal => self.priority.cmp(&other.priority),
}
}
}
impl PartialOrd for HeapItem {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
pub struct LsmMerge {
readers: Vec<FcmReader>,
heap: BinaryHeap<HeapItem>,
}
impl LsmMerge {
fn new(mut readers: Vec<FcmReader>) -> Result<Self> {
let mut heap = BinaryHeap::with_capacity(readers.len());
for (priority, r) in readers.iter_mut().enumerate() {
if let Some(rec) = r.next() {
heap.push(HeapItem {
rec: rec?,
priority,
});
}
}
Ok(Self { readers, heap })
}
fn refill(&mut self, priority: usize) -> Result<()> {
if let Some(rec) = self.readers[priority].next() {
self.heap.push(HeapItem {
rec: rec?,
priority,
});
}
Ok(())
}
}
impl Iterator for LsmMerge {
type Item = Result<Record>;
fn next(&mut self) -> Option<Self::Item> {
loop {
let top = self.heap.pop()?;
if let Err(e) = self.refill(top.priority) {
return Some(Err(e));
}
while let Some(peek) = self.heap.peek() {
if path_cmp(&peek.rec.path, &top.rec.path) == Ordering::Equal {
let dup = self.heap.pop().unwrap();
if let Err(e) = self.refill(dup.priority) {
return Some(Err(e));
}
} else {
break;
}
}
if top.rec.is_tombstone() {
continue;
}
return Some(Ok(top.rec));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn rec(p: &str, size: i64) -> Record {
Record {
path: p.into(),
size,
mtime: size,
crc32c: None,
}
}
fn collect(lsm: &Lsm) -> Vec<(String, i64)> {
lsm.current()
.unwrap()
.map(|r| {
let r = r.unwrap();
(r.path, r.size)
})
.collect()
}
#[test]
fn base_only() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.append_segment(&mut [rec("a", 1), rec("b", 2)], 3)
.unwrap();
assert_eq!(collect(&lsm), vec![("a".into(), 1), ("b".into(), 2)]);
}
#[test]
fn newer_segment_overrides_and_tombstones_delete() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.append_segment(&mut [rec("a", 1), rec("b", 2), rec("c", 3)], 3)
.unwrap();
lsm.append_segment(
&mut [rec("b", 20), Record::tombstone("c".into()), rec("d", 4)],
3,
)
.unwrap();
assert_eq!(
collect(&lsm),
vec![("a".into(), 1), ("b".into(), 20), ("d".into(), 4)]
);
}
#[test]
fn compaction_folds_segments_and_drops_tombstones() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.append_segment(&mut [rec("a", 1), rec("b", 2), rec("c", 3)], 3)
.unwrap();
lsm.append_segment(&mut [rec("b", 20), Record::tombstone("c".into())], 3)
.unwrap();
assert_eq!(lsm.segment_count().unwrap(), 2);
lsm.compact(3).unwrap();
assert_eq!(lsm.segment_count().unwrap(), 0);
assert!(lsm.has_base());
assert_eq!(collect(&lsm), vec![("a".into(), 1), ("b".into(), 20)]);
lsm.append_segment(&mut [rec("a", 100)], 3).unwrap();
assert_eq!(collect(&lsm), vec![("a".into(), 100), ("b".into(), 20)]);
}
#[test]
fn empty_manifest_current_is_empty() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
assert!(lsm.is_empty().unwrap());
assert_eq!(collect(&lsm), Vec::<(String, i64)>::new());
}
#[test]
fn compact_empty_manifest_creates_empty_base() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.compact(3).unwrap();
assert!(lsm.has_base(), "compact must leave a base even when empty");
assert_eq!(collect(&lsm), Vec::<(String, i64)>::new());
lsm.compact(3).unwrap();
assert!(lsm.has_base());
}
#[test]
fn tombstone_for_absent_path_is_harmless() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.append_segment(&mut [rec("a", 1)], 3).unwrap();
lsm.append_segment(&mut [Record::tombstone("never".into())], 3)
.unwrap();
assert_eq!(collect(&lsm), vec![("a".into(), 1)]);
}
#[test]
fn canonical_order_across_segments() {
let dir = tempfile::tempdir().unwrap();
let lsm = Lsm::new(dir.path());
lsm.append_segment(&mut [rec("a.txt", 1), rec("a/y", 2)], 3)
.unwrap();
lsm.append_segment(&mut [rec("a/x", 3)], 3).unwrap();
let paths: Vec<String> = lsm.current().unwrap().map(|r| r.unwrap().path).collect();
assert_eq!(paths, vec!["a/x", "a/y", "a.txt"]);
}
}