Skip to main content

astrs_data/buffer/
bitmap.rs

1//! [`Bitmap`] — the validity bitmap, and the free bit helpers it is built on.
2//!
3//! # Bit numbering
4//!
5//! AstRS follows the Arrow specification exactly: bits are numbered
6//! **least-significant-bit first** inside each byte, and bytes run in
7//! increasing address order. Logical bit `i` therefore lives at
8//! `data[i / 8] >> (i % 8) & 1`:
9//!
10//! ```text
11//!   logical index:  7  6  5  4  3  2  1  0    15 14 13 12 11 10  9  8
12//!                 ┌──┬──┬──┬──┬──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┬──┬──┬──┐
13//!   byte 0/1      │b7│b6│b5│b4│b3│b2│b1│b0│ │  │  │  │  │  │  │  │b8│
14//!                 └──┴──┴──┴──┴──┴──┴──┴──┘ └──┴──┴──┴──┴──┴──┴──┴──┘
15//! ```
16//!
17//! In a *validity* bitmap `1` means **valid** and `0` means **null** — so a
18//! bitmap's null count is `len - count_set()`. Bits past the logical length
19//! are unspecified; every operation here masks them off rather than trusting
20//! them, so a bitmap decoded from a foreign producer is safe to combine with
21//! one this crate built.
22//!
23//! # Offsets
24//!
25//! A [`Bitmap`] carries a *bit* offset independent of its buffer's byte
26//! offset, which is what makes slicing free: slicing a validity map by one
27//! element does not move a single byte. Every accessor, comparison and binary
28//! operation therefore has to work at arbitrary bit offsets — the helper
29//! A private `byte_at` helper extracts eight logical bits starting anywhere
30//! and is
31//! the shared core of equality, the binary ops and canonicalisation.
32//!
33//! ```
34//! use astrs_data::Bitmap;
35//!
36//! let bits: Bitmap = [true, false, true, true, false].into_iter().collect();
37//! assert_eq!(bits.len(), 5);
38//! assert_eq!(bits.count_set(), 3);
39//!
40//! let tail = bits.slice(2, 3);
41//! assert_eq!(tail.iter().collect::<Vec<_>>(), vec![true, true, false]);
42//! ```
43
44use std::fmt;
45use std::sync::atomic::{AtomicI64, Ordering};
46
47use crate::buffer::Buffer;
48use crate::buffer::aligned::AlignedBuf;
49use crate::error::{DataError, Result};
50
51/// Sentinel meaning "the set-bit count has not been computed yet".
52const UNKNOWN_COUNT: i64 = -1;
53
54/// Reads logical bit `index` from `data`, LSB-numbered.
55///
56/// Returns `false` when `index` is out of range, so the helper is total.
57///
58/// ```
59/// use astrs_data::buffer::get_bit;
60///
61/// let data = [0b0000_0101u8];
62/// assert!(get_bit(&data, 0));
63/// assert!(!get_bit(&data, 1));
64/// assert!(get_bit(&data, 2));
65/// assert!(!get_bit(&data, 99));
66/// ```
67#[inline]
68#[must_use]
69pub fn get_bit(data: &[u8], index: usize) -> bool {
70    match data.get(index / 8) {
71        Some(byte) => (byte >> (index % 8)) & 1 == 1,
72        None => false,
73    }
74}
75
76/// Writes logical bit `index` in `data`, LSB-numbered. Out-of-range writes are
77/// ignored.
78///
79/// ```
80/// use astrs_data::buffer::{get_bit, set_bit};
81///
82/// let mut data = [0u8; 2];
83/// set_bit(&mut data, 9, true);
84/// assert_eq!(data, [0, 0b0000_0010]);
85/// assert!(get_bit(&data, 9));
86/// set_bit(&mut data, 9, false);
87/// assert_eq!(data, [0, 0]);
88/// ```
89#[inline]
90pub fn set_bit(data: &mut [u8], index: usize, value: bool) {
91    if let Some(byte) = data.get_mut(index / 8) {
92        let mask = 1u8 << (index % 8);
93        if value {
94            *byte |= mask;
95        } else {
96            *byte &= !mask;
97        }
98    }
99}
100
101/// Counts the set bits in the logical range `[offset, offset + len)`.
102///
103/// Bits outside the slice are treated as unset, so the helper is total. The
104/// interior runs eight bytes at a time through `u64::count_ones`.
105///
106/// ```
107/// use astrs_data::buffer::count_set_bits;
108///
109/// let data = [0xffu8, 0x0f];
110/// assert_eq!(count_set_bits(&data, 0, 16), 12);
111/// assert_eq!(count_set_bits(&data, 4, 8), 8);
112/// assert_eq!(count_set_bits(&data, 12, 4), 0);
113/// ```
114#[must_use]
115pub fn count_set_bits(data: &[u8], offset: usize, len: usize) -> usize {
116    let available = data.len().saturating_mul(8);
117    if len == 0 || offset >= available {
118        return 0;
119    }
120    let len = len.min(available - offset);
121    let end = offset + len;
122
123    let first_byte = offset / 8;
124    let last_byte = end.div_ceil(8);
125    let Some(bytes) = data.get(first_byte..last_byte) else {
126        return 0;
127    };
128    let Some((&head, rest)) = bytes.split_first() else {
129        return 0;
130    };
131
132    let lead = offset % 8;
133    let trail = (8 - end % 8) % 8;
134    let head_mask = 0xffu8 << lead;
135
136    let Some((&tail, middle)) = rest.split_last() else {
137        // The whole range lives in one byte.
138        return usize::try_from((head & head_mask & (0xffu8 >> trail)).count_ones()).unwrap_or(0);
139    };
140
141    let mut count = (head & head_mask).count_ones();
142    // `as_chunks::<8>` hands back `&[u8; 8]` directly, so the word is loaded
143    // without the intermediate array a `chunks_exact(8)` slice would need.
144    let (words, remainder) = middle.as_chunks::<8>();
145    for word in words {
146        count += u64::from_le_bytes(*word).count_ones();
147    }
148    for byte in remainder {
149        count += byte.count_ones();
150    }
151    count += (tail & (0xffu8 >> trail)).count_ones();
152    usize::try_from(count).unwrap_or(0)
153}
154
155/// An immutable, LSB-numbered bit sequence over a shared [`Buffer`].
156///
157/// Used as the validity map of every nullable array and as the value buffer of
158/// [`crate::array::BooleanArray`].
159///
160/// The set-bit count is computed lazily and cached in an atomic, so
161/// `count_set` is `O(len / 64)` once and `O(1)` afterwards, while the type
162/// stays `Send + Sync` with no locks.
163pub struct Bitmap {
164    /// Backing bytes. `buffer.len() * 8 >= offset + len` always.
165    buffer: Buffer,
166    /// Logical bit offset of the first bit inside `buffer`.
167    offset: usize,
168    /// Number of logical bits.
169    len: usize,
170    /// Cached `count_set`, or [`UNKNOWN_COUNT`] when not yet computed.
171    set_count: AtomicI64,
172}
173
174impl Bitmap {
175    /// Wraps a byte window as a bitmap.
176    ///
177    /// # Errors
178    ///
179    /// [`DataError::BufferTooSmall`] when the buffer cannot cover
180    /// `offset + len` bits.
181    ///
182    /// ```
183    /// use astrs_data::{Bitmap, Buffer};
184    ///
185    /// let bits = Bitmap::try_new(Buffer::from_slice(&[0b1010_1010]), 1, 7)?;
186    /// assert_eq!(bits.len(), 7);
187    /// assert!(bits.value(0));
188    /// assert!(Bitmap::try_new(Buffer::from_slice(&[0]), 0, 9).is_err());
189    /// # Ok::<(), astrs_data::DataError>(())
190    /// ```
191    pub fn try_new(buffer: Buffer, offset: usize, len: usize) -> Result<Self> {
192        let required = offset.saturating_add(len).div_ceil(8);
193        if required > buffer.len() {
194            return Err(DataError::BufferTooSmall {
195                required,
196                actual: buffer.len(),
197            });
198        }
199        Ok(Self {
200            buffer,
201            offset,
202            len,
203            set_count: AtomicI64::new(UNKNOWN_COUNT),
204        })
205    }
206
207    /// Wraps a byte window, using every bit it holds.
208    ///
209    /// ```
210    /// use astrs_data::{Bitmap, Buffer};
211    ///
212    /// assert_eq!(Bitmap::from_buffer(Buffer::from_slice(&[0, 0])).len(), 16);
213    /// ```
214    #[must_use]
215    pub fn from_buffer(buffer: Buffer) -> Self {
216        let len = buffer.len() * 8;
217        Self {
218            buffer,
219            offset: 0,
220            len,
221            set_count: AtomicI64::new(UNKNOWN_COUNT),
222        }
223    }
224
225    /// An all-valid bitmap of `len` bits.
226    #[must_use]
227    pub fn new_set(len: usize) -> Self {
228        let mut buf = AlignedBuf::with_capacity(len.div_ceil(8));
229        buf.resize(len.div_ceil(8), 0xff);
230        Self {
231            buffer: Buffer::from(buf),
232            offset: 0,
233            len,
234            set_count: AtomicI64::new(i64::try_from(len).unwrap_or(UNKNOWN_COUNT)),
235        }
236    }
237
238    /// An all-null bitmap of `len` bits.
239    #[must_use]
240    pub fn new_unset(len: usize) -> Self {
241        Self {
242            buffer: Buffer::zeroed(len.div_ceil(8)),
243            offset: 0,
244            len,
245            set_count: AtomicI64::new(0),
246        }
247    }
248
249    /// Number of logical bits.
250    #[inline]
251    #[must_use]
252    pub const fn len(&self) -> usize {
253        self.len
254    }
255
256    /// Returns `true` when the bitmap covers no bits.
257    #[inline]
258    #[must_use]
259    pub const fn is_empty(&self) -> bool {
260        self.len == 0
261    }
262
263    /// Logical bit offset of the first bit inside the backing buffer.
264    #[inline]
265    #[must_use]
266    pub const fn bit_offset(&self) -> usize {
267        self.offset
268    }
269
270    /// The backing byte window.
271    #[inline]
272    #[must_use]
273    pub const fn buffer(&self) -> &Buffer {
274        &self.buffer
275    }
276
277    /// Reads bit `index`, returning `None` when out of range.
278    #[inline]
279    #[must_use]
280    pub fn get(&self, index: usize) -> Option<bool> {
281        if index >= self.len {
282            return None;
283        }
284        Some(get_bit(self.buffer.as_slice(), self.offset + index))
285    }
286
287    /// Reads bit `index`, treating out-of-range indices as `false`.
288    ///
289    /// This is the hot accessor used by every array's `is_valid`.
290    #[inline]
291    #[must_use]
292    pub fn value(&self, index: usize) -> bool {
293        index < self.len && get_bit(self.buffer.as_slice(), self.offset + index)
294    }
295
296    /// Number of set (valid) bits. Computed once, then cached.
297    ///
298    /// ```
299    /// use astrs_data::Bitmap;
300    ///
301    /// let bits: Bitmap = [true, false, true].into_iter().collect();
302    /// assert_eq!(bits.count_set(), 2);
303    /// assert_eq!(bits.count_unset(), 1);
304    /// ```
305    #[must_use]
306    pub fn count_set(&self) -> usize {
307        let cached = self.set_count.load(Ordering::Relaxed);
308        if cached >= 0 {
309            return usize::try_from(cached).unwrap_or(self.len);
310        }
311        let counted = count_set_bits(self.buffer.as_slice(), self.offset, self.len);
312        // Racing threads compute the same value, so a plain relaxed store is
313        // enough — there is no ordering relationship to establish.
314        self.set_count.store(
315            i64::try_from(counted).unwrap_or(UNKNOWN_COUNT),
316            Ordering::Relaxed,
317        );
318        counted
319    }
320
321    /// Number of unset (null) bits.
322    #[inline]
323    #[must_use]
324    pub fn count_unset(&self) -> usize {
325        self.len - self.count_set()
326    }
327
328    /// Returns `true` when every bit is set.
329    #[inline]
330    #[must_use]
331    pub fn all_set(&self) -> bool {
332        self.count_set() == self.len
333    }
334
335    /// Returns `true` when no bit is set.
336    #[inline]
337    #[must_use]
338    pub fn none_set(&self) -> bool {
339        self.count_set() == 0
340    }
341
342    /// A zero-copy sub-range, clamped to the available range (the crate-wide
343    /// slicing convention).
344    ///
345    /// ```
346    /// use astrs_data::Bitmap;
347    ///
348    /// let bits: Bitmap = (0..20).map(|i| i % 3 == 0).collect();
349    /// let window = bits.slice(5, 5);
350    /// assert_eq!(window.iter().collect::<Vec<_>>(), vec![false, true, false, false, true]);
351    /// assert_eq!(bits.slice(18, 99).len(), 2, "slices clamp");
352    /// ```
353    #[must_use]
354    pub fn slice(&self, offset: usize, len: usize) -> Self {
355        let offset = offset.min(self.len);
356        let len = len.min(self.len - offset);
357        let full = offset == 0 && len == self.len;
358        Self {
359            buffer: self.buffer.clone(),
360            offset: self.offset + offset,
361            len,
362            set_count: AtomicI64::new(if full {
363                self.set_count.load(Ordering::Relaxed)
364            } else {
365                UNKNOWN_COUNT
366            }),
367        }
368    }
369
370    /// Checked [`Bitmap::slice`].
371    pub fn try_slice(&self, offset: usize, len: usize) -> Result<Self> {
372        if offset.saturating_add(len) > self.len {
373            return Err(DataError::SliceOutOfBounds {
374                offset,
375                len,
376                available: self.len,
377            });
378        }
379        Ok(self.slice(offset, len))
380    }
381
382    /// Iterates over the bits, low index first.
383    #[inline]
384    #[must_use]
385    pub fn iter(&self) -> BitmapIter<'_> {
386        BitmapIter {
387            bitmap: self,
388            front: 0,
389            back: self.len,
390        }
391    }
392
393    /// Iterates over the indices of the set bits.
394    ///
395    /// ```
396    /// use astrs_data::Bitmap;
397    ///
398    /// let bits: Bitmap = [false, true, false, true].into_iter().collect();
399    /// assert_eq!(bits.set_indices().collect::<Vec<_>>(), vec![1, 3]);
400    /// ```
401    pub fn set_indices(&self) -> impl Iterator<Item = usize> + '_ {
402        self.iter()
403            .enumerate()
404            .filter_map(|(i, bit)| bit.then_some(i))
405    }
406
407    /// Iterates over the indices of the unset (null) bits.
408    pub fn unset_indices(&self) -> impl Iterator<Item = usize> + '_ {
409        self.iter()
410            .enumerate()
411            .filter_map(|(i, bit)| (!bit).then_some(i))
412    }
413
414    /// Eight logical bits starting at logical index `start`, packed LSB-first.
415    ///
416    /// Bits past the logical end read as `0`. This is the primitive every
417    /// offset-agnostic operation is built on: it turns "two bitmaps at
418    /// different bit offsets" into "two byte streams".
419    #[inline]
420    #[must_use]
421    fn byte_at(&self, start: usize) -> u8 {
422        if start >= self.len {
423            return 0;
424        }
425        let data = self.buffer.as_slice();
426        let bit = self.offset + start;
427        let index = bit / 8;
428        let shift = bit % 8;
429        let mut byte = data.get(index).copied().unwrap_or(0) >> shift;
430        if shift != 0 {
431            let next = data.get(index + 1).copied().unwrap_or(0);
432            byte |= next << (8 - shift);
433        }
434        let remaining = self.len - start;
435        if remaining < 8 {
436            byte &= 0xffu8 >> (8 - remaining);
437        }
438        byte
439    }
440
441    /// Copies the bits into a fresh, zero-offset, tightly packed bitmap.
442    ///
443    /// Stage 2 needs this before writing a validity buffer into an IPC body:
444    /// the wire format has no bit-offset field.
445    ///
446    /// ```
447    /// use astrs_data::Bitmap;
448    ///
449    /// let bits: Bitmap = (0..20).map(|i| i % 2 == 0).collect();
450    /// let window = bits.slice(3, 9);
451    /// let packed = window.to_canonical();
452    /// assert_eq!(packed.bit_offset(), 0);
453    /// assert_eq!(packed.iter().collect::<Vec<_>>(), window.iter().collect::<Vec<_>>());
454    /// ```
455    #[must_use]
456    pub fn to_canonical(&self) -> Self {
457        if self.offset == 0 && self.buffer.len() == self.len.div_ceil(8) {
458            return self.clone();
459        }
460        let byte_len = self.len.div_ceil(8);
461        let mut buf = AlignedBuf::with_capacity(byte_len);
462        for index in 0..byte_len {
463            buf.push(self.byte_at(index * 8));
464        }
465        Self {
466            buffer: Buffer::from(buf),
467            offset: 0,
468            len: self.len,
469            set_count: AtomicI64::new(self.set_count.load(Ordering::Relaxed)),
470        }
471    }
472
473    /// Bitwise AND of two equal-length bitmaps.
474    ///
475    /// This is how a parent's validity is pushed into a child's: a value is
476    /// valid only when both maps say so. Operand bit offsets may differ.
477    ///
478    /// # Errors
479    ///
480    /// [`DataError::BitmapLengthMismatch`] when the lengths differ.
481    ///
482    /// ```
483    /// use astrs_data::Bitmap;
484    ///
485    /// let a: Bitmap = [true, true, false, false].into_iter().collect();
486    /// let b: Bitmap = [true, false, true, false].into_iter().collect();
487    /// assert_eq!(a.and(&b)?.iter().collect::<Vec<_>>(), vec![true, false, false, false]);
488    /// # Ok::<(), astrs_data::DataError>(())
489    /// ```
490    pub fn and(&self, other: &Self) -> Result<Self> {
491        self.binary_op(other, |a, b| a & b)
492    }
493
494    /// Bitwise OR of two equal-length bitmaps.
495    ///
496    /// # Errors
497    ///
498    /// [`DataError::BitmapLengthMismatch`] when the lengths differ.
499    pub fn or(&self, other: &Self) -> Result<Self> {
500        self.binary_op(other, |a, b| a | b)
501    }
502
503    /// Bitwise XOR of two equal-length bitmaps.
504    ///
505    /// # Errors
506    ///
507    /// [`DataError::BitmapLengthMismatch`] when the lengths differ.
508    pub fn xor(&self, other: &Self) -> Result<Self> {
509        self.binary_op(other, |a, b| a ^ b)
510    }
511
512    /// Bitwise NOT.
513    ///
514    /// ```
515    /// use astrs_data::Bitmap;
516    ///
517    /// let bits: Bitmap = [true, false, true].into_iter().collect();
518    /// assert_eq!(bits.not().iter().collect::<Vec<_>>(), vec![false, true, false]);
519    /// ```
520    #[must_use]
521    pub fn not(&self) -> Self {
522        self.map_bytes(|byte| !byte)
523    }
524
525    /// Applies `op` byte-wise over the canonicalised bits, masking the tail.
526    fn map_bytes(&self, op: impl Fn(u8) -> u8) -> Self {
527        let byte_len = self.len.div_ceil(8);
528        let mut buf = AlignedBuf::with_capacity(byte_len);
529        for index in 0..byte_len {
530            buf.push(op(self.byte_at(index * 8)));
531        }
532        mask_tail(&mut buf, self.len);
533        Self {
534            buffer: Buffer::from(buf),
535            offset: 0,
536            len: self.len,
537            set_count: AtomicI64::new(UNKNOWN_COUNT),
538        }
539    }
540
541    /// Shared implementation of [`Bitmap::and`], [`Bitmap::or`] and
542    /// [`Bitmap::xor`], correct for arbitrary and differing bit offsets.
543    fn binary_op(&self, other: &Self, op: impl Fn(u8, u8) -> u8) -> Result<Self> {
544        if self.len != other.len {
545            return Err(DataError::BitmapLengthMismatch {
546                left: self.len,
547                right: other.len,
548            });
549        }
550        let byte_len = self.len.div_ceil(8);
551        let mut buf = AlignedBuf::with_capacity(byte_len);
552        for index in 0..byte_len {
553            let start = index * 8;
554            buf.push(op(self.byte_at(start), other.byte_at(start)));
555        }
556        mask_tail(&mut buf, self.len);
557        Ok(Self {
558            buffer: Buffer::from(buf),
559            offset: 0,
560            len: self.len,
561            set_count: AtomicI64::new(UNKNOWN_COUNT),
562        })
563    }
564
565    /// Combines two optional validity maps the way nested arrays need.
566    ///
567    /// `None` means "everything valid", so the result is `None` only when both
568    /// inputs are `None`.
569    ///
570    /// # Errors
571    ///
572    /// [`DataError::BitmapLengthMismatch`] when both are present with
573    /// different lengths.
574    ///
575    /// ```
576    /// use astrs_data::Bitmap;
577    ///
578    /// let a: Bitmap = [true, false].into_iter().collect();
579    /// assert!(Bitmap::intersect(None, None)?.is_none());
580    /// assert_eq!(Bitmap::intersect(Some(&a), None)?, Some(a));
581    /// # Ok::<(), astrs_data::DataError>(())
582    /// ```
583    pub fn intersect(left: Option<&Self>, right: Option<&Self>) -> Result<Option<Self>> {
584        match (left, right) {
585            (None, None) => Ok(None),
586            (Some(only), None) | (None, Some(only)) => Ok(Some(only.clone())),
587            (Some(a), Some(b)) => a.and(b).map(Some),
588        }
589    }
590
591    /// Expands the bitmap so each bit is repeated `factor` times.
592    ///
593    /// `FixedSizeList` uses this to push a parent's validity down onto the
594    /// child values it covers.
595    ///
596    /// ```
597    /// use astrs_data::Bitmap;
598    ///
599    /// let parent: Bitmap = [true, false].into_iter().collect();
600    /// let child = parent.repeat_each(3);
601    /// assert_eq!(child.iter().collect::<Vec<_>>(), vec![true, true, true, false, false, false]);
602    /// ```
603    #[must_use]
604    pub fn repeat_each(&self, factor: usize) -> Self {
605        let mut builder = BitmapBuilder::with_capacity(self.len.saturating_mul(factor));
606        for bit in self.iter() {
607            builder.append_n(factor, bit);
608        }
609        builder.finish()
610    }
611}
612
613/// Clears the bits past `len` in the final byte, so unused tail bits never
614/// leak into a count or a comparison.
615fn mask_tail(buf: &mut AlignedBuf, len: usize) {
616    let trailing = len % 8;
617    if trailing == 0 {
618        return;
619    }
620    let last = len / 8;
621    if let Some(byte) = buf.as_mut_slice().get_mut(last) {
622        *byte &= 0xffu8 >> (8 - trailing);
623    }
624}
625
626impl Clone for Bitmap {
627    fn clone(&self) -> Self {
628        Self {
629            buffer: self.buffer.clone(),
630            offset: self.offset,
631            len: self.len,
632            set_count: AtomicI64::new(self.set_count.load(Ordering::Relaxed)),
633        }
634    }
635}
636
637impl PartialEq for Bitmap {
638    /// Compares *logical* bits, so two bitmaps at different offsets over
639    /// different buffers compare equal when their bit sequences match.
640    fn eq(&self, other: &Self) -> bool {
641        if self.len != other.len {
642            return false;
643        }
644        (0..self.len.div_ceil(8)).all(|index| {
645            let start = index * 8;
646            self.byte_at(start) == other.byte_at(start)
647        })
648    }
649}
650
651impl Eq for Bitmap {}
652
653impl std::hash::Hash for Bitmap {
654    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
655        self.len.hash(state);
656        for index in 0..self.len.div_ceil(8) {
657            self.byte_at(index * 8).hash(state);
658        }
659    }
660}
661
662impl fmt::Debug for Bitmap {
663    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
664        const PREVIEW: usize = 64;
665        let mut bits = String::with_capacity(self.len.min(PREVIEW) + 1);
666        for bit in self.iter().take(PREVIEW) {
667            bits.push(if bit { '1' } else { '0' });
668        }
669        if self.len > PREVIEW {
670            bits.push('…');
671        }
672        f.debug_struct("Bitmap")
673            .field("len", &self.len)
674            .field("offset", &self.offset)
675            .field("set", &self.count_set())
676            .field("bits", &bits)
677            .finish()
678    }
679}
680
681impl FromIterator<bool> for Bitmap {
682    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
683        let iter = iter.into_iter();
684        let (lower, _) = iter.size_hint();
685        let mut builder = BitmapBuilder::with_capacity(lower);
686        for bit in iter {
687            builder.append(bit);
688        }
689        builder.finish()
690    }
691}
692
693impl<'a> IntoIterator for &'a Bitmap {
694    type Item = bool;
695    type IntoIter = BitmapIter<'a>;
696
697    fn into_iter(self) -> BitmapIter<'a> {
698        self.iter()
699    }
700}
701
702/// Double-ended iterator over a [`Bitmap`]'s bits.
703#[derive(Debug, Clone)]
704pub struct BitmapIter<'a> {
705    /// The bitmap being walked.
706    bitmap: &'a Bitmap,
707    /// Next index from the front.
708    front: usize,
709    /// One past the next index from the back.
710    back: usize,
711}
712
713impl Iterator for BitmapIter<'_> {
714    type Item = bool;
715
716    #[inline]
717    fn next(&mut self) -> Option<bool> {
718        if self.front >= self.back {
719            return None;
720        }
721        let bit = self.bitmap.value(self.front);
722        self.front += 1;
723        Some(bit)
724    }
725
726    #[inline]
727    fn size_hint(&self) -> (usize, Option<usize>) {
728        let remaining = self.back - self.front;
729        (remaining, Some(remaining))
730    }
731}
732
733impl DoubleEndedIterator for BitmapIter<'_> {
734    #[inline]
735    fn next_back(&mut self) -> Option<bool> {
736        if self.front >= self.back {
737            return None;
738        }
739        self.back -= 1;
740        Some(self.bitmap.value(self.back))
741    }
742}
743
744impl ExactSizeIterator for BitmapIter<'_> {}
745
746impl std::iter::FusedIterator for BitmapIter<'_> {}
747
748/// Row-at-a-time writer for [`Bitmap`].
749///
750/// ```
751/// use astrs_data::BitmapBuilder;
752///
753/// let mut builder = BitmapBuilder::with_capacity(8);
754/// builder.append(true);
755/// builder.append_n(3, false);
756/// builder.append_slice(&[true, true]);
757/// let bits = builder.finish();
758/// assert_eq!(bits.len(), 6);
759/// assert_eq!(bits.count_set(), 3);
760/// ```
761#[derive(Debug, Default)]
762pub struct BitmapBuilder {
763    /// Packed bytes; the tail bits past `len` are always zero.
764    buf: AlignedBuf,
765    /// Number of bits appended so far.
766    len: usize,
767    /// Running count of set bits, handed to the finished bitmap.
768    set_count: usize,
769}
770
771impl BitmapBuilder {
772    /// An empty builder.
773    #[must_use]
774    pub fn new() -> Self {
775        Self::default()
776    }
777
778    /// An empty builder with room for `capacity` bits.
779    #[must_use]
780    pub fn with_capacity(capacity: usize) -> Self {
781        Self {
782            buf: AlignedBuf::with_capacity(capacity.div_ceil(8)),
783            len: 0,
784            set_count: 0,
785        }
786    }
787
788    /// Number of bits appended so far.
789    #[inline]
790    #[must_use]
791    pub const fn len(&self) -> usize {
792        self.len
793    }
794
795    /// Returns `true` when nothing has been appended.
796    #[inline]
797    #[must_use]
798    pub const fn is_empty(&self) -> bool {
799        self.len == 0
800    }
801
802    /// Number of set bits appended so far.
803    #[inline]
804    #[must_use]
805    pub const fn count_set(&self) -> usize {
806        self.set_count
807    }
808
809    /// Appends one bit.
810    #[inline]
811    pub fn append(&mut self, value: bool) {
812        if self.len.is_multiple_of(8) {
813            self.buf.push(0);
814        }
815        if value {
816            set_bit(self.buf.as_mut_slice(), self.len, true);
817            self.set_count += 1;
818        }
819        self.len += 1;
820    }
821
822    /// Appends `count` copies of `value`.
823    pub fn append_n(&mut self, count: usize, value: bool) {
824        if count == 0 {
825            return;
826        }
827        self.buf
828            .reserve((self.len + count).div_ceil(8) - self.buf.len());
829        // Fill the partial byte one bit at a time, then whole bytes at once.
830        let head = (8 - self.len % 8) % 8;
831        let head = head.min(count);
832        for _ in 0..head {
833            self.append(value);
834        }
835        let remaining = count - head;
836        if remaining == 0 {
837            return;
838        }
839        let whole_bytes = remaining / 8;
840        if whole_bytes > 0 {
841            self.buf
842                .resize(self.buf.len() + whole_bytes, u8::from(value) * 0xff);
843            self.len += whole_bytes * 8;
844            if value {
845                self.set_count += whole_bytes * 8;
846            }
847        }
848        for _ in 0..remaining % 8 {
849            self.append(value);
850        }
851    }
852
853    /// Appends every bit in `values`.
854    pub fn append_slice(&mut self, values: &[bool]) {
855        self.buf.reserve(
856            (self.len + values.len())
857                .div_ceil(8)
858                .saturating_sub(self.buf.len()),
859        );
860        for value in values {
861            self.append(*value);
862        }
863    }
864
865    /// Appends every bit of `bitmap`.
866    pub fn append_bitmap(&mut self, bitmap: &Bitmap) {
867        self.buf.reserve(
868            (self.len + bitmap.len())
869                .div_ceil(8)
870                .saturating_sub(self.buf.len()),
871        );
872        for bit in bitmap.iter() {
873            self.append(bit);
874        }
875    }
876
877    /// Overwrites bit `index`. Out-of-range writes are ignored.
878    pub fn set(&mut self, index: usize, value: bool) {
879        if index >= self.len {
880            return;
881        }
882        let previous = get_bit(self.buf.as_slice(), index);
883        if previous == value {
884            return;
885        }
886        set_bit(self.buf.as_mut_slice(), index, value);
887        if value {
888            self.set_count += 1;
889        } else {
890            self.set_count -= 1;
891        }
892    }
893
894    /// Reads bit `index`, or `None` when out of range.
895    #[must_use]
896    pub fn get(&self, index: usize) -> Option<bool> {
897        (index < self.len).then(|| get_bit(self.buf.as_slice(), index))
898    }
899
900    /// Drops every appended bit, keeping the allocation.
901    pub fn clear(&mut self) {
902        self.buf.clear();
903        self.len = 0;
904        self.set_count = 0;
905    }
906
907    /// Finishes the bitmap, resetting the builder.
908    #[must_use]
909    pub fn finish(&mut self) -> Bitmap {
910        let buf = std::mem::take(&mut self.buf);
911        let len = std::mem::take(&mut self.len);
912        let set_count = std::mem::take(&mut self.set_count);
913        Bitmap {
914            buffer: Buffer::from(buf),
915            offset: 0,
916            len,
917            set_count: AtomicI64::new(i64::try_from(set_count).unwrap_or(UNKNOWN_COUNT)),
918        }
919    }
920
921    /// Finishes the bitmap without resetting the builder.
922    #[must_use]
923    pub fn finish_cloned(&self) -> Bitmap {
924        Bitmap {
925            buffer: Buffer::from(self.buf.clone()),
926            offset: 0,
927            len: self.len,
928            set_count: AtomicI64::new(i64::try_from(self.set_count).unwrap_or(UNKNOWN_COUNT)),
929        }
930    }
931}
932
933impl Extend<bool> for BitmapBuilder {
934    fn extend<I: IntoIterator<Item = bool>>(&mut self, iter: I) {
935        for bit in iter {
936            self.append(bit);
937        }
938    }
939}
940
941impl FromIterator<bool> for BitmapBuilder {
942    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
943        let mut builder = Self::new();
944        builder.extend(iter);
945        builder
946    }
947}
948
949#[cfg(test)]
950mod tests {
951    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
952
953    use super::*;
954
955    const fn assert_send_sync<T: Send + Sync>() {}
956
957    fn bitmap_of(bits: &[bool]) -> Bitmap {
958        bits.iter().copied().collect()
959    }
960
961    #[test]
962    fn bitmap_is_send_and_sync() {
963        assert_send_sync::<Bitmap>();
964        assert_send_sync::<BitmapBuilder>();
965    }
966
967    #[test]
968    fn lsb_numbering_matches_the_arrow_spec() {
969        let bits = Bitmap::from_buffer(Buffer::from_slice(&[0b0000_0101, 0b1000_0000]));
970        assert!(bits.value(0));
971        assert!(!bits.value(1));
972        assert!(bits.value(2));
973        assert!(!bits.value(8));
974        assert!(bits.value(15));
975        assert_eq!(bits.count_set(), 3);
976    }
977
978    #[test]
979    fn empty_bitmap() {
980        let bits = bitmap_of(&[]);
981        assert!(bits.is_empty());
982        assert_eq!(bits.len(), 0);
983        assert_eq!(bits.count_set(), 0);
984        assert_eq!(bits.count_unset(), 0);
985        assert!(bits.all_set(), "vacuously true");
986        assert!(bits.none_set());
987        assert_eq!(bits.get(0), None);
988        assert!(!bits.value(0));
989        assert_eq!(bits.iter().count(), 0);
990    }
991
992    #[test]
993    fn all_set_and_all_unset_constructors() {
994        let set = Bitmap::new_set(13);
995        assert_eq!(set.len(), 13);
996        assert_eq!(set.count_set(), 13);
997        assert!(set.all_set());
998        assert!(set.iter().all(|b| b));
999
1000        let unset = Bitmap::new_unset(13);
1001        assert_eq!(unset.count_set(), 0);
1002        assert!(unset.none_set());
1003        assert!(unset.iter().all(|b| !b));
1004    }
1005
1006    #[test]
1007    fn try_new_validates_coverage() {
1008        let buffer = Buffer::from_slice(&[0xff, 0xff]);
1009        assert!(Bitmap::try_new(buffer.clone(), 0, 16).is_ok());
1010        assert!(Bitmap::try_new(buffer.clone(), 9, 7).is_ok());
1011        assert_eq!(
1012            Bitmap::try_new(buffer.clone(), 0, 17).unwrap_err(),
1013            DataError::BufferTooSmall {
1014                required: 3,
1015                actual: 2
1016            }
1017        );
1018        assert!(Bitmap::try_new(buffer, usize::MAX, 1).is_err());
1019    }
1020
1021    #[test]
1022    fn slicing_is_zero_copy_and_offset_aware() {
1023        let source: Vec<bool> = (0..40).map(|i| i % 3 == 0).collect();
1024        let bits = bitmap_of(&source);
1025        for offset in 0..20 {
1026            for len in 0..=(40 - offset) {
1027                let window = bits.slice(offset, len);
1028                assert_eq!(window.len(), len);
1029                let expected: Vec<bool> = source[offset..offset + len].to_vec();
1030                assert_eq!(window.iter().collect::<Vec<_>>(), expected);
1031                assert_eq!(window.count_set(), expected.iter().filter(|b| **b).count());
1032            }
1033        }
1034    }
1035
1036    #[test]
1037    fn slices_clamp_and_try_slice_reports() {
1038        let bits = bitmap_of(&[true; 10]);
1039        assert_eq!(bits.slice(8, 99).len(), 2);
1040        assert_eq!(bits.slice(99, 99).len(), 0);
1041        assert_eq!(
1042            bits.try_slice(8, 5).unwrap_err(),
1043            DataError::SliceOutOfBounds {
1044                offset: 8,
1045                len: 5,
1046                available: 10
1047            }
1048        );
1049        assert_eq!(bits.try_slice(8, 2).unwrap().len(), 2);
1050    }
1051
1052    #[test]
1053    fn nested_slices_compose() {
1054        let source: Vec<bool> = (0..64).map(|i| i % 5 == 0).collect();
1055        let bits = bitmap_of(&source);
1056        let a = bits.slice(7, 40);
1057        let b = a.slice(11, 10);
1058        let expected: Vec<bool> = source[18..28].to_vec();
1059        assert_eq!(b.iter().collect::<Vec<_>>(), expected);
1060        assert_eq!(b.bit_offset(), 18);
1061    }
1062
1063    #[test]
1064    fn full_slice_reuses_the_cached_count() {
1065        let bits = bitmap_of(&[true, false, true]);
1066        assert_eq!(bits.count_set(), 2);
1067        let full = bits.slice(0, 3);
1068        assert_eq!(full.count_set(), 2);
1069    }
1070
1071    #[test]
1072    fn count_set_bits_handles_offsets_and_ragged_ends() {
1073        let data = vec![0xffu8; 9];
1074        assert_eq!(count_set_bits(&data, 0, 72), 72);
1075        assert_eq!(count_set_bits(&data, 3, 5), 5);
1076        assert_eq!(count_set_bits(&data, 3, 60), 60);
1077        assert_eq!(count_set_bits(&data, 70, 2), 2);
1078        assert_eq!(count_set_bits(&data, 0, 0), 0);
1079        assert_eq!(count_set_bits(&data, 72, 8), 0, "past the end");
1080        assert_eq!(count_set_bits(&data, 60, 100), 12, "clamped");
1081        assert_eq!(count_set_bits(&[], 0, 8), 0);
1082
1083        let sparse = [0b0000_0001u8, 0b1000_0000];
1084        assert_eq!(count_set_bits(&sparse, 0, 16), 2);
1085        assert_eq!(count_set_bits(&sparse, 1, 14), 0);
1086        assert_eq!(count_set_bits(&sparse, 1, 15), 1);
1087    }
1088
1089    #[test]
1090    fn count_set_bits_spans_many_words() {
1091        let data = vec![0b0101_0101u8; 100];
1092        assert_eq!(count_set_bits(&data, 0, 800), 400);
1093        assert_eq!(count_set_bits(&data, 1, 798), 399);
1094        assert_eq!(count_set_bits(&data, 5, 790), 395);
1095    }
1096
1097    #[test]
1098    fn binary_ops_respect_differing_offsets() {
1099        let left_src: Vec<bool> = (0..37).map(|i| i % 2 == 0).collect();
1100        let right_src: Vec<bool> = (0..37).map(|i| i % 3 == 0).collect();
1101        // Bury each operand behind a different, non-byte-aligned offset.
1102        let padded_left: Vec<bool> = std::iter::repeat_n(false, 5)
1103            .chain(left_src.iter().copied())
1104            .collect();
1105        let padded_right: Vec<bool> = std::iter::repeat_n(true, 11)
1106            .chain(right_src.iter().copied())
1107            .collect();
1108        let left = bitmap_of(&padded_left).slice(5, 37);
1109        let right = bitmap_of(&padded_right).slice(11, 37);
1110
1111        let and = left.and(&right).unwrap();
1112        let or = left.or(&right).unwrap();
1113        let xor = left.xor(&right).unwrap();
1114        for i in 0..37 {
1115            assert_eq!(and.value(i), left_src[i] && right_src[i], "and at {i}");
1116            assert_eq!(or.value(i), left_src[i] || right_src[i], "or at {i}");
1117            assert_eq!(xor.value(i), left_src[i] ^ right_src[i], "xor at {i}");
1118        }
1119        assert_eq!(and.bit_offset(), 0, "results are canonicalised");
1120    }
1121
1122    #[test]
1123    fn binary_ops_reject_length_mismatch() {
1124        let a = bitmap_of(&[true, false]);
1125        let b = bitmap_of(&[true]);
1126        assert_eq!(
1127            a.and(&b).unwrap_err(),
1128            DataError::BitmapLengthMismatch { left: 2, right: 1 }
1129        );
1130        assert!(a.or(&b).is_err());
1131        assert!(a.xor(&b).is_err());
1132    }
1133
1134    #[test]
1135    fn not_masks_the_tail() {
1136        let bits = bitmap_of(&[true, false, true]);
1137        let inverted = bits.not();
1138        assert_eq!(inverted.len(), 3);
1139        assert_eq!(
1140            inverted.iter().collect::<Vec<_>>(),
1141            vec![false, true, false]
1142        );
1143        assert_eq!(
1144            inverted.count_set(),
1145            1,
1146            "tail bits must not leak into the count"
1147        );
1148        assert_eq!(inverted.buffer().as_slice(), &[0b0000_0010]);
1149    }
1150
1151    #[test]
1152    fn intersect_treats_none_as_all_valid() {
1153        let a = bitmap_of(&[true, false, true]);
1154        let b = bitmap_of(&[true, true, false]);
1155        assert_eq!(Bitmap::intersect(None, None).unwrap(), None);
1156        assert_eq!(Bitmap::intersect(Some(&a), None).unwrap(), Some(a.clone()));
1157        assert_eq!(Bitmap::intersect(None, Some(&b)).unwrap(), Some(b.clone()));
1158        assert_eq!(
1159            Bitmap::intersect(Some(&a), Some(&b)).unwrap(),
1160            Some(bitmap_of(&[true, false, false]))
1161        );
1162        let short = bitmap_of(&[true]);
1163        assert!(Bitmap::intersect(Some(&a), Some(&short)).is_err());
1164    }
1165
1166    #[test]
1167    fn repeat_each_expands_parent_validity() {
1168        let parent = bitmap_of(&[true, false, true]);
1169        let child = parent.repeat_each(2);
1170        assert_eq!(
1171            child.iter().collect::<Vec<_>>(),
1172            vec![true, true, false, false, true, true]
1173        );
1174        assert_eq!(parent.repeat_each(0).len(), 0);
1175        assert_eq!(parent.repeat_each(1), parent);
1176    }
1177
1178    #[test]
1179    fn to_canonical_repacks_offsets() {
1180        let source: Vec<bool> = (0..50).map(|i| i % 7 < 3).collect();
1181        let bits = bitmap_of(&source);
1182        let window = bits.slice(11, 21);
1183        let packed = window.to_canonical();
1184        assert_eq!(packed.bit_offset(), 0);
1185        assert_eq!(packed.len(), 21);
1186        assert_eq!(packed.iter().collect::<Vec<_>>(), source[11..32].to_vec());
1187        assert_eq!(packed.buffer().len(), 3);
1188        assert_eq!(packed, window);
1189        // Already canonical: returns a shared clone.
1190        let again = packed.to_canonical();
1191        assert_eq!(again.buffer().as_ptr(), packed.buffer().as_ptr());
1192    }
1193
1194    #[test]
1195    fn equality_is_logical_not_physical() {
1196        let source: Vec<bool> = (0..30).map(|i| i % 4 == 1).collect();
1197        let direct = bitmap_of(&source[3..17]);
1198        let padded: Vec<bool> = std::iter::repeat_n(true, 3)
1199            .chain(source[3..17].iter().copied())
1200            .collect();
1201        let windowed = bitmap_of(&padded).slice(3, 14);
1202        assert_eq!(direct, windowed);
1203        assert_ne!(direct, bitmap_of(&source[3..16]));
1204
1205        use std::collections::hash_map::DefaultHasher;
1206        use std::hash::{Hash, Hasher};
1207        let hash = |b: &Bitmap| {
1208            let mut h = DefaultHasher::new();
1209            b.hash(&mut h);
1210            h.finish()
1211        };
1212        assert_eq!(hash(&direct), hash(&windowed));
1213    }
1214
1215    #[test]
1216    fn iterator_is_double_ended_and_exact() {
1217        let bits = bitmap_of(&[true, false, true, true]);
1218        let mut iter = bits.iter();
1219        assert_eq!(iter.len(), 4);
1220        assert_eq!(iter.next(), Some(true));
1221        assert_eq!(iter.next_back(), Some(true));
1222        assert_eq!(iter.len(), 2);
1223        assert_eq!(iter.collect::<Vec<_>>(), vec![false, true]);
1224
1225        let reversed: Vec<bool> = bits.iter().rev().collect();
1226        assert_eq!(reversed, vec![true, true, false, true]);
1227        assert_eq!((&bits).into_iter().count(), 4);
1228    }
1229
1230    #[test]
1231    fn index_iterators() {
1232        let bits = bitmap_of(&[false, true, false, true, true]);
1233        assert_eq!(bits.set_indices().collect::<Vec<_>>(), vec![1, 3, 4]);
1234        assert_eq!(bits.unset_indices().collect::<Vec<_>>(), vec![0, 2]);
1235    }
1236
1237    #[test]
1238    fn builder_round_trips() {
1239        let mut builder = BitmapBuilder::new();
1240        assert!(builder.is_empty());
1241        for i in 0..100 {
1242            builder.append(i % 3 == 0);
1243        }
1244        assert_eq!(builder.len(), 100);
1245        assert_eq!(builder.count_set(), 34);
1246        let bits = builder.finish();
1247        assert_eq!(bits.len(), 100);
1248        assert_eq!(bits.count_set(), 34);
1249        for i in 0..100 {
1250            assert_eq!(bits.value(i), i % 3 == 0);
1251        }
1252        assert!(builder.is_empty(), "finish resets the builder");
1253    }
1254
1255    #[test]
1256    fn builder_append_n_crosses_byte_boundaries() {
1257        for start in 0..16usize {
1258            for run in 0..40usize {
1259                let mut builder = BitmapBuilder::new();
1260                builder.append_n(start, false);
1261                builder.append_n(run, true);
1262                builder.append_n(3, false);
1263                let bits = builder.finish();
1264                assert_eq!(bits.len(), start + run + 3);
1265                assert_eq!(bits.count_set(), run, "start {start} run {run}");
1266                for i in 0..start {
1267                    assert!(!bits.value(i));
1268                }
1269                for i in start..start + run {
1270                    assert!(bits.value(i), "start {start} run {run} index {i}");
1271                }
1272                for i in start + run..start + run + 3 {
1273                    assert!(!bits.value(i));
1274                }
1275            }
1276        }
1277    }
1278
1279    #[test]
1280    fn builder_append_slice_and_bitmap() {
1281        let mut builder = BitmapBuilder::with_capacity(16);
1282        builder.append_slice(&[true, false, true]);
1283        builder.append_bitmap(&bitmap_of(&[false, true]));
1284        let bits = builder.finish();
1285        assert_eq!(
1286            bits.iter().collect::<Vec<_>>(),
1287            vec![true, false, true, false, true]
1288        );
1289    }
1290
1291    #[test]
1292    fn builder_set_updates_the_running_count() {
1293        let mut builder = BitmapBuilder::new();
1294        builder.append_slice(&[true, false, true]);
1295        assert_eq!(builder.count_set(), 2);
1296        builder.set(1, true);
1297        assert_eq!(builder.count_set(), 3);
1298        builder.set(1, true);
1299        assert_eq!(builder.count_set(), 3, "idempotent");
1300        builder.set(0, false);
1301        assert_eq!(builder.count_set(), 2);
1302        builder.set(99, true);
1303        assert_eq!(builder.count_set(), 2, "out-of-range writes are ignored");
1304        assert_eq!(builder.get(1), Some(true));
1305        assert_eq!(builder.get(9), None);
1306        let bits = builder.finish();
1307        assert_eq!(bits.count_set(), 2);
1308    }
1309
1310    #[test]
1311    fn builder_clear_and_finish_cloned() {
1312        let mut builder: BitmapBuilder = [true, true, false].into_iter().collect();
1313        let snapshot = builder.finish_cloned();
1314        assert_eq!(snapshot.len(), 3);
1315        assert_eq!(builder.len(), 3, "finish_cloned keeps the builder");
1316        builder.clear();
1317        assert!(builder.is_empty());
1318        assert_eq!(builder.finish().len(), 0);
1319        assert_eq!(snapshot.count_set(), 2);
1320    }
1321
1322    #[test]
1323    fn builder_extend() {
1324        let mut builder = BitmapBuilder::new();
1325        builder.extend([true, false]);
1326        builder.extend(vec![true]);
1327        assert_eq!(builder.finish().count_set(), 2);
1328    }
1329
1330    #[test]
1331    fn debug_renders_bits() {
1332        let bits = bitmap_of(&[true, false, true]);
1333        let rendered = format!("{bits:?}");
1334        assert!(rendered.contains("101"), "{rendered}");
1335        assert!(rendered.contains("set: 2"), "{rendered}");
1336
1337        let long = Bitmap::new_set(200);
1338        assert!(format!("{long:?}").contains('…'));
1339    }
1340
1341    #[test]
1342    fn free_helpers_are_total() {
1343        let mut data = [0u8; 2];
1344        set_bit(&mut data, 0, true);
1345        set_bit(&mut data, 15, true);
1346        set_bit(&mut data, 99, true);
1347        assert_eq!(data, [0b0000_0001, 0b1000_0000]);
1348        assert!(get_bit(&data, 0));
1349        assert!(get_bit(&data, 15));
1350        assert!(!get_bit(&data, 16));
1351        set_bit(&mut data, 0, false);
1352        assert!(!get_bit(&data, 0));
1353    }
1354
1355    #[test]
1356    fn cached_count_survives_cloning() {
1357        let bits = bitmap_of(&[true, false, true, true]);
1358        assert_eq!(bits.count_set(), 3);
1359        let copy = bits.clone();
1360        assert_eq!(copy.count_set(), 3);
1361        assert_eq!(copy, bits);
1362    }
1363
1364    #[test]
1365    fn from_buffer_uses_every_bit() {
1366        let bits = Bitmap::from_buffer(Buffer::from_slice(&[0b0000_1111, 0]));
1367        assert_eq!(bits.len(), 16);
1368        assert_eq!(bits.count_set(), 4);
1369        assert_eq!(bits.buffer().len(), 2);
1370    }
1371}