obj_core/pager/
freelist.rs

1//! Freelist representation.
2//!
3//! Format version 0 uses an in-page linked list: the file header's
4//! `freelist_head` points at the most-recently-freed page, and each
5//! freelist page stores the `PageId` of the next one (or `0` for the
6//! end of the list). See `docs/format.md` § Freelist representation.
7//!
8//! At M2 the freelist holds at most one id per page (the head of the
9//! list). M3 extends the freelist page to also store a bulk array of
10//! freed ids; that extension is forward-compatible (Rule 5 — the on-
11//! disk type tag does not change).
12//!
13//! This module exposes pure encode / decode helpers. The pager
14//! (`super::Pager`) is responsible for sequencing the writes; keeping
15//! the codec separate makes it easy to unit-test in isolation and to
16//! re-use from the verifier/CLI in later milestones.
17
18#![forbid(unsafe_code)]
19
20use crate::pager::page::{Page, PAGE_SIZE, PAGE_TRAILER_SIZE};
21
22/// On-disk type tag for a freelist page. See `docs/format.md`.
23pub const TYPE_FREE_LIST: u8 = 0x05;
24
25/// Offset of the `next` link inside a freelist page (in bytes).
26const OFF_NEXT: usize = 8;
27
28// Compile-time check: the page must be large enough to hold the
29// freelist header (1 tag byte, 7 reserved, 8 next-pointer) plus a
30// page trailer. The check is here rather than inside `encode` so it
31// fires at build time on any future page-size change.
32const _: () = assert!(PAGE_SIZE >= PAGE_TRAILER_SIZE + OFF_NEXT + 8);
33
34/// In-memory view of a freelist page.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub struct FreeListPage {
37    /// Next page on the freelist, or `0` if this is the last entry.
38    pub next: u64,
39}
40
41impl FreeListPage {
42    /// Construct a freelist page that points at `next`. Pass `0` to
43    /// mark the tail of the list.
44    #[must_use]
45    pub const fn new(next: u64) -> Self {
46        Self { next }
47    }
48}
49
50/// Encode `entry` into `page`. The page-trailer region (last
51/// [`PAGE_TRAILER_SIZE`] bytes) is left zero; the pager writes the
52/// trailer (issue #6).
53pub fn encode(entry: FreeListPage, page: &mut Page) {
54    let buf = page.as_bytes_mut();
55    buf.fill(0);
56    buf[0] = TYPE_FREE_LIST;
57    // bytes 1..OFF_NEXT remain zero (reserved for future flags).
58    buf[OFF_NEXT..OFF_NEXT + 8].copy_from_slice(&entry.next.to_le_bytes());
59    // bytes OFF_NEXT+8..PAGE_SIZE-PAGE_TRAILER_SIZE remain zero — the
60    // M3 bulk array slot — and the trailer remains zero in M2.
61}
62
63/// Decode a freelist page. Caller is responsible for checking the
64/// page trailer (issue #6).
65///
66/// Returns `None` if the type tag is wrong; in that case the caller
67/// should surface `Error::Corruption`.
68#[must_use]
69pub fn decode(page: &Page) -> Option<FreeListPage> {
70    let buf = page.as_bytes();
71    if buf[0] != TYPE_FREE_LIST {
72        return None;
73    }
74    let mut next_bytes = [0u8; 8];
75    next_bytes.copy_from_slice(&buf[OFF_NEXT..OFF_NEXT + 8]);
76    Some(FreeListPage {
77        next: u64::from_le_bytes(next_bytes),
78    })
79}
80
81#[cfg(test)]
82mod tests {
83    use super::{decode, encode, FreeListPage};
84    use crate::pager::page::Page;
85
86    #[test]
87    fn round_trip() {
88        for &next in &[0u64, 1, 42, u64::MAX] {
89            let mut p = Page::zeroed();
90            encode(FreeListPage::new(next), &mut p);
91            assert_eq!(decode(&p), Some(FreeListPage { next }));
92        }
93    }
94
95    #[test]
96    fn decode_rejects_bad_tag() {
97        let mut p = Page::zeroed();
98        p.as_bytes_mut()[0] = 0x03; // BTreeLeaf
99        assert!(decode(&p).is_none());
100    }
101}
obj_core/pager/freelist.rs

obj_core/pager/
freelist.rs
