sled/
ivec.rs

1use std::{
2    convert::TryFrom,
3    fmt,
4    hash::{Hash, Hasher},
5    iter::FromIterator,
6    ops::{Deref, DerefMut},
7};
8
9use crate::Arc;
10
11const CUTOFF: usize = 22;
12
13type Inner = [u8; CUTOFF];
14
15/// A buffer that may either be inline or remote and protected
16/// by an Arc
17#[derive(Clone)]
18pub struct IVec(IVecInner);
19
20impl Default for IVec {
21    fn default() -> Self {
22        Self::from(&[])
23    }
24}
25
26#[derive(Clone)]
27enum IVecInner {
28    Inline(u8, Inner),
29    Remote(Arc<[u8]>),
30    Subslice { base: Arc<[u8]>, offset: usize, len: usize },
31}
32
33impl Hash for IVec {
34    fn hash<H: Hasher>(&self, state: &mut H) {
35        self.deref().hash(state);
36    }
37}
38
39const fn is_inline_candidate(length: usize) -> bool {
40    length <= CUTOFF
41}
42
43impl IVec {
44    /// Create a subslice of this `IVec` that shares
45    /// the same backing data and reference counter.
46    ///
47    /// # Panics
48    ///
49    /// Panics if `self.len() - offset >= len`.
50    ///
51    /// # Examples
52    /// ```
53    /// # use sled::IVec;
54    /// let iv = IVec::from(vec![1]);
55    /// let subslice = iv.subslice(0, 1);
56    /// assert_eq!(&subslice, &[1]);
57    /// let subslice = subslice.subslice(0, 1);
58    /// assert_eq!(&subslice, &[1]);
59    /// let subslice = subslice.subslice(1, 0);
60    /// assert_eq!(&subslice, &[]);
61    /// let subslice = subslice.subslice(0, 0);
62    /// assert_eq!(&subslice, &[]);
63    ///
64    /// let iv2 = IVec::from(vec![1, 2, 3]);
65    /// let subslice = iv2.subslice(3, 0);
66    /// assert_eq!(&subslice, &[]);
67    /// let subslice = iv2.subslice(2, 1);
68    /// assert_eq!(&subslice, &[3]);
69    /// let subslice = iv2.subslice(1, 2);
70    /// assert_eq!(&subslice, &[2, 3]);
71    /// let subslice = iv2.subslice(0, 3);
72    /// assert_eq!(&subslice, &[1, 2, 3]);
73    /// let subslice = subslice.subslice(1, 2);
74    /// assert_eq!(&subslice, &[2, 3]);
75    /// let subslice = subslice.subslice(1, 1);
76    /// assert_eq!(&subslice, &[3]);
77    /// let subslice = subslice.subslice(1, 0);
78    /// assert_eq!(&subslice, &[]);
79    /// ```
80    pub fn subslice(&self, slice_offset: usize, len: usize) -> Self {
81        assert!(self.len().checked_sub(slice_offset).unwrap() >= len);
82
83        let inner = match self.0 {
84            IVecInner::Remote(ref base) => IVecInner::Subslice {
85                base: base.clone(),
86                offset: slice_offset,
87                len,
88            },
89            IVecInner::Inline(_, old_inner) => {
90                // old length already checked above in assertion
91                let mut new_inner = Inner::default();
92                new_inner[..len].copy_from_slice(
93                    &old_inner[slice_offset..slice_offset + len],
94                );
95
96                IVecInner::Inline(u8::try_from(len).unwrap(), new_inner)
97            }
98            IVecInner::Subslice { ref base, ref offset, .. } => {
99                IVecInner::Subslice {
100                    base: base.clone(),
101                    offset: offset + slice_offset,
102                    len,
103                }
104            }
105        };
106
107        IVec(inner)
108    }
109
110    fn inline(slice: &[u8]) -> Self {
111        assert!(is_inline_candidate(slice.len()));
112        let mut data = Inner::default();
113        data[..slice.len()].copy_from_slice(slice);
114        Self(IVecInner::Inline(u8::try_from(slice.len()).unwrap(), data))
115    }
116
117    fn remote(arc: Arc<[u8]>) -> Self {
118        Self(IVecInner::Remote(arc))
119    }
120
121    fn make_mut(&mut self) {
122        match self.0 {
123            IVecInner::Remote(ref mut buf) if Arc::strong_count(buf) != 1 => {
124                self.0 = IVecInner::Remote(buf.to_vec().into());
125            }
126            IVecInner::Subslice { ref mut base, offset, len }
127                if Arc::strong_count(base) != 1 =>
128            {
129                self.0 = IVecInner::Remote(
130                    base[offset..offset + len].to_vec().into(),
131                );
132            }
133            _ => {}
134        }
135    }
136}
137
138impl FromIterator<u8> for IVec {
139    fn from_iter<T>(iter: T) -> Self
140    where
141        T: IntoIterator<Item = u8>,
142    {
143        let bs: Vec<u8> = iter.into_iter().collect();
144        bs.into()
145    }
146}
147
148impl From<Box<[u8]>> for IVec {
149    fn from(b: Box<[u8]>) -> Self {
150        if is_inline_candidate(b.len()) {
151            Self::inline(&b)
152        } else {
153            Self::remote(Arc::from(b))
154        }
155    }
156}
157
158impl From<&[u8]> for IVec {
159    fn from(slice: &[u8]) -> Self {
160        if is_inline_candidate(slice.len()) {
161            Self::inline(slice)
162        } else {
163            Self::remote(Arc::from(slice))
164        }
165    }
166}
167
168impl From<Arc<[u8]>> for IVec {
169    fn from(arc: Arc<[u8]>) -> Self {
170        if is_inline_candidate(arc.len()) {
171            Self::inline(&arc)
172        } else {
173            Self::remote(arc)
174        }
175    }
176}
177
178impl From<&str> for IVec {
179    fn from(s: &str) -> Self {
180        Self::from(s.as_bytes())
181    }
182}
183
184impl From<&IVec> for IVec {
185    fn from(v: &Self) -> Self {
186        v.clone()
187    }
188}
189
190impl From<Vec<u8>> for IVec {
191    fn from(v: Vec<u8>) -> Self {
192        if is_inline_candidate(v.len()) {
193            Self::inline(&v)
194        } else {
195            // rely on the Arc From specialization
196            // for Vec<T>, which may improve
197            // over time
198            Self::remote(Arc::from(v))
199        }
200    }
201}
202
203impl std::borrow::Borrow<[u8]> for IVec {
204    fn borrow(&self) -> &[u8] {
205        self.as_ref()
206    }
207}
208
209impl std::borrow::Borrow<[u8]> for &IVec {
210    fn borrow(&self) -> &[u8] {
211        self.as_ref()
212    }
213}
214
215macro_rules! from_array {
216    ($($s:expr),*) => {
217        $(
218            impl From<&[u8; $s]> for IVec {
219                fn from(v: &[u8; $s]) -> Self {
220                    Self::from(&v[..])
221                }
222            }
223        )*
224    }
225}
226
227from_array!(
228    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
229    21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32
230);
231
232impl Into<Arc<[u8]>> for IVec {
233    fn into(self) -> Arc<[u8]> {
234        match self.0 {
235            IVecInner::Inline(..) => Arc::from(self.as_ref()),
236            IVecInner::Remote(arc) => arc,
237            IVecInner::Subslice { .. } => self.deref().into(),
238        }
239    }
240}
241
242impl Deref for IVec {
243    type Target = [u8];
244
245    #[inline]
246    fn deref(&self) -> &[u8] {
247        self.as_ref()
248    }
249}
250
251impl AsRef<[u8]> for IVec {
252    #[inline]
253    #[allow(unsafe_code)]
254    fn as_ref(&self) -> &[u8] {
255        match &self.0 {
256            IVecInner::Inline(sz, buf) => unsafe {
257                buf.get_unchecked(..*sz as usize)
258            },
259            IVecInner::Remote(buf) => buf,
260            IVecInner::Subslice { ref base, offset, len } => {
261                &base[*offset..*offset + *len]
262            }
263        }
264    }
265}
266
267impl DerefMut for IVec {
268    #[inline]
269    fn deref_mut(&mut self) -> &mut [u8] {
270        self.as_mut()
271    }
272}
273
274impl AsMut<[u8]> for IVec {
275    #[inline]
276    #[allow(unsafe_code)]
277    fn as_mut(&mut self) -> &mut [u8] {
278        self.make_mut();
279
280        match &mut self.0 {
281            IVecInner::Inline(ref sz, ref mut buf) => unsafe {
282                std::slice::from_raw_parts_mut(buf.as_mut_ptr(), *sz as usize)
283            },
284            IVecInner::Remote(ref mut buf) => Arc::get_mut(buf).unwrap(),
285            IVecInner::Subslice { ref mut base, offset, len } => {
286                &mut Arc::get_mut(base).unwrap()[*offset..*offset + *len]
287            }
288        }
289    }
290}
291
292impl Ord for IVec {
293    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
294        self.as_ref().cmp(other.as_ref())
295    }
296}
297
298impl PartialOrd for IVec {
299    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
300        Some(self.cmp(other))
301    }
302}
303
304impl<T: AsRef<[u8]>> PartialEq<T> for IVec {
305    fn eq(&self, other: &T) -> bool {
306        self.as_ref() == other.as_ref()
307    }
308}
309
310impl PartialEq<[u8]> for IVec {
311    fn eq(&self, other: &[u8]) -> bool {
312        self.as_ref() == other
313    }
314}
315
316impl Eq for IVec {}
317
318impl fmt::Debug for IVec {
319    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
320        self.as_ref().fmt(f)
321    }
322}
323
324#[test]
325fn ivec_usage() {
326    let iv1 = IVec::from(vec![1, 2, 3]);
327    assert_eq!(iv1, vec![1, 2, 3]);
328    let iv2 = IVec::from(&[4; 128][..]);
329    assert_eq!(iv2, vec![4; 128]);
330}
331
332#[test]
333fn boxed_slice_conversion() {
334    let boite1: Box<[u8]> = Box::new([1, 2, 3]);
335    let iv1: IVec = boite1.into();
336    assert_eq!(iv1, vec![1, 2, 3]);
337    let boite2: Box<[u8]> = Box::new([4; 128]);
338    let iv2: IVec = boite2.into();
339    assert_eq!(iv2, vec![4; 128]);
340}
341
342#[test]
343#[should_panic]
344fn subslice_usage_00() {
345    let iv1 = IVec::from(vec![1, 2, 3]);
346    let _subslice = iv1.subslice(0, 4);
347}
348
349#[test]
350#[should_panic]
351fn subslice_usage_01() {
352    let iv1 = IVec::from(vec![1, 2, 3]);
353    let _subslice = iv1.subslice(3, 1);
354}
355
356#[test]
357fn ivec_as_mut_identity() {
358    let initial = &[1];
359    let mut iv = IVec::from(initial);
360    assert_eq!(&*initial, &*iv);
361    assert_eq!(&*initial, &mut *iv);
362    assert_eq!(&*initial, iv.as_mut());
363}
364
365#[cfg(test)]
366mod qc {
367    use super::IVec;
368
369    fn prop_identity(ivec: &IVec) -> bool {
370        let mut iv2 = ivec.clone();
371
372        if iv2 != ivec {
373            println!("expected clone to equal original");
374            return false;
375        }
376
377        if *ivec != *iv2 {
378            println!("expected AsMut to equal original");
379            return false;
380        }
381
382        if *ivec != iv2.as_mut() {
383            println!("expected AsMut to equal original");
384            return false;
385        }
386
387        true
388    }
389
390    quickcheck::quickcheck! {
391        #[cfg_attr(miri, ignore)]
392        fn bool(item: IVec) -> bool {
393            prop_identity(&item)
394        }
395    }
396}
sled/ivec.rs

sled/
ivec.rs
