summaryrefslogtreecommitdiffstats
path: root/vendor/zerovec/src/flexzerovec
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/zerovec/src/flexzerovec')
-rw-r--r--vendor/zerovec/src/flexzerovec/databake.rs49
-rw-r--r--vendor/zerovec/src/flexzerovec/mod.rs20
-rw-r--r--vendor/zerovec/src/flexzerovec/owned.rs350
-rw-r--r--vendor/zerovec/src/flexzerovec/serde.rs175
-rw-r--r--vendor/zerovec/src/flexzerovec/slice.rs717
-rw-r--r--vendor/zerovec/src/flexzerovec/vec.rs275
6 files changed, 1586 insertions, 0 deletions
diff --git a/vendor/zerovec/src/flexzerovec/databake.rs b/vendor/zerovec/src/flexzerovec/databake.rs
new file mode 100644
index 000000000..23bf156ef
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/databake.rs
@@ -0,0 +1,49 @@
+// 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::{FlexZeroSlice, FlexZeroVec};
+use databake::*;
+
+impl Bake for FlexZeroVec<'_> {
+ fn bake(&self, env: &CrateEnv) -> TokenStream {
+ env.insert("zerovec");
+ let bytes = self.as_bytes();
+ quote! { unsafe { ::zerovec::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[#(#bytes),*]).as_flexzerovec() } }
+ }
+}
+
+impl Bake for &FlexZeroSlice {
+ fn bake(&self, env: &CrateEnv) -> TokenStream {
+ env.insert("zerovec");
+ let bytes = self.as_bytes();
+ quote! { unsafe { ::zerovec::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[#(#bytes),*]) } }
+ }
+}
+
+#[test]
+fn test_baked_vec() {
+ test_bake!(
+ FlexZeroVec,
+ const: unsafe {
+ crate::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[
+ 2u8, 1u8, 0u8, 22u8, 0u8, 77u8, 1u8, 92u8, 17u8,
+ ])
+ .as_flexzerovec()
+ },
+ zerovec
+ );
+}
+
+#[test]
+fn test_baked_slice() {
+ test_bake!(
+ &FlexZeroSlice,
+ const: unsafe {
+ crate::vecs::FlexZeroSlice::from_byte_slice_unchecked(&[
+ 2u8, 1u8, 0u8, 22u8, 0u8, 77u8, 1u8, 92u8, 17u8,
+ ])
+ },
+ zerovec
+ );
+}
diff --git a/vendor/zerovec/src/flexzerovec/mod.rs b/vendor/zerovec/src/flexzerovec/mod.rs
new file mode 100644
index 000000000..b6d7e780a
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/mod.rs
@@ -0,0 +1,20 @@
+// 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 ).
+
+//! See [`FlexZeroVec`](crate::vecs::FlexZeroVec) for details.
+
+pub(crate) mod owned;
+pub(crate) mod slice;
+pub(crate) mod vec;
+
+#[cfg(feature = "databake")]
+mod databake;
+
+#[cfg(feature = "serde")]
+mod serde;
+
+pub use owned::FlexZeroVecOwned;
+pub(crate) use slice::chunk_to_usize;
+pub use slice::FlexZeroSlice;
+pub use vec::FlexZeroVec;
diff --git a/vendor/zerovec/src/flexzerovec/owned.rs b/vendor/zerovec/src/flexzerovec/owned.rs
new file mode 100644
index 000000000..1039c59ae
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/owned.rs
@@ -0,0 +1,350 @@
+// 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 alloc::vec;
+use alloc::vec::Vec;
+use core::fmt;
+use core::iter::FromIterator;
+use core::ops::Deref;
+
+use super::FlexZeroSlice;
+use super::FlexZeroVec;
+
+/// The fully-owned variant of [`FlexZeroVec`]. Contains all mutation methods.
+// Safety invariant: the inner bytes must deref to a valid `FlexZeroSlice`
+#[derive(Clone, PartialEq, Eq)]
+pub struct FlexZeroVecOwned(Vec<u8>);
+
+impl FlexZeroVecOwned {
+ /// Creates a new [`FlexZeroVecOwned`] with zero elements.
+ pub fn new_empty() -> Self {
+ Self(vec![1])
+ }
+
+ /// Creates a [`FlexZeroVecOwned`] from a [`FlexZeroSlice`].
+ pub fn from_slice(other: &FlexZeroSlice) -> FlexZeroVecOwned {
+ // safety: the bytes originate from a valid FlexZeroSlice
+ Self(other.as_bytes().to_vec())
+ }
+
+ /// Obtains this [`FlexZeroVecOwned`] as a [`FlexZeroSlice`].
+ pub fn as_slice(&self) -> &FlexZeroSlice {
+ let slice: &[u8] = &*self.0;
+ unsafe {
+ // safety: the slice is known to come from a valid parsed FlexZeroSlice
+ FlexZeroSlice::from_byte_slice_unchecked(slice)
+ }
+ }
+
+ /// Mutably obtains this `FlexZeroVecOwned` as a [`FlexZeroSlice`].
+ pub(crate) fn as_mut_slice(&mut self) -> &mut FlexZeroSlice {
+ let slice: &mut [u8] = &mut *self.0;
+ unsafe {
+ // safety: the slice is known to come from a valid parsed FlexZeroSlice
+ FlexZeroSlice::from_byte_slice_mut_unchecked(slice)
+ }
+ }
+
+ /// Converts this `FlexZeroVecOwned` into a [`FlexZeroVec::Owned`].
+ #[inline]
+ pub fn into_flexzerovec(self) -> FlexZeroVec<'static> {
+ FlexZeroVec::Owned(self)
+ }
+
+ /// Clears all values out of this `FlexZeroVecOwned`.
+ #[inline]
+ pub fn clear(&mut self) {
+ *self = Self::new_empty()
+ }
+
+ /// Appends an item to the end of the vector.
+ ///
+ /// # Panics
+ ///
+ /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+ /// zv.to_mut().push(33);
+ /// assert_eq!(zv.to_vec(), vec![22, 44, 66, 33]);
+ /// ```
+ pub fn push(&mut self, item: usize) {
+ let insert_info = self.get_insert_info(item);
+ self.0.resize(insert_info.new_bytes_len, 0);
+ let insert_index = insert_info.new_count - 1;
+ self.as_mut_slice().insert_impl(insert_info, insert_index);
+ }
+
+ /// Inserts an element into the middle of the vector.
+ ///
+ /// Caution: Both arguments to this function are of type `usize`. Please be careful to pass
+ /// the index first followed by the value second.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `index > len`.
+ ///
+ /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+ /// zv.to_mut().insert(2, 33);
+ /// assert_eq!(zv.to_vec(), vec![22, 44, 33, 66]);
+ /// ```
+ pub fn insert(&mut self, index: usize, item: usize) {
+ #[allow(clippy::panic)] // panic is documented in function contract
+ if index > self.len() {
+ panic!("index {} out of range {}", index, self.len());
+ }
+ let insert_info = self.get_insert_info(item);
+ self.0.resize(insert_info.new_bytes_len, 0);
+ self.as_mut_slice().insert_impl(insert_info, index);
+ }
+
+ /// Inserts an element into an ascending sorted vector
+ /// at a position that keeps the vector sorted.
+ ///
+ /// # Panics
+ ///
+ /// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVecOwned;
+ ///
+ /// let mut fzv = FlexZeroVecOwned::new_empty();
+ /// fzv.insert_sorted(10);
+ /// fzv.insert_sorted(5);
+ /// fzv.insert_sorted(8);
+ ///
+ /// assert!(Iterator::eq(fzv.iter(), [5, 8, 10].iter().copied()));
+ /// ```
+ pub fn insert_sorted(&mut self, item: usize) {
+ let index = match self.binary_search(item) {
+ Ok(i) => i,
+ Err(i) => i,
+ };
+ let insert_info = self.get_insert_info(item);
+ self.0.resize(insert_info.new_bytes_len, 0);
+ self.as_mut_slice().insert_impl(insert_info, index);
+ }
+
+ /// Removes and returns the element at the specified index.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `index >= len`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+ /// let removed_item = zv.to_mut().remove(1);
+ /// assert_eq!(44, removed_item);
+ /// assert_eq!(zv.to_vec(), vec![22, 66]);
+ /// ```
+ pub fn remove(&mut self, index: usize) -> usize {
+ #[allow(clippy::panic)] // panic is documented in function contract
+ if index >= self.len() {
+ panic!("index {} out of range {}", index, self.len());
+ }
+ let remove_info = self.get_remove_info(index);
+ // Safety: `remove_index` is a valid index
+ let item = unsafe { self.get_unchecked(remove_info.remove_index) };
+ let new_bytes_len = remove_info.new_bytes_len;
+ self.as_mut_slice().remove_impl(remove_info);
+ self.0.truncate(new_bytes_len);
+ item
+ }
+
+ /// Removes and returns the last element from an ascending sorted vector.
+ ///
+ /// If the vector is not sorted, use [`FlexZeroVecOwned::remove()`] instead. Calling this
+ /// function would leave the FlexZeroVec in a safe, well-defined state; however, information
+ /// may be lost and/or the equality invariant might not hold.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `self.is_empty()`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
+ /// let popped_item = zv.to_mut().pop_sorted();
+ /// assert_eq!(66, popped_item);
+ /// assert_eq!(zv.to_vec(), vec![22, 44]);
+ /// ```
+ ///
+ /// Calling this function on a non-ascending vector could cause surprising results:
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv1: FlexZeroVec = [444, 222, 111].iter().copied().collect();
+ /// let popped_item = zv1.to_mut().pop_sorted();
+ /// assert_eq!(111, popped_item);
+ ///
+ /// // Oops!
+ /// assert_eq!(zv1.to_vec(), vec![188, 222]);
+ /// ```
+ pub fn pop_sorted(&mut self) -> usize {
+ #[allow(clippy::panic)] // panic is documented in function contract
+ if self.is_empty() {
+ panic!("cannot pop from an empty vector");
+ }
+ let remove_info = self.get_sorted_pop_info();
+ // Safety: `remove_index` is a valid index
+ let item = unsafe { self.get_unchecked(remove_info.remove_index) };
+ let new_bytes_len = remove_info.new_bytes_len;
+ self.as_mut_slice().remove_impl(remove_info);
+ self.0.truncate(new_bytes_len);
+ item
+ }
+}
+
+impl Deref for FlexZeroVecOwned {
+ type Target = FlexZeroSlice;
+ fn deref(&self) -> &Self::Target {
+ self.as_slice()
+ }
+}
+
+impl fmt::Debug for FlexZeroVecOwned {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "{:?}", self.to_vec())
+ }
+}
+
+impl From<&FlexZeroSlice> for FlexZeroVecOwned {
+ fn from(other: &FlexZeroSlice) -> Self {
+ Self::from_slice(other)
+ }
+}
+
+impl FromIterator<usize> for FlexZeroVecOwned {
+ /// Creates a [`FlexZeroVecOwned`] from an iterator of `usize`.
+ fn from_iter<I>(iter: I) -> Self
+ where
+ I: IntoIterator<Item = usize>,
+ {
+ let mut result = FlexZeroVecOwned::new_empty();
+ for item in iter {
+ result.push(item);
+ }
+ result
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+
+ fn check_contents(fzv: &FlexZeroSlice, expected: &[usize]) {
+ assert_eq!(
+ fzv.len(),
+ expected.len(),
+ "len: {:?} != {:?}",
+ fzv,
+ expected
+ );
+ assert_eq!(
+ fzv.is_empty(),
+ expected.is_empty(),
+ "is_empty: {:?} != {:?}",
+ fzv,
+ expected
+ );
+ assert_eq!(
+ fzv.first(),
+ expected.first().copied(),
+ "first: {:?} != {:?}",
+ fzv,
+ expected
+ );
+ assert_eq!(
+ fzv.last(),
+ expected.last().copied(),
+ "last: {:?} != {:?}",
+ fzv,
+ expected
+ );
+ for i in 0..(expected.len() + 1) {
+ assert_eq!(
+ fzv.get(i),
+ expected.get(i).copied(),
+ "@{}: {:?} != {:?}",
+ i,
+ fzv,
+ expected
+ );
+ }
+ }
+
+ #[test]
+ fn test_basic() {
+ let mut fzv = FlexZeroVecOwned::new_empty();
+ assert_eq!(fzv.get_width(), 1);
+ check_contents(&fzv, &[]);
+
+ fzv.push(42);
+ assert_eq!(fzv.get_width(), 1);
+ check_contents(&fzv, &[42]);
+
+ fzv.push(77);
+ assert_eq!(fzv.get_width(), 1);
+ check_contents(&fzv, &[42, 77]);
+
+ // Scale up
+ fzv.push(300);
+ assert_eq!(fzv.get_width(), 2);
+ check_contents(&fzv, &[42, 77, 300]);
+
+ // Does not need to be sorted
+ fzv.insert(1, 325);
+ assert_eq!(fzv.get_width(), 2);
+ check_contents(&fzv, &[42, 325, 77, 300]);
+
+ fzv.remove(3);
+ assert_eq!(fzv.get_width(), 2);
+ check_contents(&fzv, &[42, 325, 77]);
+
+ // Scale down
+ fzv.remove(1);
+ assert_eq!(fzv.get_width(), 1);
+ check_contents(&fzv, &[42, 77]);
+ }
+
+ #[test]
+ fn test_build_sorted() {
+ let nums: &[usize] = &[0, 50, 0, 77, 831, 29, 89182, 931, 0, 77, 712381];
+ let mut fzv = FlexZeroVecOwned::new_empty();
+
+ for num in nums {
+ fzv.insert_sorted(*num);
+ }
+ assert_eq!(fzv.get_width(), 3);
+ check_contents(&fzv, &[0, 0, 0, 29, 50, 77, 77, 831, 931, 89182, 712381]);
+
+ for num in nums {
+ let index = fzv.binary_search(*num).unwrap();
+ fzv.remove(index);
+ }
+ assert_eq!(fzv.get_width(), 1);
+ check_contents(&fzv, &[]);
+ }
+}
diff --git a/vendor/zerovec/src/flexzerovec/serde.rs b/vendor/zerovec/src/flexzerovec/serde.rs
new file mode 100644
index 000000000..44179be32
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/serde.rs
@@ -0,0 +1,175 @@
+// 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::{FlexZeroSlice, FlexZeroVec};
+use alloc::vec::Vec;
+use core::fmt;
+use serde::de::{self, Deserialize, Deserializer, SeqAccess, Visitor};
+#[cfg(feature = "serde")]
+use serde::ser::{Serialize, SerializeSeq, Serializer};
+
+#[derive(Default)]
+struct FlexZeroVecVisitor {}
+
+impl<'de> Visitor<'de> for FlexZeroVecVisitor {
+ type Value = FlexZeroVec<'de>;
+
+ fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+ formatter.write_str("a sequence or borrowed buffer of bytes")
+ }
+
+ fn visit_borrowed_bytes<E>(self, bytes: &'de [u8]) -> Result<Self::Value, E>
+ where
+ E: de::Error,
+ {
+ FlexZeroVec::parse_byte_slice(bytes).map_err(de::Error::custom)
+ }
+
+ fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
+ where
+ A: SeqAccess<'de>,
+ {
+ let mut vec: Vec<usize> = if let Some(capacity) = seq.size_hint() {
+ Vec::with_capacity(capacity)
+ } else {
+ Vec::new()
+ };
+ while let Some(value) = seq.next_element::<usize>()? {
+ vec.push(value);
+ }
+ Ok(vec.into_iter().collect())
+ }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a> Deserialize<'de> for FlexZeroVec<'a>
+where
+ 'de: 'a,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ let visitor = FlexZeroVecVisitor::default();
+ if deserializer.is_human_readable() {
+ deserializer.deserialize_seq(visitor)
+ } else {
+ deserializer.deserialize_bytes(visitor)
+ }
+ }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl<'de, 'a> Deserialize<'de> for &'a FlexZeroSlice
+where
+ 'de: 'a,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ if deserializer.is_human_readable() {
+ Err(de::Error::custom(
+ "&FlexZeroSlice cannot be deserialized from human-readable formats",
+ ))
+ } else {
+ let deserialized: FlexZeroVec<'a> = FlexZeroVec::deserialize(deserializer)?;
+ let borrowed = if let FlexZeroVec::Borrowed(b) = deserialized {
+ b
+ } else {
+ return Err(de::Error::custom(
+ "&FlexZeroSlice can only deserialize in zero-copy ways",
+ ));
+ };
+ Ok(borrowed)
+ }
+ }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl Serialize for FlexZeroVec<'_> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ if serializer.is_human_readable() {
+ let mut seq = serializer.serialize_seq(Some(self.len()))?;
+ for value in self.iter() {
+ seq.serialize_element(&value)?;
+ }
+ seq.end()
+ } else {
+ serializer.serialize_bytes(self.as_bytes())
+ }
+ }
+}
+
+/// This impl can be made available by enabling the optional `serde` feature of the `zerovec` crate
+impl Serialize for FlexZeroSlice {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ self.as_flexzerovec().serialize(serializer)
+ }
+}
+
+#[cfg(test)]
+#[allow(non_camel_case_types)]
+mod test {
+ use super::{FlexZeroSlice, FlexZeroVec};
+
+ #[derive(serde::Serialize, serde::Deserialize)]
+ struct DeriveTest_FlexZeroVec<'data> {
+ #[serde(borrow)]
+ _data: FlexZeroVec<'data>,
+ }
+
+ #[derive(serde::Serialize, serde::Deserialize)]
+ struct DeriveTest_FlexZeroSlice<'data> {
+ #[serde(borrow)]
+ _data: &'data FlexZeroSlice,
+ }
+
+ // [1, 22, 333, 4444];
+ const BYTES: &[u8] = &[2, 0x01, 0x00, 0x16, 0x00, 0x4D, 0x01, 0x5C, 0x11];
+ const JSON_STR: &str = "[1,22,333,4444]";
+ const BINCODE_BUF: &[u8] = &[9, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 22, 0, 77, 1, 92, 17];
+
+ #[test]
+ fn test_serde_json() {
+ let zerovec_orig: FlexZeroVec = FlexZeroVec::parse_byte_slice(BYTES).expect("parse");
+ let json_str = serde_json::to_string(&zerovec_orig).expect("serialize");
+ assert_eq!(JSON_STR, json_str);
+ // FlexZeroVec should deserialize from JSON to either Vec or FlexZeroVec
+ let vec_new: Vec<usize> =
+ serde_json::from_str(&json_str).expect("deserialize from buffer to Vec");
+ assert_eq!(zerovec_orig.to_vec(), vec_new);
+ let zerovec_new: FlexZeroVec =
+ serde_json::from_str(&json_str).expect("deserialize from buffer to FlexZeroVec");
+ assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+ assert!(matches!(zerovec_new, FlexZeroVec::Owned(_)));
+ }
+
+ #[test]
+ fn test_serde_bincode() {
+ let zerovec_orig: FlexZeroVec = FlexZeroVec::parse_byte_slice(BYTES).expect("parse");
+ let bincode_buf = bincode::serialize(&zerovec_orig).expect("serialize");
+ assert_eq!(BINCODE_BUF, bincode_buf);
+ let zerovec_new: FlexZeroVec =
+ bincode::deserialize(&bincode_buf).expect("deserialize from buffer to FlexZeroVec");
+ assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+ assert!(matches!(zerovec_new, FlexZeroVec::Borrowed(_)));
+ }
+
+ #[test]
+ fn test_vzv_borrowed() {
+ let zerovec_orig: &FlexZeroSlice = FlexZeroSlice::parse_byte_slice(BYTES).expect("parse");
+ let bincode_buf = bincode::serialize(&zerovec_orig).expect("serialize");
+ assert_eq!(BINCODE_BUF, bincode_buf);
+ let zerovec_new: &FlexZeroSlice =
+ bincode::deserialize(&bincode_buf).expect("deserialize from buffer to FlexZeroSlice");
+ assert_eq!(zerovec_orig.to_vec(), zerovec_new.to_vec());
+ }
+}
diff --git a/vendor/zerovec/src/flexzerovec/slice.rs b/vendor/zerovec/src/flexzerovec/slice.rs
new file mode 100644
index 000000000..7cc6f12fa
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/slice.rs
@@ -0,0 +1,717 @@
+// 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)]
+#[derive(Eq, PartialEq)]
+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],
+}
+
+/// 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
+ let (_, remainder) = match bytes.split_last() {
+ Some(v) => v,
+ None => panic!("slice should be non-empty"),
+ };
+ &*(remainder as *const [u8] 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::slice::from_raw_parts_mut(bytes.as_mut_ptr(), bytes.len() - 1);
+ &mut *(remainder as *mut [u8] 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(core::iter::once(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)
+ })
+ }
+}
+
+impl fmt::Debug for &FlexZeroSlice {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ write!(f, "{:?}", self.to_vec())
+ }
+}
+
+#[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;
+ }
+}
diff --git a/vendor/zerovec/src/flexzerovec/vec.rs b/vendor/zerovec/src/flexzerovec/vec.rs
new file mode 100644
index 000000000..a08f54e5d
--- /dev/null
+++ b/vendor/zerovec/src/flexzerovec/vec.rs
@@ -0,0 +1,275 @@
+// 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::FlexZeroSlice;
+use super::FlexZeroVecOwned;
+use crate::ZeroVecError;
+use core::cmp::Ordering;
+use core::iter::FromIterator;
+use core::ops::Deref;
+
+/// A zero-copy data structure that efficiently stores integer values.
+///
+/// `FlexZeroVec` automatically increases or decreases its storage capacity based on the largest
+/// integer stored in the vector. It therefore results in lower memory usage when smaller numbers
+/// are usually stored, but larger values must sometimes also be stored.
+///
+/// The maximum value that can be stored in `FlexZeroVec` is `usize::MAX` on the current platform.
+///
+/// `FlexZeroVec` is the data structure for storing `usize` in a `ZeroMap`.
+///
+/// `FlexZeroVec` derefs to [`FlexZeroSlice`], which contains most of the methods.
+///
+/// # Examples
+///
+/// Storing a vec of `usize`s in a zero-copy way:
+///
+/// ```
+/// use zerovec::vecs::FlexZeroVec;
+///
+/// // Create a FlexZeroVec and add a few numbers to it
+/// let mut zv1 = FlexZeroVec::new();
+/// zv1.to_mut().push(55);
+/// zv1.to_mut().push(33);
+/// zv1.to_mut().push(999);
+/// assert_eq!(zv1.to_vec(), vec![55, 33, 999]);
+///
+/// // Convert it to bytes and back
+/// let bytes = zv1.as_bytes();
+/// let zv2 =
+/// FlexZeroVec::parse_byte_slice(bytes).expect("bytes should round-trip");
+/// assert_eq!(zv2.to_vec(), vec![55, 33, 999]);
+///
+/// // Verify the compact storage
+/// assert_eq!(7, bytes.len());
+/// assert!(matches!(zv2, FlexZeroVec::Borrowed(_)));
+/// ```
+///
+/// Storing a map of `usize` to `usize` in a zero-copy way:
+///
+/// ```
+/// use zerovec::ZeroMap;
+///
+/// // Append some values to the ZeroMap
+/// let mut zm = ZeroMap::<usize, usize>::new();
+/// assert!(zm.try_append(&29, &92).is_none());
+/// assert!(zm.try_append(&38, &83).is_none());
+/// assert!(zm.try_append(&56, &65).is_none());
+/// assert_eq!(zm.len(), 3);
+///
+/// // Insert another value into the middle
+/// assert!(zm.try_append(&47, &74).is_some());
+/// assert!(zm.insert(&47, &74).is_none());
+/// assert_eq!(zm.len(), 4);
+///
+/// // Verify that the values are correct
+/// assert_eq!(zm.get_copied(&0), None);
+/// assert_eq!(zm.get_copied(&29), Some(92));
+/// assert_eq!(zm.get_copied(&38), Some(83));
+/// assert_eq!(zm.get_copied(&47), Some(74));
+/// assert_eq!(zm.get_copied(&56), Some(65));
+/// assert_eq!(zm.get_copied(&usize::MAX), None);
+/// ```
+#[derive(Debug)]
+#[non_exhaustive]
+pub enum FlexZeroVec<'a> {
+ Owned(FlexZeroVecOwned),
+ Borrowed(&'a FlexZeroSlice),
+}
+
+impl<'a> Deref for FlexZeroVec<'a> {
+ type Target = FlexZeroSlice;
+ fn deref(&self) -> &Self::Target {
+ match self {
+ FlexZeroVec::Owned(v) => v.deref(),
+ FlexZeroVec::Borrowed(v) => v,
+ }
+ }
+}
+
+impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a> {
+ fn as_ref(&self) -> &FlexZeroSlice {
+ self.deref()
+ }
+}
+
+impl Eq for FlexZeroVec<'_> {}
+
+impl<'a, 'b> PartialEq<FlexZeroVec<'b>> for FlexZeroVec<'a> {
+ #[inline]
+ fn eq(&self, other: &FlexZeroVec<'b>) -> bool {
+ self.iter().eq(other.iter())
+ }
+}
+
+impl<'a> Default for FlexZeroVec<'a> {
+ #[inline]
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl<'a> PartialOrd for FlexZeroVec<'a> {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ self.iter().partial_cmp(other.iter())
+ }
+}
+
+impl<'a> Ord for FlexZeroVec<'a> {
+ fn cmp(&self, other: &Self) -> Ordering {
+ self.iter().cmp(other.iter())
+ }
+}
+
+impl<'a> FlexZeroVec<'a> {
+ #[inline]
+ /// Creates a new, borrowed, empty `FlexZeroVec`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let zv: FlexZeroVec = FlexZeroVec::new();
+ /// assert!(zv.is_empty());
+ /// ```
+ pub fn new() -> Self {
+ Self::Borrowed(FlexZeroSlice::new_empty())
+ }
+
+ /// Parses a `&[u8]` buffer into a `FlexZeroVec`.
+ ///
+ /// The bytes within the byte buffer must remain constant for the life of the FlexZeroVec.
+ ///
+ /// # Endianness
+ ///
+ /// The byte buffer must be encoded in little-endian, even if running in a big-endian
+ /// environment. This ensures a consistent representation of data across platforms.
+ ///
+ /// # Max Value
+ ///
+ /// The bytes will fail to parse if the high value is greater than the capacity of `usize`
+ /// on this platform. For example, a `FlexZeroVec` created on a 64-bit platform might fail
+ /// to deserialize on a 32-bit platform.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+ /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid slice");
+ ///
+ /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+ /// assert_eq!(zv.get(2), Some(421));
+ /// ```
+ pub fn parse_byte_slice(bytes: &'a [u8]) -> Result<Self, ZeroVecError> {
+ let slice: &'a FlexZeroSlice = FlexZeroSlice::parse_byte_slice(bytes)?;
+ Ok(Self::Borrowed(slice))
+ }
+
+ /// Converts a borrowed FlexZeroVec to an owned FlexZeroVec. No-op if already owned.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+ /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
+ /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+ ///
+ /// let owned = zv.into_owned();
+ /// assert!(matches!(owned, FlexZeroVec::Owned(_)));
+ /// ```
+ pub fn into_owned(self) -> FlexZeroVec<'static> {
+ match self {
+ Self::Owned(owned) => FlexZeroVec::Owned(owned),
+ Self::Borrowed(slice) => FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice)),
+ }
+ }
+
+ /// Allows the FlexZeroVec to be mutated by converting it to an owned variant, and producing
+ /// a mutable [`FlexZeroVecOwned`].
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
+ /// let mut zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
+ /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
+ ///
+ /// zv.to_mut().push(12);
+ /// assert!(matches!(zv, FlexZeroVec::Owned(_)));
+ /// assert_eq!(zv.get(4), Some(12));
+ /// ```
+ pub fn to_mut(&mut self) -> &mut FlexZeroVecOwned {
+ match self {
+ Self::Owned(ref mut owned) => owned,
+ Self::Borrowed(slice) => {
+ *self = FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice));
+ // recursion is limited since we are guaranteed to hit the Owned branch
+ self.to_mut()
+ }
+ }
+ }
+
+ /// Remove all elements from this FlexZeroVec and reset it to an empty borrowed state.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use zerovec::vecs::FlexZeroVec;
+ ///
+ /// let mut zv: FlexZeroVec = [1, 2, 3].iter().copied().collect();
+ /// assert!(!zv.is_empty());
+ /// zv.clear();
+ /// assert!(zv.is_empty());
+ /// ```
+ pub fn clear(&mut self) {
+ *self = Self::Borrowed(FlexZeroSlice::new_empty())
+ }
+}
+
+impl FromIterator<usize> for FlexZeroVec<'_> {
+ /// Creates a [`FlexZeroVec::Owned`] from an iterator of `usize`.
+ fn from_iter<I>(iter: I) -> Self
+ where
+ I: IntoIterator<Item = usize>,
+ {
+ FlexZeroVecOwned::from_iter(iter).into_flexzerovec()
+ }
+}
+
+#[test]
+fn test_zeromap_usize() {
+ use crate::ZeroMap;
+
+ let mut zm = ZeroMap::<usize, usize>::new();
+ assert!(zm.try_append(&29, &92).is_none());
+ assert!(zm.try_append(&38, &83).is_none());
+ assert!(zm.try_append(&47, &74).is_none());
+ assert!(zm.try_append(&56, &65).is_none());
+
+ assert_eq!(zm.keys.get_width(), 1);
+ assert_eq!(zm.values.get_width(), 1);
+
+ assert_eq!(zm.insert(&47, &744), Some(74));
+ assert_eq!(zm.values.get_width(), 2);
+ assert_eq!(zm.insert(&47, &774), Some(744));
+ assert_eq!(zm.values.get_width(), 2);
+ assert!(zm.try_append(&1100, &1).is_none());
+ assert_eq!(zm.keys.get_width(), 2);
+ assert_eq!(zm.remove(&1100), Some(1));
+ assert_eq!(zm.keys.get_width(), 1);
+
+ assert_eq!(zm.get_copied(&0), None);
+ assert_eq!(zm.get_copied(&29), Some(92));
+ assert_eq!(zm.get_copied(&38), Some(83));
+ assert_eq!(zm.get_copied(&47), Some(774));
+ assert_eq!(zm.get_copied(&56), Some(65));
+ assert_eq!(zm.get_copied(&usize::MAX), None);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 02:35:58 +0000