reifydb_core/value/column/
nones.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (c) 2026 ReifyDB
3
4use reifydb_value::{reifydb_assertions, 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		reifydb_assertions! {
43			assert!(row < self.len, "row {} out of bounds for len {}", row, self.len);
44		}
45		(self.words[row / 64] >> (row % 64)) & 1 == 1
46	}
47
48	pub fn set_none(&mut self, row: usize) {
49		reifydb_assertions! {
50			assert!(row < self.len);
51		}
52		self.words[row / 64] |= 1u64 << (row % 64);
53	}
54
55	pub fn clear_none(&mut self, row: usize) {
56		reifydb_assertions! {
57			assert!(row < self.len);
58		}
59		self.words[row / 64] &= !(1u64 << (row % 64));
60	}
61
62	pub fn none_count(&self) -> usize {
63		popcount_masked(&self.words, self.len)
64	}
65
66	pub fn and(&self, other: &Self) -> Self {
67		assert_eq!(self.len, other.len, "NoneBitmap::and length mismatch");
68		let words = self.words.iter().zip(&other.words).map(|(a, b)| a & b).collect();
69		Self {
70			words,
71			len: self.len,
72		}
73	}
74
75	pub fn or(&self, other: &Self) -> Self {
76		assert_eq!(self.len, other.len, "NoneBitmap::or length mismatch");
77		let words = self.words.iter().zip(&other.words).map(|(a, b)| a | b).collect();
78		Self {
79			words,
80			len: self.len,
81		}
82	}
83
84	pub fn from_defined_bitvec(bv: &BitVec) -> Self {
85		let len = DataBitVec::len(bv);
86		let mut out = Self::all_present(len);
87		for row in 0..len {
88			if !DataBitVec::get(bv, row) {
89				out.set_none(row);
90			}
91		}
92		out
93	}
94
95	pub fn to_defined_bitvec(&self) -> BitVec {
96		let mut bits = Vec::with_capacity(self.len);
97		for row in 0..self.len {
98			bits.push(!self.is_none(row));
99		}
100		BitVec::from(bits)
101	}
102}
103
104const fn words_for(bits: usize) -> usize {
105	bits.div_ceil(64)
106}
107
108fn popcount_masked(words: &[u64], len: usize) -> usize {
109	let word_count = words.len();
110	if word_count == 0 {
111		return 0;
112	}
113	let mut count = 0usize;
114	for &w in &words[..word_count - 1] {
115		count += w.count_ones() as usize;
116	}
117	let trailing = len - 64 * (word_count - 1);
118	let mask = if trailing == 64 {
119		u64::MAX
120	} else {
121		(1u64 << trailing) - 1
122	};
123	count += (words[word_count - 1] & mask).count_ones() as usize;
124	count
125}
126
127#[cfg(test)]
128mod tests {
129	use super::*;
130
131	#[test]
132	fn all_present_has_zero_none_count() {
133		let b = NoneBitmap::all_present(100);
134		assert_eq!(b.none_count(), 0);
135		assert!(!b.is_none(0));
136		assert!(!b.is_none(99));
137	}
138
139	#[test]
140	fn all_none_counts_every_row() {
141		let b = NoneBitmap::all_none(65);
142		assert_eq!(b.none_count(), 65);
143		assert!(b.is_none(0));
144		assert!(b.is_none(64));
145	}
146
147	#[test]
148	fn set_and_clear_round_trip() {
149		let mut b = NoneBitmap::all_present(10);
150		b.set_none(3);
151		b.set_none(7);
152		assert_eq!(b.none_count(), 2);
153		assert!(b.is_none(3));
154		assert!(b.is_none(7));
155		assert!(!b.is_none(5));
156		b.clear_none(3);
157		assert_eq!(b.none_count(), 1);
158		assert!(!b.is_none(3));
159	}
160
161	#[test]
162	fn and_or_combine_bitmaps() {
163		let mut a = NoneBitmap::all_present(8);
164		a.set_none(1);
165		a.set_none(3);
166		let mut b = NoneBitmap::all_present(8);
167		b.set_none(3);
168		b.set_none(5);
169		assert_eq!(a.and(&b).none_count(), 1);
170		assert_eq!(a.or(&b).none_count(), 3);
171	}
172}
reifydb_core/value/column/nones.rs

reifydb_core/value/column/
nones.rs
