apfsds_storage/
blink_tree.rs

1//! B-link tree index (simplified version for Phase 1)
2
3use dashmap::DashMap;
4
5use crate::SegmentPtr;
6
7/// A simplified B-link tree index using DashMap
8/// Full B-link tree implementation will be added in Phase 2
9pub struct BLinkTree {
10    /// Connection ID -> Segment pointer
11    index: DashMap<u64, SegmentPtr>,
12}
13
14impl BLinkTree {
15    /// Create a new index
16    pub fn new() -> Self {
17        Self {
18            index: DashMap::new(),
19        }
20    }
21
22    /// Insert or update an entry
23    pub fn insert(&self, conn_id: u64, ptr: SegmentPtr) {
24        self.index.insert(conn_id, ptr);
25    }
26
27    /// Search for a connection
28    pub fn search(&self, conn_id: u64) -> Option<SegmentPtr> {
29        self.index.get(&conn_id).map(|r| *r)
30    }
31
32    /// Remove a connection
33    pub fn remove(&self, conn_id: u64) -> Option<SegmentPtr> {
34        self.index.remove(&conn_id).map(|(_, v)| v)
35    }
36
37    /// Get the number of entries
38    pub fn len(&self) -> usize {
39        self.index.len()
40    }
41
42    /// Check if empty
43    pub fn is_empty(&self) -> bool {
44        self.index.is_empty()
45    }
46
47    /// Iterate over all entries
48    pub fn iter(&self) -> impl Iterator<Item = (u64, SegmentPtr)> + '_ {
49        self.index.iter().map(|r| (*r.key(), *r.value()))
50    }
51}
52
53impl Default for BLinkTree {
54    fn default() -> Self {
55        Self::new()
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_insert_search() {
65        let tree = BLinkTree::new();
66
67        let ptr = SegmentPtr {
68            segment_id: 1,
69            offset: 100,
70        };
71
72        tree.insert(42, ptr);
73
74        let found = tree.search(42).unwrap();
75        assert_eq!(found.segment_id, 1);
76        assert_eq!(found.offset, 100);
77    }
78
79    #[test]
80    fn test_remove() {
81        let tree = BLinkTree::new();
82
83        let ptr = SegmentPtr {
84            segment_id: 1,
85            offset: 100,
86        };
87
88        tree.insert(42, ptr);
89        assert!(tree.search(42).is_some());
90
91        tree.remove(42);
92        assert!(tree.search(42).is_none());
93    }
94}
apfsds_storage/blink_tree.rs

apfsds_storage/
blink_tree.rs
