1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 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> {
Some(self.cmp(other))
}
}
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 const 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);
}