mongreldb_core/
rowid.rs

1use serde::{Deserialize, Serialize};
2
3use crate::{MongrelError, Result};
4
5/// A stable, dense row identifier shared by *every* index in a table.
6///
7/// Row IDs are allocated monotonically and **never reused**. Deletes record a
8/// tombstone at the row id; updates allocate a *new* row id and tombstone the
9/// old one. All indexes (primary HOT, learned PGM, secondary bitmaps, ANN,
10/// FM-index) resolve to or from `RowId`, so multi-condition queries intersect
11/// in a single id space.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
13pub struct RowId(pub u64);
14
15impl RowId {
16    pub const MIN: RowId = RowId(0);
17    pub const NULL_SORT_KEY: u16 = 0xFFFF;
18
19    #[inline]
20    pub fn next(self) -> Option<RowId> {
21        self.0.checked_add(1).map(RowId)
22    }
23}
24
25impl std::fmt::Display for RowId {
26    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
27        write!(f, "RowId({})", self.0)
28    }
29}
30
31impl From<u64> for RowId {
32    fn from(v: u64) -> Self {
33        RowId(v)
34    }
35}
36
37/// Monotonic allocator for [`RowId`]s.
38#[derive(Debug, Default, Clone)]
39pub struct RowIdAllocator {
40    next: u64,
41}
42
43impl RowIdAllocator {
44    pub fn new(start: u64) -> Self {
45        Self { next: start }
46    }
47
48    /// Allocate a single new row id.
49    #[inline]
50    pub fn alloc(&mut self) -> Result<RowId> {
51        let id = self.next;
52        self.next = self
53            .next
54            .checked_add(1)
55            .filter(|next| *next < u64::MAX)
56            .ok_or_else(row_id_exhausted)?;
57        Ok(RowId(id))
58    }
59
60    /// Allocate a contiguous range of `n` row ids, returning the inclusive start.
61    pub fn alloc_range(&mut self, n: u64) -> Result<RowId> {
62        let start = self.next;
63        if n != 0 {
64            self.next = self
65                .next
66                .checked_add(n)
67                .filter(|next| *next < u64::MAX)
68                .ok_or_else(row_id_exhausted)?;
69        }
70        Ok(RowId(start))
71    }
72
73    #[inline]
74    pub fn current(&self) -> RowId {
75        RowId(self.next)
76    }
77
78    /// Advance the allocator past `id` if it is ahead. Used during recovery.
79    pub fn advance_to(&mut self, id: RowId) -> Result<()> {
80        if id.0 >= self.next {
81            self.next =
82                id.0.checked_add(1)
83                    .filter(|next| *next < u64::MAX)
84                    .ok_or_else(row_id_exhausted)?;
85        }
86        Ok(())
87    }
88}
89
90fn row_id_exhausted() -> MongrelError {
91    MongrelError::Full("row-id namespace exhausted".into())
92}
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97
98    #[test]
99    fn allocates_monotonically() {
100        let mut a = RowIdAllocator::default();
101        assert_eq!(a.alloc().unwrap(), RowId(0));
102        assert_eq!(a.alloc().unwrap(), RowId(1));
103        let start = a.alloc_range(3).unwrap();
104        assert_eq!(start, RowId(2));
105        assert_eq!(a.current(), RowId(5));
106        assert_eq!(a.alloc().unwrap(), RowId(5));
107    }
108
109    #[test]
110    fn advance_to_moves_head() {
111        let mut a = RowIdAllocator::default();
112        a.advance_to(RowId(100)).unwrap();
113        assert_eq!(a.alloc().unwrap(), RowId(101));
114    }
115
116    #[test]
117    fn exhaustion_never_wraps_or_partially_allocates() {
118        let mut a = RowIdAllocator::new(u64::MAX - 2);
119        assert_eq!(a.alloc().unwrap(), RowId(u64::MAX - 2));
120        assert!(matches!(a.alloc(), Err(MongrelError::Full(_))));
121        assert_eq!(a.current(), RowId(u64::MAX - 1));
122        assert!(matches!(a.alloc_range(2), Err(MongrelError::Full(_))));
123        assert_eq!(a.current(), RowId(u64::MAX - 1));
124        assert!(matches!(
125            a.advance_to(RowId(u64::MAX)),
126            Err(MongrelError::Full(_))
127        ));
128        assert_eq!(a.current(), RowId(u64::MAX - 1));
129    }
130}
mongreldb_core/rowid.rs

mongreldb_core/
rowid.rs
