20234062436

Committed 15 Dec 2025 01:32PM UTC coverage: 74.624% (-0.02%) from 74.641%

Build # 20234062436

Build Type

Pull #93

github

Committed by

web-flow

Commit Message

Merge ec6392f55 into 04a540e9b

Pull Request Pull Request #93: partial_array: Fix mmap support

Run Details

3 of 5 new or added lines in 1 file covered. (60.0%)

1 existing line in 1 file now uncovered.

4464 of 5982 relevant lines covered (74.62%)

122266230.13 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

79.71

/src/array/partial_array.rs

/*
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

//! Immutable [partial array](PartialArray) implementations.

use std::marker::PhantomData;

use mem_dbg::*;
use value_traits::slices::SliceByValue;

use crate::bits::BitVec;
use crate::dict::EliasFanoBuilder;
use crate::dict::elias_fano::EliasFano;
use crate::panic_if_out_of_bounds;
use crate::rank_sel::{Rank9, SelectZeroAdaptConst};
use crate::traits::{BitVecOps, BitVecOpsMut};
use crate::traits::{RankUnchecked, SuccUnchecked};

type DenseIndex = Rank9<BitVec<Box<[usize]>>>;

/// An internal index for sparse partial arrays.
///
/// We cannot use directly an [Elias–Fano](crate::dict::EliasFano) structure
/// because we need to keep track of the first invalid position; and we need to
/// keep track of the first invalid position because we want to implement just
/// [`SuccUnchecked`](crate::traits::SuccUnchecked) on the Elias–Fano structure,
/// because it requires just
/// [`SelectZeroUnchecked`](crate::traits::SelectZeroUnchecked), whereas
/// [`Succ`](crate::traits::Succ) would require
/// [`SelectUnchecked`](crate::traits::SelectUnchecked) as well.
#[doc(hidden)]
#[derive(Debug, Clone, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct SparseIndex<D> {
    ef: EliasFano<SelectZeroAdaptConst<BitVec<D>, D, 12, 3>>,
    /// self.ef should be not be queried for values >= self.first_invalid_position
    first_invalid_pos: usize,
}

/// Builder for creating an immutable partial array.
///
/// The builder allows you to specify the array length and then add
/// (position, value) pairs. Positions must be added in strictly
/// increasing order.
///
/// To get a builder you can use either [new_dense] or [new_sparse].
#[derive(Debug, Clone, MemDbg, MemSize)]
pub struct PartialArrayBuilder<T, B> {
    builder: B,
    values: Vec<T>,
    len: usize,
    min_next_pos: usize,
}

/// Creates a new builder for a dense partial array of the given length.
///
/// A dense partial array stores a bit vector of the given length to mark
/// which positions contain values, and use ranking on this bit vector to
/// map positions to indices in a contiguous value array.
///
/// If your set of values is really sparse, consider using a
/// [sparse partial array](new_sparse).
///
/// # Examples
///
/// ```rust
/// use sux::array::partial_array;
///
/// let mut builder = partial_array::new_dense(10);
/// builder.set(1, "foo");
/// builder.set(2, "hello");
/// builder.set(7, "world");
///
/// let array = builder.build();
/// assert_eq!(array.get(1), Some(&"foo"));
/// assert_eq!(array.get(2), Some(&"hello"));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(&"world"));
/// ```
pub fn new_dense<T>(len: usize) -> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    PartialArrayBuilder {
        builder: BitVec::new(len).into(),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    /// Sets a value at the given position.
    ///
    /// The provided position must be greater than the last position set.
    pub fn set(&mut self, position: usize, value: T) {
        if position < self.min_next_pos {
            panic!(
                "Positions must be set in increasing order: got {} after {}",
                position,
                self.min_next_pos - 1
            );
        }
        panic_if_out_of_bounds!(position, self.len);
        // SAFETY: position < len
        unsafe {
            self.builder.set_unchecked(position, true);
        }
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

    /// Builds the immutable dense partial array.
    pub fn build(self) -> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {
        let (bit_vec, values) = (self.builder, self.values);
        let rank9 = Rank9::new(bit_vec);
        let values = values.into_boxed_slice();

        PartialArray {
            index: rank9,
            values,
            _marker: PhantomData,
        }
    }
}

/// Creates a new builder for a sparse partial array of the given length.
///
/// A sparse partial array stores the non-empty positions of the array in an
/// [Elias-Fano](crate::dict::EliasFano) structure.
///
/// If your set of values is really dense, consider using a [dense partial
/// array](new_dense).
///
/// # Examples
///
/// ```rust
/// use sux::array::partial_array;
///
/// let mut builder = partial_array::new_sparse(10, 3);
/// builder.set(1, "foo");
/// builder.set(2, "hello");
/// builder.set(7, "world");
///
/// let array = builder.build();
/// assert_eq!(array.get(1), Some(&"foo"));
/// assert_eq!(array.get(2), Some(&"hello"));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(&"world"));
/// ```
///
/// Note that you must specify the number of values in advance.
pub fn new_sparse<T>(len: usize, num_values: usize) -> PartialArrayBuilder<T, EliasFanoBuilder> {
    PartialArrayBuilder {
        builder: EliasFanoBuilder::new(num_values, len),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, EliasFanoBuilder> {
    /// Sets a value at the given position.
    ///
    /// The provided position must be greater than the last position
    /// set.
    pub fn set(&mut self, position: usize, value: T) {
        if position < self.min_next_pos {
            panic!(
                "Positions must be set in increasing order: got {} after {}",
                position,
                self.min_next_pos - 1
            );
        }
        panic_if_out_of_bounds!(position, self.len);
        // SAFETY: conditions have been just checked.
        unsafe { self.builder.push_unchecked(position) };
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

    /// Builds the immutable sparse partial array.
    pub fn build(self) -> PartialArray<T, SparseIndex<Box<[usize]>>> {
        let (builder, values) = (self.builder, self.values);
        let ef_dict = builder.build_with_dict();
        let values = values.into_boxed_slice();

        PartialArray {
            index: SparseIndex {
                ef: ef_dict,
                first_invalid_pos: self.min_next_pos,
            },
            values,
            _marker: PhantomData,
        }
    }
}

/// Extends the builder with an iterator of (position, value) pairs.
///
/// Position must be in strictly increasing order. The first returned
/// position must be greater than the last position set.
impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {
        for (pos, val) in iter {
            self.set(pos, val);
        }
    }
}

/// Extends the builder with an iterator of (position, value) pairs.
///
/// Position must be in strictly increasing order. The first returned
/// position must be greater than the last position set.
impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, EliasFanoBuilder> {
    fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {
        for (pos, val) in iter {
            self.set(pos, val);
        }
    }
}

/// An immutable partial array that supports efficient queries
/// in compacted storage.
///
/// This structure stores a *partial array*—an array in which only
/// some positions contain values. There is a [dense](new_dense)
/// and a [sparse](new_sparse) implementation with different
/// space/time trade-offs.
///
/// For convenience, this structure implements
/// [`SliceByValue`](crate::traits::slices::SliceByValue).
///
/// See [`PartialArrayBuilder`] for details on how to create a partial array.
#[derive(Debug, Clone, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct PartialArray<T, P, V: AsRef<[T]> = Box<[T]>> {
    index: P,
    values: V,
    _marker: PhantomData<T>,
}

impl<T, P, V: AsRef<[T]>> PartialArray<T, P, V> {
    /// Returns the number of values stored in the array.
    #[inline(always)]
    pub fn num_values(&self) -> usize {
        self.values.as_ref().len()
    }
}

impl<T, V: AsRef<[T]>> PartialArray<T, DenseIndex, V> {
    /// Returns the total length of the array.
    ///
    /// This is the length that was specified when creating the builder,
    /// not the number of values actually stored.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.index.len()
    }

    /// Returns true if the array length is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Gets a reference to the value at the given position.
    ///
    /// Returns `Some(&value)` if a value is present at the position,
    /// or `None` if no value was stored there.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sux::array::partial_array;
    /// let mut builder = partial_array::new_dense(10);
    /// builder.set(5, 42);
    ///
    /// let array = builder.build();
    /// assert_eq!(array.get(5), Some(&42));
    /// assert_eq!(array.get(6), None);
    /// ```
    pub fn get(&self, position: usize) -> Option<&T> {
        panic_if_out_of_bounds!(position, self.len());
        // Check if there's a value at this position
        // SAFETY: position < len()
        if !unsafe { self.index.get_unchecked(position) } {
            return None;
        }

        // Use ranking to find the index in the values array
        // SAFETY: position < len()
        let value_index = unsafe { self.index.rank_unchecked(position) };

        // SAFETY: necessarily value_index < num_values().
        Some(unsafe { self.values.as_ref().get_unchecked(value_index) })
    }
}

impl<T, D: AsRef<[usize]>, V: AsRef<[T]>> PartialArray<T, SparseIndex<D>, V> {
    /// Returns the total length of the array.
    ///
    /// This is the length that was specified when creating the builder,
    /// not the number of values actually stored.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.index.ef.upper_bound()
    }

    /// Returns true if the array len is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.index.ef.len() == 0
    }

    /// Gets a reference to the value at the given position.
    ///
    /// Returns `Some(&value)` if a value is present at the position,
    /// or `None` if no value was stored there.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sux::array::partial_array;
    /// let mut builder = partial_array::new_sparse(10, 1);
    /// builder.set(5, 42);
    ///
    /// let array = builder.build();
    /// assert_eq!(array.get(5), Some(&42));
    /// assert_eq!(array.get(6), None);
    /// ```
    pub fn get(&self, position: usize) -> Option<&T> {
        if position >= self.index.first_invalid_pos {
            panic_if_out_of_bounds!(position, self.len());
            return None;
        }
        // Check if there's a value at this position
        // SAFETY: position <= last set position
        let (index, pos) = unsafe { self.index.ef.succ_unchecked::<false>(position) };

        if pos != position {
            None
        } else {
            // SAFETY: necessarily value_index < num values.
            Some(unsafe { self.values.as_ref().get_unchecked(index) })
        }
    }
}

impl<T: Clone, P, V: AsRef<[T]>> SliceByValue for PartialArray<T, P, V> {
    type Value = T;

    fn len(&self) -> usize {
        self.values.as_ref().len()
    }

    unsafe fn get_value_unchecked(&self, index: usize) -> Self::Value {
        // SAFETY: the caller guarantees that index < len()
        unsafe { self.values.as_ref().get_unchecked(index) }.clone()
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	//! Immutable [partial array](PartialArray) implementations.
8
9	use std::marker::PhantomData;
10
11	use mem_dbg::*;
12	use value_traits::slices::SliceByValue;
13
14	use crate::bits::BitVec;
15	use crate::dict::EliasFanoBuilder;
16	use crate::dict::elias_fano::EliasFano;
17	use crate::panic_if_out_of_bounds;
18	use crate::rank_sel::{Rank9, SelectZeroAdaptConst};
19	use crate::traits::{BitVecOps, BitVecOpsMut};
20	use crate::traits::{RankUnchecked, SuccUnchecked};
21
22	type DenseIndex = Rank9<BitVec<Box<[usize]>>>;
23
24	/// An internal index for sparse partial arrays.
25	///
26	/// We cannot use directly an [Elias–Fano](crate::dict::EliasFano) structure
27	/// because we need to keep track of the first invalid position; and we need to
28	/// keep track of the first invalid position because we want to implement just
29	/// [`SuccUnchecked`](crate::traits::SuccUnchecked) on the Elias–Fano structure,
30	/// because it requires just
31	/// [`SelectZeroUnchecked`](crate::traits::SelectZeroUnchecked), whereas
32	/// [`Succ`](crate::traits::Succ) would require
33	/// [`SelectUnchecked`](crate::traits::SelectUnchecked) as well.
34	#[doc(hidden)]
35	#[derive(Debug, Clone, MemDbg, MemSize)]
36	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
37	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
38	pub struct SparseIndex<D> {
39	ef: EliasFano<SelectZeroAdaptConst<BitVec<D>, D, 12, 3>>,
40	/// self.ef should be not be queried for values >= self.first_invalid_position
41	first_invalid_pos: usize,
42	}
43
44	/// Builder for creating an immutable partial array.
45	///
46	/// The builder allows you to specify the array length and then add
47	/// (position, value) pairs. Positions must be added in strictly
48	/// increasing order.
49	///
50	/// To get a builder you can use either [new_dense] or [new_sparse].
51	#[derive(Debug, Clone, MemDbg, MemSize)]
52	pub struct PartialArrayBuilder<T, B> {
53	builder: B,
54	values: Vec<T>,
55	len: usize,
56	min_next_pos: usize,
57	}
58
59	/// Creates a new builder for a dense partial array of the given length.
60	///
61	/// A dense partial array stores a bit vector of the given length to mark
62	/// which positions contain values, and use ranking on this bit vector to
63	/// map positions to indices in a contiguous value array.
64	///
65	/// If your set of values is really sparse, consider using a
66	/// [sparse partial array](new_sparse).
67	///
68	/// # Examples
69	///
70	/// ```rust
71	/// use sux::array::partial_array;
72	///
73	/// let mut builder = partial_array::new_dense(10);
74	/// builder.set(1, "foo");
75	/// builder.set(2, "hello");
76	/// builder.set(7, "world");
77	///
78	/// let array = builder.build();
79	/// assert_eq!(array.get(1), Some(&"foo"));
80	/// assert_eq!(array.get(2), Some(&"hello"));
81	/// assert_eq!(array.get(3), None);
82	/// assert_eq!(array.get(7), Some(&"world"));
83	/// ```
84	pub fn new_dense<T>(len: usize) -> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {	6✔
85	PartialArrayBuilder {
86	builder: BitVec::new(len).into(),	24✔
87	values: vec![],	6✔
88	len,
89	min_next_pos: 0,
90	}
91	}
92
93	impl<T> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
94	/// Sets a value at the given position.
95	///
96	/// The provided position must be greater than the last position set.
97	pub fn set(&mut self, position: usize, value: T) {	7✔
98	if position < self.min_next_pos {	7✔
99	panic!(	1✔
100	"Positions must be set in increasing order: got {} after {}",	×
101	position,	×
102	self.min_next_pos - 1	1✔
103	);
104	}
105	panic_if_out_of_bounds!(position, self.len);	18✔
106	// SAFETY: position < len
107	unsafe {
108	self.builder.set_unchecked(position, true);	10✔
109	}
110	self.values.push(value);	15✔
111	self.min_next_pos = position + 1;	5✔
112	}
113
114	/// Builds the immutable dense partial array.
115	pub fn build(self) -> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {	4✔
116	let (bit_vec, values) = (self.builder, self.values);	12✔
117	let rank9 = Rank9::new(bit_vec);	12✔
118	let values = values.into_boxed_slice();	12✔
119
120	PartialArray {
121	index: rank9,
122	values,
123	_marker: PhantomData,
124	}
125	}
126	}
127
128	/// Creates a new builder for a sparse partial array of the given length.
129	///
130	/// A sparse partial array stores the non-empty positions of the array in an
131	/// [Elias-Fano](crate::dict::EliasFano) structure.
132	///
133	/// If your set of values is really dense, consider using a [dense partial
134	/// array](new_dense).
135	///
136	/// # Examples
137	///
138	/// ```rust
139	/// use sux::array::partial_array;
140	///
141	/// let mut builder = partial_array::new_sparse(10, 3);
142	/// builder.set(1, "foo");
143	/// builder.set(2, "hello");
144	/// builder.set(7, "world");
145	///
146	/// let array = builder.build();
147	/// assert_eq!(array.get(1), Some(&"foo"));
148	/// assert_eq!(array.get(2), Some(&"hello"));
149	/// assert_eq!(array.get(3), None);
150	/// assert_eq!(array.get(7), Some(&"world"));
151	/// ```
152	///
153	/// Note that you must specify the number of values in advance.
154	pub fn new_sparse<T>(len: usize, num_values: usize) -> PartialArrayBuilder<T, EliasFanoBuilder> {	7✔
155	PartialArrayBuilder {
156	builder: EliasFanoBuilder::new(num_values, len),	28✔
157	values: vec![],	7✔
158	len,
159	min_next_pos: 0,
160	}
161	}
162
163	impl<T> PartialArrayBuilder<T, EliasFanoBuilder> {
164	/// Sets a value at the given position.
165	///
166	/// The provided position must be greater than the last position
167	/// set.
168	pub fn set(&mut self, position: usize, value: T) {	10✔
169	if position < self.min_next_pos {	10✔
170	panic!(	1✔
171	"Positions must be set in increasing order: got {} after {}",	×
172	position,	×
173	self.min_next_pos - 1	1✔
174	);
175	}
176	panic_if_out_of_bounds!(position, self.len);	27✔
177	// SAFETY: conditions have been just checked.
178	unsafe { self.builder.push_unchecked(position) };	24✔
179	self.values.push(value);	24✔
180	self.min_next_pos = position + 1;	8✔
181	}
182
183	/// Builds the immutable sparse partial array.
184	pub fn build(self) -> PartialArray<T, SparseIndex<Box<[usize]>>> {	5✔
185	let (builder, values) = (self.builder, self.values);	15✔
186	let ef_dict = builder.build_with_dict();	15✔
187	let values = values.into_boxed_slice();	15✔
188
189	PartialArray {
190	index: SparseIndex {	10✔
191	ef: ef_dict,
192	first_invalid_pos: self.min_next_pos,
193	},
194	values,
195	_marker: PhantomData,
196	}
197	}
198	}
199
200	/// Extends the builder with an iterator of (position, value) pairs.
201	///
202	/// Position must be in strictly increasing order. The first returned
203	/// position must be greater than the last position set.
204	impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
205	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
206	for (pos, val) in iter {	×
207	self.set(pos, val);	×
208	}
209	}
210	}
211
212	/// Extends the builder with an iterator of (position, value) pairs.
213	///
214	/// Position must be in strictly increasing order. The first returned
215	/// position must be greater than the last position set.
216	impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, EliasFanoBuilder> {
217	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
218	for (pos, val) in iter {	×
219	self.set(pos, val);	×
220	}
221	}
222	}
223
224	/// An immutable partial array that supports efficient queries
225	/// in compacted storage.
226	///
227	/// This structure stores a partial array—an array in which only
228	/// some positions contain values. There is a [dense](new_dense)
229	/// and a [sparse](new_sparse) implementation with different
230	/// space/time trade-offs.
231	///
232	/// For convenience, this structure implements
233	/// [`SliceByValue`](crate::traits::slices::SliceByValue).
234	///
235	/// See [`PartialArrayBuilder`] for details on how to create a partial array.
236	#[derive(Debug, Clone, MemDbg, MemSize)]
237	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
238	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
239	pub struct PartialArray<T, P, V: AsRef<[T]> = Box<[T]>> {
240	index: P,
241	values: V,
242	_marker: PhantomData<T>,
243	}
244
245	impl<T, P, V: AsRef<[T]>> PartialArray<T, P, V> {
246	/// Returns the number of values stored in the array.
247	#[inline(always)]
248	pub fn num_values(&self) -> usize {	8✔
249	self.values.as_ref().len()	16✔
250	}
251	}
252
253	impl<T, V: AsRef<[T]>> PartialArray<T, DenseIndex, V> {
254	/// Returns the total length of the array.
255	///
256	/// This is the length that was specified when creating the builder,
257	/// not the number of values actually stored.
258	#[inline(always)]
259	pub fn len(&self) -> usize {	1,014✔
260	self.index.len()	2,028✔
261	}
262
263	/// Returns true if the array length is 0.
264	#[inline(always)]
265	pub fn is_empty(&self) -> bool {	1✔
266	self.len() == 0	1✔
267	}
268
269	/// Gets a reference to the value at the given position.
270	///
271	/// Returns `Some(&value)` if a value is present at the position,
272	/// or `None` if no value was stored there.
273	///
274	/// # Examples
275	///
276	/// ```rust
277	/// use sux::array::partial_array;
278	/// let mut builder = partial_array::new_dense(10);
279	/// builder.set(5, 42);
280	///
281	/// let array = builder.build();
282	/// assert_eq!(array.get(5), Some(&42));
283	/// assert_eq!(array.get(6), None);
284	/// ```
285	pub fn get(&self, position: usize) -> Option<&T> {	1,011✔
286	panic_if_out_of_bounds!(position, self.len());	2,024✔
287	// Check if there's a value at this position
288	// SAFETY: position < len()
289	if !unsafe { self.index.get_unchecked(position) } {	2,020✔
290	return None;	1,006✔
291	}
292
293	// Use ranking to find the index in the values array
294	// SAFETY: position < len()
295	let value_index = unsafe { self.index.rank_unchecked(position) };	16✔
296
297	// SAFETY: necessarily value_index < num_values().
298	Some(unsafe { self.values.as_ref().get_unchecked(value_index) })	8✔
299	}
300	}
301
302	impl<T, D: AsRef<[usize]>, V: AsRef<[T]>> PartialArray<T, SparseIndex<D>, V> {
303	/// Returns the total length of the array.
304	///
305	/// This is the length that was specified when creating the builder,
306	/// not the number of values actually stored.
307	#[inline(always)]
308	pub fn len(&self) -> usize {	508✔
309	self.index.ef.upper_bound()	1,016✔
310	}
311
312	/// Returns true if the array len is 0.
313	#[inline(always)]
314	pub fn is_empty(&self) -> bool {	1✔
315	self.index.ef.len() == 0	1✔
316	}
317
318	/// Gets a reference to the value at the given position.
319	///
320	/// Returns `Some(&value)` if a value is present at the position,
321	/// or `None` if no value was stored there.
322	///
323	/// # Examples
324	///
325	/// ```rust
326	/// use sux::array::partial_array;
327	/// let mut builder = partial_array::new_sparse(10, 1);
328	/// builder.set(5, 42);
329	///
330	/// let array = builder.build();
331	/// assert_eq!(array.get(5), Some(&42));
332	/// assert_eq!(array.get(6), None);
333	/// ```
334	pub fn get(&self, position: usize) -> Option<&T> {	1,031✔
335	if position >= self.index.first_invalid_pos {	1,031✔
336	panic_if_out_of_bounds!(position, self.len());	1,014✔
337	return None;	505✔
338	}
339	// Check if there's a value at this position
340	// SAFETY: position <= last set position
341	let (index, pos) = unsafe { self.index.ef.succ_unchecked::<false>(position) };	2,100✔
342
343	if pos != position {	525✔
344	None	515✔
345	} else {
346	// SAFETY: necessarily value_index < num values.
347	Some(unsafe { self.values.as_ref().get_unchecked(index) })	20✔
348	}
349	}
350	}
351
352	impl<T: Clone, P, V: AsRef<[T]>> SliceByValue for PartialArray<T, P, V> {
353	type Value = T;
354
355	fn len(&self) -> usize {	×
NEW 356	self.values.as_ref().len()	×
357	}
358
359	unsafe fn get_value_unchecked(&self, index: usize) -> Self::Value {	×
360	// SAFETY: the caller guarantees that index < len()
NEW 361	unsafe { self.values.as_ref().get_unchecked(index) }.clone()	×
362	}
363	}

vigna / sux-rs / 20234062436

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous