allocator_api2/
slice.rs

1use crate::{
2    alloc::{Allocator, Global},
3    vec::Vec,
4};
5
6/// Slice methods that use `Box` and `Vec` from this crate.
7pub trait SliceExt<T> {
8    /// Copies `self` into a new `Vec`.
9    ///
10    /// # Examples
11    ///
12    /// ```
13    /// use allocator_api2::SliceExt;
14    ///
15    /// let s = [10, 40, 30];
16    /// let x = SliceExt::to_vec(&s[..]);
17    /// // Here, `s` and `x` can be modified independently.
18    /// ```
19    #[cfg(not(no_global_oom_handling))]
20    #[inline(always)]
21    fn to_vec(&self) -> Vec<T, Global>
22    where
23        T: Clone,
24    {
25        self.to_vec_in(Global)
26    }
27
28    /// Copies `self` into a new `Vec` with an allocator.
29    ///
30    /// # Examples
31    ///
32    /// ```
33    /// use allocator_api2::{SliceExt, alloc::System};
34    ///
35    /// let s = [10, 40, 30];
36    /// let x = SliceExt::to_vec_in(&s[..], System);
37    /// // Here, `s` and `x` can be modified independently.
38    /// ```
39    #[cfg(not(no_global_oom_handling))]
40    fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
41    where
42        T: Clone;
43
44    /// Creates a vector by copying a slice `n` times.
45    ///
46    /// # Panics
47    ///
48    /// This function will panic if the capacity would overflow.
49    ///
50    /// # Examples
51    ///
52    /// Basic usage:
53    ///
54    /// ```
55    /// use allocator_api2::{SliceExt, vec};
56    ///
57    /// assert_eq!(SliceExt::repeat(&[1, 2][..], 3), vec![1, 2, 1, 2, 1, 2]);
58    /// ```
59    ///
60    /// A panic upon overflow:
61    ///
62    /// ```should_panic
63    /// // this will panic at runtime
64    /// b"0123456789abcdef".repeat(usize::MAX);
65    /// ```
66    fn repeat(&self, n: usize) -> Vec<T, Global>
67    where
68        T: Copy;
69}
70
71impl<T> SliceExt<T> for [T] {
72    #[cfg(not(no_global_oom_handling))]
73    #[inline]
74    fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
75    where
76        T: Clone,
77    {
78        struct DropGuard<'a, T, A: Allocator> {
79            vec: &'a mut Vec<T, A>,
80            num_init: usize,
81        }
82        impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
83            #[inline]
84            fn drop(&mut self) {
85                // SAFETY:
86                // items were marked initialized in the loop below
87                unsafe {
88                    self.vec.set_len(self.num_init);
89                }
90            }
91        }
92
93        let mut vec = Vec::with_capacity_in(self.len(), alloc);
94        let mut guard = DropGuard {
95            vec: &mut vec,
96            num_init: 0,
97        };
98        let slots = guard.vec.spare_capacity_mut();
99        // .take(slots.len()) is necessary for LLVM to remove bounds checks
100        // and has better codegen than zip.
101        for (i, b) in self.iter().enumerate().take(slots.len()) {
102            guard.num_init = i;
103            slots[i].write(b.clone());
104        }
105        core::mem::forget(guard);
106        // SAFETY:
107        // the vec was allocated and initialized above to at least this length.
108        unsafe {
109            vec.set_len(self.len());
110        }
111        vec
112    }
113
114    #[cfg(not(no_global_oom_handling))]
115    #[inline]
116    fn repeat(&self, n: usize) -> Vec<T, Global>
117    where
118        T: Copy,
119    {
120        if n == 0 {
121            return Vec::new();
122        }
123
124        // If `n` is larger than zero, it can be split as
125        // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
126        // `2^expn` is the number represented by the leftmost '1' bit of `n`,
127        // and `rem` is the remaining part of `n`.
128
129        // Using `Vec` to access `set_len()`.
130        let capacity = self.len().checked_mul(n).expect("capacity overflow");
131        let mut buf = Vec::with_capacity(capacity);
132
133        // `2^expn` repetition is done by doubling `buf` `expn`-times.
134        buf.extend(self);
135        {
136            let mut m = n >> 1;
137            // If `m > 0`, there are remaining bits up to the leftmost '1'.
138            while m > 0 {
139                // `buf.extend(buf)`:
140                unsafe {
141                    core::ptr::copy_nonoverlapping(
142                        buf.as_ptr(),
143                        (buf.as_mut_ptr() as *mut T).add(buf.len()),
144                        buf.len(),
145                    );
146                    // `buf` has capacity of `self.len() * n`.
147                    let buf_len = buf.len();
148                    buf.set_len(buf_len * 2);
149                }
150
151                m >>= 1;
152            }
153        }
154
155        // `rem` (`= n - 2^expn`) repetition is done by copying
156        // first `rem` repetitions from `buf` itself.
157        let rem_len = capacity - buf.len(); // `self.len() * rem`
158        if rem_len > 0 {
159            // `buf.extend(buf[0 .. rem_len])`:
160            unsafe {
161                // This is non-overlapping since `2^expn > rem`.
162                core::ptr::copy_nonoverlapping(
163                    buf.as_ptr(),
164                    (buf.as_mut_ptr() as *mut T).add(buf.len()),
165                    rem_len,
166                );
167                // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
168                buf.set_len(capacity);
169            }
170        }
171        buf
172    }
173}
allocator_api2/slice.rs

allocator_api2/
slice.rs
