journal_index/
bitmap.rs

1//! Compressed bitmap for efficient set operations on entry indices.
2
3use roaring::RoaringBitmap;
4use serde::{Deserialize, Serialize};
5
6/// A compressed bitmap representing a set of journal entry indices.
7///
8/// Wraps [`RoaringBitmap`] and supports bitwise AND/OR operations for combining filters.
9#[derive(Debug, Clone, Default, Serialize, Deserialize)]
10#[cfg_attr(feature = "allocative", derive(allocative::Allocative))]
11#[serde(transparent)]
12pub struct Bitmap(pub RoaringBitmap);
13
14impl Bitmap {
15    /// Create an empty bitmap.
16    pub fn new() -> Self {
17        Self(RoaringBitmap::new())
18    }
19
20    /// Create a bitmap from a sorted iterator of entry indices.
21    pub fn from_sorted_iter<I: IntoIterator<Item = u32>>(
22        iterator: I,
23    ) -> Result<Bitmap, roaring::NonSortedIntegers> {
24        RoaringBitmap::from_sorted_iter(iterator).map(Bitmap)
25    }
26
27    /// Create a bitmap containing all integers in the given range.
28    pub fn insert_range<R>(range: R) -> Self
29    where
30        R: std::ops::RangeBounds<u32>,
31    {
32        let mut bitmap = Self::new();
33        RoaringBitmap::insert_range(&mut bitmap, range);
34        bitmap
35    }
36}
37
38impl std::ops::Deref for Bitmap {
39    type Target = RoaringBitmap;
40
41    fn deref(&self) -> &Self::Target {
42        &self.0
43    }
44}
45
46impl std::ops::DerefMut for Bitmap {
47    fn deref_mut(&mut self) -> &mut Self::Target {
48        &mut self.0
49    }
50}
51
52impl From<RoaringBitmap> for Bitmap {
53    fn from(bitmap: RoaringBitmap) -> Self {
54        Self(bitmap)
55    }
56}
57
58impl From<Bitmap> for RoaringBitmap {
59    fn from(wrapper: Bitmap) -> Self {
60        wrapper.0
61    }
62}
63
64impl std::ops::BitAndAssign<&Bitmap> for Bitmap {
65    fn bitand_assign(&mut self, rhs: &Bitmap) {
66        self.0 &= &rhs.0;
67    }
68}
69
70impl std::ops::BitAndAssign<Bitmap> for Bitmap {
71    fn bitand_assign(&mut self, rhs: Bitmap) {
72        self.0 &= rhs.0;
73    }
74}
75
76impl std::ops::BitOrAssign<&Bitmap> for Bitmap {
77    fn bitor_assign(&mut self, rhs: &Bitmap) {
78        self.0 |= &rhs.0;
79    }
80}
81
82impl std::ops::BitOrAssign<Bitmap> for Bitmap {
83    fn bitor_assign(&mut self, rhs: Bitmap) {
84        self.0 |= rhs.0;
85    }
86}
87
88impl std::ops::BitAnd for &Bitmap {
89    type Output = Bitmap;
90
91    fn bitand(self, rhs: &Bitmap) -> Bitmap {
92        Bitmap(&self.0 & &rhs.0)
93    }
94}
95
96impl std::ops::BitAnd<Bitmap> for &Bitmap {
97    type Output = Bitmap;
98
99    fn bitand(self, rhs: Bitmap) -> Bitmap {
100        Bitmap(&self.0 & rhs.0)
101    }
102}
103
104impl std::ops::BitAnd<&Bitmap> for Bitmap {
105    type Output = Bitmap;
106
107    fn bitand(self, rhs: &Bitmap) -> Bitmap {
108        Bitmap(self.0 & &rhs.0)
109    }
110}
111
112impl std::ops::BitAnd for Bitmap {
113    type Output = Bitmap;
114
115    fn bitand(self, rhs: Bitmap) -> Bitmap {
116        Bitmap(self.0 & rhs.0)
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123
124    #[test]
125    fn test_from_sorted_iter() {
126        let bitmap = Bitmap::from_sorted_iter([0, 5, 10, 15]).expect("sorted iterator");
127
128        assert_eq!(bitmap.len(), 4);
129        assert!(bitmap.contains(5));
130        assert!(!bitmap.contains(6));
131    }
132
133    #[test]
134    fn test_from_sorted_iter_rejects_unsorted() {
135        let result = Bitmap::from_sorted_iter([10, 5, 15]);
136        assert!(result.is_err());
137    }
138
139    #[test]
140    fn test_insert_range() {
141        let bitmap = Bitmap::insert_range(10..15);
142
143        assert_eq!(bitmap.len(), 5);
144        assert!(bitmap.contains(10));
145        assert!(bitmap.contains(14));
146        assert!(!bitmap.contains(15));
147    }
148
149    #[test]
150    fn test_bitwise_operations() {
151        let bitmap1 = Bitmap::from_sorted_iter([1, 2, 3]).expect("sorted");
152        let bitmap2 = Bitmap::from_sorted_iter([2, 3, 4]).expect("sorted");
153
154        let intersection = &bitmap1 & &bitmap2;
155        assert_eq!(intersection.len(), 2);
156
157        let mut union = bitmap1.clone();
158        union |= bitmap2;
159        assert_eq!(union.len(), 4);
160    }
161}
journal_index/bitmap.rs

journal_index/
bitmap.rs
