compressed_intvec/fixed/atomic/
builder.rs

1//! # [`AtomicFixedVec`] Builder
2//!
3//! This module provides a builder for constructing an owned [`AtomicFixedVec`]
4//! from a slice of data (`&[T]`). It mirrors the functionality of the standard
5//! [`FixedVecBuilder`](crate::fixed::builder::FixedVecBuilder), allowing for
6//! automatic bit-width detection and a consistent API.
7//!
8//! # Examples
9//!
10//! ## Building from a slice
11//!
12//! ```rust
13//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
14//! use compressed_intvec::prelude::*;
15//! use compressed_intvec::fixed::{AtomicFixedVec, UAtomicFixedVec, BitWidth};
16//!
17//! let data: &[u32] = &[10, 20, 30, 40, 50];
18//!
19//! // The builder can infer the minimal bit width (6 bits for 50).
20//! let vec: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
21//!     .build(data)?;
22//!
23//! assert_eq!(vec.bit_width(), 6);
24//!
25//! // Or a specific strategy can be chosen.
26//! let vec_pow2: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
27//!     .bit_width(BitWidth::PowerOfTwo)
28//!     .build(data)?;
29//!
30//! assert_eq!(vec_pow2.bit_width(), 8);
31//! # Ok(())
32//! # }
33//! ```
34
35use crate::fixed::atomic::AtomicFixedVec;
36use crate::fixed::traits::Storable;
37use crate::fixed::{BitWidth, Error};
38use num_traits::ToPrimitive;
39use std::marker::PhantomData;
40use std::sync::atomic::AtomicU64;
41
42/// A builder for creating an [`AtomicFixedVec`] from a slice of integers.
43///
44/// This builder analyzes a slice to determine the `bit_width` based on
45/// the selected [`BitWidth`] strategy and then constructs the thread-safe vector.
46///
47/// # Example
48///
49/// ```
50/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
51/// use compressed_intvec::prelude::*;
52/// use compressed_intvec::fixed::{AtomicFixedVec, UAtomicFixedVec, BitWidth};
53///
54/// let data: &[u32] = &[10, 20, 30, 40, 50];
55///
56/// // The builder can infer the minimal bit width (6 bits for 50).
57/// let vec: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
58///     .build(data)?;
59///
60/// assert_eq!(vec.bit_width(), 6);
61///
62/// // Or a specific strategy can be chosen.
63/// let vec_pow2: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
64///     .bit_width(BitWidth::PowerOfTwo)
65///     .build(data)?;
66///
67/// assert_eq!(vec_pow2.bit_width(), 8);
68///
69/// // You can also specify an explicit bit width.
70/// let vec_explicit: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
71///    .bit_width(BitWidth::Explicit(10))
72///    .build(data)?;
73///
74/// assert_eq!(vec_explicit.bit_width(), 10);
75/// # Ok(())
76/// # }
77/// ```
78#[derive(Debug, Clone)]
79pub struct AtomicFixedVecBuilder<T: Storable<u64>> {
80    bit_width_strategy: BitWidth,
81    _phantom: PhantomData<T>,
82}
83
84impl<T> Default for AtomicFixedVecBuilder<T>
85where
86    T: Storable<u64>,
87{
88    fn default() -> Self {
89        Self {
90            bit_width_strategy: BitWidth::default(),
91            _phantom: PhantomData,
92        }
93    }
94}
95
96impl<T> AtomicFixedVecBuilder<T>
97where
98    T: Storable<u64> + Copy + ToPrimitive,
99{
100    /// Creates a new builder with the default [`BitWidth::Minimal`] strategy.
101    pub fn new() -> Self {
102        Self::default()
103    }
104
105    /// Sets the strategy for determining the number of bits for each element.
106    ///
107    /// This can be one of:
108    /// - [`BitWidth::Minimal`]: Automatically determines the minimal bit width needed.
109    /// - [`BitWidth::PowerOfTwo`]: Rounds up to the next power of two.
110    /// - [`BitWidth::Explicit`]: Uses the specified number of bits explicitly.
111    ///
112    /// # Note
113    ///
114    /// Choosing [`BitWidth::Minimal`] and [`BitWidth::PowerOfTwo`] introduces a one-time overhead
115    /// at construction time to find the maximum value in the input slice.
116    ///
117    /// # Performance
118    ///
119    /// Choosing [`BitWidth::PowerOfTwo`] allows for true atomic operations on the vector, resulting in
120    /// better performance for concurrent access patterns. However, it may use more space than necessary.
121    pub fn bit_width(mut self, strategy: BitWidth) -> Self {
122        self.bit_width_strategy = strategy;
123        self
124    }
125
126    /// Builds the [`AtomicFixedVec`] from a slice of data.
127    ///
128    /// This method consumes the builder and returns a new [`AtomicFixedVec`].
129    /// The initial data is populated using non-atomic writes, as the vector
130    /// is not yet shared during construction.
131    ///
132    /// # Errors
133    ///
134    /// Returns an [`Error`] if a value in the input is too large for the
135    /// specified `bit_width`, or if the parameters are invalid.
136    pub fn build(self, input: &[T]) -> Result<AtomicFixedVec<T>, Error> {
137        let bits_per_word = u64::BITS as usize;
138
139        // Determine the final bit width based on the chosen strategy.
140        let final_bit_width = match self.bit_width_strategy {
141            BitWidth::Explicit(n) => n,
142            _ => {
143                let max_val: u64 = input
144                    .iter()
145                    .map(|&val| T::into_word(val))
146                    .max()
147                    .unwrap_or(0);
148
149                let min_bits = if max_val == 0 {
150                    1
151                } else {
152                    bits_per_word - max_val.leading_zeros() as usize
153                };
154
155                match self.bit_width_strategy {
156                    BitWidth::Minimal => min_bits,
157                    BitWidth::PowerOfTwo => min_bits.next_power_of_two().min(bits_per_word),
158                    BitWidth::Explicit(_) => unreachable!(),
159                }
160            }
161        };
162
163        if !input.is_empty() && final_bit_width == 0 {
164            return Err(Error::InvalidParameters(
165                "bit_width cannot be zero for a non-empty vector".to_string(),
166            ));
167        }
168
169        // Create a new, zero-initialized AtomicFixedVec.
170        let mut atomic_vec = AtomicFixedVec::new(final_bit_width, input.len())?;
171
172        if input.is_empty() {
173            return Ok(atomic_vec);
174        }
175
176        // --- Initial data population using non-atomic writes ---
177        let limit = if final_bit_width < bits_per_word {
178            1u64 << final_bit_width
179        } else {
180            u64::MAX
181        };
182
183        for (i, &value_t) in input.iter().enumerate() {
184            let value_w = T::into_word(value_t);
185            if final_bit_width < bits_per_word && value_w >= limit {
186                return Err(Error::ValueTooLarge {
187                    value: value_w as u128,
188                    index: i,
189                    bit_width: final_bit_width,
190                });
191            }
192            // SAFETY: We are writing within the allocated bounds. The vector is
193            // not shared at this point, so non-atomic writes are safe and correct.
194            unsafe {
195                set_unchecked_non_atomic(
196                    &mut atomic_vec.storage,
197                    i,
198                    value_w,
199                    final_bit_width,
200                    atomic_vec.mask,
201                );
202            }
203        }
204
205        Ok(atomic_vec)
206    }
207}
208
209/// A non-atomic, unsafe helper to set a value in a slice of [`AtomicU64`].
210/// This is only used during the initial construction of the vector.
211///
212/// # Safety
213/// The caller must ensure that `index` is within bounds and that `value_w`
214/// fits within the configured `bit_width`.
215unsafe fn set_unchecked_non_atomic(
216    limbs: &mut [AtomicU64],
217    index: usize,
218    value: u64,
219    bit_width: usize,
220    mask: u64,
221) {
222    let bits_per_word = u64::BITS as usize;
223    let bit_pos = index * bit_width;
224    let word_index = bit_pos / bits_per_word;
225    let bit_offset = bit_pos % bits_per_word;
226
227    // Use `get_mut()` to get a mutable reference to the underlying `u64`.
228    // This is safe because we have exclusive access to the vector during building.
229    if bit_offset + bit_width <= bits_per_word {
230        let word = unsafe { limbs.get_unchecked_mut(word_index).get_mut() };
231        *word &= !(mask << bit_offset);
232        *word |= value << bit_offset;
233    } else {
234        // The value spans two words.
235        let low_word_ptr = unsafe { limbs.as_mut_ptr().add(word_index) };
236        let high_word_ptr = unsafe { limbs.as_mut_ptr().add(word_index + 1) };
237
238        let low_word = unsafe { (*low_word_ptr).get_mut() };
239        let high_word = unsafe { (*high_word_ptr).get_mut() };
240
241        *low_word &= !(u64::MAX << bit_offset);
242        *low_word |= value << bit_offset;
243
244        let bits_in_high = (bit_offset + bit_width) - bits_per_word;
245        let high_mask = (1u64 << bits_in_high).wrapping_sub(1);
246        *high_word &= !high_mask;
247        *high_word |= value >> (bits_per_word - bit_offset);
248    }
249}
compressed_intvec/fixed/atomic/builder.rs

compressed_intvec/fixed/atomic/
builder.rs
