armdb 0.15.3

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Owned byte-order query bounds.

use crate::{key::Key, map_index::Dir};
use std::ops::Bound;

/// An owned range for a segmented byte-ordered collection.
///
/// Bounds compare encoded key bytes. The time hint selects whole layers,
/// rather than filtering individual rows by their write time.
#[derive(Clone)]
pub struct SegRange<K: Key> {
    pub(crate) start: Bound<K>,
    pub(crate) end: Bound<K>,
    pub(crate) dir: Dir,
    pub(crate) since_ms: Option<u64>,
    pub(crate) pruning_prefix: Vec<u8>,
    pub(crate) empty: bool,
}

impl<K: Key> SegRange<K> {
    /// Select every key in ascending byte order.
    pub fn all() -> Self {
        Self {
            start: Bound::Unbounded,
            end: Bound::Unbounded,
            dir: Dir::Asc,
            since_ms: None,
            pruning_prefix: Vec::new(),
            empty: false,
        }
    }

    /// Select keys whose encoded bytes begin with `prefix`.
    pub fn prefix(prefix: &[u8]) -> Self {
        let mut query = Self::all();
        if prefix.len() > K::zeroed().as_bytes().len() {
            query.empty = true;
            return query;
        }
        if prefix.is_empty() {
            return query;
        }
        let mut start = K::zeroed();
        start.as_bytes_mut()[..prefix.len()].copy_from_slice(prefix);
        query.start = Bound::Included(start);
        query.end = crate::scope::key_math::prefix_to_end_bound(prefix);
        query.pruning_prefix = prefix.to_vec();
        query
    }

    /// Select an inclusive, exclusive or unbounded pair of owned bounds.
    pub fn range(start: Bound<&K>, end: Bound<&K>) -> Self {
        let mut query = Self::all();
        query.start = start.map(|k| *k);
        query.end = end.map(|k| *k);
        if let (Some(a), Some(b)) = (bound_key(&query.start), bound_key(&query.end)) {
            query.pruning_prefix = a
                .as_bytes()
                .iter()
                .zip(b.as_bytes())
                .take_while(|(a, b)| a == b)
                .map(|(a, _)| *a)
                .collect();
        }
        query.normalize();
        query
    }

    /// Reverse the traversal direction, keeping bounds and hints.
    pub fn rev(mut self) -> Self {
        self.dir = self.dir.flip();
        self
    }

    /// Skip immutable layers frozen before `ms`.
    pub fn written_since(mut self, ms: u64) -> Self {
        self.since_ms = Some(ms);
        self
    }

    /// Intersect the range with keys strictly beyond the consumed cursor.
    pub(crate) fn after(mut self, cursor: Option<&K>) -> Self {
        if let Some(cursor) = cursor {
            match self.dir {
                Dir::Asc => {
                    if bound_key(&self.start).is_none_or(|k| k.as_bytes() <= cursor.as_bytes()) {
                        self.start = Bound::Excluded(*cursor);
                    }
                }
                Dir::Desc => {
                    if bound_key(&self.end).is_none_or(|k| k.as_bytes() >= cursor.as_bytes()) {
                        self.end = Bound::Excluded(*cursor);
                    }
                }
            }
        }
        self.normalize();
        self
    }

    fn normalize(&mut self) {
        if let (Some(a), Some(b)) = (bound_key(&self.start), bound_key(&self.end)) {
            self.empty |= a.as_bytes() > b.as_bytes()
                || (a.as_bytes() == b.as_bytes()
                    && (!matches!(self.start, Bound::Included(_))
                        || !matches!(self.end, Bound::Included(_))));
        }
    }

    pub(crate) fn contains(&self, key: &[u8]) -> bool {
        !self.empty && lower_allows(&self.start, key) && upper_allows(&self.end, key)
    }

    pub(crate) fn overlaps(&self, min: &[u8], max: &[u8]) -> bool {
        !self.empty && lower_allows(&self.start, max) && upper_allows(&self.end, min)
    }
}

pub(crate) fn bound_key<K>(b: &Bound<K>) -> Option<&K> {
    match b {
        Bound::Included(k) | Bound::Excluded(k) => Some(k),
        Bound::Unbounded => None,
    }
}
fn lower_allows<K: Key>(b: &Bound<K>, k: &[u8]) -> bool {
    match b {
        Bound::Included(v) => k >= v.as_bytes(),
        Bound::Excluded(v) => k > v.as_bytes(),
        Bound::Unbounded => true,
    }
}
fn upper_allows<K: Key>(b: &Bound<K>, k: &[u8]) -> bool {
    match b {
        Bound::Included(v) => k <= v.as_bytes(),
        Bound::Excluded(v) => k < v.as_bytes(),
        Bound::Unbounded => true,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::seg::testkit::{TestKey, ordered_key};
    #[test]
    fn empty_inverted_ff_and_cursor_bounds() {
        assert!(SegRange::<TestKey>::prefix(&[0; 33]).empty);
        assert!(SegRange::<TestKey>::prefix(&[]).contains(&ordered_key(1)));
        assert!(SegRange::<TestKey>::prefix(&[255]).contains(&[255; 32]));
        assert!(
            SegRange::range(
                Bound::Included(&ordered_key(2)),
                Bound::Included(&ordered_key(1))
            )
            .empty
        );
        let query = SegRange::range(
            Bound::Included(&ordered_key(1)),
            Bound::Included(&ordered_key(3)),
        )
        .rev()
        .written_since(7)
        .after(Some(&ordered_key(2)));
        assert!(query.contains(&ordered_key(1)));
        assert!(!query.contains(&ordered_key(2)));
        assert_eq!(query.since_ms, Some(7));
        assert_eq!(query.dir, Dir::Desc);
        assert!(query.after(Some(&ordered_key(0))).empty);
    }
}