triomphe/
header.rs

1use alloc::alloc::Layout;
2use alloc::boxed::Box;
3use alloc::string::String;
4use alloc::vec::Vec;
5use core::cmp::Ordering;
6use core::iter::{ExactSizeIterator, Iterator};
7use core::marker::PhantomData;
8use core::mem::{self, ManuallyDrop};
9use core::ptr::{self, addr_of_mut};
10use core::usize;
11
12use super::{Arc, ArcInner};
13
14/// Structure to allow Arc-managing some fixed-sized data and a variably-sized
15/// slice in a single allocation.
16#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, PartialOrd, Ord)]
17#[repr(C)]
18pub struct HeaderSlice<H, T: ?Sized> {
19    /// The fixed-sized data.
20    pub header: H,
21
22    /// The dynamically-sized data.
23    pub slice: T,
24}
25
26impl<H, T> Arc<HeaderSlice<H, [T]>> {
27    /// Creates an Arc for a HeaderSlice using the given header struct and
28    /// iterator to generate the slice. The resulting Arc will be fat.
29    pub fn from_header_and_iter<I>(header: H, mut items: I) -> Self
30    where
31        I: Iterator<Item = T> + ExactSizeIterator,
32    {
33        assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST");
34
35        let num_items = items.len();
36
37        let inner = Arc::allocate_for_header_and_slice(num_items);
38
39        unsafe {
40            // Write the data.
41            //
42            // Note that any panics here (i.e. from the iterator) are safe, since
43            // we'll just leak the uninitialized memory.
44            ptr::write(&mut ((*inner.as_ptr()).data.header), header);
45            let mut current = (*inner.as_ptr()).data.slice.as_mut_ptr();
46            for _ in 0..num_items {
47                ptr::write(
48                    current,
49                    items
50                        .next()
51                        .expect("ExactSizeIterator over-reported length"),
52                );
53                current = current.offset(1);
54            }
55            assert!(
56                items.next().is_none(),
57                "ExactSizeIterator under-reported length"
58            );
59        }
60
61        // Safety: ptr is valid & the inner structure is fully initialized
62        Arc {
63            p: inner,
64            phantom: PhantomData,
65        }
66    }
67
68    /// Creates an Arc for a HeaderSlice using the given header struct and
69    /// iterator to generate the slice. The resulting Arc will be fat.
70    pub fn from_header_and_slice(header: H, items: &[T]) -> Self
71    where
72        T: Copy,
73    {
74        assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST");
75
76        let num_items = items.len();
77
78        let inner = Arc::allocate_for_header_and_slice(num_items);
79
80        unsafe {
81            // Write the data.
82            ptr::write(&mut ((*inner.as_ptr()).data.header), header);
83            let dst = (*inner.as_ptr()).data.slice.as_mut_ptr();
84            ptr::copy_nonoverlapping(items.as_ptr(), dst, num_items);
85        }
86
87        // Safety: ptr is valid & the inner structure is fully initialized
88        Arc {
89            p: inner,
90            phantom: PhantomData,
91        }
92    }
93
94    /// Creates an Arc for a HeaderSlice using the given header struct and
95    /// vec to generate the slice. The resulting Arc will be fat.
96    pub fn from_header_and_vec(header: H, mut v: Vec<T>) -> Self {
97        let len = v.len();
98
99        let inner = Arc::allocate_for_header_and_slice(len);
100
101        unsafe {
102            // Safety: inner is a valid pointer, so this can't go out of bounds
103            let dst = addr_of_mut!((*inner.as_ptr()).data.header);
104
105            // Safety: `dst` is valid for writes (just allocated)
106            ptr::write(dst, header);
107        }
108
109        unsafe {
110            let src = v.as_mut_ptr();
111
112            // Safety: inner is a valid pointer, so this can't go out of bounds
113            let dst = addr_of_mut!((*inner.as_ptr()).data.slice) as *mut T;
114
115            // Safety:
116            // - `src` is valid for reads for `len` (got from `Vec`)
117            // - `dst` is valid for writes for `len` (just allocated, with layout for appropriate slice)
118            // - `src` and `dst` don't overlap (separate allocations)
119            ptr::copy_nonoverlapping(src, dst, len);
120
121            // Deallocate vec without dropping `T`
122            //
123            // Safety: 0..0 elements are always initialized, 0 <= cap for any cap
124            v.set_len(0);
125        }
126
127        // Safety: ptr is valid & the inner structure is fully initialized
128        Arc {
129            p: inner,
130            phantom: PhantomData,
131        }
132    }
133}
134
135impl<H> Arc<HeaderSlice<H, str>> {
136    /// Creates an Arc for a HeaderSlice using the given header struct and
137    /// a str slice to generate the slice. The resulting Arc will be fat.
138    pub fn from_header_and_str(header: H, string: &str) -> Self {
139        let bytes = Arc::from_header_and_slice(header, string.as_bytes());
140
141        // Safety: `ArcInner` and `HeaderSlice` are `repr(C)`, `str` has the same layout as `[u8]`,
142        //         thus it's ok to "transmute" between `Arc<HeaderSlice<H, [u8]>>` and `Arc<HeaderSlice<H, str>>`.
143        //
144        //         `bytes` are a valid string since we've just got them from a valid `str`.
145        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(bytes) as _) }
146    }
147}
148
149/// Header data with an inline length. Consumers that use HeaderWithLength as the
150/// Header type in HeaderSlice can take advantage of ThinArc.
151#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
152#[repr(C)]
153pub struct HeaderWithLength<H> {
154    /// The fixed-sized data.
155    pub header: H,
156
157    /// The slice length.
158    pub length: usize,
159}
160
161impl<H> HeaderWithLength<H> {
162    /// Creates a new HeaderWithLength.
163    #[inline]
164    pub fn new(header: H, length: usize) -> Self {
165        HeaderWithLength { header, length }
166    }
167}
168
169impl<T: ?Sized> From<Arc<HeaderSlice<(), T>>> for Arc<T> {
170    fn from(this: Arc<HeaderSlice<(), T>>) -> Self {
171        debug_assert_eq!(
172            Layout::for_value::<HeaderSlice<(), T>>(&this),
173            Layout::for_value::<T>(&this.slice)
174        );
175
176        // Safety: `HeaderSlice<(), T>` and `T` has the same layout
177        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(this) as _) }
178    }
179}
180
181impl<T: ?Sized> From<Arc<T>> for Arc<HeaderSlice<(), T>> {
182    fn from(this: Arc<T>) -> Self {
183        // Safety: `T` and `HeaderSlice<(), T>` has the same layout
184        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(this) as _) }
185    }
186}
187
188impl<T: Copy> From<&[T]> for Arc<[T]> {
189    fn from(slice: &[T]) -> Self {
190        Arc::from_header_and_slice((), slice).into()
191    }
192}
193
194impl From<&str> for Arc<str> {
195    fn from(s: &str) -> Self {
196        Arc::from_header_and_str((), s).into()
197    }
198}
199
200impl From<String> for Arc<str> {
201    fn from(s: String) -> Self {
202        Self::from(&s[..])
203    }
204}
205
206// FIXME: once `pointer::with_metadata_of` is stable or
207//        implementable on stable without assuming ptr layout
208//        this will be able to accept `T: ?Sized`.
209impl<T> From<Box<T>> for Arc<T> {
210    fn from(b: Box<T>) -> Self {
211        let layout = Layout::for_value::<T>(&b);
212
213        // Safety: the closure only changes the type of the pointer
214        let inner = unsafe { Self::allocate_for_layout(layout, |mem| mem as *mut ArcInner<T>) };
215
216        unsafe {
217            let src = Box::into_raw(b);
218
219            // Safety: inner is a valid pointer, so this can't go out of bounds
220            let dst = addr_of_mut!((*inner.as_ptr()).data);
221
222            // Safety:
223            // - `src` is valid for reads (got from `Box`)
224            // - `dst` is valid for writes (just allocated)
225            // - `src` and `dst` don't overlap (separate allocations)
226            ptr::copy_nonoverlapping(src, dst, 1);
227
228            // Deallocate box without dropping `T`
229            //
230            // Safety:
231            // - `src` has been got from `Box::into_raw`
232            // - `ManuallyDrop<T>` is guaranteed to have the same layout as `T`
233            drop(Box::<ManuallyDrop<T>>::from_raw(src as _));
234        }
235
236        Arc {
237            p: inner,
238            phantom: PhantomData,
239        }
240    }
241}
242
243impl<T> From<Vec<T>> for Arc<[T]> {
244    fn from(v: Vec<T>) -> Self {
245        Arc::from_header_and_vec((), v).into()
246    }
247}
248
249pub(crate) type HeaderSliceWithLength<H, T> = HeaderSlice<HeaderWithLength<H>, T>;
250
251impl<H: PartialOrd, T: ?Sized + PartialOrd> PartialOrd for HeaderSliceWithLength<H, T> {
252    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
253        (&self.header.header, &self.slice).partial_cmp(&(&other.header.header, &other.slice))
254    }
255}
256
257impl<H: Ord, T: ?Sized + Ord> Ord for HeaderSliceWithLength<H, T> {
258    fn cmp(&self, other: &Self) -> Ordering {
259        (&self.header.header, &self.slice).cmp(&(&other.header.header, &other.slice))
260    }
261}
262
263#[cfg(test)]
264mod tests {
265    use alloc::boxed::Box;
266    use alloc::string::String;
267    use alloc::vec;
268    use core::iter;
269
270    use crate::{Arc, HeaderSlice};
271
272    #[test]
273    fn from_header_and_iter_smoke() {
274        let arc = Arc::from_header_and_iter(
275            (42u32, 17u8),
276            IntoIterator::into_iter([1u16, 2, 3, 4, 5, 6, 7]),
277        );
278
279        assert_eq!(arc.header, (42, 17));
280        assert_eq!(arc.slice, [1, 2, 3, 4, 5, 6, 7]);
281    }
282
283    #[test]
284    fn from_header_and_slice_smoke() {
285        let arc = Arc::from_header_and_slice((42u32, 17u8), &[1u16, 2, 3, 4, 5, 6, 7]);
286
287        assert_eq!(arc.header, (42, 17));
288        assert_eq!(arc.slice, [1u16, 2, 3, 4, 5, 6, 7]);
289    }
290
291    #[test]
292    fn from_header_and_vec_smoke() {
293        let arc = Arc::from_header_and_vec((42u32, 17u8), vec![1u16, 2, 3, 4, 5, 6, 7]);
294
295        assert_eq!(arc.header, (42, 17));
296        assert_eq!(arc.slice, [1u16, 2, 3, 4, 5, 6, 7]);
297    }
298
299    #[test]
300    fn from_header_and_iter_empty() {
301        let arc = Arc::from_header_and_iter((42u32, 17u8), iter::empty::<u16>());
302
303        assert_eq!(arc.header, (42, 17));
304        assert_eq!(arc.slice, []);
305    }
306
307    #[test]
308    fn from_header_and_slice_empty() {
309        let arc = Arc::from_header_and_slice((42u32, 17u8), &[1u16; 0]);
310
311        assert_eq!(arc.header, (42, 17));
312        assert_eq!(arc.slice, []);
313    }
314
315    #[test]
316    fn from_header_and_vec_empty() {
317        let arc = Arc::from_header_and_vec((42u32, 17u8), vec![1u16; 0]);
318
319        assert_eq!(arc.header, (42, 17));
320        assert_eq!(arc.slice, []);
321    }
322
323    #[test]
324    fn issue_13_empty() {
325        crate::Arc::from_header_and_iter((), iter::empty::<usize>());
326    }
327
328    #[test]
329    fn issue_13_consumption() {
330        let s: &[u8] = &[0u8; 255];
331        crate::Arc::from_header_and_iter((), s.iter().copied());
332    }
333
334    #[test]
335    fn from_header_and_str_smoke() {
336        let a = Arc::from_header_and_str(
337            42,
338            "The answer to the ultimate question of life, the universe, and everything",
339        );
340        assert_eq!(a.header, 42);
341        assert_eq!(
342            &a.slice,
343            "The answer to the ultimate question of life, the universe, and everything"
344        );
345
346        let empty = Arc::from_header_and_str((), "");
347        assert_eq!(empty.header, ());
348        assert_eq!(&empty.slice, "");
349    }
350
351    #[test]
352    fn erase_and_create_from_thin_air_header() {
353        let a: Arc<HeaderSlice<(), [u32]>> = Arc::from_header_and_slice((), &[12, 17, 16]);
354        let b: Arc<[u32]> = a.into();
355
356        assert_eq!(&*b, [12, 17, 16]);
357
358        let c: Arc<HeaderSlice<(), [u32]>> = b.into();
359
360        assert_eq!(&c.slice, [12, 17, 16]);
361        assert_eq!(c.header, ());
362    }
363
364    #[test]
365    fn from_box_and_vec() {
366        let b = Box::new(String::from("xxx"));
367        let b = Arc::<String>::from(b);
368        assert_eq!(&*b, "xxx");
369
370        let v = vec![String::from("1"), String::from("2"), String::from("3")];
371        let v = Arc::<[_]>::from(v);
372        assert_eq!(
373            &*v,
374            [String::from("1"), String::from("2"), String::from("3")]
375        );
376
377        let mut v = vec![String::from("1"), String::from("2"), String::from("3")];
378        v.reserve(10);
379        let v = Arc::<[_]>::from(v);
380        assert_eq!(
381            &*v,
382            [String::from("1"), String::from("2"), String::from("3")]
383        );
384    }
385
386    /// It’s possible to make a generic `Arc` wrapper that supports both:
387    ///
388    /// * `T: !Sized`
389    /// * `Arc::make_mut` if `T: Sized`
390    #[test]
391    fn dst_and_make_mut() {
392        struct MyArc<T: ?Sized>(Arc<HeaderSlice<MyHeader, T>>);
393
394        #[derive(Clone)]
395        struct MyHeader {
396            // Very interesting things go here
397        }
398
399        // MyArc<str> is possible
400        let dst: MyArc<str> = MyArc(Arc::from_header_and_str(MyHeader {}, "example"));
401        assert_eq!(&dst.0.slice, "example");
402
403        // `make_mut` is still available when `T: Sized`
404        let mut answer: MyArc<u32> = MyArc(Arc::new(HeaderSlice {
405            header: MyHeader {},
406            // Not actually a slice in this case,
407            // but `HeaderSlice` is required to use `from_header_and_str`
408            // and we want the same `MyArc` to support both cases.
409            slice: 6 * 9,
410        }));
411        let mut_ref = Arc::make_mut(&mut answer.0);
412        mut_ref.slice = 42;
413    }
414}
triomphe/header.rs

triomphe/
header.rs
