nodedb_types/surrogate_bitmap/
bitmap.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! `SurrogateBitmap` — a roaring bitmap of `Surrogate` values used as the
4//! universal cross-engine prefilter currency.
5//!
6//! Every engine that produces candidate row sets returns (or accepts) a
7//! `SurrogateBitmap`. Cross-engine prefilter reduces to bitmap intersection
8//! with zero per-query ID translation.
9
10use roaring::RoaringBitmap;
11
12use crate::surrogate::Surrogate;
13
14/// A dense set of [`Surrogate`] values backed by a roaring bitmap.
15///
16/// Used as the prefilter currency flowing between engines in a
17/// `PhysicalPlan`: the planner may embed a `SurrogateBitmap` produced
18/// by one engine sub-plan directly into another engine's prefilter
19/// slot without any ID translation step.
20#[derive(Debug, Clone, PartialEq)]
21pub struct SurrogateBitmap(pub RoaringBitmap);
22
23impl SurrogateBitmap {
24    /// Create an empty bitmap.
25    pub fn new() -> Self {
26        Self(RoaringBitmap::new())
27    }
28
29    // `from_iter` is provided by the `FromIterator<Surrogate>` impl below.
30
31    /// Return `true` if `surrogate` is present in the bitmap.
32    pub fn contains(&self, surrogate: Surrogate) -> bool {
33        self.0.contains(surrogate.0)
34    }
35
36    /// Insert `surrogate` into the bitmap.
37    pub fn insert(&mut self, surrogate: Surrogate) {
38        self.0.insert(surrogate.0);
39    }
40
41    /// Remove `surrogate` from the bitmap. No-op when absent.
42    pub fn remove(&mut self, surrogate: Surrogate) {
43        self.0.remove(surrogate.0);
44    }
45
46    /// Number of elements in the bitmap.
47    pub fn len(&self) -> u64 {
48        self.0.len()
49    }
50
51    /// Return `true` if the bitmap contains no elements.
52    pub fn is_empty(&self) -> bool {
53        self.0.is_empty()
54    }
55
56    /// Iterate over the surrogates in ascending order.
57    pub fn iter(&self) -> impl Iterator<Item = Surrogate> + '_ {
58        self.0.iter().map(Surrogate)
59    }
60}
61
62impl Default for SurrogateBitmap {
63    fn default() -> Self {
64        Self::new()
65    }
66}
67
68impl FromIterator<Surrogate> for SurrogateBitmap {
69    fn from_iter<I: IntoIterator<Item = Surrogate>>(iter: I) -> Self {
70        let mut inner = RoaringBitmap::new();
71        for s in iter {
72            inner.insert(s.0);
73        }
74        Self(inner)
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn new_is_empty() {
84        let b = SurrogateBitmap::new();
85        assert!(b.is_empty());
86        assert_eq!(b.len(), 0);
87    }
88
89    #[test]
90    fn insert_and_contains() {
91        let mut b = SurrogateBitmap::new();
92        b.insert(Surrogate(1));
93        b.insert(Surrogate(100));
94        assert!(b.contains(Surrogate(1)));
95        assert!(b.contains(Surrogate(100)));
96        assert!(!b.contains(Surrogate(2)));
97        assert_eq!(b.len(), 2);
98    }
99
100    #[test]
101    fn remove_is_noop_when_absent() {
102        let mut b = SurrogateBitmap::new();
103        b.remove(Surrogate(99));
104        assert!(b.is_empty());
105    }
106
107    #[test]
108    fn from_iter_deduplicates() {
109        let b = SurrogateBitmap::from_iter([Surrogate(1), Surrogate(1), Surrogate(2)]);
110        assert_eq!(b.len(), 2);
111    }
112
113    #[test]
114    fn iter_yields_ascending_order() {
115        let b = SurrogateBitmap::from_iter([Surrogate(5), Surrogate(1), Surrogate(3)]);
116        let v: Vec<u32> = b.iter().map(|s| s.0).collect();
117        assert_eq!(v, vec![1, 3, 5]);
118    }
119
120    #[test]
121    fn large_bitmap_roundtrip() {
122        let b = SurrogateBitmap::from_iter((1u32..=10_000).map(Surrogate));
123        assert_eq!(b.len(), 10_000);
124        assert!(b.contains(Surrogate(1)));
125        assert!(b.contains(Surrogate(10_000)));
126        assert!(!b.contains(Surrogate(10_001)));
127    }
128}
nodedb_types/surrogate_bitmap/bitmap.rs

nodedb_types/surrogate_bitmap/
bitmap.rs
