1use crate::bit_iterator::{BitIndexIterator, BitIterator, BitSliceIterator};
6use crate::bit_util;
7use crate::buffer::BooleanBuffer;
8use crate::{Buffer, MutableBuffer, OverflowError};
9
10#[derive(Debug, Clone, Eq, PartialEq)]
22pub struct NullBuffer {
23 buffer: BooleanBuffer,
24 null_count: usize,
25}
26
27impl NullBuffer {
28 pub fn new(buffer: BooleanBuffer) -> Self {
30 let null_count = buffer.len() - buffer.count_set_bits();
31 Self { buffer, null_count }
32 }
33
34 pub fn new_null(len: usize) -> Self {
36 Self {
37 buffer: BooleanBuffer::new_unset(len),
38 null_count: len,
39 }
40 }
41
42 pub fn new_valid(len: usize) -> Self {
47 Self {
48 buffer: BooleanBuffer::new_set(len),
49 null_count: 0,
50 }
51 }
52
53 pub unsafe fn new_unchecked(buffer: BooleanBuffer, null_count: usize) -> Self {
59 Self { buffer, null_count }
60 }
61
62 pub fn union(lhs: Option<&NullBuffer>, rhs: Option<&NullBuffer>) -> Option<NullBuffer> {
68 match (lhs, rhs) {
69 (Some(lhs), Some(rhs)) if lhs.null_count() > 0 || rhs.null_count() > 0 => {
70 Some(Self::new(lhs.inner() & rhs.inner()))
71 }
72 (Some(n), None) | (None, Some(n)) if n.null_count() > 0 => Some(n.clone()),
73 (_, _) => None,
74 }
75 }
76
77 pub fn union_many<'a>(
81 nulls: impl IntoIterator<Item = Option<&'a NullBuffer>>,
82 ) -> Option<NullBuffer> {
83 let mut buffers = nulls.into_iter().filter_map(|nb| match nb {
85 Some(nb) if nb.null_count > 0 => Some(nb.inner()),
86 _ => None,
87 });
88 let first = buffers.next()?;
89 let mut result = first.clone();
90 for buf in buffers {
91 result &= buf;
92 }
93 Some(Self::new(result))
94 }
95
96 pub fn contains(&self, other: &NullBuffer) -> bool {
98 if other.null_count == 0 {
99 return true;
100 }
101 let lhs = self.inner().bit_chunks().iter_padded();
102 let rhs = other.inner().bit_chunks().iter_padded();
103 lhs.zip(rhs).all(|(l, r)| (l & !r) == 0)
104 }
105
106 pub fn expand(&self, count: usize) -> Self {
116 self.try_expand(count).unwrap_or_else(|err| panic!("{err}"))
117 }
118
119 pub fn try_expand(&self, count: usize) -> Result<Self, OverflowError> {
128 let capacity = self
129 .buffer
130 .len()
131 .checked_mul(count)
132 .ok_or_else(|| OverflowError::new::<usize>("buffer length"))?;
133 let mut buffer = MutableBuffer::try_from_len_zeroed(bit_util::ceil(capacity, 8))
134 .map_err(|_| OverflowError::new::<usize>("buffer length"))?;
135
136 if count.is_multiple_of(8) {
137 let bytes_per_bit = count / 8;
142 let buf = buffer.as_mut();
143 for (start, end) in BitSliceIterator::new(
144 self.buffer.values(),
145 self.buffer.offset(),
146 self.buffer.len(),
147 ) {
148 let byte_start = start * bytes_per_bit;
149 let byte_end = end * bytes_per_bit;
150 buf[byte_start..byte_end].fill(0xFF);
151 }
152 } else if count.is_multiple_of(4) {
153 let buf = buffer.as_mut();
157 for i in 0..self.buffer.len() {
158 if self.is_null(i) {
159 continue;
160 }
161 let start_bit = i * count;
162 let end_bit = start_bit + count;
163 if start_bit.is_multiple_of(8) {
164 buf[start_bit / 8..end_bit / 8].fill(0xFF);
165 buf[end_bit / 8] |= 0x0F;
166 } else {
167 buf[start_bit / 8] |= 0xF0;
168 buf[start_bit / 8 + 1..end_bit / 8].fill(0xFF);
169 }
170 }
171 } else {
172 let buf = buffer.as_mut();
177 for (start, end) in BitSliceIterator::new(
178 self.buffer.values(),
179 self.buffer.offset(),
180 self.buffer.len(),
181 ) {
182 let start_bit = start * count;
183 let end_bit = end * count;
184 let start_byte = start_bit / 8;
185 let start_offset = (start_bit % 8) as u32; let end_byte = end_bit / 8;
187 let end_offset = (end_bit % 8) as u32; if start_byte == end_byte {
190 buf[start_byte] |= (0xFFu8 << start_offset) & ((1u8 << end_offset) - 1);
195 } else {
196 if start_offset != 0 {
197 buf[start_byte] |= 0xFFu8 << start_offset;
199 }
200 let full_start = start_byte + (start_offset != 0) as usize;
202 buf[full_start..end_byte].fill(0xFF);
203 if end_offset != 0 {
204 buf[end_byte] |= (1u8 << end_offset) - 1;
207 }
208 }
209 }
210 }
211 Ok(Self {
212 buffer: BooleanBuffer::new(buffer.into(), 0, capacity),
213 null_count: self.null_count * count,
214 })
215 }
216
217 #[inline]
219 pub fn len(&self) -> usize {
220 self.buffer.len()
221 }
222
223 #[inline]
225 pub fn offset(&self) -> usize {
226 self.buffer.offset()
227 }
228
229 #[inline]
231 pub fn is_empty(&self) -> bool {
232 self.buffer.is_empty()
233 }
234
235 pub fn shrink_to_fit(&mut self) {
237 self.buffer.shrink_to_fit();
238 }
239
240 #[inline]
242 pub fn null_count(&self) -> usize {
243 self.null_count
244 }
245
246 #[inline]
252 pub fn is_valid(&self, idx: usize) -> bool {
253 self.buffer.value(idx)
254 }
255
256 #[inline]
262 pub fn is_null(&self, idx: usize) -> bool {
263 !self.is_valid(idx)
264 }
265
266 #[inline]
268 pub fn validity(&self) -> &[u8] {
269 self.buffer.values()
270 }
271
272 pub fn slice(&self, offset: usize, len: usize) -> Self {
278 Self::new(self.buffer.slice(offset, len))
279 }
280
281 pub fn iter(&self) -> BitIterator<'_> {
288 self.buffer.iter()
289 }
290
291 pub fn valid_indices(&self) -> BitIndexIterator<'_> {
295 self.buffer.set_indices()
296 }
297
298 pub fn valid_slices(&self) -> BitSliceIterator<'_> {
302 self.buffer.set_slices()
303 }
304
305 #[inline]
307 pub fn try_for_each_valid_idx<E, F: FnMut(usize) -> Result<(), E>>(
308 &self,
309 f: F,
310 ) -> Result<(), E> {
311 if self.null_count == self.len() {
312 return Ok(());
313 }
314 self.valid_indices().try_for_each(f)
315 }
316
317 #[inline]
319 pub fn inner(&self) -> &BooleanBuffer {
320 &self.buffer
321 }
322
323 #[inline]
325 pub fn into_inner(self) -> BooleanBuffer {
326 self.buffer
327 }
328
329 #[inline]
331 pub fn buffer(&self) -> &Buffer {
332 self.buffer.inner()
333 }
334
335 pub fn from_unsliced_buffer(buffer: impl Into<Buffer>, len: usize) -> Option<Self> {
339 let bb = BooleanBuffer::new(buffer.into(), 0, len);
340 let nb = NullBuffer::new(bb);
341 (nb.null_count() > 0).then_some(nb)
342 }
343
344 #[cfg(feature = "pool")]
346 pub fn claim(&self, pool: &dyn crate::MemoryPool) {
347 self.buffer.inner().claim(pool);
349 }
350}
351
352impl<'a> IntoIterator for &'a NullBuffer {
353 type Item = bool;
354 type IntoIter = BitIterator<'a>;
355
356 fn into_iter(self) -> Self::IntoIter {
357 self.buffer.iter()
358 }
359}
360
361impl From<BooleanBuffer> for NullBuffer {
362 fn from(value: BooleanBuffer) -> Self {
363 Self::new(value)
364 }
365}
366
367impl From<&[bool]> for NullBuffer {
368 fn from(value: &[bool]) -> Self {
369 BooleanBuffer::from(value).into()
370 }
371}
372
373impl<const N: usize> From<&[bool; N]> for NullBuffer {
374 fn from(value: &[bool; N]) -> Self {
375 value[..].into()
376 }
377}
378
379impl From<Vec<bool>> for NullBuffer {
380 fn from(value: Vec<bool>) -> Self {
381 BooleanBuffer::from(value).into()
382 }
383}
384
385impl FromIterator<bool> for NullBuffer {
386 fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
387 BooleanBuffer::from_iter(iter).into()
388 }
389}
390
391#[cfg(test)]
392mod tests {
393 use super::*;
394
395 #[test]
396 fn test_size() {
397 assert_eq!(
399 std::mem::size_of::<NullBuffer>(),
400 std::mem::size_of::<Option<NullBuffer>>()
401 );
402 }
403
404 #[test]
405 fn test_from_unsliced_buffer_with_nulls() {
406 let buf = Buffer::from([0b10110010u8]);
408 let result = NullBuffer::from_unsliced_buffer(buf, 8);
409 assert!(result.is_some());
410 let nb = result.unwrap();
411 assert_eq!(nb.len(), 8);
412 assert_eq!(nb.null_count(), 4);
413 assert!(nb.is_null(0));
414 assert!(nb.is_valid(1));
415 assert!(nb.is_null(2));
416 assert!(nb.is_null(3));
417 assert!(nb.is_valid(4));
418 assert!(nb.is_valid(5));
419 assert!(nb.is_null(6));
420 assert!(nb.is_valid(7));
421 }
422
423 #[test]
424 fn test_from_unsliced_buffer_all_valid() {
425 let buf = Buffer::from([0b11111111u8]);
427 let result = NullBuffer::from_unsliced_buffer(buf, 8);
428 assert!(result.is_none());
429 }
430
431 #[test]
432 fn test_from_unsliced_buffer_all_null() {
433 let buf = Buffer::from([0b00000000u8]);
435 let result = NullBuffer::from_unsliced_buffer(buf, 8);
436 assert!(result.is_some());
437 let nb = result.unwrap();
438 assert_eq!(nb.len(), 8);
439 assert_eq!(nb.null_count(), 8);
440 }
441
442 #[test]
443 fn test_from_unsliced_buffer_empty() {
444 let buf = Buffer::from([]);
445 let result = NullBuffer::from_unsliced_buffer(buf, 0);
446 assert!(result.is_none());
447 }
448
449 #[test]
450 fn test_union_many_all_none() {
451 let result = NullBuffer::union_many([None, None, None]);
452 assert!(result.is_none());
453 }
454
455 #[test]
456 fn test_union_many_single_some() {
457 let a = NullBuffer::from(&[true, false, true, true]);
458 let result = NullBuffer::union_many([Some(&a)]);
459 assert_eq!(result, Some(a));
460 }
461
462 #[test]
463 fn test_union_many_two_inputs() {
464 let a = NullBuffer::from(&[true, false, true, true]);
465 let b = NullBuffer::from(&[true, true, false, true]);
466 let result = NullBuffer::union_many([Some(&a), Some(&b)]);
467 let expected = NullBuffer::union(Some(&a), Some(&b));
468 assert_eq!(result, expected);
469 }
470
471 #[test]
472 fn test_union_many_three_inputs() {
473 let a = NullBuffer::from(&[true, false, true, true]);
474 let b = NullBuffer::from(&[true, true, false, true]);
475 let c = NullBuffer::from(&[false, true, true, true]);
476 let result = NullBuffer::union_many([Some(&a), Some(&b), Some(&c)]);
477 let expected = NullBuffer::from(&[false, false, false, true]);
478 assert_eq!(result, Some(expected));
479 }
480
481 #[test]
482 fn test_union_many_mixed_none() {
483 let a = NullBuffer::from(&[true, false, true, true]);
484 let b = NullBuffer::from(&[false, true, true, true]);
485 let result = NullBuffer::union_many([Some(&a), None, Some(&b)]);
486 let expected = NullBuffer::union(Some(&a), Some(&b));
487 assert_eq!(result, expected);
488 }
489
490 #[test]
491 fn test_union_many_empty_slice() {
492 let result = NullBuffer::union_many([] as [Option<&NullBuffer>; 0]);
493 assert!(result.is_none());
494 }
495
496 #[test]
497 fn test_union_many_no_nulls() {
498 let a = NullBuffer::from(&[true, true, true, true]);
499
500 let result = NullBuffer::union_many([Some(&a), Some(&a), Some(&a)]);
501 assert_eq!(result, None);
502 }
503
504 #[test]
505 fn test_union_no_nulls() {
506 let a = NullBuffer::from(&[true, true, true, true]);
507
508 let result = NullBuffer::union(Some(&a), Some(&a));
509 assert_eq!(result, None);
510
511 let result = NullBuffer::union(Some(&a), None);
512 assert_eq!(result, None);
513
514 let result = NullBuffer::union(None, Some(&a));
515 assert_eq!(result, None);
516 }
517
518 #[test]
519 fn test_union_nulls_one_side() {
520 let all_valid = NullBuffer::from(&[true, true, true, true]);
521 let all_null = NullBuffer::from(&[false, false, false, false]);
522
523 let result = NullBuffer::union(Some(&all_valid), Some(&all_null));
524 assert_eq!(result, Some(all_null.clone()));
525
526 let result = NullBuffer::union(Some(&all_null), Some(&all_valid));
527 assert_eq!(result, Some(all_null.clone()));
528 }
529
530 #[test]
531 fn test_expand_code_paths() {
532 let source = NullBuffer::from(&[true, false, true] as &[bool]);
533
534 for count in [8, 4, 3] {
535 let expanded = source.expand(count);
536 assert_eq!(expanded.len(), 3 * count);
537 assert_eq!(expanded.null_count(), count);
538 assert!((0..count).all(|i| expanded.is_valid(i)));
539 assert!((count..2 * count).all(|i| expanded.is_null(i)));
540 assert!((2 * count..3 * count).all(|i| expanded.is_valid(i)));
541 }
542 }
543}