Skip to main content

arrow_buffer/builder/
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::{BooleanBufferBuilder, MutableBuffer, NullBuffer};
6
7/// Builder for creating [`NullBuffer`]s (bitmaps indicating validity/nulls).
8///
9/// # See also
10/// * [`BooleanBufferBuilder`] for a lower-level bitmap builder.
11/// * [`Self::allocated_size`] for the current memory allocated by the builder.
12///
13/// # Performance
14///
15/// This builder only materializes the buffer when null values (`false`) are
16/// appended. If you only append non-null, (`true`) to the builder, no buffer is
17/// allocated and [`build`](#method.build) or [`finish`](#method.finish) return
18/// `None`.
19///
20/// This optimization is **very** important for the performance as it avoids
21/// allocating memory for the null buffer when there are no nulls.
22///
23/// # Example
24/// ```
25/// # use arrow_buffer::NullBufferBuilder;
26/// let mut builder = NullBufferBuilder::new(8);
27/// builder.append_n_non_nulls(8);
28/// // If no non null values are appended, the null buffer is not created
29/// let buffer = builder.finish();
30/// assert!(buffer.is_none());
31/// // however, if a null value is appended, the null buffer is created
32/// let mut builder = NullBufferBuilder::new(8);
33/// builder.append_n_non_nulls(7);
34/// builder.append_null();
35/// let buffer = builder.finish().unwrap();
36/// assert_eq!(buffer.len(), 8);
37/// assert_eq!(buffer.iter().collect::<Vec<_>>(), vec![true, true, true, true, true, true, true, false]);
38/// ```
39#[derive(Debug)]
40pub struct NullBufferBuilder {
41    /// The bitmap builder to store the null buffer:
42    /// * `Some` if any nulls have been appended ("materialized")
43    /// * `None` if no nulls have been appended.
44    bitmap_builder: Option<BooleanBufferBuilder>,
45    /// Length of the buffer before materializing.
46    ///
47    /// if `bitmap_buffer` buffer is `Some`, this value is not used.
48    len: usize,
49    /// Initial capacity of the `bitmap_builder`, when it is materialized.
50    capacity: usize,
51}
52
53impl NullBufferBuilder {
54    /// Creates a new empty builder.
55    ///
56    /// Note that this method does not allocate any memory, regardless of the
57    /// `capacity` parameter. If an allocation is required, `capacity` is the
58    /// size in bits (not bytes) that will be allocated at minimum.
59    pub fn new(capacity: usize) -> Self {
60        Self {
61            bitmap_builder: None,
62            len: 0,
63            capacity,
64        }
65    }
66
67    /// Creates a new builder with given length.
68    pub fn new_with_len(len: usize) -> Self {
69        Self {
70            bitmap_builder: None,
71            len,
72            capacity: len,
73        }
74    }
75
76    /// Creates a new builder from a `MutableBuffer`.
77    ///
78    /// # Panics
79    ///
80    /// Panics if `len > buffer.len() * 8`
81    pub fn new_from_buffer(buffer: MutableBuffer, len: usize) -> Self {
82        let capacity = buffer.len() * 8;
83        assert!(len <= capacity);
84
85        let bitmap_builder = Some(BooleanBufferBuilder::new_from_buffer(buffer, len));
86        Self {
87            bitmap_builder,
88            len,
89            capacity,
90        }
91    }
92
93    /// Appends `n` `true`s into the builder
94    /// to indicate that these `n` items are not nulls.
95    #[inline]
96    pub fn append_n_non_nulls(&mut self, n: usize) {
97        if let Some(buf) = self.bitmap_builder.as_mut() {
98            buf.append_n(n, true)
99        } else {
100            self.len += n;
101        }
102    }
103
104    /// Appends a `true` into the builder
105    /// to indicate that this item is not null.
106    #[inline]
107    pub fn append_non_null(&mut self) {
108        if let Some(buf) = self.bitmap_builder.as_mut() {
109            buf.append(true)
110        } else {
111            self.len += 1;
112        }
113    }
114
115    /// Appends `n` `false`s into the builder
116    /// to indicate that these `n` items are nulls.
117    #[inline]
118    pub fn append_n_nulls(&mut self, n: usize) {
119        if n == 0 {
120            return;
121        }
122        self.materialize_if_needed().append_n(n, false);
123    }
124
125    /// Appends a `false` into the builder
126    /// to indicate that this item is null.
127    #[inline]
128    pub fn append_null(&mut self) {
129        self.materialize_if_needed().append(false);
130    }
131
132    /// Appends a boolean value into the builder.
133    #[inline]
134    pub fn append(&mut self, not_null: bool) {
135        if not_null {
136            self.append_non_null()
137        } else {
138            self.append_null()
139        }
140    }
141
142    /// Appends the low `count` bits from `word` as validity values.
143    ///
144    /// `word` is treated as a packed LSB-first bitmap, where set bits indicate
145    /// non-null values. Only the lowest `count` bits are appended; higher bits
146    /// are ignored.
147    ///
148    /// This does not materialize the null buffer when all appended bits are set.
149    ///
150    /// # Panics
151    ///
152    /// Panics if `count` is greater than 64.
153    #[inline]
154    pub fn append_word(&mut self, word: u64, count: usize) {
155        assert!(count <= 64, "count must be less than or equal to 64");
156        if word.trailing_ones() as usize >= count {
157            self.append_n_non_nulls(count);
158        } else {
159            self.materialize_if_needed().append_word(word, count)
160        }
161    }
162
163    /// Sets a bit in the builder at `index`
164    ///
165    /// # Panics
166    ///
167    /// Panics for the same reasons as [`BooleanBufferBuilder::set_bit`]
168    #[inline]
169    pub fn set_bit(&mut self, index: usize, v: bool) {
170        // Setting a bit to `true` before the bitmap exists changes nothing:
171        // every bit is implicitly `true` until a null is appended.
172        // Out-of-bounds indices still panic, as before.
173        if v && self.bitmap_builder.is_none() && index < self.len {
174            return;
175        }
176        self.materialize_if_needed().set_bit(index, v);
177    }
178
179    /// Gets a bit in the buffer at `index`
180    ///
181    /// # Panics
182    ///
183    /// Panics for the same reasons as [`BooleanBufferBuilder::get_bit`], but only if
184    /// a bitmap has been materialized (i.e. a null was appended)
185    #[inline]
186    pub fn is_valid(&self, index: usize) -> bool {
187        if let Some(ref buf) = self.bitmap_builder {
188            buf.get_bit(index)
189        } else {
190            true
191        }
192    }
193
194    /// Truncates the builder to the given length
195    ///
196    /// If `len` is greater than the buffer's current length, this has no effect
197    #[inline]
198    pub fn truncate(&mut self, len: usize) {
199        if let Some(buf) = self.bitmap_builder.as_mut() {
200            buf.truncate(len);
201        } else if len <= self.len {
202            self.len = len
203        }
204    }
205
206    /// Appends a boolean slice into the builder
207    /// to indicate the validations of these items.
208    pub fn append_slice(&mut self, slice: &[bool]) {
209        // First check if not already materialized before checking if there are any nulls
210        if self.bitmap_builder.is_none() && slice.iter().any(|v| !v) {
211            self.materialize_if_needed();
212        }
213        if let Some(buf) = self.bitmap_builder.as_mut() {
214            buf.append_slice(slice)
215        } else {
216            self.len += slice.len();
217        }
218    }
219
220    /// Append [`NullBuffer`] to this [`NullBufferBuilder`]
221    ///
222    /// This is useful when you want to concatenate two null buffers.
223    pub fn append_buffer(&mut self, buffer: &NullBuffer) {
224        if buffer.null_count() > 0 {
225            self.materialize_if_needed();
226        }
227        if let Some(buf) = self.bitmap_builder.as_mut() {
228            buf.append_buffer(buffer.inner())
229        } else {
230            self.len += buffer.len();
231        }
232    }
233
234    /// Builds the [`NullBuffer`] and resets the builder.
235    ///
236    /// Returns `None` if the builder only contains `true`s. Use [`Self::build`]
237    /// when you don't need to reuse this builder.
238    pub fn finish(&mut self) -> Option<NullBuffer> {
239        self.len = 0;
240        self.bitmap_builder
241            .take()
242            .map(|builder| NullBuffer::new(builder.build()))
243            .filter(|buffer| buffer.null_count() > 0)
244    }
245
246    /// Builds the [`NullBuffer`] without resetting the builder.
247    ///
248    /// This consumes the builder. Use [`Self::finish`] to reuse it.
249    pub fn build(self) -> Option<NullBuffer> {
250        self.bitmap_builder
251            .map(NullBuffer::from)
252            .filter(|buffer| buffer.null_count() > 0)
253    }
254
255    /// Builds the [NullBuffer] without resetting the builder.
256    pub fn finish_cloned(&self) -> Option<NullBuffer> {
257        self.bitmap_builder
258            .as_ref()
259            .map(|builder| NullBuffer::new(builder.finish_cloned()))
260            .filter(|buffer| buffer.null_count() > 0)
261    }
262
263    /// Returns the inner bitmap builder as slice
264    pub fn as_slice(&self) -> Option<&[u8]> {
265        Some(self.bitmap_builder.as_ref()?.as_slice())
266    }
267
268    fn materialize_if_needed(&mut self) -> &mut BooleanBufferBuilder {
269        let (len, capacity) = (self.len, self.capacity);
270        self.bitmap_builder
271            .get_or_insert_with(|| Self::materialize(len, capacity))
272    }
273
274    #[cold]
275    fn materialize(len: usize, capacity: usize) -> BooleanBufferBuilder {
276        let mut b = BooleanBufferBuilder::new(len.max(capacity));
277        b.append_n(len, true);
278        b
279    }
280
281    /// Return a mutable reference to the inner bitmap slice.
282    pub fn as_slice_mut(&mut self) -> Option<&mut [u8]> {
283        self.bitmap_builder.as_mut().map(|b| b.as_slice_mut())
284    }
285
286    /// Return the allocated size of this builder, in bytes, useful for memory accounting.
287    pub fn allocated_size(&self) -> usize {
288        self.bitmap_builder
289            .as_ref()
290            .map(|b| b.capacity() / 8)
291            .unwrap_or(0)
292    }
293
294    /// Return the number of bits in the buffer.
295    pub fn len(&self) -> usize {
296        self.bitmap_builder.as_ref().map_or(self.len, |b| b.len())
297    }
298
299    /// Check if the builder is empty.
300    pub fn is_empty(&self) -> bool {
301        self.len() == 0
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308
309    #[test]
310    fn test_null_buffer_builder() {
311        let mut builder = NullBufferBuilder::new(0);
312        builder.append_null();
313        builder.append_non_null();
314        builder.append_n_nulls(2);
315        builder.append_n_non_nulls(2);
316        assert_eq!(6, builder.len());
317        assert_eq!(64, builder.allocated_size());
318
319        let buf = builder.finish().unwrap();
320        assert_eq!(&[0b110010_u8], buf.validity());
321    }
322
323    #[test]
324    fn test_null_buffer_builder_all_nulls() {
325        let mut builder = NullBufferBuilder::new(0);
326        builder.append_null();
327        builder.append_n_nulls(2);
328        builder.append_slice(&[false, false, false]);
329        assert_eq!(6, builder.len());
330        assert_eq!(64, builder.allocated_size());
331
332        let buf = builder.finish().unwrap();
333        assert_eq!(&[0b0_u8], buf.validity());
334    }
335
336    #[test]
337    fn test_null_buffer_builder_no_null() {
338        let mut builder = NullBufferBuilder::new(0);
339        builder.append_non_null();
340        builder.append_n_non_nulls(2);
341        builder.append_slice(&[true, true, true]);
342        assert_eq!(6, builder.len());
343        assert_eq!(0, builder.allocated_size());
344
345        let buf = builder.finish();
346        assert!(buf.is_none());
347    }
348
349    #[test]
350    fn test_null_buffer_builder_reset() {
351        let mut builder = NullBufferBuilder::new(0);
352        builder.append_slice(&[true, false, true]);
353        builder.finish();
354        assert!(builder.is_empty());
355
356        builder.append_slice(&[true, true, true]);
357        assert!(builder.finish().is_none());
358        assert!(builder.is_empty());
359
360        builder.append_slice(&[true, true, false, true]);
361
362        let buf = builder.finish().unwrap();
363        assert_eq!(&[0b1011_u8], buf.validity());
364    }
365
366    #[test]
367    fn test_append_word_all_valid() {
368        let mut builder = NullBufferBuilder::new(0);
369        builder.append_word(u64::MAX, 64);
370        builder.append_word(0b0111, 3);
371
372        assert_eq!(builder.len(), 67);
373        assert_eq!(builder.allocated_size(), 0);
374        assert!(builder.finish().is_none());
375    }
376
377    #[test]
378    fn test_append_word_mixed() {
379        let mut builder = NullBufferBuilder::new(0);
380        builder.append_n_non_nulls(3);
381        builder.append_word(0b1100_1010, 6);
382        builder.append_word(0b1111, 4);
383
384        let buffer = builder.finish().unwrap();
385        assert_eq!(&[0b0101_0111, 0b0001_1110], buffer.validity());
386    }
387
388    #[test]
389    #[should_panic(expected = "count must be less than or equal to 64")]
390    fn test_append_word_count_too_large() {
391        let mut builder = NullBufferBuilder::new(0);
392        builder.append_word(u64::MAX, 65);
393    }
394
395    #[test]
396    fn test_null_buffer_builder_is_valid() {
397        let mut builder = NullBufferBuilder::new(0);
398        builder.append_n_non_nulls(6);
399        assert!(builder.is_valid(0));
400
401        builder.append_null();
402        assert!(!builder.is_valid(6));
403
404        builder.append_non_null();
405        assert!(builder.is_valid(7));
406    }
407
408    #[test]
409    fn test_null_buffer_builder_truncate() {
410        let mut builder = NullBufferBuilder::new(10);
411        builder.append_n_non_nulls(16);
412        assert_eq!(builder.as_slice(), None);
413        builder.truncate(20);
414        assert_eq!(builder.as_slice(), None);
415        assert_eq!(builder.len(), 16);
416        assert_eq!(builder.allocated_size(), 0);
417        builder.truncate(14);
418        assert_eq!(builder.as_slice(), None);
419        assert_eq!(builder.len(), 14);
420        builder.append_null();
421        builder.append_non_null();
422        assert_eq!(builder.as_slice().unwrap(), &[0xFF, 0b10111111]);
423        assert_eq!(builder.allocated_size(), 64);
424    }
425
426    #[test]
427    fn test_null_buffer_builder_truncate_never_materialized() {
428        let mut builder = NullBufferBuilder::new(0);
429        assert_eq!(builder.len(), 0);
430        builder.append_n_nulls(2); // doesn't materialize
431        assert_eq!(builder.len(), 2);
432        builder.truncate(1);
433        assert_eq!(builder.len(), 1);
434    }
435
436    #[test]
437    fn test_append_buffers() {
438        let mut builder = NullBufferBuilder::new(0);
439        let buffer1 = NullBuffer::from(&[true, true]);
440        let buffer2 = NullBuffer::from(&[true, true, false]);
441
442        builder.append_buffer(&buffer1);
443        builder.append_buffer(&buffer2);
444
445        assert_eq!(builder.as_slice().unwrap(), &[0b01111_u8]);
446    }
447
448    #[test]
449    fn test_append_buffers_with_unaligned_length() {
450        let mut builder = NullBufferBuilder::new(0);
451        let buffer = NullBuffer::from(&[true, true, false, true, false]);
452        builder.append_buffer(&buffer);
453        assert_eq!(builder.as_slice().unwrap(), &[0b01011_u8]);
454
455        let buffer = NullBuffer::from(&[false, false, true, true, true, false, false]);
456        builder.append_buffer(&buffer);
457        assert_eq!(builder.as_slice().unwrap(), &[0b10001011_u8, 0b0011_u8]);
458    }
459
460    #[test]
461    fn test_append_empty_buffer() {
462        let mut builder = NullBufferBuilder::new(0);
463        let buffer = NullBuffer::from(&[true, true, false, true]);
464        builder.append_buffer(&buffer);
465        assert_eq!(builder.as_slice().unwrap(), &[0b1011_u8]);
466
467        let buffer = NullBuffer::from(&[]);
468        builder.append_buffer(&buffer);
469
470        assert_eq!(builder.as_slice().unwrap(), &[0b1011_u8]);
471    }
472
473    #[test]
474    fn test_should_not_materialize_when_appending_all_valid_buffers() {
475        let mut builder = NullBufferBuilder::new(0);
476        let buffer = NullBuffer::from(&[true; 10]);
477        builder.append_buffer(&buffer);
478
479        let buffer = NullBuffer::from(&[true; 2]);
480        builder.append_buffer(&buffer);
481
482        assert_eq!(builder.finish(), None);
483    }
484
485    #[test]
486    fn test_finish_returns_none_when_no_nulls_were_appended() {
487        // append_n_nulls(0) must not materialize the bitmap (#12238)
488        let mut builder = NullBufferBuilder::new(0);
489        builder.append_n_nulls(0);
490        builder.append_non_null();
491        assert_eq!(builder.allocated_size(), 0);
492        assert!(builder.finish_cloned().is_none());
493        assert!(builder.finish().is_none());
494
495        // set_bit(i, true) can clear the only null (#12238)
496        let mut builder = NullBufferBuilder::new(0);
497        builder.append_null();
498        builder.set_bit(0, true);
499        assert!(builder.build().is_none());
500    }
501
502    #[test]
503    fn test_set_bit_true_does_not_materialize() {
504        let mut builder = NullBufferBuilder::new(0);
505        builder.append_n_non_nulls(4);
506        builder.set_bit(2, true);
507        assert_eq!(builder.allocated_size(), 0);
508        assert!(builder.finish().is_none());
509    }
510
511    #[test]
512    #[should_panic(expected = "index out of bounds")]
513    fn test_set_bit_true_out_of_bounds_panics() {
514        let mut builder = NullBufferBuilder::new(0);
515        builder.append_n_non_nulls(2);
516        builder.set_bit(8, true);
517    }
518
519    #[test]
520    fn test_finish_returns_none_after_truncate_removes_nulls() {
521        let mut builder = NullBufferBuilder::new(0);
522        builder.append_non_null();
523        builder.append_null();
524        builder.truncate(1);
525        assert!(builder.finish().is_none());
526    }
527
528    #[test]
529    fn test_finish_returns_none_after_clearing_nulls_via_slice_mut() {
530        let mut builder = NullBufferBuilder::new(0);
531        builder.append_null();
532        builder.append_non_null();
533        builder.as_slice_mut().unwrap()[0] = 0b11;
534        assert!(builder.finish().is_none());
535    }
536
537    #[test]
538    fn test_finish_returns_none_for_all_valid_buffer() {
539        let mut buffer = MutableBuffer::new(1);
540        buffer.push(0xFFu8);
541        let builder = NullBufferBuilder::new_from_buffer(buffer, 8);
542        assert!(builder.finish_cloned().is_none());
543        assert!(builder.build().is_none());
544    }
545}