]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | #![unstable(feature = "raw_vec_internals", reason = "implementation detail", issue = "none")] |
8faf50e0 XL |
2 | #![doc(hidden)] |
3 | ||
3b2f2976 | 4 | use core::cmp; |
c1a9b12d | 5 | use core::mem; |
3b2f2976 | 6 | use core::ops::Drop; |
83c7162d | 7 | use core::ptr::{self, NonNull, Unique}; |
92a42be0 | 8 | use core::slice; |
83c7162d | 9 | |
74b04a01 | 10 | use crate::alloc::{handle_alloc_error, AllocErr, AllocRef, Global, Layout}; |
9fa01778 | 11 | use crate::boxed::Box; |
dfeec247 | 12 | use crate::collections::TryReserveError::{self, *}; |
c1a9b12d | 13 | |
416331ca XL |
14 | #[cfg(test)] |
15 | mod tests; | |
16 | ||
5bcae85e | 17 | /// A low-level utility for more ergonomically allocating, reallocating, and deallocating |
c1a9b12d SL |
18 | /// a buffer of memory on the heap without having to worry about all the corner cases |
19 | /// involved. This type is excellent for building your own data structures like Vec and VecDeque. | |
20 | /// In particular: | |
21 | /// | |
e1599b0c XL |
22 | /// * Produces `Unique::empty()` on zero-sized types. |
23 | /// * Produces `Unique::empty()` on zero-length allocations. | |
24 | /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics). | |
25 | /// * Guards against 32-bit systems allocating more than isize::MAX bytes. | |
26 | /// * Guards against overflowing your length. | |
27 | /// * Aborts on OOM or calls `handle_alloc_error` as applicable. | |
28 | /// * Avoids freeing `Unique::empty()`. | |
29 | /// * Contains a `ptr::Unique` and thus endows the user with all related benefits. | |
c1a9b12d SL |
30 | /// |
31 | /// This type does not in anyway inspect the memory that it manages. When dropped it *will* | |
e1599b0c XL |
32 | /// free its memory, but it *won't* try to drop its contents. It is up to the user of `RawVec` |
33 | /// to handle the actual things *stored* inside of a `RawVec`. | |
c1a9b12d | 34 | /// |
e1599b0c XL |
35 | /// Note that a `RawVec` always forces its capacity to be `usize::MAX` for zero-sized types. |
36 | /// This enables you to use capacity-growing logic catch the overflows in your length | |
c1a9b12d SL |
37 | /// that might occur with zero-sized types. |
38 | /// | |
e1599b0c XL |
39 | /// The above means that you need to be careful when round-tripping this type with a |
40 | /// `Box<[T]>`, since `capacity()` won't yield the length. However, `with_capacity`, | |
41 | /// `shrink_to_fit`, and `from_box` will actually set `RawVec`'s private capacity | |
c1a9b12d SL |
42 | /// field. This allows zero-sized types to not be special-cased by consumers of |
43 | /// this type. | |
041b39d2 | 44 | #[allow(missing_debug_implementations)] |
74b04a01 | 45 | pub struct RawVec<T, A: AllocRef = Global> { |
c1a9b12d SL |
46 | ptr: Unique<T>, |
47 | cap: usize, | |
041b39d2 | 48 | a: A, |
c1a9b12d SL |
49 | } |
50 | ||
74b04a01 | 51 | impl<T, A: AllocRef> RawVec<T, A> { |
e1599b0c XL |
52 | /// Like `new`, but parameterized over the choice of allocator for |
53 | /// the returned `RawVec`. | |
83c7162d | 54 | pub const fn new_in(a: A) -> Self { |
dfeec247 | 55 | let cap = if mem::size_of::<T>() == 0 { core::usize::MAX } else { 0 }; |
c1a9b12d | 56 | |
e1599b0c | 57 | // `Unique::empty()` doubles as "unallocated" and "zero-sized allocation". |
dfeec247 | 58 | RawVec { ptr: Unique::empty(), cap, a } |
c1a9b12d SL |
59 | } |
60 | ||
e1599b0c XL |
61 | /// Like `with_capacity`, but parameterized over the choice of |
62 | /// allocator for the returned `RawVec`. | |
cc61c64b | 63 | #[inline] |
416331ca XL |
64 | pub fn with_capacity_in(capacity: usize, a: A) -> Self { |
65 | RawVec::allocate_in(capacity, false, a) | |
cc61c64b XL |
66 | } |
67 | ||
e1599b0c XL |
68 | /// Like `with_capacity_zeroed`, but parameterized over the choice |
69 | /// of allocator for the returned `RawVec`. | |
cc61c64b | 70 | #[inline] |
416331ca XL |
71 | pub fn with_capacity_zeroed_in(capacity: usize, a: A) -> Self { |
72 | RawVec::allocate_in(capacity, true, a) | |
cc61c64b XL |
73 | } |
74 | ||
74b04a01 XL |
75 | fn allocate_in(mut capacity: usize, zeroed: bool, mut a: A) -> Self { |
76 | let elem_size = mem::size_of::<T>(); | |
c1a9b12d | 77 | |
74b04a01 XL |
78 | let alloc_size = capacity.checked_mul(elem_size).unwrap_or_else(|| capacity_overflow()); |
79 | alloc_guard(alloc_size).unwrap_or_else(|_| capacity_overflow()); | |
c1a9b12d | 80 | |
74b04a01 XL |
81 | // Handles ZSTs and `capacity == 0` alike. |
82 | let ptr = if alloc_size == 0 { | |
83 | NonNull::<T>::dangling() | |
84 | } else { | |
85 | let align = mem::align_of::<T>(); | |
86 | let layout = Layout::from_size_align(alloc_size, align).unwrap(); | |
87 | let result = if zeroed { a.alloc_zeroed(layout) } else { a.alloc(layout) }; | |
88 | match result { | |
89 | Ok((ptr, size)) => { | |
90 | capacity = size / elem_size; | |
91 | ptr.cast() | |
b039eaaf | 92 | } |
74b04a01 XL |
93 | Err(_) => handle_alloc_error(layout), |
94 | } | |
95 | }; | |
c1a9b12d | 96 | |
74b04a01 | 97 | RawVec { ptr: ptr.into(), cap: capacity, a } |
c1a9b12d | 98 | } |
041b39d2 XL |
99 | } |
100 | ||
83c7162d | 101 | impl<T> RawVec<T, Global> { |
e1599b0c XL |
102 | /// HACK(Centril): This exists because `#[unstable]` `const fn`s needn't conform |
103 | /// to `min_const_fn` and so they cannot be called in `min_const_fn`s either. | |
104 | /// | |
105 | /// If you change `RawVec<T>::new` or dependencies, please take care to not | |
106 | /// introduce anything that would truly violate `min_const_fn`. | |
107 | /// | |
108 | /// NOTE: We could avoid this hack and check conformance with some | |
109 | /// `#[rustc_force_min_const_fn]` attribute which requires conformance | |
110 | /// with `min_const_fn` but does not necessarily allow calling it in | |
111 | /// `stable(...) const fn` / user code not enabling `foo` when | |
112 | /// `#[rustc_const_unstable(feature = "foo", ..)]` is present. | |
113 | pub const NEW: Self = Self::new(); | |
114 | ||
115 | /// Creates the biggest possible `RawVec` (on the system heap) | |
116 | /// without allocating. If `T` has positive size, then this makes a | |
117 | /// `RawVec` with capacity `0`. If `T` is zero-sized, then it makes a | |
118 | /// `RawVec` with capacity `usize::MAX`. Useful for implementing | |
041b39d2 | 119 | /// delayed allocation. |
83c7162d | 120 | pub const fn new() -> Self { |
dfeec247 | 121 | Self::new_in(Global) |
041b39d2 XL |
122 | } |
123 | ||
e1599b0c | 124 | /// Creates a `RawVec` (on the system heap) with exactly the |
416331ca | 125 | /// capacity and alignment requirements for a `[T; capacity]`. This is |
e1599b0c | 126 | /// equivalent to calling `RawVec::new` when `capacity` is `0` or `T` is |
041b39d2 | 127 | /// zero-sized. Note that if `T` is zero-sized this means you will |
e1599b0c | 128 | /// *not* get a `RawVec` with the requested capacity. |
041b39d2 XL |
129 | /// |
130 | /// # Panics | |
131 | /// | |
132 | /// * Panics if the requested capacity exceeds `usize::MAX` bytes. | |
133 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
134 | /// `isize::MAX` bytes. | |
135 | /// | |
136 | /// # Aborts | |
137 | /// | |
e1599b0c | 138 | /// Aborts on OOM. |
041b39d2 | 139 | #[inline] |
416331ca XL |
140 | pub fn with_capacity(capacity: usize) -> Self { |
141 | RawVec::allocate_in(capacity, false, Global) | |
041b39d2 | 142 | } |
c1a9b12d | 143 | |
e1599b0c | 144 | /// Like `with_capacity`, but guarantees the buffer is zeroed. |
041b39d2 | 145 | #[inline] |
416331ca XL |
146 | pub fn with_capacity_zeroed(capacity: usize) -> Self { |
147 | RawVec::allocate_in(capacity, true, Global) | |
041b39d2 XL |
148 | } |
149 | } | |
150 | ||
74b04a01 | 151 | impl<T, A: AllocRef> RawVec<T, A> { |
e1599b0c | 152 | /// Reconstitutes a `RawVec` from a pointer, capacity, and allocator. |
c1a9b12d | 153 | /// |
b039eaaf | 154 | /// # Undefined Behavior |
c1a9b12d | 155 | /// |
e1599b0c XL |
156 | /// The `ptr` must be allocated (via the given allocator `a`), and with the given `capacity`. |
157 | /// The `capacity` cannot exceed `isize::MAX` (only a concern on 32-bit systems). | |
158 | /// If the `ptr` and `capacity` come from a `RawVec` created via `a`, then this is guaranteed. | |
416331ca | 159 | pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, a: A) -> Self { |
dfeec247 | 160 | RawVec { ptr: Unique::new_unchecked(ptr), cap: capacity, a } |
041b39d2 XL |
161 | } |
162 | } | |
163 | ||
83c7162d | 164 | impl<T> RawVec<T, Global> { |
e1599b0c | 165 | /// Reconstitutes a `RawVec` from a pointer and capacity. |
041b39d2 XL |
166 | /// |
167 | /// # Undefined Behavior | |
168 | /// | |
e1599b0c XL |
169 | /// The `ptr` must be allocated (on the system heap), and with the given `capacity`. |
170 | /// The `capacity` cannot exceed `isize::MAX` (only a concern on 32-bit systems). | |
171 | /// If the `ptr` and `capacity` come from a `RawVec`, then this is guaranteed. | |
416331ca | 172 | pub unsafe fn from_raw_parts(ptr: *mut T, capacity: usize) -> Self { |
dfeec247 | 173 | RawVec { ptr: Unique::new_unchecked(ptr), cap: capacity, a: Global } |
c1a9b12d SL |
174 | } |
175 | ||
176 | /// Converts a `Box<[T]>` into a `RawVec<T>`. | |
177 | pub fn from_box(mut slice: Box<[T]>) -> Self { | |
178 | unsafe { | |
179 | let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len()); | |
180 | mem::forget(slice); | |
181 | result | |
182 | } | |
183 | } | |
184 | } | |
185 | ||
74b04a01 | 186 | impl<T, A: AllocRef> RawVec<T, A> { |
c1a9b12d | 187 | /// Gets a raw pointer to the start of the allocation. Note that this is |
e1599b0c | 188 | /// `Unique::empty()` if `capacity == 0` or `T` is zero-sized. In the former case, you must |
c1a9b12d SL |
189 | /// be careful. |
190 | pub fn ptr(&self) -> *mut T { | |
7cac9316 | 191 | self.ptr.as_ptr() |
c1a9b12d SL |
192 | } |
193 | ||
194 | /// Gets the capacity of the allocation. | |
195 | /// | |
196 | /// This will always be `usize::MAX` if `T` is zero-sized. | |
a7813a04 | 197 | #[inline(always)] |
416331ca | 198 | pub fn capacity(&self) -> usize { |
dfeec247 | 199 | if mem::size_of::<T>() == 0 { !0 } else { self.cap } |
c1a9b12d SL |
200 | } |
201 | ||
e1599b0c | 202 | /// Returns a shared reference to the allocator backing this `RawVec`. |
041b39d2 XL |
203 | pub fn alloc(&self) -> &A { |
204 | &self.a | |
205 | } | |
206 | ||
e1599b0c | 207 | /// Returns a mutable reference to the allocator backing this `RawVec`. |
041b39d2 XL |
208 | pub fn alloc_mut(&mut self) -> &mut A { |
209 | &mut self.a | |
210 | } | |
211 | ||
3b2f2976 XL |
212 | fn current_layout(&self) -> Option<Layout> { |
213 | if self.cap == 0 { | |
214 | None | |
215 | } else { | |
216 | // We have an allocated chunk of memory, so we can bypass runtime | |
217 | // checks to get our current layout. | |
218 | unsafe { | |
219 | let align = mem::align_of::<T>(); | |
220 | let size = mem::size_of::<T>() * self.cap; | |
221 | Some(Layout::from_size_align_unchecked(size, align)) | |
222 | } | |
223 | } | |
224 | } | |
225 | ||
c1a9b12d SL |
226 | /// Doubles the size of the type's backing allocation. This is common enough |
227 | /// to want to do that it's easiest to just have a dedicated method. Slightly | |
228 | /// more efficient logic can be provided for this than the general case. | |
229 | /// | |
230 | /// This function is ideal for when pushing elements one-at-a-time because | |
231 | /// you don't need to incur the costs of the more general computations | |
232 | /// reserve needs to do to guard against overflow. You do however need to | |
416331ca | 233 | /// manually check if your `len == capacity`. |
c1a9b12d SL |
234 | /// |
235 | /// # Panics | |
236 | /// | |
e1599b0c | 237 | /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust |
c1a9b12d SL |
238 | /// all `usize::MAX` slots in your imaginary buffer. |
239 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
240 | /// `isize::MAX` bytes. | |
241 | /// | |
242 | /// # Aborts | |
243 | /// | |
244 | /// Aborts on OOM | |
245 | /// | |
246 | /// # Examples | |
247 | /// | |
041b39d2 | 248 | /// ``` |
48663c56 | 249 | /// # #![feature(raw_vec_internals)] |
041b39d2 XL |
250 | /// # extern crate alloc; |
251 | /// # use std::ptr; | |
252 | /// # use alloc::raw_vec::RawVec; | |
c1a9b12d SL |
253 | /// struct MyVec<T> { |
254 | /// buf: RawVec<T>, | |
255 | /// len: usize, | |
256 | /// } | |
257 | /// | |
258 | /// impl<T> MyVec<T> { | |
259 | /// pub fn push(&mut self, elem: T) { | |
416331ca | 260 | /// if self.len == self.buf.capacity() { self.buf.double(); } |
c1a9b12d SL |
261 | /// // double would have aborted or panicked if the len exceeded |
262 | /// // `isize::MAX` so this is safe to do unchecked now. | |
263 | /// unsafe { | |
b7449926 | 264 | /// ptr::write(self.buf.ptr().add(self.len), elem); |
c1a9b12d SL |
265 | /// } |
266 | /// self.len += 1; | |
267 | /// } | |
268 | /// } | |
041b39d2 XL |
269 | /// # fn main() { |
270 | /// # let mut vec = MyVec { buf: RawVec::new(), len: 0 }; | |
271 | /// # vec.push(1); | |
272 | /// # } | |
c1a9b12d SL |
273 | /// ``` |
274 | #[inline(never)] | |
275 | #[cold] | |
276 | pub fn double(&mut self) { | |
277 | unsafe { | |
278 | let elem_size = mem::size_of::<T>(); | |
279 | ||
e1599b0c XL |
280 | // Since we set the capacity to `usize::MAX` when `elem_size` is |
281 | // 0, getting to here necessarily means the `RawVec` is overfull. | |
c1a9b12d SL |
282 | assert!(elem_size != 0, "capacity overflow"); |
283 | ||
74b04a01 | 284 | let (ptr, new_cap) = match self.current_layout() { |
3b2f2976 XL |
285 | Some(cur) => { |
286 | // Since we guarantee that we never allocate more than | |
e1599b0c | 287 | // `isize::MAX` bytes, `elem_size * self.cap <= isize::MAX` as |
3b2f2976 XL |
288 | // a precondition, so this can't overflow. Additionally the |
289 | // alignment will never be too large as to "not be | |
290 | // satisfiable", so `Layout::from_size_align` will always | |
291 | // return `Some`. | |
292 | // | |
e1599b0c | 293 | // TL;DR, we bypass runtime checks due to dynamic assertions |
3b2f2976 XL |
294 | // in this module, allowing us to use |
295 | // `from_size_align_unchecked`. | |
296 | let new_cap = 2 * self.cap; | |
297 | let new_size = new_cap * elem_size; | |
83c7162d | 298 | alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow()); |
dfeec247 | 299 | let ptr_res = self.a.realloc(NonNull::from(self.ptr).cast(), cur, new_size); |
3b2f2976 | 300 | match ptr_res { |
74b04a01 | 301 | Ok((ptr, new_size)) => (ptr, new_size / elem_size), |
dfeec247 XL |
302 | Err(_) => handle_alloc_error(Layout::from_size_align_unchecked( |
303 | new_size, | |
304 | cur.align(), | |
305 | )), | |
3b2f2976 XL |
306 | } |
307 | } | |
308 | None => { | |
e1599b0c XL |
309 | // Skip to 4 because tiny `Vec`'s are dumb; but not if that |
310 | // would cause overflow. | |
3b2f2976 | 311 | let new_cap = if elem_size > (!0) / 8 { 1 } else { 4 }; |
74b04a01 XL |
312 | let layout = Layout::array::<T>(new_cap).unwrap(); |
313 | match self.a.alloc(layout) { | |
314 | Ok((ptr, new_size)) => (ptr, new_size / elem_size), | |
315 | Err(_) => handle_alloc_error(layout), | |
3b2f2976 XL |
316 | } |
317 | } | |
041b39d2 | 318 | }; |
74b04a01 | 319 | self.ptr = ptr.cast().into(); |
c1a9b12d SL |
320 | self.cap = new_cap; |
321 | } | |
322 | } | |
323 | ||
9cc50fc6 SL |
324 | /// Attempts to double the size of the type's backing allocation in place. This is common |
325 | /// enough to want to do that it's easiest to just have a dedicated method. Slightly | |
326 | /// more efficient logic can be provided for this than the general case. | |
327 | /// | |
9fa01778 | 328 | /// Returns `true` if the reallocation attempt has succeeded. |
9cc50fc6 SL |
329 | /// |
330 | /// # Panics | |
331 | /// | |
e1599b0c | 332 | /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust |
9cc50fc6 SL |
333 | /// all `usize::MAX` slots in your imaginary buffer. |
334 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
335 | /// `isize::MAX` bytes. | |
336 | #[inline(never)] | |
337 | #[cold] | |
338 | pub fn double_in_place(&mut self) -> bool { | |
339 | unsafe { | |
340 | let elem_size = mem::size_of::<T>(); | |
3b2f2976 XL |
341 | let old_layout = match self.current_layout() { |
342 | Some(layout) => layout, | |
343 | None => return false, // nothing to double | |
344 | }; | |
9cc50fc6 | 345 | |
e1599b0c XL |
346 | // Since we set the capacity to `usize::MAX` when `elem_size` is |
347 | // 0, getting to here necessarily means the `RawVec` is overfull. | |
9cc50fc6 SL |
348 | assert!(elem_size != 0, "capacity overflow"); |
349 | ||
e1599b0c | 350 | // Since we guarantee that we never allocate more than `isize::MAX` |
3b2f2976 XL |
351 | // bytes, `elem_size * self.cap <= isize::MAX` as a precondition, so |
352 | // this can't overflow. | |
353 | // | |
e1599b0c | 354 | // Similarly to with `double` above, we can go straight to |
3b2f2976 XL |
355 | // `Layout::from_size_align_unchecked` as we know this won't |
356 | // overflow and the alignment is sufficiently small. | |
9cc50fc6 | 357 | let new_cap = 2 * self.cap; |
3b2f2976 | 358 | let new_size = new_cap * elem_size; |
83c7162d | 359 | alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow()); |
94b46f34 | 360 | match self.a.grow_in_place(NonNull::from(self.ptr).cast(), old_layout, new_size) { |
041b39d2 XL |
361 | Ok(_) => { |
362 | // We can't directly divide `size`. | |
363 | self.cap = new_cap; | |
364 | true | |
365 | } | |
dfeec247 | 366 | Err(_) => false, |
9cc50fc6 | 367 | } |
9cc50fc6 SL |
368 | } |
369 | } | |
370 | ||
94b46f34 | 371 | /// The same as `reserve_exact`, but returns on errors instead of panicking or aborting. |
dfeec247 XL |
372 | pub fn try_reserve_exact( |
373 | &mut self, | |
374 | used_capacity: usize, | |
375 | needed_extra_capacity: usize, | |
376 | ) -> Result<(), TryReserveError> { | |
416331ca | 377 | self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Exact) |
94b46f34 XL |
378 | } |
379 | ||
c1a9b12d | 380 | /// Ensures that the buffer contains at least enough space to hold |
416331ca | 381 | /// `used_capacity + needed_extra_capacity` elements. If it doesn't already, |
c1a9b12d SL |
382 | /// will reallocate the minimum possible amount of memory necessary. |
383 | /// Generally this will be exactly the amount of memory necessary, | |
384 | /// but in principle the allocator is free to give back more than | |
385 | /// we asked for. | |
386 | /// | |
416331ca | 387 | /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate |
c1a9b12d | 388 | /// the requested space. This is not really unsafe, but the unsafe |
b039eaaf | 389 | /// code *you* write that relies on the behavior of this function may break. |
c1a9b12d SL |
390 | /// |
391 | /// # Panics | |
392 | /// | |
393 | /// * Panics if the requested capacity exceeds `usize::MAX` bytes. | |
394 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
395 | /// `isize::MAX` bytes. | |
396 | /// | |
397 | /// # Aborts | |
398 | /// | |
e1599b0c | 399 | /// Aborts on OOM. |
416331ca XL |
400 | pub fn reserve_exact(&mut self, used_capacity: usize, needed_extra_capacity: usize) { |
401 | match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Exact) { | |
83c7162d | 402 | Err(CapacityOverflow) => capacity_overflow(), |
e1599b0c | 403 | Err(AllocError { .. }) => unreachable!(), |
0531ce1d | 404 | Ok(()) => { /* yay */ } |
dfeec247 XL |
405 | } |
406 | } | |
0531ce1d | 407 | |
416331ca XL |
408 | /// Calculates the buffer's new size given that it'll hold `used_capacity + |
409 | /// needed_extra_capacity` elements. This logic is used in amortized reserve methods. | |
9cc50fc6 | 410 | /// Returns `(new_capacity, new_alloc_size)`. |
dfeec247 XL |
411 | fn amortized_new_size( |
412 | &self, | |
413 | used_capacity: usize, | |
414 | needed_extra_capacity: usize, | |
415 | ) -> Result<usize, TryReserveError> { | |
e1599b0c | 416 | // Nothing we can really do about these checks, sadly. |
dfeec247 XL |
417 | let required_cap = |
418 | used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; | |
9cc50fc6 SL |
419 | // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`. |
420 | let double_cap = self.cap * 2; | |
421 | // `double_cap` guarantees exponential growth. | |
0531ce1d | 422 | Ok(cmp::max(double_cap, required_cap)) |
9cc50fc6 SL |
423 | } |
424 | ||
94b46f34 | 425 | /// The same as `reserve`, but returns on errors instead of panicking or aborting. |
dfeec247 XL |
426 | pub fn try_reserve( |
427 | &mut self, | |
428 | used_capacity: usize, | |
429 | needed_extra_capacity: usize, | |
430 | ) -> Result<(), TryReserveError> { | |
416331ca | 431 | self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Amortized) |
94b46f34 XL |
432 | } |
433 | ||
c1a9b12d | 434 | /// Ensures that the buffer contains at least enough space to hold |
416331ca | 435 | /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have |
c1a9b12d | 436 | /// enough capacity, will reallocate enough space plus comfortable slack |
b039eaaf | 437 | /// space to get amortized `O(1)` behavior. Will limit this behavior |
c1a9b12d SL |
438 | /// if it would needlessly cause itself to panic. |
439 | /// | |
416331ca | 440 | /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate |
c1a9b12d | 441 | /// the requested space. This is not really unsafe, but the unsafe |
b039eaaf | 442 | /// code *you* write that relies on the behavior of this function may break. |
c1a9b12d SL |
443 | /// |
444 | /// This is ideal for implementing a bulk-push operation like `extend`. | |
445 | /// | |
446 | /// # Panics | |
447 | /// | |
448 | /// * Panics if the requested capacity exceeds `usize::MAX` bytes. | |
449 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
450 | /// `isize::MAX` bytes. | |
451 | /// | |
452 | /// # Aborts | |
453 | /// | |
e1599b0c | 454 | /// Aborts on OOM. |
c1a9b12d SL |
455 | /// |
456 | /// # Examples | |
457 | /// | |
041b39d2 | 458 | /// ``` |
48663c56 | 459 | /// # #![feature(raw_vec_internals)] |
041b39d2 XL |
460 | /// # extern crate alloc; |
461 | /// # use std::ptr; | |
462 | /// # use alloc::raw_vec::RawVec; | |
c1a9b12d SL |
463 | /// struct MyVec<T> { |
464 | /// buf: RawVec<T>, | |
465 | /// len: usize, | |
466 | /// } | |
467 | /// | |
041b39d2 | 468 | /// impl<T: Clone> MyVec<T> { |
c1a9b12d SL |
469 | /// pub fn push_all(&mut self, elems: &[T]) { |
470 | /// self.buf.reserve(self.len, elems.len()); | |
471 | /// // reserve would have aborted or panicked if the len exceeded | |
472 | /// // `isize::MAX` so this is safe to do unchecked now. | |
473 | /// for x in elems { | |
474 | /// unsafe { | |
b7449926 | 475 | /// ptr::write(self.buf.ptr().add(self.len), x.clone()); |
c1a9b12d SL |
476 | /// } |
477 | /// self.len += 1; | |
478 | /// } | |
479 | /// } | |
480 | /// } | |
041b39d2 XL |
481 | /// # fn main() { |
482 | /// # let mut vector = MyVec { buf: RawVec::new(), len: 0 }; | |
483 | /// # vector.push_all(&[1, 3, 5, 7, 9]); | |
484 | /// # } | |
c1a9b12d | 485 | /// ``` |
416331ca XL |
486 | pub fn reserve(&mut self, used_capacity: usize, needed_extra_capacity: usize) { |
487 | match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Amortized) { | |
83c7162d | 488 | Err(CapacityOverflow) => capacity_overflow(), |
e1599b0c | 489 | Err(AllocError { .. }) => unreachable!(), |
0531ce1d | 490 | Ok(()) => { /* yay */ } |
94b46f34 XL |
491 | } |
492 | } | |
9cc50fc6 | 493 | /// Attempts to ensure that the buffer contains at least enough space to hold |
416331ca | 494 | /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have |
9cc50fc6 | 495 | /// enough capacity, will reallocate in place enough space plus comfortable slack |
3b2f2976 | 496 | /// space to get amortized `O(1)` behavior. Will limit this behaviour |
9cc50fc6 SL |
497 | /// if it would needlessly cause itself to panic. |
498 | /// | |
416331ca | 499 | /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate |
9cc50fc6 | 500 | /// the requested space. This is not really unsafe, but the unsafe |
3b2f2976 | 501 | /// code *you* write that relies on the behavior of this function may break. |
9cc50fc6 | 502 | /// |
9fa01778 | 503 | /// Returns `true` if the reallocation attempt has succeeded. |
9cc50fc6 SL |
504 | /// |
505 | /// # Panics | |
506 | /// | |
507 | /// * Panics if the requested capacity exceeds `usize::MAX` bytes. | |
508 | /// * Panics on 32-bit platforms if the requested capacity exceeds | |
509 | /// `isize::MAX` bytes. | |
416331ca | 510 | pub fn reserve_in_place(&mut self, used_capacity: usize, needed_extra_capacity: usize) -> bool { |
9cc50fc6 | 511 | unsafe { |
9cc50fc6 SL |
512 | // NOTE: we don't early branch on ZSTs here because we want this |
513 | // to actually catch "asking for more than usize::MAX" in that case. | |
514 | // If we make it past the first branch then we are guaranteed to | |
515 | // panic. | |
516 | ||
517 | // Don't actually need any more capacity. If the current `cap` is 0, we can't | |
518 | // reallocate in place. | |
416331ca | 519 | // Wrapping in case they give a bad `used_capacity` |
3b2f2976 XL |
520 | let old_layout = match self.current_layout() { |
521 | Some(layout) => layout, | |
522 | None => return false, | |
523 | }; | |
416331ca | 524 | if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity { |
9cc50fc6 SL |
525 | return false; |
526 | } | |
527 | ||
dfeec247 XL |
528 | let new_cap = self |
529 | .amortized_new_size(used_capacity, needed_extra_capacity) | |
83c7162d | 530 | .unwrap_or_else(|_| capacity_overflow()); |
9cc50fc6 | 531 | |
416331ca XL |
532 | // Here, `cap < used_capacity + needed_extra_capacity <= new_cap` |
533 | // (regardless of whether `self.cap - used_capacity` wrapped). | |
e1599b0c | 534 | // Therefore, we can safely call `grow_in_place`. |
041b39d2 | 535 | |
041b39d2 | 536 | let new_layout = Layout::new::<T>().repeat(new_cap).unwrap().0; |
3b2f2976 | 537 | // FIXME: may crash and burn on over-reserve |
83c7162d XL |
538 | alloc_guard(new_layout.size()).unwrap_or_else(|_| capacity_overflow()); |
539 | match self.a.grow_in_place( | |
dfeec247 XL |
540 | NonNull::from(self.ptr).cast(), |
541 | old_layout, | |
542 | new_layout.size(), | |
83c7162d | 543 | ) { |
041b39d2 XL |
544 | Ok(_) => { |
545 | self.cap = new_cap; | |
546 | true | |
547 | } | |
dfeec247 | 548 | Err(_) => false, |
9cc50fc6 | 549 | } |
9cc50fc6 SL |
550 | } |
551 | } | |
552 | ||
c1a9b12d SL |
553 | /// Shrinks the allocation down to the specified amount. If the given amount |
554 | /// is 0, actually completely deallocates. | |
555 | /// | |
556 | /// # Panics | |
557 | /// | |
558 | /// Panics if the given amount is *larger* than the current capacity. | |
559 | /// | |
560 | /// # Aborts | |
561 | /// | |
562 | /// Aborts on OOM. | |
563 | pub fn shrink_to_fit(&mut self, amount: usize) { | |
564 | let elem_size = mem::size_of::<T>(); | |
c1a9b12d SL |
565 | |
566 | // Set the `cap` because they might be about to promote to a `Box<[T]>` | |
567 | if elem_size == 0 { | |
568 | self.cap = amount; | |
569 | return; | |
570 | } | |
571 | ||
e1599b0c | 572 | // This check is my waterloo; it's the only thing `Vec` wouldn't have to do. |
c1a9b12d SL |
573 | assert!(self.cap >= amount, "Tried to shrink to a larger capacity"); |
574 | ||
575 | if amount == 0 { | |
041b39d2 | 576 | // We want to create a new zero-length vector within the |
e1599b0c | 577 | // same allocator. We use `ptr::write` to avoid an |
041b39d2 | 578 | // erroneous attempt to drop the contents, and we use |
e1599b0c | 579 | // `ptr::read` to sidestep condition against destructuring |
041b39d2 XL |
580 | // types that implement Drop. |
581 | ||
582 | unsafe { | |
583 | let a = ptr::read(&self.a as *const A); | |
584 | self.dealloc_buffer(); | |
585 | ptr::write(self, RawVec::new_in(a)); | |
586 | } | |
c1a9b12d SL |
587 | } else if self.cap != amount { |
588 | unsafe { | |
3b2f2976 XL |
589 | // We know here that our `amount` is greater than zero. This |
590 | // implies, via the assert above, that capacity is also greater | |
591 | // than zero, which means that we've got a current layout that | |
592 | // "fits" | |
593 | // | |
594 | // We also know that `self.cap` is greater than `amount`, and | |
595 | // consequently we don't need runtime checks for creating either | |
e1599b0c | 596 | // layout. |
3b2f2976 XL |
597 | let old_size = elem_size * self.cap; |
598 | let new_size = elem_size * amount; | |
599 | let align = mem::align_of::<T>(); | |
600 | let old_layout = Layout::from_size_align_unchecked(old_size, align); | |
dfeec247 | 601 | match self.a.realloc(NonNull::from(self.ptr).cast(), old_layout, new_size) { |
74b04a01 | 602 | Ok((ptr, _)) => self.ptr = ptr.cast().into(), |
dfeec247 XL |
603 | Err(_) => { |
604 | handle_alloc_error(Layout::from_size_align_unchecked(new_size, align)) | |
605 | } | |
b039eaaf | 606 | } |
c1a9b12d SL |
607 | } |
608 | self.cap = amount; | |
609 | } | |
610 | } | |
041b39d2 | 611 | } |
c1a9b12d | 612 | |
94b46f34 XL |
613 | enum Fallibility { |
614 | Fallible, | |
615 | Infallible, | |
616 | } | |
617 | ||
9fa01778 | 618 | use Fallibility::*; |
94b46f34 XL |
619 | |
620 | enum ReserveStrategy { | |
621 | Exact, | |
622 | Amortized, | |
623 | } | |
624 | ||
9fa01778 | 625 | use ReserveStrategy::*; |
94b46f34 | 626 | |
74b04a01 | 627 | impl<T, A: AllocRef> RawVec<T, A> { |
94b46f34 XL |
628 | fn reserve_internal( |
629 | &mut self, | |
416331ca XL |
630 | used_capacity: usize, |
631 | needed_extra_capacity: usize, | |
94b46f34 XL |
632 | fallibility: Fallibility, |
633 | strategy: ReserveStrategy, | |
e1599b0c | 634 | ) -> Result<(), TryReserveError> { |
74b04a01 XL |
635 | let elem_size = mem::size_of::<T>(); |
636 | ||
94b46f34 | 637 | unsafe { |
94b46f34 XL |
638 | // NOTE: we don't early branch on ZSTs here because we want this |
639 | // to actually catch "asking for more than usize::MAX" in that case. | |
640 | // If we make it past the first branch then we are guaranteed to | |
641 | // panic. | |
642 | ||
643 | // Don't actually need any more capacity. | |
416331ca XL |
644 | // Wrapping in case they gave a bad `used_capacity`. |
645 | if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity { | |
94b46f34 XL |
646 | return Ok(()); |
647 | } | |
648 | ||
e1599b0c | 649 | // Nothing we can really do about these checks, sadly. |
94b46f34 | 650 | let new_cap = match strategy { |
dfeec247 XL |
651 | Exact => { |
652 | used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)? | |
653 | } | |
416331ca | 654 | Amortized => self.amortized_new_size(used_capacity, needed_extra_capacity)?, |
94b46f34 XL |
655 | }; |
656 | let new_layout = Layout::array::<T>(new_cap).map_err(|_| CapacityOverflow)?; | |
657 | ||
658 | alloc_guard(new_layout.size())?; | |
659 | ||
660 | let res = match self.current_layout() { | |
661 | Some(layout) => { | |
662 | debug_assert!(new_layout.align() == layout.align()); | |
663 | self.a.realloc(NonNull::from(self.ptr).cast(), layout, new_layout.size()) | |
664 | } | |
665 | None => self.a.alloc(new_layout), | |
666 | }; | |
667 | ||
74b04a01 | 668 | let (ptr, new_cap) = match (res, fallibility) { |
94b46f34 | 669 | (Err(AllocErr), Infallible) => handle_alloc_error(new_layout), |
dfeec247 XL |
670 | (Err(AllocErr), Fallible) => { |
671 | return Err(TryReserveError::AllocError { | |
672 | layout: new_layout, | |
673 | non_exhaustive: (), | |
674 | }); | |
675 | } | |
74b04a01 | 676 | (Ok((ptr, new_size)), _) => (ptr, new_size / elem_size), |
e1599b0c | 677 | }; |
94b46f34 | 678 | |
e1599b0c | 679 | self.ptr = ptr.cast().into(); |
94b46f34 XL |
680 | self.cap = new_cap; |
681 | ||
682 | Ok(()) | |
683 | } | |
684 | } | |
94b46f34 XL |
685 | } |
686 | ||
83c7162d | 687 | impl<T> RawVec<T, Global> { |
c1a9b12d SL |
688 | /// Converts the entire buffer into `Box<[T]>`. |
689 | /// | |
c1a9b12d | 690 | /// Note that this will correctly reconstitute any `cap` changes |
e1599b0c | 691 | /// that may have been performed. (See description of type for details.) |
dc9dc135 XL |
692 | /// |
693 | /// # Undefined Behavior | |
694 | /// | |
695 | /// All elements of `RawVec<T, Global>` must be initialized. Notice that | |
696 | /// the rules around uninitialized boxed values are not finalized yet, | |
697 | /// but until they are, it is advisable to avoid them. | |
c1a9b12d | 698 | pub unsafe fn into_box(self) -> Box<[T]> { |
e1599b0c | 699 | // NOTE: not calling `capacity()` here; actually using the real `cap` field! |
c1a9b12d SL |
700 | let slice = slice::from_raw_parts_mut(self.ptr(), self.cap); |
701 | let output: Box<[T]> = Box::from_raw(slice); | |
702 | mem::forget(self); | |
703 | output | |
704 | } | |
c1a9b12d SL |
705 | } |
706 | ||
74b04a01 | 707 | impl<T, A: AllocRef> RawVec<T, A> { |
e1599b0c | 708 | /// Frees the memory owned by the `RawVec` *without* trying to drop its contents. |
041b39d2 | 709 | pub unsafe fn dealloc_buffer(&mut self) { |
c1a9b12d | 710 | let elem_size = mem::size_of::<T>(); |
3b2f2976 XL |
711 | if elem_size != 0 { |
712 | if let Some(layout) = self.current_layout() { | |
94b46f34 | 713 | self.a.dealloc(NonNull::from(self.ptr).cast(), layout); |
3b2f2976 | 714 | } |
c1a9b12d SL |
715 | } |
716 | } | |
717 | } | |
718 | ||
74b04a01 | 719 | unsafe impl<#[may_dangle] T, A: AllocRef> Drop for RawVec<T, A> { |
e1599b0c | 720 | /// Frees the memory owned by the `RawVec` *without* trying to drop its contents. |
041b39d2 | 721 | fn drop(&mut self) { |
dfeec247 XL |
722 | unsafe { |
723 | self.dealloc_buffer(); | |
724 | } | |
041b39d2 XL |
725 | } |
726 | } | |
727 | ||
c1a9b12d | 728 | // We need to guarantee the following: |
e1599b0c XL |
729 | // * We don't ever allocate `> isize::MAX` byte-size objects. |
730 | // * We don't overflow `usize::MAX` and actually allocate too little. | |
c1a9b12d SL |
731 | // |
732 | // On 64-bit we just need to check for overflow since trying to allocate | |
3157f602 XL |
733 | // `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add |
734 | // an extra guard for this in case we're running on a platform which can use | |
e1599b0c | 735 | // all 4GB in user-space, e.g., PAE or x32. |
c1a9b12d SL |
736 | |
737 | #[inline] | |
e1599b0c | 738 | fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> { |
9fa01778 | 739 | if mem::size_of::<usize>() < 8 && alloc_size > core::isize::MAX as usize { |
0531ce1d XL |
740 | Err(CapacityOverflow) |
741 | } else { | |
742 | Ok(()) | |
e9174d1e | 743 | } |
c1a9b12d | 744 | } |
92a42be0 | 745 | |
83c7162d XL |
746 | // One central function responsible for reporting capacity overflows. This'll |
747 | // ensure that the code generation related to these panics is minimal as there's | |
748 | // only one location which panics rather than a bunch throughout the module. | |
749 | fn capacity_overflow() -> ! { | |
e1599b0c | 750 | panic!("capacity overflow"); |
83c7162d | 751 | } |