| // This file is part of ICU4X. For terms of use, please see the file |
| // called LICENSE at the top level of the ICU4X source tree |
| // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). |
| |
| use super::FlexZeroVec; |
| use crate::ZeroVecError; |
| use alloc::vec::Vec; |
| use core::cmp::Ordering; |
| use core::fmt; |
| use core::mem; |
| use core::ops::Range; |
| |
| const USIZE_WIDTH: usize = mem::size_of::<usize>(); |
| |
| /// A zero-copy "slice" that efficiently represents `[usize]`. |
| #[repr(packed)] |
| pub struct FlexZeroSlice { |
| // Hard Invariant: 1 <= width <= USIZE_WIDTH (which is target_pointer_width) |
| // Soft Invariant: width == the width of the largest element |
| width: u8, |
| // Hard Invariant: data.len() % width == 0 |
| data: [u8], |
| } |
| |
| impl fmt::Debug for FlexZeroSlice { |
| fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| self.to_vec().fmt(f) |
| } |
| } |
| |
| impl PartialEq for FlexZeroSlice { |
| fn eq(&self, other: &Self) -> bool { |
| self.width == other.width && self.data == other.data |
| } |
| } |
| impl Eq for FlexZeroSlice {} |
| |
| /// Helper function to decode a little-endian "chunk" (byte slice of a specific length) |
| /// into a `usize`. We cannot call `usize::from_le_bytes` directly because that function |
| /// requires the high bits to be set to 0. |
| #[inline] |
| pub(crate) fn chunk_to_usize(chunk: &[u8], width: usize) -> usize { |
| debug_assert_eq!(chunk.len(), width); |
| let mut bytes = [0; USIZE_WIDTH]; |
| #[allow(clippy::indexing_slicing)] // protected by debug_assert above |
| bytes[0..width].copy_from_slice(chunk); |
| usize::from_le_bytes(bytes) |
| } |
| |
| impl FlexZeroSlice { |
| /// Constructs a new empty [`FlexZeroSlice`]. |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroSlice; |
| /// |
| /// const EMPTY_SLICE: &FlexZeroSlice = FlexZeroSlice::new_empty(); |
| /// |
| /// assert!(EMPTY_SLICE.is_empty()); |
| /// assert_eq!(EMPTY_SLICE.len(), 0); |
| /// assert_eq!(EMPTY_SLICE.first(), None); |
| /// ``` |
| #[inline] |
| pub const fn new_empty() -> &'static Self { |
| const ARR: &[u8] = &[1u8]; |
| // Safety: The slice is a valid empty `FlexZeroSlice` |
| unsafe { Self::from_byte_slice_unchecked(ARR) } |
| } |
| |
| /// Safely constructs a [`FlexZeroSlice`] from a byte array. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroSlice; |
| /// |
| /// const FZS: &FlexZeroSlice = match FlexZeroSlice::parse_byte_slice(&[ |
| /// 2, // width |
| /// 0x42, 0x00, // first value |
| /// 0x07, 0x09, // second value |
| /// 0xFF, 0xFF, // third value |
| /// ]) { |
| /// Ok(v) => v, |
| /// Err(_) => panic!("invalid bytes"), |
| /// }; |
| /// |
| /// assert!(!FZS.is_empty()); |
| /// assert_eq!(FZS.len(), 3); |
| /// assert_eq!(FZS.first(), Some(0x0042)); |
| /// assert_eq!(FZS.get(0), Some(0x0042)); |
| /// assert_eq!(FZS.get(1), Some(0x0907)); |
| /// assert_eq!(FZS.get(2), Some(0xFFFF)); |
| /// assert_eq!(FZS.get(3), None); |
| /// assert_eq!(FZS.last(), Some(0xFFFF)); |
| /// ``` |
| pub const fn parse_byte_slice(bytes: &[u8]) -> Result<&Self, ZeroVecError> { |
| let (width_u8, data) = match bytes.split_first() { |
| Some(v) => v, |
| None => { |
| return Err(ZeroVecError::InvalidLength { |
| ty: "FlexZeroSlice", |
| len: 0, |
| }) |
| } |
| }; |
| let width = *width_u8 as usize; |
| if width < 1 || width > USIZE_WIDTH { |
| return Err(ZeroVecError::ParseError { |
| ty: "FlexZeroSlice", |
| }); |
| } |
| if data.len() % width != 0 { |
| return Err(ZeroVecError::InvalidLength { |
| ty: "FlexZeroSlice", |
| len: bytes.len(), |
| }); |
| } |
| // Safety: All hard invariants have been checked. |
| // Note: The soft invariant requires a linear search that we don't do here. |
| Ok(unsafe { Self::from_byte_slice_unchecked(bytes) }) |
| } |
| |
| /// Constructs a [`FlexZeroSlice`] without checking invariants. |
| /// |
| /// # Panics |
| /// |
| /// Panics if `bytes` is empty. |
| /// |
| /// # Safety |
| /// |
| /// Must be called on a valid [`FlexZeroSlice`] byte array. |
| #[inline] |
| pub const unsafe fn from_byte_slice_unchecked(bytes: &[u8]) -> &Self { |
| // Safety: The DST of FlexZeroSlice is a pointer to the `width` element and has a metadata |
| // equal to the length of the `data` field, which will be one less than the length of the |
| // overall array. |
| #[allow(clippy::panic)] // panic is documented in function contract |
| if bytes.is_empty() { |
| panic!("from_byte_slice_unchecked called with empty slice") |
| } |
| let slice = core::ptr::slice_from_raw_parts(bytes.as_ptr(), bytes.len() - 1); |
| &*(slice as *const Self) |
| } |
| |
| #[inline] |
| pub(crate) unsafe fn from_byte_slice_mut_unchecked(bytes: &mut [u8]) -> &mut Self { |
| // Safety: See comments in `from_byte_slice_unchecked` |
| let remainder = core::ptr::slice_from_raw_parts_mut(bytes.as_mut_ptr(), bytes.len() - 1); |
| &mut *(remainder as *mut Self) |
| } |
| |
| /// Returns this slice as its underlying `&[u8]` byte buffer representation. |
| /// |
| /// Useful for serialization. |
| /// |
| /// # Example |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroSlice; |
| /// |
| /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80]; |
| /// let fzv = FlexZeroSlice::parse_byte_slice(bytes).expect("valid bytes"); |
| /// |
| /// assert_eq!(bytes, fzv.as_bytes()); |
| /// ``` |
| #[inline] |
| pub fn as_bytes(&self) -> &[u8] { |
| // Safety: See comments in `from_byte_slice_unchecked` |
| unsafe { |
| core::slice::from_raw_parts(self as *const Self as *const u8, self.data.len() + 1) |
| } |
| } |
| |
| /// Borrows this `FlexZeroSlice` as a [`FlexZeroVec::Borrowed`]. |
| #[inline] |
| pub const fn as_flexzerovec(&self) -> FlexZeroVec { |
| FlexZeroVec::Borrowed(self) |
| } |
| |
| /// Returns the number of elements in the `FlexZeroSlice`. |
| #[inline] |
| pub fn len(&self) -> usize { |
| self.data.len() / self.get_width() |
| } |
| |
| #[inline] |
| pub(crate) fn get_width(&self) -> usize { |
| usize::from(self.width) |
| } |
| |
| /// Returns whether there are zero elements in the `FlexZeroSlice`. |
| #[inline] |
| pub fn is_empty(&self) -> bool { |
| self.data.len() == 0 |
| } |
| |
| /// Gets the element at `index`, or `None` if `index >= self.len()`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroVec; |
| /// |
| /// let fzv: FlexZeroVec = [22, 33].iter().copied().collect(); |
| /// assert_eq!(fzv.get(0), Some(22)); |
| /// assert_eq!(fzv.get(1), Some(33)); |
| /// assert_eq!(fzv.get(2), None); |
| /// ``` |
| #[inline] |
| pub fn get(&self, index: usize) -> Option<usize> { |
| if index >= self.len() { |
| None |
| } else { |
| Some(unsafe { self.get_unchecked(index) }) |
| } |
| } |
| |
| /// Gets the element at `index` as a chunk of bytes, or `None` if `index >= self.len()`. |
| #[inline] |
| pub(crate) fn get_chunk(&self, index: usize) -> Option<&[u8]> { |
| let w = self.get_width(); |
| self.data.get(index * w..index * w + w) |
| } |
| |
| /// Gets the element at `index` without checking bounds. |
| /// |
| /// # Safety |
| /// |
| /// `index` must be in-range. |
| #[inline] |
| pub unsafe fn get_unchecked(&self, index: usize) -> usize { |
| match self.width { |
| 1 => *self.data.get_unchecked(index) as usize, |
| 2 => { |
| let ptr = self.data.as_ptr().add(index * 2); |
| u16::from_le_bytes(core::ptr::read(ptr as *const [u8; 2])) as usize |
| } |
| _ => { |
| let mut bytes = [0; USIZE_WIDTH]; |
| let w = self.get_width(); |
| assert!(w <= USIZE_WIDTH); |
| let ptr = self.data.as_ptr().add(index * w); |
| core::ptr::copy_nonoverlapping(ptr, bytes.as_mut_ptr(), w); |
| usize::from_le_bytes(bytes) |
| } |
| } |
| } |
| |
| /// Gets the first element of the slice, or `None` if the slice is empty. |
| #[inline] |
| pub fn first(&self) -> Option<usize> { |
| let w = self.get_width(); |
| self.data.get(0..w).map(|chunk| chunk_to_usize(chunk, w)) |
| } |
| |
| /// Gets the last element of the slice, or `None` if the slice is empty. |
| #[inline] |
| pub fn last(&self) -> Option<usize> { |
| let l = self.data.len(); |
| if l == 0 { |
| None |
| } else { |
| let w = self.get_width(); |
| self.data |
| .get(l - w..l) |
| .map(|chunk| chunk_to_usize(chunk, w)) |
| } |
| } |
| |
| /// Gets an iterator over the elements of the slice as `usize`. |
| #[inline] |
| pub fn iter( |
| &self, |
| ) -> impl DoubleEndedIterator<Item = usize> + '_ + ExactSizeIterator<Item = usize> { |
| let w = self.get_width(); |
| self.data |
| .chunks_exact(w) |
| .map(move |chunk| chunk_to_usize(chunk, w)) |
| } |
| |
| /// Gets an iterator over pairs of elements. |
| /// |
| /// The second element of the final pair is `None`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroVec; |
| /// |
| /// let nums: &[usize] = &[211, 281, 421, 461]; |
| /// let fzv: FlexZeroVec = nums.iter().copied().collect(); |
| /// |
| /// let mut pairs_it = fzv.iter_pairs(); |
| /// |
| /// assert_eq!(pairs_it.next(), Some((211, Some(281)))); |
| /// assert_eq!(pairs_it.next(), Some((281, Some(421)))); |
| /// assert_eq!(pairs_it.next(), Some((421, Some(461)))); |
| /// assert_eq!(pairs_it.next(), Some((461, None))); |
| /// assert_eq!(pairs_it.next(), None); |
| /// ``` |
| pub fn iter_pairs(&self) -> impl Iterator<Item = (usize, Option<usize>)> + '_ { |
| self.iter().zip(self.iter().skip(1).map(Some).chain([None])) |
| } |
| |
| /// Creates a `Vec<usize>` from a [`FlexZeroSlice`] (or `FlexZeroVec`). |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroVec; |
| /// |
| /// let nums: &[usize] = &[211, 281, 421, 461]; |
| /// let fzv: FlexZeroVec = nums.iter().copied().collect(); |
| /// let vec: Vec<usize> = fzv.to_vec(); |
| /// |
| /// assert_eq!(nums, vec.as_slice()); |
| /// ``` |
| #[inline] |
| pub fn to_vec(&self) -> Vec<usize> { |
| self.iter().collect() |
| } |
| |
| /// Binary searches a sorted `FlexZeroSlice` for the given `usize` value. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroVec; |
| /// |
| /// let nums: &[usize] = &[211, 281, 421, 461]; |
| /// let fzv: FlexZeroVec = nums.iter().copied().collect(); |
| /// |
| /// assert_eq!(fzv.binary_search(0), Err(0)); |
| /// assert_eq!(fzv.binary_search(211), Ok(0)); |
| /// assert_eq!(fzv.binary_search(250), Err(1)); |
| /// assert_eq!(fzv.binary_search(281), Ok(1)); |
| /// assert_eq!(fzv.binary_search(300), Err(2)); |
| /// assert_eq!(fzv.binary_search(421), Ok(2)); |
| /// assert_eq!(fzv.binary_search(450), Err(3)); |
| /// assert_eq!(fzv.binary_search(461), Ok(3)); |
| /// assert_eq!(fzv.binary_search(462), Err(4)); |
| /// ``` |
| #[inline] |
| pub fn binary_search(&self, needle: usize) -> Result<usize, usize> { |
| self.binary_search_by(|probe| probe.cmp(&needle)) |
| } |
| |
| /// Binary searches a sorted range of a `FlexZeroSlice` for the given `usize` value. |
| /// |
| /// The indices in the return value are relative to the start of the range. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use zerovec::vecs::FlexZeroVec; |
| /// |
| /// // Make a FlexZeroVec with two sorted ranges: 0..3 and 3..5 |
| /// let nums: &[usize] = &[111, 222, 444, 333, 555]; |
| /// let fzv: FlexZeroVec = nums.iter().copied().collect(); |
| /// |
| /// // Search in the first range: |
| /// assert_eq!(fzv.binary_search_in_range(0, 0..3), Some(Err(0))); |
| /// assert_eq!(fzv.binary_search_in_range(111, 0..3), Some(Ok(0))); |
| /// assert_eq!(fzv.binary_search_in_range(199, 0..3), Some(Err(1))); |
| /// assert_eq!(fzv.binary_search_in_range(222, 0..3), Some(Ok(1))); |
| /// assert_eq!(fzv.binary_search_in_range(399, 0..3), Some(Err(2))); |
| /// assert_eq!(fzv.binary_search_in_range(444, 0..3), Some(Ok(2))); |
| /// assert_eq!(fzv.binary_search_in_range(999, 0..3), Some(Err(3))); |
| /// |
| /// // Search in the second range: |
| /// assert_eq!(fzv.binary_search_in_range(0, 3..5), Some(Err(0))); |
| /// assert_eq!(fzv.binary_search_in_range(333, 3..5), Some(Ok(0))); |
| /// assert_eq!(fzv.binary_search_in_range(399, 3..5), Some(Err(1))); |
| /// assert_eq!(fzv.binary_search_in_range(555, 3..5), Some(Ok(1))); |
| /// assert_eq!(fzv.binary_search_in_range(999, 3..5), Some(Err(2))); |
| /// |
| /// // Out-of-bounds range: |
| /// assert_eq!(fzv.binary_search_in_range(0, 4..6), None); |
| /// ``` |
| #[inline] |
| pub fn binary_search_in_range( |
| &self, |
| needle: usize, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| self.binary_search_in_range_by(|probe| probe.cmp(&needle), range) |
| } |
| |
| /// Binary searches a sorted `FlexZeroSlice` according to a predicate function. |
| #[inline] |
| pub fn binary_search_by( |
| &self, |
| predicate: impl FnMut(usize) -> Ordering, |
| ) -> Result<usize, usize> { |
| debug_assert!(self.len() <= self.data.len()); |
| // Safety: self.len() <= self.data.len() |
| let scaled_slice = unsafe { self.data.get_unchecked(0..self.len()) }; |
| self.binary_search_impl(predicate, scaled_slice) |
| } |
| |
| /// Binary searches a sorted range of a `FlexZeroSlice` according to a predicate function. |
| /// |
| /// The indices in the return value are relative to the start of the range. |
| #[inline] |
| pub fn binary_search_in_range_by( |
| &self, |
| predicate: impl FnMut(usize) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| // Note: We need to check bounds separately, since `self.data.get(range)` does not return |
| // bounds errors, since it is indexing directly into the upscaled data array |
| if range.start > self.len() || range.end > self.len() { |
| return None; |
| } |
| let scaled_slice = self.data.get(range)?; |
| Some(self.binary_search_impl(predicate, scaled_slice)) |
| } |
| |
| /// Binary searches a `FlexZeroSlice` by its indices. |
| /// |
| /// The `predicate` function is passed in-bounds indices into the `FlexZeroSlice`. |
| #[inline] |
| pub fn binary_search_with_index( |
| &self, |
| predicate: impl FnMut(usize) -> Ordering, |
| ) -> Result<usize, usize> { |
| debug_assert!(self.len() <= self.data.len()); |
| // Safety: self.len() <= self.data.len() |
| let scaled_slice = unsafe { self.data.get_unchecked(0..self.len()) }; |
| self.binary_search_with_index_impl(predicate, scaled_slice) |
| } |
| |
| /// Binary searches a range of a `FlexZeroSlice` by its indices. |
| /// |
| /// The `predicate` function is passed in-bounds indices into the `FlexZeroSlice`, which are |
| /// relative to the start of the entire slice. |
| /// |
| /// The indices in the return value are relative to the start of the range. |
| #[inline] |
| pub fn binary_search_in_range_with_index( |
| &self, |
| predicate: impl FnMut(usize) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| // Note: We need to check bounds separately, since `self.data.get(range)` does not return |
| // bounds errors, since it is indexing directly into the upscaled data array |
| if range.start > self.len() || range.end > self.len() { |
| return None; |
| } |
| let scaled_slice = self.data.get(range)?; |
| Some(self.binary_search_with_index_impl(predicate, scaled_slice)) |
| } |
| |
| /// # Safety |
| /// |
| /// `scaled_slice` must be a subslice of `self.data` |
| #[inline] |
| fn binary_search_impl( |
| &self, |
| mut predicate: impl FnMut(usize) -> Ordering, |
| scaled_slice: &[u8], |
| ) -> Result<usize, usize> { |
| self.binary_search_with_index_impl( |
| |index| { |
| // Safety: The contract of `binary_search_with_index_impl` says `index` is in bounds |
| let actual_probe = unsafe { self.get_unchecked(index) }; |
| predicate(actual_probe) |
| }, |
| scaled_slice, |
| ) |
| } |
| |
| /// `predicate` is passed a valid index as an argument. |
| /// |
| /// # Safety |
| /// |
| /// `scaled_slice` must be a subslice of `self.data` |
| fn binary_search_with_index_impl( |
| &self, |
| mut predicate: impl FnMut(usize) -> Ordering, |
| scaled_slice: &[u8], |
| ) -> Result<usize, usize> { |
| // This code is an absolute atrocity. This code is not a place of honor. This |
| // code is known to the State of California to cause cancer. |
| // |
| // Unfortunately, the stdlib's `binary_search*` functions can only operate on slices. |
| // We do not have a slice. We have something we can .get() and index on, but that is not |
| // a slice. |
| // |
| // The `binary_search*` functions also do not have a variant where they give you the element's |
| // index, which we could otherwise use to directly index `self`. |
| // We do have `self.indices`, but these are indices into a byte buffer, which cannot in |
| // isolation be used to recoup the logical index of the element they refer to. |
| // |
| // However, `binary_search_by()` provides references to the elements of the slice being iterated. |
| // Since the layout of Rust slices is well-defined, we can do pointer arithmetic on these references |
| // to obtain the index being used by the search. |
| // |
| // It's worth noting that the slice we choose to search is irrelevant, as long as it has the appropriate |
| // length. `self.indices` is defined to have length `self.len()`, so it is convenient to use |
| // here and does not require additional allocations. |
| // |
| // The alternative to doing this is to implement our own binary search. This is significantly less fun. |
| |
| // Note: We always use zero_index relative to the whole indices array, even if we are |
| // only searching a subslice of it. |
| let zero_index = self.data.as_ptr() as *const _ as usize; |
| scaled_slice.binary_search_by(|probe: &_| { |
| // Note: `scaled_slice` is a slice of u8 |
| let index = probe as *const _ as usize - zero_index; |
| predicate(index) |
| }) |
| } |
| } |
| |
| #[inline] |
| pub(crate) fn get_item_width(item_bytes: &[u8; USIZE_WIDTH]) -> usize { |
| USIZE_WIDTH - item_bytes.iter().rev().take_while(|b| **b == 0).count() |
| } |
| |
| /// Pre-computed information about a pending insertion operation. |
| /// |
| /// Do not create one of these directly; call `get_insert_info()`. |
| pub(crate) struct InsertInfo { |
| /// The bytes to be inserted, with zero-fill. |
| pub item_bytes: [u8; USIZE_WIDTH], |
| /// The new item width after insertion. |
| pub new_width: usize, |
| /// The new number of items in the vector: self.len() after insertion. |
| pub new_count: usize, |
| /// The new number of bytes required for the entire slice (self.data.len() + 1). |
| pub new_bytes_len: usize, |
| } |
| |
| impl FlexZeroSlice { |
| /// Compute the [`InsertInfo`] for inserting the specified item anywhere into the vector. |
| /// |
| /// # Panics |
| /// |
| /// Panics if inserting the element would require allocating more than `usize::MAX` bytes. |
| pub(crate) fn get_insert_info(&self, new_item: usize) -> InsertInfo { |
| let item_bytes = new_item.to_le_bytes(); |
| let item_width = get_item_width(&item_bytes); |
| let old_width = self.get_width(); |
| let new_width = core::cmp::max(old_width, item_width); |
| let new_count = 1 + (self.data.len() / old_width); |
| #[allow(clippy::unwrap_used)] // panic is documented in function contract |
| let new_bytes_len = new_count |
| .checked_mul(new_width) |
| .unwrap() |
| .checked_add(1) |
| .unwrap(); |
| InsertInfo { |
| item_bytes, |
| new_width, |
| new_count, |
| new_bytes_len, |
| } |
| } |
| |
| /// This function should be called on a slice with a data array `new_data_len` long |
| /// which previously held `new_count - 1` elements. |
| /// |
| /// After calling this function, all bytes in the slice will have been written. |
| pub(crate) fn insert_impl(&mut self, insert_info: InsertInfo, insert_index: usize) { |
| let InsertInfo { |
| item_bytes, |
| new_width, |
| new_count, |
| new_bytes_len, |
| } = insert_info; |
| debug_assert!(new_width <= USIZE_WIDTH); |
| debug_assert!(new_width >= self.get_width()); |
| debug_assert!(insert_index < new_count); |
| debug_assert_eq!(new_bytes_len, new_count * new_width + 1); |
| debug_assert_eq!(new_bytes_len, self.data.len() + 1); |
| // For efficiency, calculate how many items we can skip copying. |
| let lower_i = if new_width == self.get_width() { |
| insert_index |
| } else { |
| 0 |
| }; |
| // Copy elements starting from the end into the new empty section of the vector. |
| // Note: We could copy fully in place, but we need to set 0 bytes for the high bytes, |
| // so we stage the new value on the stack. |
| for i in (lower_i..new_count).rev() { |
| let bytes_to_write = if i == insert_index { |
| item_bytes |
| } else { |
| let j = if i > insert_index { i - 1 } else { i }; |
| debug_assert!(j < new_count - 1); |
| // Safety: j is in range (assertion on previous line), and it has not been |
| // overwritten yet since we are walking backwards. |
| unsafe { self.get_unchecked(j).to_le_bytes() } |
| }; |
| // Safety: The vector has capacity for `new_width` items at the new index, which is |
| // later in the array than the bytes that we read above. |
| unsafe { |
| core::ptr::copy_nonoverlapping( |
| bytes_to_write.as_ptr(), |
| self.data.as_mut_ptr().add(new_width * i), |
| new_width, |
| ); |
| } |
| } |
| self.width = new_width as u8; |
| } |
| } |
| |
| /// Pre-computed information about a pending removal operation. |
| /// |
| /// Do not create one of these directly; call `get_remove_info()` or `get_sorted_pop_info()`. |
| pub(crate) struct RemoveInfo { |
| /// The index of the item to be removed. |
| pub remove_index: usize, |
| /// The new item width after insertion. |
| pub new_width: usize, |
| /// The new number of items in the vector: self.len() after insertion. |
| pub new_count: usize, |
| /// The new number of bytes required for the entire slice (self.data.len() + 1). |
| pub new_bytes_len: usize, |
| } |
| |
| impl FlexZeroSlice { |
| /// Compute the [`RemoveInfo`] for removing the item at the specified index. |
| pub(crate) fn get_remove_info(&self, remove_index: usize) -> RemoveInfo { |
| debug_assert!(remove_index < self.len()); |
| // Safety: remove_index is in range (assertion on previous line) |
| let item_bytes = unsafe { self.get_unchecked(remove_index).to_le_bytes() }; |
| let item_width = get_item_width(&item_bytes); |
| let old_width = self.get_width(); |
| let old_count = self.data.len() / old_width; |
| let new_width = if item_width < old_width { |
| old_width |
| } else { |
| debug_assert_eq!(old_width, item_width); |
| // We might be removing the widest element. If so, we need to scale down. |
| let mut largest_width = 1; |
| for i in 0..old_count { |
| if i == remove_index { |
| continue; |
| } |
| // Safety: i is in range (between 0 and old_count) |
| let curr_bytes = unsafe { self.get_unchecked(i).to_le_bytes() }; |
| let curr_width = get_item_width(&curr_bytes); |
| largest_width = core::cmp::max(curr_width, largest_width); |
| } |
| largest_width |
| }; |
| let new_count = old_count - 1; |
| // Note: the following line won't overflow because we are making the slice shorter. |
| let new_bytes_len = new_count * new_width + 1; |
| RemoveInfo { |
| remove_index, |
| new_width, |
| new_count, |
| new_bytes_len, |
| } |
| } |
| |
| /// Returns the [`RemoveInfo`] for removing the last element. Should be called |
| /// on a slice sorted in ascending order. |
| /// |
| /// This is more efficient than `get_remove_info()` because it doesn't require a |
| /// linear traversal of the vector in order to calculate `new_width`. |
| pub(crate) fn get_sorted_pop_info(&self) -> RemoveInfo { |
| debug_assert!(!self.is_empty()); |
| let remove_index = self.len() - 1; |
| let old_count = self.len(); |
| let new_width = if old_count == 1 { |
| 1 |
| } else { |
| // Safety: the FlexZeroSlice has at least two elements |
| let largest_item = unsafe { self.get_unchecked(remove_index - 1).to_le_bytes() }; |
| get_item_width(&largest_item) |
| }; |
| let new_count = old_count - 1; |
| // Note: the following line won't overflow because we are making the slice shorter. |
| let new_bytes_len = new_count * new_width + 1; |
| RemoveInfo { |
| remove_index, |
| new_width, |
| new_count, |
| new_bytes_len, |
| } |
| } |
| |
| /// This function should be called on a valid slice. |
| /// |
| /// After calling this function, the slice data should be truncated to `new_data_len` bytes. |
| pub(crate) fn remove_impl(&mut self, remove_info: RemoveInfo) { |
| let RemoveInfo { |
| remove_index, |
| new_width, |
| new_count, |
| .. |
| } = remove_info; |
| debug_assert!(new_width <= self.get_width()); |
| debug_assert!(new_count < self.len()); |
| // For efficiency, calculate how many items we can skip copying. |
| let lower_i = if new_width == self.get_width() { |
| remove_index |
| } else { |
| 0 |
| }; |
| // Copy elements starting from the beginning to compress the vector to fewer bytes. |
| for i in lower_i..new_count { |
| let j = if i < remove_index { i } else { i + 1 }; |
| // Safety: j is in range because j <= new_count < self.len() |
| let bytes_to_write = unsafe { self.get_unchecked(j).to_le_bytes() }; |
| // Safety: The bytes are being copied to a section of the array that is not after |
| // the section of the array that currently holds the bytes. |
| unsafe { |
| core::ptr::copy_nonoverlapping( |
| bytes_to_write.as_ptr(), |
| self.data.as_mut_ptr().add(new_width * i), |
| new_width, |
| ); |
| } |
| } |
| self.width = new_width as u8; |
| } |
| } |
