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