Skip to main content

arrow_buffer/buffer/
mutable.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 std::alloc::Layout;
6use std::mem;
7use std::ptr::NonNull;
8
9use crate::alloc::{ALIGNMENT, Deallocation};
10use crate::{
11    bytes::Bytes,
12    native::{ArrowNativeType, ToByteSlice},
13    util::bit_util,
14};
15
16#[cfg(feature = "pool")]
17use crate::pool::{MemoryPool, TrackedReservation};
18
19use super::Buffer;
20
21/// Error returned by fallible [`MutableBuffer`] operations.
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub enum MutableBufferError {
24    /// Arithmetic overflow when computing the required buffer length or capacity.
25    LengthOverflow,
26    /// The requested capacity cannot be represented as a valid allocation layout.
27    LayoutError,
28    /// An allocation failed due to insufficient memory.
29    AllocationError(Layout),
30}
31
32impl std::fmt::Display for MutableBufferError {
33    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34        match self {
35            Self::LengthOverflow => write!(f, "buffer length overflow"),
36            Self::LayoutError => write!(f, "invalid allocation layout for requested capacity"),
37            Self::AllocationError(layout) => {
38                write!(f, "failed to allocate memory for layout {layout:?}")
39            }
40        }
41    }
42}
43
44impl std::error::Error for MutableBufferError {}
45
46/// A [`MutableBuffer`] is a wrapper over memory regions, used to build
47/// [`Buffer`]s out of items or slices of items.
48///
49/// [`Buffer`]s created from [`MutableBuffer`] (via `into`) are guaranteed to be
50/// aligned along cache lines and in multiples of 64 bytes.
51///
52/// Use [MutableBuffer::push] to insert an item, [MutableBuffer::extend_from_slice]
53/// to insert many items, and `into` to convert it to [`Buffer`]. For typed data,
54/// it is often more efficient to use [`Vec`] and convert it to [`Buffer`] rather
55/// than using [`MutableBuffer`] (see examples below).
56///
57/// # See Also
58/// * For a safe, strongly typed API consider using [`Vec`] and [`ScalarBuffer`](crate::ScalarBuffer)
59/// * To apply bitwise operations, see [`apply_bitwise_binary_op`] and [`apply_bitwise_unary_op`]
60///
61/// [`apply_bitwise_binary_op`]: crate::bit_util::apply_bitwise_binary_op
62/// [`apply_bitwise_unary_op`]: crate::bit_util::apply_bitwise_unary_op
63///
64/// # Example: Creating a [`Buffer`] from a [`MutableBuffer`]
65/// ```
66/// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
67/// let mut buffer = MutableBuffer::new(0);
68/// buffer.push(256u32);
69/// buffer.extend_from_slice(&[1u32]);
70/// let buffer = Buffer::from(buffer);
71/// assert_eq!(buffer.as_slice(), &[0u8, 1, 0, 0, 1, 0, 0, 0])
72/// ```
73///
74/// The same can be achieved more efficiently by using a `Vec<u32>`
75/// ```
76/// # use arrow_buffer::buffer::Buffer;
77/// let mut vec = Vec::new();
78/// vec.push(256u32);
79/// vec.extend_from_slice(&[1u32]);
80/// let buffer = Buffer::from(vec);
81/// assert_eq!(buffer.as_slice(), &[0u8, 1, 0, 0, 1, 0, 0, 0]);
82/// ```
83///
84/// # Example: Creating a [`MutableBuffer`] from a `Vec<T>`
85/// ```
86/// # use arrow_buffer::buffer::MutableBuffer;
87/// let vec = vec![1u32, 2, 3];
88/// let mutable_buffer = MutableBuffer::from(vec); // reuses the allocation from vec
89/// assert_eq!(mutable_buffer.len(), 12); // 3 * 4 bytes
90/// ```
91///
92/// # Example: Creating a [`MutableBuffer`] from a [`Buffer`]
93/// ```
94/// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
95/// let buffer: Buffer = Buffer::from(&[1u8, 2, 3, 4][..]);
96/// // Only possible to convert a Buffer into a MutableBuffer if uniquely owned
97/// // (i.e., there are no other references to it).
98/// let mut mutable_buffer = match buffer.into_mutable() {
99///    Ok(mutable) => mutable,
100///    Err(orig_buffer) => {
101///      panic!("buffer was not uniquely owned");
102///    }
103/// };
104/// mutable_buffer.push(5u8);
105/// let buffer = Buffer::from(mutable_buffer);
106/// assert_eq!(buffer.as_slice(), &[1u8, 2, 3, 4, 5])
107/// ```
108#[derive(Debug)]
109pub struct MutableBuffer {
110    // dangling iff capacity = 0
111    data: NonNull<u8>,
112    // invariant: len <= capacity
113    len: usize,
114    layout: Layout,
115
116    /// Memory reservation for tracking memory usage
117    #[cfg(feature = "pool")]
118    reservation: TrackedReservation,
119}
120
121impl MutableBuffer {
122    /// Allocate a new [MutableBuffer] with initial capacity to be at least `capacity`.
123    ///
124    /// See [`MutableBuffer::with_capacity`].
125    ///
126    /// # Panics
127    ///
128    /// See [`MutableBuffer::with_capacity`].
129    #[inline]
130    pub fn new(capacity: usize) -> Self {
131        Self::try_with_capacity(capacity).unwrap_or_else(|e| panic!("{e}"))
132    }
133
134    /// Allocate a new [MutableBuffer] with initial capacity to be at least `capacity`.
135    ///
136    /// # Panics
137    ///
138    /// If `capacity`, when rounded up to the nearest multiple of [`ALIGNMENT`], is greater
139    /// then `isize::MAX`, then this function will panic.
140    #[inline]
141    pub fn with_capacity(capacity: usize) -> Self {
142        Self::try_with_capacity(capacity).unwrap_or_else(|e| panic!("{e}"))
143    }
144
145    /// Fallible version of [`MutableBuffer::with_capacity`].
146    #[inline]
147    pub fn try_with_capacity(capacity: usize) -> Result<Self, MutableBufferError> {
148        let capacity = capacity
149            .checked_next_multiple_of(64)
150            .ok_or(MutableBufferError::LayoutError)?;
151        let layout = Layout::from_size_align(capacity, ALIGNMENT)
152            .map_err(|_| MutableBufferError::LayoutError)?;
153        let data = match layout.size() {
154            0 => dangling_ptr(),
155            _ => {
156                // Safety: Verified size != 0
157                let raw_ptr = unsafe { std::alloc::alloc(layout) };
158                match NonNull::new(raw_ptr) {
159                    Some(ptr) => ptr,
160                    None => return Err(MutableBufferError::AllocationError(layout)),
161                }
162            }
163        };
164        Ok(Self {
165            data,
166            len: 0,
167            layout,
168            #[cfg(feature = "pool")]
169            reservation: TrackedReservation::default(),
170        })
171    }
172
173    /// Allocates a new [MutableBuffer] with `len` and capacity to be at least `len` where
174    /// all bytes are guaranteed to be `0u8`.
175    /// # Example
176    /// ```
177    /// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
178    /// let mut buffer = MutableBuffer::from_len_zeroed(127);
179    /// assert_eq!(buffer.len(), 127);
180    /// assert!(buffer.capacity() >= 127);
181    /// let data = buffer.as_slice_mut();
182    /// assert_eq!(data[126], 0u8);
183    /// ```
184    ///
185    /// # Panics
186    ///
187    /// Panics if `len` is too large to construct a valid allocation [`Layout`]
188    pub fn from_len_zeroed(len: usize) -> Self {
189        Self::try_from_len_zeroed(len).unwrap_or_else(|e| panic!("{e}"))
190    }
191
192    /// Fallible version of [`MutableBuffer::from_len_zeroed`].
193    pub fn try_from_len_zeroed(len: usize) -> Result<Self, MutableBufferError> {
194        let layout =
195            Layout::from_size_align(len, ALIGNMENT).map_err(|_| MutableBufferError::LayoutError)?;
196        let data = match layout.size() {
197            0 => dangling_ptr(),
198            _ => {
199                // Safety: Verified size != 0
200                let raw_ptr = unsafe { std::alloc::alloc_zeroed(layout) };
201                match NonNull::new(raw_ptr) {
202                    Some(ptr) => ptr,
203                    None => return Err(MutableBufferError::AllocationError(layout)),
204                }
205            }
206        };
207        Ok(Self {
208            data,
209            len,
210            layout,
211            #[cfg(feature = "pool")]
212            reservation: TrackedReservation::default(),
213        })
214    }
215
216    /// Allocates a new [MutableBuffer] from given `Bytes`.
217    pub(crate) fn from_bytes(bytes: Bytes) -> Result<Self, Bytes> {
218        let layout = match bytes.deallocation() {
219            Deallocation::Standard(layout) => *layout,
220            Deallocation::Custom(..) => return Err(bytes),
221        };
222
223        let len = bytes.len();
224        let data = bytes.ptr();
225        #[cfg(feature = "pool")]
226        let reservation = bytes.reservation.take();
227
228        mem::forget(bytes);
229
230        Ok(Self {
231            data,
232            len,
233            layout,
234            #[cfg(feature = "pool")]
235            reservation,
236        })
237    }
238
239    /// creates a new [MutableBuffer] with capacity and length capable of holding `len` bits.
240    /// This is useful to create a buffer for packed bitmaps.
241    ///
242    /// # Panics
243    ///
244    /// See [`MutableBuffer::from_len_zeroed`].
245    pub fn new_null(len: usize) -> Self {
246        let num_bytes = bit_util::ceil(len, 8);
247        MutableBuffer::from_len_zeroed(num_bytes)
248    }
249
250    /// Set the bits in the range of `[0, end)` to 0 (if `val` is false), or 1 (if `val`
251    /// is true). Also extend the length of this buffer to be `end`.
252    ///
253    /// This is useful when one wants to clear (or set) the bits and then manipulate
254    /// the buffer directly (e.g., modifying the buffer by holding a mutable reference
255    /// from `data_mut()`).
256    ///
257    /// # Panics
258    ///
259    /// Panics if `end` exceeds the buffer capacity.
260    pub fn with_bitset(mut self, end: usize, val: bool) -> Self {
261        assert!(end <= self.layout.size());
262        let v = if val { 255 } else { 0 };
263        unsafe {
264            std::ptr::write_bytes(self.data.as_ptr(), v, end);
265            self.len = end;
266        }
267        self
268    }
269
270    /// Ensure that `count` bytes from `start` contain zero bits
271    ///
272    /// This is used to initialize the bits in a buffer, however, it has no impact on the
273    /// `len` of the buffer and so can be used to initialize the memory region from
274    /// `len` to `capacity`.
275    ///
276    /// # Panics
277    ///
278    /// Panics if the byte range `start..start + count` exceeds the buffer capacity.
279    pub fn set_null_bits(&mut self, start: usize, count: usize) {
280        assert!(
281            start.saturating_add(count) <= self.layout.size(),
282            "range start index {start} and count {count} out of bounds for \
283            buffer of length {}",
284            self.layout.size(),
285        );
286
287        // Safety: `self.data[start..][..count]` is in-bounds and well-aligned for `u8`
288        unsafe {
289            std::ptr::write_bytes(self.data.as_ptr().add(start), 0, count);
290        }
291    }
292
293    /// Fallible version of [`MutableBuffer::reserve`].
294    #[inline]
295    pub fn try_reserve(&mut self, additional: usize) -> Result<(), MutableBufferError> {
296        let required_cap = self
297            .len
298            .checked_add(additional)
299            .ok_or(MutableBufferError::LengthOverflow)?;
300        if required_cap > self.layout.size() {
301            let new_capacity = required_cap
302                .checked_next_multiple_of(64)
303                .ok_or(MutableBufferError::LayoutError)?;
304            let new_capacity = std::cmp::max(new_capacity, self.layout.size().saturating_mul(2));
305            self.try_reallocate(new_capacity)?;
306        }
307        Ok(())
308    }
309    /// Ensures that this buffer has at least `self.len + additional` bytes. This re-allocates iff
310    /// `self.len + additional > capacity`.
311    /// # Example
312    /// ```
313    /// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
314    /// let mut buffer = MutableBuffer::new(0);
315    /// buffer.reserve(253); // allocates for the first time
316    /// (0..253u8).for_each(|i| buffer.push(i)); // no reallocation
317    /// let buffer: Buffer = buffer.into();
318    /// assert_eq!(buffer.len(), 253);
319    /// ```
320    ///
321    /// # Panics
322    ///
323    /// Panics if `self.len + additional` overflows `usize`, or if the required capacity is too
324    /// large to round up to the next 64-byte boundary and construct a valid allocation layout.
325    // For performance reasons, this must be inlined so that the `if` is executed inside the caller, and not as an extra call that just
326    // exits.
327    #[inline(always)]
328    pub fn reserve(&mut self, additional: usize) {
329        self.try_reserve(additional)
330            .unwrap_or_else(|e| panic!("{e}"))
331    }
332
333    /// Fallible version of [`MutableBuffer::repeat_slice_n_times`].
334    pub fn try_repeat_slice_n_times<T: ArrowNativeType>(
335        &mut self,
336        slice_to_repeat: &[T],
337        repeat_count: usize,
338    ) -> Result<(), MutableBufferError> {
339        if repeat_count == 0 || slice_to_repeat.is_empty() {
340            return Ok(());
341        }
342        let bytes_per_copy = size_of_val(slice_to_repeat);
343        let total_bytes = repeat_count
344            .checked_mul(bytes_per_copy)
345            .ok_or(MutableBufferError::LengthOverflow)?;
346        self.len
347            .checked_add(total_bytes)
348            .ok_or(MutableBufferError::LengthOverflow)?;
349
350        // Ensure capacity
351        self.try_reserve(total_bytes)?;
352
353        // Save the length before we do all the copies to know where to start from
354        let length_before = self.len;
355
356        // Copy the initial slice once so we can use doubling strategy on it
357        self.try_extend_from_slice(slice_to_repeat)?;
358
359        // Number of times the slice was repeated
360        let mut already_repeated = 1usize;
361
362        // We will use doubling strategy to fill the buffer in log(repeat_count) steps
363        while already_repeated < repeat_count {
364            // How many slices can we copy in this iteration
365            // (either double what we have, or just the remaining ones)
366            let to_copy = already_repeated.min(repeat_count - already_repeated);
367            let byte_count = to_copy * bytes_per_copy;
368            unsafe {
369                // Get to the start of the data before we started copying anything
370                let src = self.data.as_ptr().add(length_before).cast_const();
371                // Go to the current location to copy to (end of current data)
372                let dst = self.data.as_ptr().add(self.len);
373                // SAFETY: the pointers are not overlapping as there is `byte_count` or less between them
374                std::ptr::copy_nonoverlapping(src, dst, byte_count);
375            }
376            // Advance the length by the amount of data we just copied (doubled)
377            self.len += byte_count;
378            already_repeated += to_copy;
379        }
380        Ok(())
381    }
382    /// Adding to this mutable buffer `slice_to_repeat` repeated `repeat_count` times.
383    ///
384    /// # Example
385    ///
386    /// ## Repeat the same string bytes multiple times
387    /// ```
388    /// # use arrow_buffer::buffer::MutableBuffer;
389    /// let mut buffer = MutableBuffer::new(0);
390    /// let bytes_to_repeat = b"ab";
391    /// buffer.repeat_slice_n_times(bytes_to_repeat, 3);
392    /// assert_eq!(buffer.as_slice(), b"ababab");
393    /// ```
394    ///
395    /// # Panics
396    ///
397    /// Panics if the repeated slice byte length overflows `usize`, if the resulting buffer
398    /// length overflows `usize`, or if reserving the required capacity fails for the same
399    /// reasons as [`MutableBuffer::reserve`].
400    pub fn repeat_slice_n_times<T: ArrowNativeType>(
401        &mut self,
402        slice_to_repeat: &[T],
403        repeat_count: usize,
404    ) {
405        self.try_repeat_slice_n_times(slice_to_repeat, repeat_count)
406            .unwrap_or_else(|e| panic!("{e}"))
407    }
408
409    #[cold]
410    fn try_reallocate(&mut self, capacity: usize) -> Result<(), MutableBufferError> {
411        let new_layout = Layout::from_size_align(capacity, self.layout.align())
412            .map_err(|_| MutableBufferError::LayoutError)?;
413
414        if new_layout.size() == 0 {
415            if self.layout.size() != 0 {
416                // Safety: data was allocated with layout
417                unsafe { std::alloc::dealloc(self.as_mut_ptr(), self.layout) };
418                self.layout = new_layout;
419            }
420            return Ok(());
421        }
422
423        let data = match self.layout.size() {
424            // Safety: new_layout is not empty
425            0 => unsafe { std::alloc::alloc(new_layout) },
426            // Safety: verified new layout is valid and not empty
427            _ => unsafe { std::alloc::realloc(self.as_mut_ptr(), self.layout, capacity) },
428        };
429        self.data = match NonNull::new(data) {
430            Some(ptr) => ptr,
431            None => return Err(MutableBufferError::AllocationError(new_layout)),
432        };
433        self.layout = new_layout;
434        #[cfg(feature = "pool")]
435        self.reservation.resize(self.layout.size());
436        Ok(())
437    }
438    /// Truncates this buffer to `len` bytes
439    ///
440    /// If `len` is greater than the buffer's current length, this has no effect
441    #[inline(always)]
442    pub fn truncate(&mut self, len: usize) {
443        if len > self.len {
444            return;
445        }
446        self.len = len;
447        #[cfg(feature = "pool")]
448        self.reservation.resize(self.len);
449    }
450
451    /// Fallible version of [`MutableBuffer::resize`].
452    #[inline]
453    pub fn try_resize(&mut self, new_len: usize, value: u8) -> Result<(), MutableBufferError> {
454        if new_len > self.len {
455            let diff = new_len - self.len;
456            self.try_reserve(diff)?;
457            // Safety: try_reserve ensured capacity >= new_len.
458            // write the value
459            unsafe { self.data.as_ptr().add(self.len).write_bytes(value, diff) };
460        }
461        // this truncates the buffer when new_len < self.len
462        self.len = new_len;
463        #[cfg(feature = "pool")]
464        self.reservation.resize(self.len);
465        Ok(())
466    }
467    /// Resizes the buffer, either truncating its contents (with no change in capacity), or
468    /// growing it (potentially reallocating it) and writing `value` in the newly available bytes.
469    /// # Example
470    /// ```
471    /// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
472    /// let mut buffer = MutableBuffer::new(0);
473    /// buffer.resize(253, 2); // allocates for the first time
474    /// assert_eq!(buffer.as_slice()[252], 2u8);
475    /// ```
476    ///
477    /// # Panics
478    ///
479    /// Panics if growing the buffer requires reserving a capacity that fails for the same
480    /// reasons as [`MutableBuffer::reserve`].
481    // For performance reasons, this must be inlined so that the `if` is executed inside the caller, and not as an extra call that just
482    // exits.
483    #[inline(always)]
484    pub fn resize(&mut self, new_len: usize, value: u8) {
485        self.try_resize(new_len, value)
486            .unwrap_or_else(|e| panic!("{e}"))
487    }
488
489    /// Fallible version of [`MutableBuffer::shrink_to_fit`].
490    pub fn try_shrink_to_fit(&mut self) -> Result<(), MutableBufferError> {
491        let new_capacity = self
492            .len
493            .checked_next_multiple_of(64)
494            .ok_or(MutableBufferError::LayoutError)?;
495        if new_capacity < self.layout.size() {
496            self.try_reallocate(new_capacity)?;
497        }
498        Ok(())
499    }
500    /// Shrinks the capacity of the buffer as much as possible.
501    /// The new capacity will aligned to the nearest 64 bit alignment.
502    ///
503    /// # Example
504    /// ```
505    /// # use arrow_buffer::buffer::{Buffer, MutableBuffer};
506    /// // 2 cache lines
507    /// let mut buffer = MutableBuffer::new(128);
508    /// assert_eq!(buffer.capacity(), 128);
509    /// buffer.push(1);
510    /// buffer.push(2);
511    ///
512    /// buffer.shrink_to_fit();
513    /// assert!(buffer.capacity() >= 64 && buffer.capacity() < 128);
514    /// ```
515    ///
516    /// # Panics
517    ///
518    /// Panics if the current length is too large to round up to the next 64-byte boundary and
519    /// construct a valid allocation layout.
520    pub fn shrink_to_fit(&mut self) {
521        self.try_shrink_to_fit().unwrap_or_else(|e| panic!("{e}"))
522    }
523
524    /// Returns whether this buffer is empty or not.
525    #[inline]
526    pub const fn is_empty(&self) -> bool {
527        self.len == 0
528    }
529
530    /// Returns the length (the number of bytes written) in this buffer.
531    /// The invariant `buffer.len() <= buffer.capacity()` is always upheld.
532    #[inline]
533    pub const fn len(&self) -> usize {
534        self.len
535    }
536
537    /// Returns the total capacity in this buffer, in bytes.
538    ///
539    /// The invariant `buffer.len() <= buffer.capacity()` is always upheld.
540    #[inline]
541    pub const fn capacity(&self) -> usize {
542        self.layout.size()
543    }
544
545    /// Clear all existing data from this buffer.
546    pub fn clear(&mut self) {
547        self.len = 0;
548        #[cfg(feature = "pool")]
549        self.reservation.resize(self.len);
550    }
551
552    /// Returns the data stored in this buffer as a slice.
553    pub fn as_slice(&self) -> &[u8] {
554        self
555    }
556
557    /// Returns the data stored in this buffer as a mutable slice.
558    pub fn as_slice_mut(&mut self) -> &mut [u8] {
559        self
560    }
561
562    /// Returns a raw pointer to this buffer's internal memory
563    /// This pointer is guaranteed to be aligned along cache-lines.
564    #[inline]
565    pub const fn as_ptr(&self) -> *const u8 {
566        self.data.as_ptr()
567    }
568
569    /// Returns a mutable raw pointer to this buffer's internal memory
570    /// This pointer is guaranteed to be aligned along cache-lines.
571    #[inline]
572    pub fn as_mut_ptr(&mut self) -> *mut u8 {
573        self.data.as_ptr()
574    }
575
576    #[inline]
577    pub(super) fn into_buffer(self) -> Buffer {
578        let bytes = unsafe { Bytes::new(self.data, self.len, Deallocation::Standard(self.layout)) };
579        #[cfg(feature = "pool")]
580        bytes.reservation.replace(self.reservation.take());
581        std::mem::forget(self);
582        Buffer::from(bytes)
583    }
584
585    /// View this buffer as a mutable slice of a specific type.
586    ///
587    /// # Panics
588    ///
589    /// This function panics if the underlying buffer is not aligned correctly for type `T`, or
590    /// if its length is not a multiple of `size_of::<T>()`.
591    pub fn typed_data_mut<T: ArrowNativeType>(&mut self) -> &mut [T] {
592        // SAFETY
593        // ArrowNativeType is trivially transmutable, is sealed to prevent potentially incorrect
594        // implementation outside this crate, and this method checks alignment
595        let (prefix, offsets, suffix) = unsafe { self.as_slice_mut().align_to_mut::<T>() };
596        assert!(prefix.is_empty() && suffix.is_empty());
597        offsets
598    }
599
600    /// View buffer as a immutable slice of a specific type.
601    ///
602    /// # Panics
603    ///
604    /// This function panics if the underlying buffer is not aligned correctly for type `T`, or
605    /// if its length is not a multiple of `size_of::<T>()`.
606    pub fn typed_data<T: ArrowNativeType>(&self) -> &[T] {
607        // SAFETY
608        // ArrowNativeType is trivially transmutable, is sealed to prevent potentially incorrect
609        // implementation outside this crate, and this method checks alignment
610        let (prefix, offsets, suffix) = unsafe { self.as_slice().align_to::<T>() };
611        assert!(prefix.is_empty() && suffix.is_empty());
612        offsets
613    }
614
615    /// Fallible version of [`MutableBuffer::extend_from_slice`].
616    #[inline]
617    pub fn try_extend_from_slice<T: ArrowNativeType>(
618        &mut self,
619        items: &[T],
620    ) -> Result<(), MutableBufferError> {
621        let additional = mem::size_of_val(items);
622        self.try_reserve(additional)?;
623        unsafe {
624            // this assumes that `[ToByteSlice]` can be copied directly
625            // without calling `to_byte_slice` for each element,
626            // which is correct for all ArrowNativeType implementations.
627            let src = items.as_ptr().cast::<u8>();
628            let dst = self.data.as_ptr().add(self.len);
629            std::ptr::copy_nonoverlapping(src, dst, additional);
630        }
631        self.len += additional;
632        Ok(())
633    }
634    /// Extends this buffer from a slice of items that can be represented in bytes, increasing its capacity if needed.
635    /// # Example
636    /// ```
637    /// # use arrow_buffer::buffer::MutableBuffer;
638    /// let mut buffer = MutableBuffer::new(0);
639    /// buffer.extend_from_slice(&[2u32, 0]);
640    /// assert_eq!(buffer.len(), 8) // u32 has 4 bytes
641    /// ```
642    ///
643    /// # Panics
644    ///
645    /// Panics if extending the buffer requires reserving a capacity that fails for the same
646    /// reasons as [`MutableBuffer::reserve`].
647    #[inline]
648    pub fn extend_from_slice<T: ArrowNativeType>(&mut self, items: &[T]) {
649        self.try_extend_from_slice(items)
650            .unwrap_or_else(|e| panic!("{e}"))
651    }
652
653    /// Extends the buffer with a new item, increasing its capacity if needed.
654    /// # Example
655    /// ```
656    /// # use arrow_buffer::buffer::MutableBuffer;
657    /// let mut buffer = MutableBuffer::new(0);
658    /// buffer.push(256u32);
659    /// assert_eq!(buffer.len(), 4) // u32 has 4 bytes
660    /// ```
661    ///
662    /// # Panics
663    ///
664    /// Panics if extending the buffer requires reserving a capacity that fails for the same
665    /// reasons as [`MutableBuffer::reserve`].
666    #[inline]
667    pub fn push<T: ToByteSlice>(&mut self, item: T) {
668        let additional = std::mem::size_of::<T>();
669        self.reserve(additional);
670        unsafe {
671            let src = item.to_byte_slice().as_ptr();
672            let dst = self.data.as_ptr().add(self.len);
673            std::ptr::copy_nonoverlapping(src, dst, additional);
674        }
675        self.len += additional;
676    }
677
678    /// Extends the buffer with a new item, without checking for sufficient capacity
679    /// # Safety
680    /// Caller must ensure that the capacity()-len()>=`size_of<T>`()
681    #[inline]
682    pub unsafe fn push_unchecked<T: ToByteSlice>(&mut self, item: T) {
683        let additional = std::mem::size_of::<T>();
684        let src = item.to_byte_slice().as_ptr();
685        let dst = unsafe { self.data.as_ptr().add(self.len) };
686        unsafe { std::ptr::copy_nonoverlapping(src, dst, additional) };
687        self.len += additional;
688    }
689
690    /// Fallible version of [`MutableBuffer::extend_zeros`].
691    #[inline]
692    pub fn try_extend_zeros(&mut self, additional: usize) -> Result<(), MutableBufferError> {
693        let new_len = self
694            .len
695            .checked_add(additional)
696            .ok_or(MutableBufferError::LengthOverflow)?;
697        self.try_resize(new_len, 0)
698    }
699    /// Extends the buffer by `additional` bytes equal to `0u8`, incrementing its capacity if needed.
700    ///
701    /// # Panics
702    ///
703    /// Panics if `self.len + additional` overflows `usize`, or if growing the buffer requires
704    /// reserving a capacity that fails for the same reasons as [`MutableBuffer::reserve`].
705    #[inline]
706    pub fn extend_zeros(&mut self, additional: usize) {
707        self.try_extend_zeros(additional)
708            .unwrap_or_else(|e| panic!("{e}"))
709    }
710
711    /// # Safety
712    /// The caller must ensure that the buffer was properly initialized up to `len`.
713    ///
714    /// # Panics
715    ///
716    /// Panics if `len` exceeds the buffer capacity.
717    #[inline]
718    pub unsafe fn set_len(&mut self, len: usize) {
719        assert!(len <= self.capacity());
720        self.len = len;
721    }
722
723    /// Invokes `f` with values `0..len` collecting the boolean results into a new `MutableBuffer`
724    ///
725    /// This is similar to `from_trusted_len_iter_bool`, however, can be significantly faster
726    /// as it eliminates the conditional `Iterator::next`
727    ///
728    /// # Panics
729    ///
730    /// Panics if the backing storage for `len` bits cannot be allocated. Use
731    /// [`MutableBuffer::try_collect_bool`] for a fallible version.
732    #[inline]
733    pub fn collect_bool<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
734        Self::try_collect_bool(len, f).unwrap_or_else(|e| panic!("{e}"))
735    }
736
737    /// Fallible version of [`MutableBuffer::collect_bool`].
738    ///
739    /// `len` is a bit count, so the reservation is `ceil(len / 64)` u64 slots. This function
740    /// returns an error if that much memory cannot be reserved up front.
741    #[inline]
742    pub fn try_collect_bool<F: FnMut(usize) -> bool>(
743        len: usize,
744        mut f: F,
745    ) -> Result<Self, MutableBufferError> {
746        let words = bit_util::ceil(len, 64);
747        let layout = Layout::array::<u64>(words).map_err(|_| MutableBufferError::LayoutError)?;
748        let mut buffer: Vec<u64> = Vec::new();
749        buffer
750            .try_reserve(words)
751            .map_err(|_| MutableBufferError::AllocationError(layout))?;
752
753        let chunks = len / 64;
754        let remainder = len % 64;
755        buffer.extend((0..chunks).map(|chunk| {
756            let mut packed = 0;
757            for bit_idx in 0..64 {
758                let i = bit_idx + chunk * 64;
759                packed |= (f(i) as u64) << bit_idx;
760            }
761
762            packed
763        }));
764
765        if remainder != 0 {
766            let mut packed = 0;
767            for bit_idx in 0..remainder {
768                let i = bit_idx + chunks * 64;
769                packed |= (f(i) as u64) << bit_idx;
770            }
771
772            buffer.push(packed)
773        }
774
775        let mut buffer: MutableBuffer = buffer.into();
776        buffer.truncate(bit_util::ceil(len, 8));
777        Ok(buffer)
778    }
779
780    /// Extends this buffer with boolean values.
781    ///
782    /// This requires `iter` to report an exact size via `size_hint`.
783    /// `offset` indicates the starting offset in bits in this buffer to begin writing to
784    /// and must be less than or equal to the current length of this buffer.
785    /// All bits not written to (but readable due to byte alignment) will be zeroed out.
786    ///
787    /// # Panics
788    ///
789    /// Panics if `iter` does not report an exact size via `size_hint`, or if it yields fewer
790    /// items than reported, or if extending the buffer requires reserving a capacity that fails
791    /// for the same reasons as [`MutableBuffer::reserve`].
792    ///
793    /// # Safety
794    /// Callers must ensure that `iter` reports an exact size via `size_hint`
795    /// and that `I::next()` does not panic, or `set_len` will leave the buffer
796    /// in an inconsistent state, exposing uninitialized/stale bytes as though
797    /// they were valid.
798    #[inline]
799    pub unsafe fn extend_bool_trusted_len<I: Iterator<Item = bool>>(
800        &mut self,
801        mut iter: I,
802        offset: usize,
803    ) {
804        let (lower, upper) = iter.size_hint();
805        let len = upper.expect("Iterator must have exact size_hint");
806        assert_eq!(lower, len, "Iterator must have exact size_hint");
807        debug_assert!(
808            offset <= self.len * 8,
809            "offset must be <= buffer length in bits"
810        );
811
812        if len == 0 {
813            return;
814        }
815
816        let start_len = offset;
817        let end_bit = start_len + len;
818
819        // SAFETY: we will initialize all newly exposed bytes before they are read
820        let new_len_bytes = bit_util::ceil(end_bit, 8);
821        if new_len_bytes > self.len {
822            self.reserve(new_len_bytes - self.len);
823            // SAFETY: caller will initialize all newly exposed bytes before they are read
824            unsafe { self.set_len(new_len_bytes) };
825        }
826
827        let slice = self.as_slice_mut();
828
829        let mut bit_idx = start_len;
830
831        // ---- Unaligned prefix: advance to the next 64-bit boundary ----
832        let misalignment = bit_idx & 63;
833        let prefix_bits = if misalignment == 0 {
834            0
835        } else {
836            (64 - misalignment).min(end_bit - bit_idx)
837        };
838
839        if prefix_bits != 0 {
840            let byte_start = bit_idx / 8;
841            let byte_end = bit_util::ceil(bit_idx + prefix_bits, 8);
842            let bit_offset = bit_idx % 8;
843
844            // Clear any newly-visible bits in the existing partial byte
845            if bit_offset != 0 {
846                let keep_mask = (1u8 << bit_offset).wrapping_sub(1);
847                slice[byte_start] &= keep_mask;
848            }
849
850            // Zero any new bytes we will partially fill in this prefix
851            let zero_from = if bit_offset == 0 {
852                byte_start
853            } else {
854                byte_start + 1
855            };
856            if byte_end > zero_from {
857                slice[zero_from..byte_end].fill(0);
858            }
859
860            for _ in 0..prefix_bits {
861                let v = iter.next().unwrap();
862                if v {
863                    let byte_idx = bit_idx / 8;
864                    let bit = bit_idx % 8;
865                    slice[byte_idx] |= 1 << bit;
866                }
867                bit_idx += 1;
868            }
869        }
870
871        if bit_idx < end_bit {
872            // ---- Aligned middle: write u64 chunks ----
873            debug_assert_eq!(bit_idx & 63, 0);
874            let remaining_bits = end_bit - bit_idx;
875            let chunks = remaining_bits / 64;
876
877            let words_start = bit_idx / 8;
878            let words_end = words_start + chunks * 8;
879            for dst in slice[words_start..words_end].as_chunks_mut::<8>().0 {
880                let mut packed: u64 = 0;
881                for i in 0..64 {
882                    packed |= (iter.next().unwrap() as u64) << i;
883                }
884                dst.copy_from_slice(&packed.to_le_bytes());
885                bit_idx += 64;
886            }
887
888            // ---- Unaligned suffix: remaining < 64 bits ----
889            let suffix_bits = end_bit - bit_idx;
890            if suffix_bits != 0 {
891                debug_assert_eq!(bit_idx % 8, 0);
892                let byte_start = bit_idx / 8;
893                let byte_end = bit_util::ceil(end_bit, 8);
894                slice[byte_start..byte_end].fill(0);
895
896                for _ in 0..suffix_bits {
897                    let v = iter.next().unwrap();
898                    if v {
899                        let byte_idx = bit_idx / 8;
900                        let bit = bit_idx % 8;
901                        slice[byte_idx] |= 1 << bit;
902                    }
903                    bit_idx += 1;
904                }
905            }
906        }
907
908        // Clear any unused bits in the last byte
909        let remainder = end_bit % 8;
910        if remainder != 0 {
911            let mask = (1u8 << remainder).wrapping_sub(1);
912            slice[bit_util::ceil(end_bit, 8) - 1] &= mask;
913        }
914
915        debug_assert_eq!(bit_idx, end_bit);
916    }
917
918    /// Register this [`MutableBuffer`] with the provided [`MemoryPool`]
919    ///
920    /// This claims the memory used by this buffer in the pool, allowing for
921    /// accurate accounting of memory usage. Any prior reservation will be
922    /// released so this works well when the buffer is being shared among
923    /// multiple arrays.
924    #[cfg(feature = "pool")]
925    pub fn claim(&self, pool: &dyn MemoryPool) {
926        self.reservation.claim(pool, self.capacity());
927    }
928}
929
930/// Creates a non-null pointer with alignment of [`ALIGNMENT`]
931///
932/// This is similar to [`NonNull::dangling`]
933#[inline]
934pub(crate) fn dangling_ptr() -> NonNull<u8> {
935    // SAFETY: ALIGNMENT is a non-zero usize which is then cast
936    // to a *mut u8. Therefore, `ptr` is not null and the conditions for
937    // calling new_unchecked() are respected.
938    #[cfg(miri)]
939    {
940        // Since miri implies a nightly rust version we can use the unstable strict_provenance feature
941        unsafe { NonNull::new_unchecked(std::ptr::without_provenance_mut(ALIGNMENT)) }
942    }
943    #[cfg(not(miri))]
944    {
945        unsafe { NonNull::new_unchecked(ALIGNMENT as *mut u8) }
946    }
947}
948
949impl<A: ArrowNativeType> Extend<A> for MutableBuffer {
950    #[inline]
951    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
952        let iterator = iter.into_iter();
953        self.extend_from_iter(iterator)
954    }
955}
956
957impl<T: ArrowNativeType> From<Vec<T>> for MutableBuffer {
958    fn from(mut value: Vec<T>) -> Self {
959        // Safety
960        // Vec::as_mut_ptr guaranteed to not be null and ArrowNativeType are trivially transmutable
961        let data = unsafe { NonNull::new_unchecked(value.as_mut_ptr().cast()) };
962        let len = value.len() * mem::size_of::<T>();
963        // Safety
964        // Vec guaranteed to have a valid layout matching that of `Layout::array`
965        // This is based on `RawVec::current_memory`
966        let layout = unsafe { Layout::array::<T>(value.capacity()).unwrap_unchecked() };
967        mem::forget(value);
968        Self {
969            data,
970            len,
971            layout,
972            #[cfg(feature = "pool")]
973            reservation: TrackedReservation::default(),
974        }
975    }
976}
977
978impl MutableBuffer {
979    #[inline]
980    pub(super) fn extend_from_iter<T: ArrowNativeType, I: Iterator<Item = T>>(
981        &mut self,
982        mut iterator: I,
983    ) {
984        let item_size = std::mem::size_of::<T>();
985        let (lower, _) = iterator.size_hint();
986        let additional = lower * item_size;
987        self.reserve(additional);
988
989        // this is necessary because of https://github.com/rust-lang/rust/issues/32155
990        let mut len = SetLenOnDrop::new(&mut self.len);
991        let mut dst = unsafe { self.data.as_ptr().add(len.local_len) };
992        let capacity = self.layout.size();
993
994        while len.local_len + item_size <= capacity {
995            if let Some(item) = iterator.next() {
996                unsafe {
997                    let src = item.to_byte_slice().as_ptr();
998                    std::ptr::copy_nonoverlapping(src, dst, item_size);
999                    dst = dst.add(item_size);
1000                }
1001                len.local_len += item_size;
1002            } else {
1003                break;
1004            }
1005        }
1006        drop(len);
1007
1008        iterator.for_each(|item| self.push(item));
1009    }
1010
1011    /// Creates a [`MutableBuffer`] from an [`Iterator`] with a trusted (upper) length.
1012    /// Prefer this to `collect` whenever possible, as it is faster ~60% faster.
1013    /// # Example
1014    /// ```
1015    /// # use arrow_buffer::buffer::MutableBuffer;
1016    /// let v = vec![1u32];
1017    /// let iter = v.iter().map(|x| x * 2);
1018    /// let buffer = unsafe { MutableBuffer::from_trusted_len_iter(iter) };
1019    /// assert_eq!(buffer.len(), 4) // u32 has 4 bytes
1020    /// ```
1021    ///
1022    /// # Panics
1023    ///
1024    /// Panics if the iterator does not report an upper bound via `size_hint`, or if the
1025    /// reported length does not match the number of items produced, or if allocating the
1026    /// required buffer fails for the same reasons as [`MutableBuffer::new`].
1027    ///
1028    /// # Safety
1029    /// This method assumes that the iterator's size is correct and is undefined behavior
1030    /// to use it on an iterator that reports an incorrect length.
1031    // This implementation is required for two reasons:
1032    // 1. there is no trait `TrustedLen` in stable rust and therefore
1033    //    we can't specialize `extend` for `TrustedLen` like `Vec` does.
1034    // 2. `from_trusted_len_iter` is faster.
1035    #[inline]
1036    pub unsafe fn from_trusted_len_iter<T: ArrowNativeType, I: Iterator<Item = T>>(
1037        iterator: I,
1038    ) -> Self {
1039        let item_size = std::mem::size_of::<T>();
1040        let (_, upper) = iterator.size_hint();
1041        let upper = upper.expect("from_trusted_len_iter requires an upper limit");
1042        let len = upper * item_size;
1043
1044        let mut buffer = MutableBuffer::new(len);
1045
1046        let mut dst = buffer.data.as_ptr();
1047        for item in iterator {
1048            // note how there is no reserve here (compared with `extend_from_iter`)
1049            let src = item.to_byte_slice().as_ptr();
1050            unsafe { std::ptr::copy_nonoverlapping(src, dst, item_size) };
1051            dst = unsafe { dst.add(item_size) };
1052        }
1053        assert_eq!(
1054            unsafe { dst.offset_from(buffer.data.as_ptr()) } as usize,
1055            len,
1056            "Trusted iterator length was not accurately reported"
1057        );
1058        buffer.len = len;
1059        buffer
1060    }
1061
1062    /// Creates a [`MutableBuffer`] from a boolean [`Iterator`] with a trusted (upper) length.
1063    /// # use arrow_buffer::buffer::MutableBuffer;
1064    /// # Example
1065    /// ```
1066    /// # use arrow_buffer::buffer::MutableBuffer;
1067    /// let v = vec![false, true, false];
1068    /// let iter = v.iter().map(|x| *x || true);
1069    /// let buffer = unsafe { MutableBuffer::from_trusted_len_iter_bool(iter) };
1070    /// assert_eq!(buffer.len(), 1) // 3 booleans have 1 byte
1071    /// ```
1072    ///
1073    /// # Panics
1074    ///
1075    /// Panics if the iterator does not report an upper bound via `size_hint`, or if it yields
1076    /// fewer items than reported.
1077    ///
1078    /// # Safety
1079    /// This method assumes that the iterator's size is correct and is undefined behavior
1080    /// to use it on an iterator that reports an incorrect length.
1081    // This implementation is required for two reasons:
1082    // 1. there is no trait `TrustedLen` in stable rust and therefore
1083    //    we can't specialize `extend` for `TrustedLen` like `Vec` does.
1084    // 2. `from_trusted_len_iter_bool` is faster.
1085    #[inline]
1086    pub unsafe fn from_trusted_len_iter_bool<I: Iterator<Item = bool>>(mut iterator: I) -> Self {
1087        let (_, upper) = iterator.size_hint();
1088        let len = upper.expect("from_trusted_len_iter requires an upper limit");
1089
1090        Self::collect_bool(len, |_| iterator.next().unwrap())
1091    }
1092
1093    /// Creates a [`MutableBuffer`] from an [`Iterator`] with a trusted (upper) length or errors
1094    /// if any of the items of the iterator is an error.
1095    /// Prefer this to `collect` whenever possible, as it is faster ~60% faster.
1096    ///
1097    /// # Errors
1098    ///
1099    /// Returns the first error yielded by the iterator.
1100    ///
1101    /// # Panics
1102    ///
1103    /// Note that unlike the [`Err`] cases, these panics are violations of the safety contract
1104    /// below, and are only checks that happen to be cheap enough to keep:
1105    ///
1106    /// Panics if the iterator does not report an upper bound via `size_hint`, or if the
1107    /// reported length does not match the number of items produced before an error-free finish,
1108    /// or if allocating the required buffer fails for the same reasons as
1109    /// [`MutableBuffer::new`].
1110    ///
1111    /// # Safety
1112    /// This method assumes that the iterator's size is correct and is undefined behavior
1113    /// to use it on an iterator that reports an incorrect length.
1114    #[inline]
1115    pub unsafe fn try_from_trusted_len_iter<
1116        E,
1117        T: ArrowNativeType,
1118        I: Iterator<Item = Result<T, E>>,
1119    >(
1120        iterator: I,
1121    ) -> Result<Self, E> {
1122        let item_size = std::mem::size_of::<T>();
1123        let (_, upper) = iterator.size_hint();
1124        let upper = upper.expect("try_from_trusted_len_iter requires an upper limit");
1125        let len = upper * item_size;
1126
1127        let mut buffer = MutableBuffer::new(len);
1128
1129        let mut dst = buffer.data.as_ptr();
1130        for item in iterator {
1131            let item = item?;
1132            // note how there is no reserve here (compared with `extend_from_iter`)
1133            let src = item.to_byte_slice().as_ptr();
1134            unsafe { std::ptr::copy_nonoverlapping(src, dst, item_size) };
1135            dst = unsafe { dst.add(item_size) };
1136        }
1137        // try_from_trusted_len_iter is instantiated a lot, so we extract part of it into a less
1138        // generic method to reduce compile time
1139        unsafe fn finalize_buffer(dst: *mut u8, buffer: &mut MutableBuffer, len: usize) {
1140            unsafe {
1141                assert_eq!(
1142                    dst.offset_from(buffer.data.as_ptr()) as usize,
1143                    len,
1144                    "Trusted iterator length was not accurately reported"
1145                );
1146                buffer.len = len;
1147            }
1148        }
1149        unsafe { finalize_buffer(dst, &mut buffer, len) };
1150        Ok(buffer)
1151    }
1152}
1153
1154impl Default for MutableBuffer {
1155    fn default() -> Self {
1156        Self::with_capacity(0)
1157    }
1158}
1159
1160impl std::ops::Deref for MutableBuffer {
1161    type Target = [u8];
1162
1163    fn deref(&self) -> &[u8] {
1164        unsafe { std::slice::from_raw_parts(self.as_ptr(), self.len) }
1165    }
1166}
1167
1168impl std::ops::DerefMut for MutableBuffer {
1169    fn deref_mut(&mut self) -> &mut [u8] {
1170        unsafe { std::slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
1171    }
1172}
1173
1174impl AsRef<[u8]> for &MutableBuffer {
1175    fn as_ref(&self) -> &[u8] {
1176        self.as_slice()
1177    }
1178}
1179
1180impl Drop for MutableBuffer {
1181    fn drop(&mut self) {
1182        if self.layout.size() != 0 {
1183            // Safety: data was allocated with standard allocator with given layout
1184            unsafe { std::alloc::dealloc(self.data.as_ptr().cast(), self.layout) };
1185        }
1186    }
1187}
1188
1189impl PartialEq for MutableBuffer {
1190    fn eq(&self, other: &MutableBuffer) -> bool {
1191        if self.len != other.len {
1192            return false;
1193        }
1194        if self.layout != other.layout {
1195            return false;
1196        }
1197        self.as_slice() == other.as_slice()
1198    }
1199}
1200
1201unsafe impl Sync for MutableBuffer {}
1202unsafe impl Send for MutableBuffer {}
1203
1204struct SetLenOnDrop<'a> {
1205    len: &'a mut usize,
1206    local_len: usize,
1207}
1208
1209impl<'a> SetLenOnDrop<'a> {
1210    #[inline]
1211    fn new(len: &'a mut usize) -> Self {
1212        SetLenOnDrop {
1213            local_len: *len,
1214            len,
1215        }
1216    }
1217}
1218
1219impl Drop for SetLenOnDrop<'_> {
1220    #[inline]
1221    fn drop(&mut self) {
1222        *self.len = self.local_len;
1223    }
1224}
1225
1226/// Creating a `MutableBuffer` instance by setting bits according to the boolean values
1227impl std::iter::FromIterator<bool> for MutableBuffer {
1228    fn from_iter<I>(iter: I) -> Self
1229    where
1230        I: IntoIterator<Item = bool>,
1231    {
1232        let mut iterator = iter.into_iter();
1233        let mut result = {
1234            let byte_capacity: usize = iterator.size_hint().0.saturating_add(7) / 8;
1235            MutableBuffer::new(byte_capacity)
1236        };
1237
1238        loop {
1239            let mut exhausted = false;
1240            let mut byte_accum: u8 = 0;
1241            let mut mask: u8 = 1;
1242
1243            //collect (up to) 8 bits into a byte
1244            while mask != 0 {
1245                if let Some(value) = iterator.next() {
1246                    byte_accum |= match value {
1247                        true => mask,
1248                        false => 0,
1249                    };
1250                    mask <<= 1;
1251                } else {
1252                    exhausted = true;
1253                    break;
1254                }
1255            }
1256
1257            // break if the iterator was exhausted before it provided a bool for this byte
1258            if exhausted && mask == 1 {
1259                break;
1260            }
1261
1262            //ensure we have capacity to write the byte
1263            if result.len() == result.capacity() {
1264                //no capacity for new byte, allocate 1 byte more (plus however many more the iterator advertises)
1265                let additional_byte_capacity = 1usize.saturating_add(
1266                    iterator.size_hint().0.saturating_add(7) / 8, //convert bit count to byte count, rounding up
1267                );
1268                result.reserve(additional_byte_capacity)
1269            }
1270
1271            // Soundness: capacity was allocated above
1272            unsafe { result.push_unchecked(byte_accum) };
1273            if exhausted {
1274                break;
1275            }
1276        }
1277        result
1278    }
1279}
1280
1281impl<T: ArrowNativeType> std::iter::FromIterator<T> for MutableBuffer {
1282    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1283        let mut buffer = Self::default();
1284        buffer.extend_from_iter(iter.into_iter());
1285        buffer
1286    }
1287}
1288
1289#[cfg(test)]
1290mod tests {
1291    use super::*;
1292
1293    #[test]
1294    fn test_mutable_new() {
1295        let buf = MutableBuffer::new(63);
1296        assert_eq!(64, buf.capacity());
1297        assert_eq!(0, buf.len());
1298        assert!(buf.is_empty());
1299    }
1300
1301    #[test]
1302    fn test_mutable_default() {
1303        let buf = MutableBuffer::default();
1304        assert_eq!(0, buf.capacity());
1305        assert_eq!(0, buf.len());
1306        assert!(buf.is_empty());
1307
1308        let mut buf = MutableBuffer::default();
1309        buf.extend_from_slice(b"hello");
1310        assert_eq!(5, buf.len());
1311        assert_eq!(b"hello", buf.as_slice());
1312    }
1313
1314    #[test]
1315    fn test_mutable_extend_from_slice() {
1316        let mut buf = MutableBuffer::new(100);
1317        buf.extend_from_slice(b"hello");
1318        assert_eq!(5, buf.len());
1319        assert_eq!(b"hello", buf.as_slice());
1320
1321        buf.extend_from_slice(b" world");
1322        assert_eq!(11, buf.len());
1323        assert_eq!(b"hello world", buf.as_slice());
1324
1325        buf.clear();
1326        assert_eq!(0, buf.len());
1327        buf.extend_from_slice(b"hello arrow");
1328        assert_eq!(11, buf.len());
1329        assert_eq!(b"hello arrow", buf.as_slice());
1330    }
1331
1332    #[test]
1333    fn mutable_extend_from_iter() {
1334        let mut buf = MutableBuffer::new(0);
1335        buf.extend(vec![1u32, 2]);
1336        assert_eq!(8, buf.len());
1337        assert_eq!(&[1u8, 0, 0, 0, 2, 0, 0, 0], buf.as_slice());
1338
1339        buf.extend(vec![3u32, 4]);
1340        assert_eq!(16, buf.len());
1341        assert_eq!(
1342            &[1u8, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0],
1343            buf.as_slice()
1344        );
1345    }
1346
1347    #[test]
1348    fn mutable_extend_from_iter_unaligned_u64() {
1349        let mut buf = MutableBuffer::new(16);
1350        buf.push(1_u8);
1351        buf.extend([1_u64]);
1352        assert_eq!(9, buf.len());
1353        assert_eq!(&[1u8, 1u8, 0, 0, 0, 0, 0, 0, 0], buf.as_slice());
1354    }
1355
1356    #[test]
1357    fn mutable_extend_from_slice_unaligned_u64() {
1358        let mut buf = MutableBuffer::new(16);
1359        buf.extend_from_slice(&[1_u8]);
1360        buf.extend_from_slice(&[1_u64]);
1361        assert_eq!(9, buf.len());
1362        assert_eq!(&[1u8, 1u8, 0, 0, 0, 0, 0, 0, 0], buf.as_slice());
1363    }
1364
1365    #[test]
1366    fn mutable_push_unaligned_u64() {
1367        let mut buf = MutableBuffer::new(16);
1368        buf.push(1_u8);
1369        buf.push(1_u64);
1370        assert_eq!(9, buf.len());
1371        assert_eq!(&[1u8, 1u8, 0, 0, 0, 0, 0, 0, 0], buf.as_slice());
1372    }
1373
1374    #[test]
1375    fn mutable_push_unchecked_unaligned_u64() {
1376        let mut buf = MutableBuffer::new(16);
1377        unsafe {
1378            buf.push_unchecked(1_u8);
1379            buf.push_unchecked(1_u64);
1380        }
1381        assert_eq!(9, buf.len());
1382        assert_eq!(&[1u8, 1u8, 0, 0, 0, 0, 0, 0, 0], buf.as_slice());
1383    }
1384
1385    #[test]
1386    fn test_from_trusted_len_iter() {
1387        let iter = vec![1u32, 2].into_iter();
1388        let buf = unsafe { MutableBuffer::from_trusted_len_iter(iter) };
1389        assert_eq!(8, buf.len());
1390        assert_eq!(&[1u8, 0, 0, 0, 2, 0, 0, 0], buf.as_slice());
1391    }
1392
1393    #[test]
1394    fn test_mutable_reserve() {
1395        let mut buf = MutableBuffer::new(1);
1396        assert_eq!(64, buf.capacity());
1397
1398        // Reserving a smaller capacity should have no effect.
1399        buf.reserve(10);
1400        assert_eq!(64, buf.capacity());
1401
1402        buf.reserve(80);
1403        assert_eq!(128, buf.capacity());
1404
1405        buf.reserve(129);
1406        assert_eq!(256, buf.capacity());
1407    }
1408
1409    #[test]
1410    fn test_mutable_resize() {
1411        let mut buf = MutableBuffer::new(1);
1412        assert_eq!(64, buf.capacity());
1413        assert_eq!(0, buf.len());
1414
1415        buf.resize(20, 0);
1416        assert_eq!(64, buf.capacity());
1417        assert_eq!(20, buf.len());
1418
1419        buf.resize(10, 0);
1420        assert_eq!(64, buf.capacity());
1421        assert_eq!(10, buf.len());
1422
1423        buf.resize(100, 0);
1424        assert_eq!(128, buf.capacity());
1425        assert_eq!(100, buf.len());
1426
1427        buf.resize(30, 0);
1428        assert_eq!(128, buf.capacity());
1429        assert_eq!(30, buf.len());
1430
1431        buf.resize(0, 0);
1432        assert_eq!(128, buf.capacity());
1433        assert_eq!(0, buf.len());
1434    }
1435
1436    #[test]
1437    fn test_mutable_into() {
1438        let mut buf = MutableBuffer::new(1);
1439        buf.extend_from_slice(b"aaaa bbbb cccc dddd");
1440        assert_eq!(19, buf.len());
1441        assert_eq!(64, buf.capacity());
1442        assert_eq!(b"aaaa bbbb cccc dddd", buf.as_slice());
1443
1444        let immutable_buf: Buffer = buf.into();
1445        assert_eq!(19, immutable_buf.len());
1446        assert_eq!(64, immutable_buf.capacity());
1447        assert_eq!(b"aaaa bbbb cccc dddd", immutable_buf.as_slice());
1448    }
1449
1450    #[test]
1451    fn test_mutable_equal() {
1452        let mut buf = MutableBuffer::new(1);
1453        let mut buf2 = MutableBuffer::new(1);
1454
1455        buf.extend_from_slice(&[0xaa]);
1456        buf2.extend_from_slice(&[0xaa, 0xbb]);
1457        assert_ne!(buf, buf2);
1458
1459        buf.extend_from_slice(&[0xbb]);
1460        assert_eq!(buf, buf2);
1461
1462        buf2.reserve(65);
1463        assert_ne!(buf, buf2);
1464    }
1465
1466    #[test]
1467    fn test_mutable_shrink_to_fit() {
1468        let mut buffer = MutableBuffer::new(128);
1469        assert_eq!(buffer.capacity(), 128);
1470        buffer.push(1);
1471        buffer.push(2);
1472
1473        buffer.shrink_to_fit();
1474        assert!(buffer.capacity() >= 64 && buffer.capacity() < 128);
1475    }
1476
1477    #[test]
1478    fn test_mutable_set_null_bits() {
1479        let mut buffer = MutableBuffer::new(8).with_bitset(8, true);
1480
1481        for i in 0..=buffer.capacity() {
1482            buffer.set_null_bits(i, 0);
1483            assert_eq!(buffer[..8], [255; 8][..]);
1484        }
1485
1486        buffer.set_null_bits(1, 4);
1487        assert_eq!(buffer[..8], [255, 0, 0, 0, 0, 255, 255, 255][..]);
1488    }
1489
1490    #[test]
1491    #[should_panic = "out of bounds for buffer of length"]
1492    fn test_mutable_set_null_bits_oob() {
1493        let mut buffer = MutableBuffer::new(64);
1494        buffer.set_null_bits(1, buffer.capacity());
1495    }
1496
1497    #[test]
1498    #[should_panic = "out of bounds for buffer of length"]
1499    fn test_mutable_set_null_bits_oob_by_overflow() {
1500        let mut buffer = MutableBuffer::new(0);
1501        buffer.set_null_bits(1, usize::MAX);
1502    }
1503
1504    #[test]
1505    fn from_iter() {
1506        let buffer = [1u16, 2, 3, 4].into_iter().collect::<MutableBuffer>();
1507        assert_eq!(buffer.len(), 4 * mem::size_of::<u16>());
1508        assert_eq!(buffer.as_slice(), &[1, 0, 2, 0, 3, 0, 4, 0]);
1509    }
1510
1511    #[test]
1512    #[should_panic(expected = "invalid allocation layout for requested capacity")]
1513    fn test_with_capacity_panics_above_max_capacity() {
1514        let max_capacity = isize::MAX as usize - (isize::MAX as usize % ALIGNMENT);
1515        let _ = MutableBuffer::with_capacity(max_capacity + 1);
1516    }
1517
1518    #[cfg(feature = "pool")]
1519    mod pool_tests {
1520        use super::*;
1521        use crate::pool::{MemoryPool, TrackingMemoryPool};
1522
1523        #[test]
1524        fn test_reallocate_with_pool() {
1525            let pool = TrackingMemoryPool::default();
1526            let mut buffer = MutableBuffer::with_capacity(100);
1527            buffer.claim(&pool);
1528
1529            // Initial capacity should be 128 (multiple of 64)
1530            assert_eq!(buffer.capacity(), 128);
1531            assert_eq!(pool.used(), 128);
1532
1533            // Reallocate to a larger size
1534            buffer.try_reallocate(200).unwrap();
1535
1536            // The capacity is exactly the requested size, not rounded up
1537            assert_eq!(buffer.capacity(), 200);
1538            assert_eq!(pool.used(), 200);
1539
1540            // Reallocate to a smaller size
1541            buffer.try_reallocate(50).unwrap();
1542
1543            // The capacity is exactly the requested size, not rounded up
1544            assert_eq!(buffer.capacity(), 50);
1545            assert_eq!(pool.used(), 50);
1546        }
1547
1548        #[test]
1549        fn test_truncate_with_pool() {
1550            let pool = TrackingMemoryPool::default();
1551            let mut buffer = MutableBuffer::with_capacity(100);
1552
1553            // Fill buffer with some data
1554            buffer.resize(80, 1);
1555            assert_eq!(buffer.len(), 80);
1556
1557            buffer.claim(&pool);
1558            assert_eq!(pool.used(), 128);
1559
1560            // Truncate buffer
1561            buffer.truncate(40);
1562            assert_eq!(buffer.len(), 40);
1563            assert_eq!(pool.used(), 40);
1564
1565            // Truncate to zero
1566            buffer.clear();
1567            assert_eq!(buffer.len(), 0);
1568            assert_eq!(pool.used(), 0);
1569        }
1570
1571        #[test]
1572        fn test_resize_with_pool() {
1573            let pool = TrackingMemoryPool::default();
1574            let mut buffer = MutableBuffer::with_capacity(100);
1575            buffer.claim(&pool);
1576
1577            // Initial state
1578            assert_eq!(buffer.len(), 0);
1579            assert_eq!(pool.used(), 128);
1580
1581            // Resize to increase length
1582            buffer.resize(50, 1);
1583            assert_eq!(buffer.len(), 50);
1584            assert_eq!(pool.used(), 50);
1585
1586            // Resize to increase length beyond capacity
1587            buffer.resize(150, 1);
1588            assert_eq!(buffer.len(), 150);
1589            assert_eq!(buffer.capacity(), 256);
1590            assert_eq!(pool.used(), 150);
1591
1592            // Resize to decrease length
1593            buffer.resize(30, 1);
1594            assert_eq!(buffer.len(), 30);
1595            assert_eq!(pool.used(), 30);
1596        }
1597
1598        #[test]
1599        fn test_buffer_lifecycle_with_pool() {
1600            let pool = TrackingMemoryPool::default();
1601
1602            // Create a buffer with memory reservation
1603            let mut mutable = MutableBuffer::with_capacity(100);
1604            mutable.resize(80, 1);
1605            mutable.claim(&pool);
1606
1607            // Memory reservation is based on capacity when using claim()
1608            assert_eq!(pool.used(), 128);
1609
1610            // Convert to immutable Buffer
1611            let buffer = mutable.into_buffer();
1612
1613            // Memory reservation should be preserved
1614            assert_eq!(pool.used(), 128);
1615
1616            // Drop the buffer and the reservation should be released
1617            drop(buffer);
1618            assert_eq!(pool.used(), 0);
1619        }
1620    }
1621
1622    fn create_expected_repeated_slice<T: ArrowNativeType>(
1623        slice_to_repeat: &[T],
1624        repeat_count: usize,
1625    ) -> Buffer {
1626        let mut expected = MutableBuffer::new(size_of_val(slice_to_repeat) * repeat_count);
1627        for _ in 0..repeat_count {
1628            // Not using push_slice_repeated as this is the function under test
1629            expected.extend_from_slice(slice_to_repeat);
1630        }
1631        expected.into()
1632    }
1633
1634    // Helper to test a specific repeat count with various slice sizes
1635    fn test_repeat_count<T: ArrowNativeType + PartialEq + std::fmt::Debug>(
1636        repeat_count: usize,
1637        test_data: &[T],
1638    ) {
1639        let mut buffer = MutableBuffer::new(0);
1640        buffer.repeat_slice_n_times(test_data, repeat_count);
1641
1642        let expected = create_expected_repeated_slice(test_data, repeat_count);
1643        let result: Buffer = buffer.into();
1644
1645        assert_eq!(
1646            result,
1647            expected,
1648            "Failed for repeat_count={}, slice_len={}",
1649            repeat_count,
1650            test_data.len()
1651        );
1652    }
1653
1654    #[test]
1655    fn test_repeat_slice_count_edge_cases() {
1656        // Empty slice
1657        test_repeat_count(100, &[] as &[i32]);
1658
1659        // Zero repeats
1660        test_repeat_count(0, &[1i32, 2, 3]);
1661    }
1662
1663    #[test]
1664    #[should_panic(expected = "buffer length overflow")]
1665    fn test_repeat_slice_count_multiply_overflow() {
1666        let mut buffer = MutableBuffer::new(0);
1667        buffer.repeat_slice_n_times(&[0_u64], usize::MAX / mem::size_of::<u64>() + 1);
1668    }
1669
1670    #[test]
1671    #[should_panic(expected = "buffer length overflow")]
1672    fn test_repeat_slice_count_len_overflow() {
1673        let mut buffer = MutableBuffer::new(0);
1674        buffer.push(0_u8);
1675        buffer.repeat_slice_n_times(&[0_u8], usize::MAX);
1676    }
1677
1678    #[test]
1679    fn test_small_repeats_counts() {
1680        // test any special implementation for small repeat counts
1681        let data = &[1u8, 2, 3, 4, 5];
1682
1683        for _ in 1..=10 {
1684            test_repeat_count(2, data);
1685        }
1686    }
1687
1688    #[test]
1689    fn test_different_size_of_i32_repeat_slice() {
1690        let data: &[i32] = &[1, 2, 3];
1691        let data_with_single_item: &[i32] = &[42];
1692
1693        for data in &[data, data_with_single_item] {
1694            for item in 1..=9 {
1695                let base_repeat_count = 2_usize.pow(item);
1696                test_repeat_count(base_repeat_count - 1, data);
1697                test_repeat_count(base_repeat_count, data);
1698                test_repeat_count(base_repeat_count + 1, data);
1699            }
1700        }
1701    }
1702
1703    #[test]
1704    fn test_different_size_of_u8_repeat_slice() {
1705        let data: &[u8] = &[1, 2, 3];
1706        let data_with_single_item: &[u8] = &[10];
1707
1708        for data in &[data, data_with_single_item] {
1709            for item in 1..=9 {
1710                let base_repeat_count = 2_usize.pow(item);
1711                test_repeat_count(base_repeat_count - 1, data);
1712                test_repeat_count(base_repeat_count, data);
1713                test_repeat_count(base_repeat_count + 1, data);
1714            }
1715        }
1716    }
1717
1718    #[test]
1719    fn test_different_size_of_u16_repeat_slice() {
1720        let data: &[u16] = &[1, 2, 3];
1721        let data_with_single_item: &[u16] = &[10];
1722
1723        for data in &[data, data_with_single_item] {
1724            for item in 1..=9 {
1725                let base_repeat_count = 2_usize.pow(item);
1726                test_repeat_count(base_repeat_count - 1, data);
1727                test_repeat_count(base_repeat_count, data);
1728                test_repeat_count(base_repeat_count + 1, data);
1729            }
1730        }
1731    }
1732
1733    #[test]
1734    fn test_various_slice_lengths() {
1735        // Test different slice lengths with same repeat pattern
1736        let repeat_count = 37; // Arbitrary non-power-of-2
1737
1738        // Single element
1739        test_repeat_count(repeat_count, &[42i32]);
1740
1741        // Small slices
1742        test_repeat_count(repeat_count, &[1i32, 2]);
1743        test_repeat_count(repeat_count, &[1i32, 2, 3]);
1744        test_repeat_count(repeat_count, &[1i32, 2, 3, 4]);
1745        test_repeat_count(repeat_count, &[1i32, 2, 3, 4, 5]);
1746
1747        // Larger slices
1748        let data_10: Vec<i32> = (0..10).collect();
1749        test_repeat_count(repeat_count, &data_10);
1750
1751        let data_100: Vec<i32> = (0..100).collect();
1752        test_repeat_count(repeat_count, &data_100);
1753
1754        let data_1000: Vec<i32> = (0..1000).collect();
1755        test_repeat_count(repeat_count, &data_1000);
1756    }
1757
1758    #[test]
1759    #[should_panic(expected = "invalid allocation layout for requested capacity")]
1760    fn test_mutable_new_capacity_overflow() {
1761        // Tests overflow during initial allocation
1762        let _ = MutableBuffer::new(usize::MAX - 10);
1763    }
1764
1765    #[test]
1766    #[should_panic(expected = "buffer length overflow")]
1767    fn test_mutable_reserve_overflow() {
1768        // Tests overflow during growth (checked_add)
1769        let mut buf = MutableBuffer::new(1);
1770        buf.push(1u8);
1771        buf.reserve(usize::MAX);
1772    }
1773}