Skip to main content

arrow_buffer/buffer/
null.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use crate::bit_iterator::{BitIndexIterator, BitIterator, BitSliceIterator};
6use crate::bit_util;
7use crate::buffer::BooleanBuffer;
8use crate::{Buffer, MutableBuffer, OverflowError};
9
10/// A [`BooleanBuffer`] used to encode validity (null values) for Arrow arrays
11///
12/// In the [Arrow specification], array validity is encoded in a packed bitmask with a
13/// `true` value indicating the corresponding slot is not null, and `false` indicating
14/// that it is null.
15///
16/// # See also
17/// * [`NullBufferBuilder`] for creating `NullBuffer`s
18///
19/// [Arrow specification]: https://arrow.apache.org/docs/format/Columnar.html#validity-bitmaps
20/// [`NullBufferBuilder`]: crate::NullBufferBuilder
21#[derive(Debug, Clone, Eq, PartialEq)]
22pub struct NullBuffer {
23    buffer: BooleanBuffer,
24    null_count: usize,
25}
26
27impl NullBuffer {
28    /// Create a new [`NullBuffer`] computing the null count
29    pub fn new(buffer: BooleanBuffer) -> Self {
30        let null_count = buffer.len() - buffer.count_set_bits();
31        Self { buffer, null_count }
32    }
33
34    /// Create a new [`NullBuffer`] of length `len` where all values are null
35    pub fn new_null(len: usize) -> Self {
36        Self {
37            buffer: BooleanBuffer::new_unset(len),
38            null_count: len,
39        }
40    }
41
42    /// Create a new [`NullBuffer`] of length `len` where all values are valid
43    ///
44    /// Note: it is more efficient to not set the null buffer if it is known to
45    /// be all valid (aka all values are not null)
46    pub fn new_valid(len: usize) -> Self {
47        Self {
48            buffer: BooleanBuffer::new_set(len),
49            null_count: 0,
50        }
51    }
52
53    /// Create a new [`NullBuffer`] with the provided `buffer` and `null_count`
54    ///
55    /// # Safety
56    ///
57    /// `buffer` must contain `null_count` `0` bits
58    pub unsafe fn new_unchecked(buffer: BooleanBuffer, null_count: usize) -> Self {
59        Self { buffer, null_count }
60    }
61
62    /// Computes the union of the nulls in two optional [`NullBuffer`]
63    ///
64    /// This is commonly used by binary operations where the result is NULL if either
65    /// of the input values is NULL. Handling the null mask separately in this way
66    /// can yield significant performance improvements over an iterator approach
67    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    /// Computes the union of the nulls in multiple optional [`NullBuffer`]s
78    ///
79    /// See [`union`](Self::union)
80    pub fn union_many<'a>(
81        nulls: impl IntoIterator<Item = Option<&'a NullBuffer>>,
82    ) -> Option<NullBuffer> {
83        // Unwrap to BooleanBuffer because BitAndAssign is not implemented for NullBuffer
84        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    /// Returns true if all nulls in `other` also exist in self
97    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    /// Returns a new [`NullBuffer`] where each bit in the current null buffer
107    /// is repeated `count` times. This is useful for masking the nulls of
108    /// the child of a FixedSizeListArray based on its parent
109    ///
110    /// # Panics
111    ///
112    /// Panics if `self.len() * count` overflows `usize` or if the required
113    /// buffer cannot be allocated.
114    /// Use [`Self::try_expand`] for a fallible version.
115    pub fn expand(&self, count: usize) -> Self {
116        self.try_expand(count).unwrap_or_else(|err| panic!("{err}"))
117    }
118
119    /// Returns a new [`NullBuffer`] where each bit in the current null buffer
120    /// is repeated `count` times. This is useful for masking the nulls of
121    /// the child of a FixedSizeListArray based on its parent
122    ///
123    /// # Errors
124    ///
125    /// Errors if `self.len() * count` overflows `usize` or if the required
126    /// buffer cannot be allocated.
127    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            // When count is a multiple of 8 every expanded run starts on a byte
138            // boundary (bit i starts at bit i*count, which is divisible by 8),
139            // so we can fill count/8 bytes of 0xFF at a time instead of setting
140            // bits individually.
141            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            // count is a multiple of 4 but not 8: each bit's range starts and ends
154            // on a nibble boundary. Fill any full bytes, then OR in the partial nibble
155            // (0x0F if the range ends mid-byte, 0xF0 if it starts mid-byte).
156            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            // For each contiguous run of valid bits [start, end), the corresponding
173            // output bits [start*count, end*count) are set. Boundary bytes that are
174            // only partially covered are ORed with a mask; fully covered interior
175            // bytes are filled with 0xFF.
176            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; // first bit to set within start_byte
186                let end_byte = end_bit / 8;
187                let end_offset = (end_bit % 8) as u32; // one-past-last bit within end_byte
188
189                if start_byte == end_byte {
190                    // All bits land in one byte: mask from start_offset up to end_offset.
191                    // 0xFF << start_offset  → bits [start_offset, 7] set
192                    // (1 << end_offset) - 1 → bits [0, end_offset) set
193                    // AND of both           → bits [start_offset, end_offset) set
194                    buf[start_byte] |= (0xFFu8 << start_offset) & ((1u8 << end_offset) - 1);
195                } else {
196                    if start_offset != 0 {
197                        // Partial leading byte: set bits from start_offset to bit 7.
198                        buf[start_byte] |= 0xFFu8 << start_offset;
199                    }
200                    // Full interior bytes (skip start_byte if it was only partially covered).
201                    let full_start = start_byte + (start_offset != 0) as usize;
202                    buf[full_start..end_byte].fill(0xFF);
203                    if end_offset != 0 {
204                        // Partial trailing byte: set bits 0 up to end_offset.
205                        // (1 << end_offset) - 1 → bits [0, end_offset) set
206                        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    /// Returns the length of this [`NullBuffer`] in bits
218    #[inline]
219    pub fn len(&self) -> usize {
220        self.buffer.len()
221    }
222
223    /// Returns the offset of this [`NullBuffer`] in bits
224    #[inline]
225    pub fn offset(&self) -> usize {
226        self.buffer.offset()
227    }
228
229    /// Returns true if this [`NullBuffer`] is empty
230    #[inline]
231    pub fn is_empty(&self) -> bool {
232        self.buffer.is_empty()
233    }
234
235    /// Free up unused memory.
236    pub fn shrink_to_fit(&mut self) {
237        self.buffer.shrink_to_fit();
238    }
239
240    /// Returns the null count for this [`NullBuffer`]
241    #[inline]
242    pub fn null_count(&self) -> usize {
243        self.null_count
244    }
245
246    /// Returns `true` if the value at `idx` is not null
247    ///
248    /// # Panics
249    ///
250    /// Panics if `idx >= self.len()`
251    #[inline]
252    pub fn is_valid(&self, idx: usize) -> bool {
253        self.buffer.value(idx)
254    }
255
256    /// Returns `true` if the value at `idx` is null
257    ///
258    /// # Panics
259    ///
260    /// Panics if `idx >= self.len()`
261    #[inline]
262    pub fn is_null(&self, idx: usize) -> bool {
263        !self.is_valid(idx)
264    }
265
266    /// Returns the packed validity of this [`NullBuffer`] not including any offset
267    #[inline]
268    pub fn validity(&self) -> &[u8] {
269        self.buffer.values()
270    }
271
272    /// Slices this [`NullBuffer`] by the provided `offset` and `length`
273    ///
274    /// # Panics
275    ///
276    /// Panics if `offset + len > self.len()`
277    pub fn slice(&self, offset: usize, len: usize) -> Self {
278        Self::new(self.buffer.slice(offset, len))
279    }
280
281    /// Returns an iterator over the bits in this [`NullBuffer`]
282    ///
283    /// * `true` indicates that the corresponding value is not NULL
284    /// * `false` indicates that the corresponding value is NULL
285    ///
286    /// Note: [`Self::valid_indices`] will be significantly faster for most use-cases
287    pub fn iter(&self) -> BitIterator<'_> {
288        self.buffer.iter()
289    }
290
291    /// Returns a [`BitIndexIterator`] over the valid indices in this [`NullBuffer`]
292    ///
293    /// Valid indices indicate the corresponding value is not NULL
294    pub fn valid_indices(&self) -> BitIndexIterator<'_> {
295        self.buffer.set_indices()
296    }
297
298    /// Returns a [`BitSliceIterator`] yielding contiguous ranges of valid indices
299    ///
300    /// Valid indices indicate the corresponding value is not NULL
301    pub fn valid_slices(&self) -> BitSliceIterator<'_> {
302        self.buffer.set_slices()
303    }
304
305    /// Calls the provided closure for each index in this null mask that is set
306    #[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    /// Returns the inner [`BooleanBuffer`]
318    #[inline]
319    pub fn inner(&self) -> &BooleanBuffer {
320        &self.buffer
321    }
322
323    /// Returns the inner [`BooleanBuffer`]
324    #[inline]
325    pub fn into_inner(self) -> BooleanBuffer {
326        self.buffer
327    }
328
329    /// Returns the underlying [`Buffer`]
330    #[inline]
331    pub fn buffer(&self) -> &Buffer {
332        self.buffer.inner()
333    }
334
335    /// Create a [`NullBuffer`] from an *unsliced* validity bitmap (`offset = 0` **bits**) of length `len`.
336    ///
337    /// Returns `None` if there are no nulls (all values valid).
338    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    /// Claim memory used by this null buffer in the provided memory pool.
345    #[cfg(feature = "pool")]
346    pub fn claim(&self, pool: &dyn crate::MemoryPool) {
347        // NullBuffer wraps a BooleanBuffer which wraps a Buffer
348        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        // This tests that the niche optimisation eliminates the overhead of an option
398        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        // 0b10110010 → null(0), valid(1), null(2), null(3), valid(4), valid(5), null(6), valid(7)
407        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        // All bits set = all valid, no nulls
426        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        // No bits set = all null
434        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}