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

reifydb_core/value/column/
nones.rs
