reifydb_core/value/column/
nones.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (c) 2025 ReifyDB
3
4use reifydb_type::{storage::DataBitVec, util::bitvec::BitVec};
5
6#[derive(Clone, Debug, PartialEq, Eq)]
7pub struct NoneBitmap {
8	words: Vec<u64>,
9	len: usize,
10}
11
12impl NoneBitmap {
13	pub fn all_present(len: usize) -> Self {
14		Self {
15			words: vec![0u64; words_for(len)],
16			len,
17		}
18	}
19
20	pub fn all_none(len: usize) -> Self {
21		let word_count = words_for(len);
22		let mut words = vec![u64::MAX; word_count];
23		let trailing = len % 64;
24		if trailing != 0 && word_count > 0 {
25			words[word_count - 1] = (1u64 << trailing) - 1;
26		}
27		Self {
28			words,
29			len,
30		}
31	}
32
33	pub fn len(&self) -> usize {
34		self.len
35	}
36
37	pub fn is_empty(&self) -> bool {
38		self.len == 0
39	}
40
41	pub fn is_none(&self, row: usize) -> bool {
42		debug_assert!(row < self.len, "row {} out of bounds for len {}", row, self.len);
43		(self.words[row / 64] >> (row % 64)) & 1 == 1
44	}
45
46	pub fn set_none(&mut self, row: usize) {
47		debug_assert!(row < self.len);
48		self.words[row / 64] |= 1u64 << (row % 64);
49	}
50
51	pub fn clear_none(&mut self, row: usize) {
52		debug_assert!(row < self.len);
53		self.words[row / 64] &= !(1u64 << (row % 64));
54	}
55
56	pub fn none_count(&self) -> usize {
57		popcount_masked(&self.words, self.len)
58	}
59
60	pub fn and(&self, other: &Self) -> Self {
61		assert_eq!(self.len, other.len, "NoneBitmap::and length mismatch");
62		let words = self.words.iter().zip(&other.words).map(|(a, b)| a & b).collect();
63		Self {
64			words,
65			len: self.len,
66		}
67	}
68
69	pub fn or(&self, other: &Self) -> Self {
70		assert_eq!(self.len, other.len, "NoneBitmap::or length mismatch");
71		let words = self.words.iter().zip(&other.words).map(|(a, b)| a | b).collect();
72		Self {
73			words,
74			len: self.len,
75		}
76	}
77
78	pub fn from_defined_bitvec(bv: &BitVec) -> Self {
79		let len = DataBitVec::len(bv);
80		let mut out = Self::all_present(len);
81		for row in 0..len {
82			if !DataBitVec::get(bv, row) {
83				out.set_none(row);
84			}
85		}
86		out
87	}
88
89	pub fn to_defined_bitvec(&self) -> BitVec {
90		let mut bits = Vec::with_capacity(self.len);
91		for row in 0..self.len {
92			bits.push(!self.is_none(row));
93		}
94		BitVec::from(bits)
95	}
96}
97
98const fn words_for(bits: usize) -> usize {
99	bits.div_ceil(64)
100}
101
102fn popcount_masked(words: &[u64], len: usize) -> usize {
103	let word_count = words.len();
104	if word_count == 0 {
105		return 0;
106	}
107	let mut count = 0usize;
108	for &w in &words[..word_count - 1] {
109		count += w.count_ones() as usize;
110	}
111	let trailing = len - 64 * (word_count - 1);
112	let mask = if trailing == 64 {
113		u64::MAX
114	} else {
115		(1u64 << trailing) - 1
116	};
117	count += (words[word_count - 1] & mask).count_ones() as usize;
118	count
119}
120
121#[cfg(test)]
122mod tests {
123	use super::*;
124
125	#[test]
126	fn all_present_has_zero_none_count() {
127		let b = NoneBitmap::all_present(100);
128		assert_eq!(b.none_count(), 0);
129		assert!(!b.is_none(0));
130		assert!(!b.is_none(99));
131	}
132
133	#[test]
134	fn all_none_counts_every_row() {
135		let b = NoneBitmap::all_none(65);
136		assert_eq!(b.none_count(), 65);
137		assert!(b.is_none(0));
138		assert!(b.is_none(64));
139	}
140
141	#[test]
142	fn set_and_clear_round_trip() {
143		let mut b = NoneBitmap::all_present(10);
144		b.set_none(3);
145		b.set_none(7);
146		assert_eq!(b.none_count(), 2);
147		assert!(b.is_none(3));
148		assert!(b.is_none(7));
149		assert!(!b.is_none(5));
150		b.clear_none(3);
151		assert_eq!(b.none_count(), 1);
152		assert!(!b.is_none(3));
153	}
154
155	#[test]
156	fn and_or_combine_bitmaps() {
157		let mut a = NoneBitmap::all_present(8);
158		a.set_none(1);
159		a.set_none(3);
160		let mut b = NoneBitmap::all_present(8);
161		b.set_none(3);
162		b.set_none(5);
163		assert_eq!(a.and(&b).none_count(), 1);
164		assert_eq!(a.or(&b).none_count(), 3);
165	}
166}
reifydb_core/value/column/nones.rs

reifydb_core/value/column/
nones.rs
