linkrs_core/
null_bitmap.rs

1//! Null Bitmap
2//!
3//! Bit-packed null value bitmap for efficient storage.
4//! Uses 1 bit per element instead of 1 byte per element in Vec<bool>.
5
6use std::fmt;
7use std::ops::{BitAnd, BitOr, Not};
8
9/// Bit-packed null bitmap for efficient storage
10///
11/// Uses 64-bit words to store null flags, achieving 8x memory savings
12/// compared to Vec<bool>.
13#[derive(Clone, PartialEq, Eq)]
14pub struct NullBitmap {
15    /// Bit storage (64 bits per word)
16    data: Vec<u64>,
17    /// Number of elements tracked
18    len: usize,
19}
20
21impl NullBitmap {
22    /// Bits per word
23    const BITS_PER_WORD: usize = 64;
24
25    /// Create a new empty null bitmap
26    pub fn new() -> Self {
27        Self {
28            data: Vec::new(),
29            len: 0,
30        }
31    }
32
33    /// Create a new null bitmap with specified capacity
34    pub fn with_capacity(capacity: usize) -> Self {
35        let words = Self::word_count(capacity);
36        Self {
37            data: Vec::with_capacity(words),
38            len: 0,
39        }
40    }
41
42    /// Create a null bitmap with all elements set to non-null
43    pub fn with_len(len: usize) -> Self {
44        let words = Self::word_count(len);
45        Self {
46            data: vec![0; words],
47            len,
48        }
49    }
50
51    /// Create a null bitmap with all elements set to null
52    pub fn all_null(len: usize) -> Self {
53        let words = Self::word_count(len);
54        Self {
55            data: vec![u64::MAX; words],
56            len,
57        }
58    }
59
60    /// Create a null bitmap from raw u64 word data and element length.
61    pub fn from_raw(data: Vec<u64>, len: usize) -> Self {
62        Self { data, len }
63    }
64
65    /// Calculate number of words needed for given length
66    fn word_count(len: usize) -> usize {
67        len.div_ceil(Self::BITS_PER_WORD)
68    }
69
70    /// Get the word index and bit position for an element
71    fn get_position(idx: usize) -> (usize, usize) {
72        (idx / Self::BITS_PER_WORD, idx % Self::BITS_PER_WORD)
73    }
74
75    /// Ensure capacity for at least `new_len` elements
76    pub fn reserve(&mut self, new_len: usize) {
77        let words = Self::word_count(new_len);
78        if words > self.data.len() {
79            self.data.resize(words, 0);
80        }
81    }
82
83    /// Set the length of the bitmap
84    /// New elements are initialized to non-null (0)
85    pub fn resize(&mut self, new_len: usize) {
86        let words = Self::word_count(new_len);
87        self.data.resize(words, 0);
88        self.len = new_len;
89    }
90
91    /// Check if an element is null
92    ///
93    /// Returns true if the element is null or out of bounds
94    pub fn is_null(&self, idx: usize) -> bool {
95        if idx >= self.len {
96            return true;
97        }
98        unsafe { self.is_null_unchecked(idx) }
99    }
100
101    /// Check if an element is null without bounds checking
102    ///
103    /// # Safety
104    /// Caller must ensure `idx < self.len`.
105    pub unsafe fn is_null_unchecked(&self, idx: usize) -> bool {
106        let (word_idx, bit_idx) = Self::get_position(idx);
107        (self.data.get_unchecked(word_idx) >> bit_idx) & 1 == 1
108    }
109
110    /// Check if an element is valid (not null)
111    pub fn is_valid(&self, idx: usize) -> bool {
112        !self.is_null(idx)
113    }
114
115    /// Set an element as null or non-null
116    pub fn set(&mut self, idx: usize, is_null: bool) {
117        if idx >= self.len {
118            self.resize(idx + 1);
119        }
120        let (word_idx, bit_idx) = Self::get_position(idx);
121        if is_null {
122            self.data[word_idx] |= 1u64 << bit_idx;
123        } else {
124            self.data[word_idx] &= !(1u64 << bit_idx);
125        }
126    }
127
128    /// Set an element as null
129    pub fn set_null(&mut self, idx: usize) {
130        self.set(idx, true);
131    }
132
133    /// Set an element as valid (non-null)
134    pub fn set_valid(&mut self, idx: usize) {
135        self.set(idx, false);
136    }
137
138    /// Set a range of elements as null
139    ///
140    /// All indices in `[start, end)` are marked as null.
141    ///
142    /// # Panics
143    /// Panics if `end > self.len` or `start > end`.
144    pub fn set_null_range(&mut self, start: usize, end: usize) {
145        assert!(end <= self.len && start <= end);
146        if start == end {
147            return;
148        }
149        let (start_word, start_bit) = Self::get_position(start);
150        let (end_word, end_bit) = Self::get_position(end);
151
152        if start_word == end_word {
153            // Range within a single word
154            let len = end_bit - start_bit;
155            let mask = ((1u64 << len) - 1) << start_bit;
156            self.data[start_word] |= mask;
157        } else {
158            // First partial word
159            self.data[start_word] |= !0u64 << start_bit;
160
161            // Full words in between
162            for word in &mut self.data[start_word + 1..end_word] {
163                *word = u64::MAX;
164            }
165
166            // Last partial word
167            if end_bit > 0 {
168                let mask = (1u64 << end_bit) - 1;
169                self.data[end_word] |= mask;
170            }
171        }
172    }
173
174    /// Get the number of elements
175    pub fn len(&self) -> usize {
176        self.len
177    }
178
179    /// Check if the bitmap is empty
180    pub fn is_empty(&self) -> bool {
181        self.len == 0
182    }
183
184    /// Count the number of null elements
185    pub fn null_count(&self) -> usize {
186        let full_words = self.len / Self::BITS_PER_WORD;
187        let remaining_bits = self.len % Self::BITS_PER_WORD;
188
189        let mut count: usize = self.data[..full_words]
190            .iter()
191            .map(|&w| w.count_ones() as usize)
192            .sum();
193
194        if remaining_bits > 0 && full_words < self.data.len() {
195            let last_word = self.data[full_words];
196            let mask = (1u64 << remaining_bits) - 1;
197            count += (last_word & mask).count_ones() as usize;
198        }
199
200        count
201    }
202
203    /// Count the number of valid (non-null) elements
204    pub fn valid_count(&self) -> usize {
205        self.len - self.null_count()
206    }
207
208    /// Check if all elements are null
209    pub fn is_all_null(&self) -> bool {
210        self.null_count() == self.len
211    }
212
213    /// Check if all elements are valid
214    pub fn is_all_valid(&self) -> bool {
215        self.null_count() == 0
216    }
217
218    /// Get the underlying bit data
219    pub fn as_bits(&self) -> &[u64] {
220        &self.data
221    }
222
223    /// Append a null (true) or non-null (false) element to the end
224    pub fn push(&mut self, is_null: bool) {
225        let idx = self.len;
226        self.len += 1;
227        let needed_words = Self::word_count(self.len);
228        if needed_words > self.data.len() {
229            self.data.push(0);
230        }
231        if is_null {
232            let (word_idx, bit_idx) = Self::get_position(idx);
233            self.data[word_idx] |= 1u64 << bit_idx;
234        }
235    }
236
237    /// Clear all elements
238    pub fn clear(&mut self) {
239        self.data.clear();
240        self.len = 0;
241    }
242
243    /// Fill all elements with the given value
244    pub fn fill(&mut self, is_null: bool) {
245        let value = if is_null { u64::MAX } else { 0 };
246        self.data.fill(value);
247    }
248
249    /// Invert all bits (null becomes valid, valid becomes null)
250    pub fn invert(&mut self) {
251        for word in &mut self.data {
252            *word = !*word;
253        }
254    }
255
256    /// Get an iterator over null indices
257    pub fn null_indices(&self) -> impl Iterator<Item = usize> + '_ {
258        let len = self.len;
259        self.data
260            .iter()
261            .enumerate()
262            .flat_map(move |(word_idx, &word)| {
263                let base = word_idx * Self::BITS_PER_WORD;
264                (0..Self::BITS_PER_WORD).filter_map(move |bit_idx| {
265                    let idx = base + bit_idx;
266                    if idx < len && (word >> bit_idx) & 1 == 1 {
267                        Some(idx)
268                    } else {
269                        None
270                    }
271                })
272            })
273    }
274
275    /// Get an iterator over valid (non-null) indices
276    pub fn valid_indices(&self) -> impl Iterator<Item = usize> + '_ {
277        let len = self.len;
278        self.data
279            .iter()
280            .enumerate()
281            .flat_map(move |(word_idx, &word)| {
282                let base = word_idx * Self::BITS_PER_WORD;
283                (0..Self::BITS_PER_WORD).filter_map(move |bit_idx| {
284                    let idx = base + bit_idx;
285                    if idx < len && (word >> bit_idx) & 1 == 0 {
286                        Some(idx)
287                    } else {
288                        None
289                    }
290                })
291            })
292    }
293
294    /// Memory usage in bytes
295    pub fn memory_usage(&self) -> usize {
296        self.data.len() * std::mem::size_of::<u64>()
297    }
298
299    /// Memory usage per element in bits
300    pub fn bits_per_element(&self) -> f64 {
301        if self.len == 0 {
302            return 0.0;
303        }
304        (self.memory_usage() * 8) as f64 / self.len as f64
305    }
306}
307
308impl Default for NullBitmap {
309    fn default() -> Self {
310        Self::new()
311    }
312}
313
314impl fmt::Debug for NullBitmap {
315    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316        write!(f, "NullBitmap {{ len: {}, nulls: [", self.len)?;
317        let nulls: Vec<_> = self.null_indices().take(10).collect();
318        for (i, idx) in nulls.iter().enumerate() {
319            if i > 0 {
320                write!(f, ", ")?;
321            }
322            write!(f, "{}", idx)?;
323        }
324        if self.null_count() > 10 {
325            write!(f, ", ...")?;
326        }
327        write!(f, "] }}")
328    }
329}
330
331impl BitAnd for &NullBitmap {
332    type Output = NullBitmap;
333
334    fn bitand(self, rhs: Self) -> Self::Output {
335        let len = self.len.min(rhs.len);
336        let mut result = NullBitmap::with_len(len);
337        for i in 0..result.data.len() {
338            let left = self.data.get(i).copied().unwrap_or(0);
339            let right = rhs.data.get(i).copied().unwrap_or(0);
340            result.data[i] = left & right;
341        }
342        result
343    }
344}
345
346impl BitOr for &NullBitmap {
347    type Output = NullBitmap;
348
349    fn bitor(self, rhs: Self) -> Self::Output {
350        let len = self.len.max(rhs.len);
351        let mut result = NullBitmap::with_len(len);
352        for i in 0..result.data.len() {
353            let left = self.data.get(i).copied().unwrap_or(0);
354            let right = rhs.data.get(i).copied().unwrap_or(0);
355            result.data[i] = left | right;
356        }
357        result
358    }
359}
360
361impl Not for &NullBitmap {
362    type Output = NullBitmap;
363
364    fn not(self) -> Self::Output {
365        let mut result = self.clone();
366        result.invert();
367        result
368    }
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374
375    #[test]
376    fn test_basic_operations() {
377        let mut bitmap = NullBitmap::with_len(10);
378
379        assert!(!bitmap.is_null(0));
380        assert!(!bitmap.is_null(5));
381
382        bitmap.set_null(3);
383        assert!(bitmap.is_null(3));
384        assert!(!bitmap.is_null(4));
385
386        bitmap.set_valid(3);
387        assert!(!bitmap.is_null(3));
388    }
389
390    #[test]
391    fn test_all_null() {
392        let bitmap = NullBitmap::all_null(100);
393        assert!(bitmap.is_all_null());
394        assert_eq!(bitmap.null_count(), 100);
395        assert_eq!(bitmap.valid_count(), 0);
396    }
397
398    #[test]
399    fn test_all_valid() {
400        let bitmap = NullBitmap::with_len(100);
401        assert!(bitmap.is_all_valid());
402        assert_eq!(bitmap.null_count(), 0);
403        assert_eq!(bitmap.valid_count(), 100);
404    }
405
406    #[test]
407    fn test_memory_efficiency() {
408        let bitmap = NullBitmap::with_len(1000);
409        assert!(bitmap.memory_usage() <= 128);
410        assert!(bitmap.bits_per_element() <= 1.1);
411    }
412
413    #[test]
414    fn test_comparison_with_vec_bool() {
415        let n = 1000;
416        let bitmap = NullBitmap::with_len(n);
417        let vec_bool: Vec<bool> = vec![false; n];
418
419        let bitmap_size = bitmap.memory_usage();
420        let vec_size = vec_bool.len() * std::mem::size_of::<bool>();
421        assert!(bitmap_size < vec_size / 7);
422    }
423
424    #[test]
425    fn test_resize() {
426        let mut bitmap = NullBitmap::with_len(10);
427        bitmap.set_null(5);
428
429        bitmap.resize(100);
430        assert!(bitmap.is_null(5));
431        assert!(!bitmap.is_null(50));
432        assert_eq!(bitmap.len(), 100);
433    }
434
435    #[test]
436    fn test_null_indices() {
437        let mut bitmap = NullBitmap::with_len(10);
438        bitmap.set_null(1);
439        bitmap.set_null(3);
440        bitmap.set_null(7);
441
442        let nulls: Vec<_> = bitmap.null_indices().collect();
443        assert_eq!(nulls, vec![1, 3, 7]);
444    }
445
446    #[test]
447    fn test_valid_indices() {
448        let mut bitmap = NullBitmap::all_null(5);
449        bitmap.set_valid(1);
450        bitmap.set_valid(3);
451
452        let valids: Vec<_> = bitmap.valid_indices().collect();
453        assert_eq!(valids, vec![1, 3]);
454    }
455
456    #[test]
457    fn test_bitwise_operations() {
458        let mut a = NullBitmap::with_len(10);
459        a.set_null(1);
460        a.set_null(2);
461
462        let mut b = NullBitmap::with_len(10);
463        b.set_null(2);
464        b.set_null(3);
465
466        let and_result = &a & &b;
467        assert!(and_result.is_null(2));
468        assert!(!and_result.is_null(1));
469        assert!(!and_result.is_null(3));
470
471        let or_result = &a | &b;
472        assert!(or_result.is_null(1));
473        assert!(or_result.is_null(2));
474        assert!(or_result.is_null(3));
475
476        let not_result = !&a;
477        assert!(!not_result.is_null(1));
478        assert!(!not_result.is_null(2));
479        assert!(not_result.is_null(0));
480    }
481
482    #[test]
483    fn test_out_of_bounds() {
484        let bitmap = NullBitmap::with_len(10);
485        assert!(bitmap.is_null(100));
486    }
487
488    #[test]
489    fn test_large_bitmap() {
490        let mut bitmap = NullBitmap::with_len(10000);
491
492        for i in (0..10000).step_by(100) {
493            bitmap.set_null(i);
494        }
495
496        assert_eq!(bitmap.null_count(), 100);
497
498        for i in 0..10000 {
499            if i % 100 == 0 {
500                assert!(bitmap.is_null(i));
501            } else {
502                assert!(!bitmap.is_null(i));
503            }
504        }
505    }
506
507    #[test]
508    fn test_is_null_unchecked() {
509        let mut bitmap = NullBitmap::with_len(100);
510        bitmap.set_null(42);
511
512        unsafe {
513            assert!(bitmap.is_null_unchecked(42));
514            assert!(!bitmap.is_null_unchecked(0));
515            assert!(!bitmap.is_null_unchecked(99));
516        }
517    }
518
519    #[test]
520    fn test_set_null_range_single_word() {
521        let mut bitmap = NullBitmap::with_len(64);
522        bitmap.set_null_range(10, 20);
523
524        for i in 0..64 {
525            if (10..20).contains(&i) {
526                assert!(bitmap.is_null(i), "bit {} should be null", i);
527            } else {
528                assert!(!bitmap.is_null(i), "bit {} should not be null", i);
529            }
530        }
531        assert_eq!(bitmap.null_count(), 10);
532    }
533
534    #[test]
535    fn test_set_null_range_multi_word() {
536        let mut bitmap = NullBitmap::with_len(200);
537        bitmap.set_null_range(60, 130);
538
539        for i in 0..200 {
540            if (60..130).contains(&i) {
541                assert!(bitmap.is_null(i), "bit {} should be null", i);
542            } else {
543                assert!(!bitmap.is_null(i), "bit {} should not be null", i);
544            }
545        }
546        assert_eq!(bitmap.null_count(), 70);
547    }
548
549    #[test]
550    fn test_set_null_range_empty() {
551        let mut bitmap = NullBitmap::with_len(100);
552        bitmap.set_null_range(30, 30);
553        assert_eq!(bitmap.null_count(), 0);
554    }
555
556    #[test]
557    fn test_set_null_range_full() {
558        let mut bitmap = NullBitmap::with_len(200);
559        bitmap.set_null_range(0, 200);
560        assert!(bitmap.is_all_null());
561        assert_eq!(bitmap.null_count(), 200);
562    }
563
564    #[test]
565    fn test_bitand_different_lengths() {
566        let mut a = NullBitmap::with_len(10);
567        a.set_null(5);
568        a.set_null(8);
569
570        let mut b = NullBitmap::with_len(20);
571        b.set_null(8);
572        b.set_null(15);
573
574        let result = &a & &b;
575        assert_eq!(result.len(), 10);
576        assert!(result.is_null(8));
577        assert!(!result.is_null(5));
578        assert!(!result.is_null(9));
579    }
580
581    #[test]
582    fn test_bitor_different_lengths() {
583        let mut a = NullBitmap::with_len(10);
584        a.set_null(5);
585        a.set_null(8);
586
587        let mut b = NullBitmap::with_len(20);
588        b.set_null(8);
589        b.set_null(15);
590
591        let result = &a | &b;
592        assert_eq!(result.len(), 20);
593        assert!(result.is_null(5));
594        assert!(result.is_null(8));
595        assert!(result.is_null(15));
596        assert!(!result.is_null(0));
597        assert!(!result.is_null(16));
598    }
599
600    #[test]
601    #[should_panic(expected = "end <= self.len")]
602    fn test_set_null_range_panic() {
603        let mut bitmap = NullBitmap::with_len(10);
604        bitmap.set_null_range(5, 15);
605    }
606
607    #[test]
608    fn test_push() {
609        let mut bitmap = NullBitmap::new();
610        bitmap.push(false);
611        bitmap.push(true);
612        bitmap.push(false);
613        bitmap.push(true);
614        bitmap.push(true);
615
616        assert_eq!(bitmap.len(), 5);
617        assert!(!bitmap.is_null(0));
618        assert!(bitmap.is_null(1));
619        assert!(!bitmap.is_null(2));
620        assert!(bitmap.is_null(3));
621        assert!(bitmap.is_null(4));
622        assert_eq!(bitmap.null_count(), 3);
623        assert_eq!(bitmap.valid_count(), 2);
624    }
625}
linkrs_core/null_bitmap.rs

linkrs_core/
null_bitmap.rs
