| 1 | |
| 2 |
|
| 3 | #![unstable(feature = "raw_vec_internals", reason = "unstable const warnings", issue = "none")]
|
| 4 |
|
| 5 | use core::alloc::LayoutError;
|
| 6 | use core::cmp;
|
| 7 | use core::intrinsics;
|
| 8 | use core::mem::{self, ManuallyDrop, MaybeUninit};
|
| 9 | use core::ops::Drop;
|
| 10 | use core::ptr::{self, NonNull, Unique};
|
| 11 | use core::slice;
|
| 12 |
|
| 13 | #[cfg(not(no_global_oom_handling))]
|
| 14 | use crate::alloc::handle_alloc_error;
|
| 15 | use crate::alloc::{Allocator, Global, Layout};
|
| 16 | use crate::boxed::Box;
|
| 17 | use crate::collections::TryReserveError;
|
| 18 | use crate::collections::TryReserveErrorKind::*;
|
| 19 |
|
| 20 | #[cfg(test)]
|
| 21 | mod tests;
|
| 22 |
|
| 23 | enum AllocInit {
|
| 24 | |
| 25 | Uninitialized,
|
| 26 | |
| 27 | #[allow(dead_code)]
|
| 28 | Zeroed,
|
| 29 | }
|
| 30 |
|
| 31 | |
| 32 | |
| 33 | |
| 34 | |
| 35 | |
| 36 | |
| 37 | |
| 38 | |
| 39 | |
| 40 | |
| 41 | |
| 42 | |
| 43 | |
| 44 | |
| 45 | |
| 46 | |
| 47 | |
| 48 | |
| 49 | |
| 50 | |
| 51 | |
| 52 | |
| 53 | #[allow(missing_debug_implementations)]
|
| 54 | pub(crate) struct RawVec<T, A: Allocator = Global> {
|
| 55 | ptr: Unique<T>,
|
| 56 | cap: usize,
|
| 57 | alloc: A,
|
| 58 | }
|
| 59 |
|
| 60 | impl<T> RawVec<T, Global> {
|
| 61 | |
| 62 | |
| 63 | |
| 64 | |
| 65 | |
| 66 | pub const NEW: Self = Self::new();
|
| 67 |
|
| 68 | |
| 69 | |
| 70 | |
| 71 | |
| 72 | |
| 73 | #[must_use]
|
| 74 | pub const fn new() -> Self {
|
| 75 | Self::new_in(Global)
|
| 76 | }
|
| 77 |
|
| 78 | |
| 79 | |
| 80 | |
| 81 | |
| 82 | |
| 83 | |
| 84 | |
| 85 | |
| 86 | |
| 87 | |
| 88 | |
| 89 | |
| 90 | |
| 91 | #[cfg(not(any(no_global_oom_handling, test)))]
|
| 92 | #[must_use]
|
| 93 | #[inline]
|
| 94 | pub fn with_capacity(capacity: usize) -> Self {
|
| 95 | Self::with_capacity_in(capacity, Global)
|
| 96 | }
|
| 97 |
|
| 98 | |
| 99 | #[cfg(not(any(no_global_oom_handling, test)))]
|
| 100 | #[must_use]
|
| 101 | #[inline]
|
| 102 | pub fn with_capacity_zeroed(capacity: usize) -> Self {
|
| 103 | Self::with_capacity_zeroed_in(capacity, Global)
|
| 104 | }
|
| 105 | }
|
| 106 |
|
| 107 | impl<T, A: Allocator> RawVec<T, A> {
|
| 108 | |
| 109 | |
| 110 | |
| 111 | |
| 112 | |
| 113 | pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::<T>() == 1 {
|
| 114 | 8
|
| 115 | } else if mem::size_of::<T>() <= 1024 {
|
| 116 | 4
|
| 117 | } else {
|
| 118 | 1
|
| 119 | };
|
| 120 |
|
| 121 | |
| 122 | |
| 123 | pub const fn new_in(alloc: A) -> Self {
|
| 124 | |
| 125 | Self { ptr: Unique::dangling(), cap: 0, alloc }
|
| 126 | }
|
| 127 |
|
| 128 | |
| 129 | |
| 130 | #[cfg(not(no_global_oom_handling))]
|
| 131 | #[inline]
|
| 132 | pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
|
| 133 | Self::allocate_in(capacity, AllocInit::Uninitialized, alloc)
|
| 134 | }
|
| 135 |
|
| 136 | |
| 137 | |
| 138 | #[inline]
|
| 139 | pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
|
| 140 | Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc)
|
| 141 | }
|
| 142 |
|
| 143 | |
| 144 | |
| 145 | #[cfg(not(no_global_oom_handling))]
|
| 146 | #[inline]
|
| 147 | pub fn with_capacity_zeroed_in(capacity: usize, alloc: A) -> Self {
|
| 148 | Self::allocate_in(capacity, AllocInit::Zeroed, alloc)
|
| 149 | }
|
| 150 |
|
| 151 | |
| 152 | |
| 153 | |
| 154 | |
| 155 | |
| 156 | |
| 157 | |
| 158 | |
| 159 | |
| 160 | |
| 161 | |
| 162 | |
| 163 | pub unsafe fn into_box(self, len: usize) -> Box<[MaybeUninit<T>], A> {
|
| 164 | |
| 165 | debug_assert!(
|
| 166 | len <= self.capacity(),
|
| 167 | "`len` must be smaller than or equal to `self.capacity()`"
|
| 168 | );
|
| 169 |
|
| 170 | let me = ManuallyDrop::new(self);
|
| 171 | unsafe {
|
| 172 | let slice = slice::from_raw_parts_mut(me.ptr() as *mut MaybeUninit<T>, len);
|
| 173 | Box::from_raw_in(slice, ptr::read(&me.alloc))
|
| 174 | }
|
| 175 | }
|
| 176 |
|
| 177 | #[cfg(not(no_global_oom_handling))]
|
| 178 | fn allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Self {
|
| 179 | |
| 180 | if mem::size_of::<T>() == 0 || capacity == 0 {
|
| 181 | Self::new_in(alloc)
|
| 182 | } else {
|
| 183 | |
| 184 | |
| 185 | let layout = match Layout::array::<T>(capacity) {
|
| 186 | Ok(layout) => layout,
|
| 187 | Err(_) => capacity_overflow(),
|
| 188 | };
|
| 189 | match alloc_guard(layout.size()) {
|
| 190 | Ok(_) => {}
|
| 191 | Err(_) => capacity_overflow(),
|
| 192 | }
|
| 193 | let result = match init {
|
| 194 | AllocInit::Uninitialized => alloc.allocate(layout),
|
| 195 | AllocInit::Zeroed => alloc.allocate_zeroed(layout),
|
| 196 | };
|
| 197 | let ptr = match result {
|
| 198 | Ok(ptr) => ptr,
|
| 199 | Err(_) => handle_alloc_error(layout),
|
| 200 | };
|
| 201 |
|
| 202 | |
| 203 | |
| 204 | |
| 205 | Self {
|
| 206 | ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) },
|
| 207 | cap: capacity,
|
| 208 | alloc,
|
| 209 | }
|
| 210 | }
|
| 211 | }
|
| 212 |
|
| 213 | fn try_allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Result<Self, TryReserveError> {
|
| 214 | |
| 215 | if mem::size_of::<T>() == 0 || capacity == 0 {
|
| 216 | return Ok(Self::new_in(alloc));
|
| 217 | }
|
| 218 |
|
| 219 | let layout = Layout::array::<T>(capacity).map_err(|_| CapacityOverflow)?;
|
| 220 | alloc_guard(layout.size())?;
|
| 221 | let result = match init {
|
| 222 | AllocInit::Uninitialized => alloc.allocate(layout),
|
| 223 | AllocInit::Zeroed => alloc.allocate_zeroed(layout),
|
| 224 | };
|
| 225 | let ptr = result.map_err(|_| AllocError { layout, non_exhaustive: () })?;
|
| 226 |
|
| 227 | |
| 228 | |
| 229 | |
| 230 | Ok(Self {
|
| 231 | ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) },
|
| 232 | cap: capacity,
|
| 233 | alloc,
|
| 234 | })
|
| 235 | }
|
| 236 |
|
| 237 | |
| 238 | |
| 239 | |
| 240 | |
| 241 | |
| 242 | |
| 243 | |
| 244 | |
| 245 | |
| 246 | |
| 247 | #[inline]
|
| 248 | pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, alloc: A) -> Self {
|
| 249 | Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap: capacity, alloc }
|
| 250 | }
|
| 251 |
|
| 252 | |
| 253 | |
| 254 | |
| 255 | #[inline]
|
| 256 | pub fn ptr(&self) -> *mut T {
|
| 257 | self.ptr.as_ptr()
|
| 258 | }
|
| 259 |
|
| 260 | |
| 261 | |
| 262 | |
| 263 | #[inline(always)]
|
| 264 | pub fn capacity(&self) -> usize {
|
| 265 | if mem::size_of::<T>() == 0 { usize::MAX } else { self.cap }
|
| 266 | }
|
| 267 |
|
| 268 | |
| 269 | pub fn allocator(&self) -> &A {
|
| 270 | &self.alloc
|
| 271 | }
|
| 272 |
|
| 273 | fn current_memory(&self) -> Option<(NonNull<u8>, Layout)> {
|
| 274 | if mem::size_of::<T>() == 0 || self.cap == 0 {
|
| 275 | None
|
| 276 | } else {
|
| 277 | |
| 278 | |
| 279 | unsafe {
|
| 280 | let layout = Layout::array::<T>(self.cap).unwrap_unchecked();
|
| 281 | Some((self.ptr.cast().into(), layout))
|
| 282 | }
|
| 283 | }
|
| 284 | }
|
| 285 |
|
| 286 | |
| 287 | |
| 288 | |
| 289 | |
| 290 | |
| 291 | |
| 292 | |
| 293 | |
| 294 | |
| 295 | |
| 296 | |
| 297 | |
| 298 | |
| 299 | |
| 300 | |
| 301 | |
| 302 | |
| 303 | |
| 304 | |
| 305 | #[cfg(not(no_global_oom_handling))]
|
| 306 | #[inline]
|
| 307 | pub fn reserve(&mut self, len: usize, additional: usize) {
|
| 308 | |
| 309 | |
| 310 | |
| 311 | |
| 312 | #[cold]
|
| 313 | fn do_reserve_and_handle<T, A: Allocator>(
|
| 314 | slf: &mut RawVec<T, A>,
|
| 315 | len: usize,
|
| 316 | additional: usize,
|
| 317 | ) {
|
| 318 | handle_reserve(slf.grow_amortized(len, additional));
|
| 319 | }
|
| 320 |
|
| 321 | if self.needs_to_grow(len, additional) {
|
| 322 | do_reserve_and_handle(self, len, additional);
|
| 323 | }
|
| 324 | }
|
| 325 |
|
| 326 | |
| 327 | |
| 328 | #[cfg(not(no_global_oom_handling))]
|
| 329 | #[inline(never)]
|
| 330 | pub fn reserve_for_push(&mut self, len: usize) {
|
| 331 | handle_reserve(self.grow_amortized(len, 1));
|
| 332 | }
|
| 333 |
|
| 334 | |
| 335 | pub fn try_reserve(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
|
| 336 | if self.needs_to_grow(len, additional) {
|
| 337 | self.grow_amortized(len, additional)
|
| 338 | } else {
|
| 339 | Ok(())
|
| 340 | }
|
| 341 | }
|
| 342 |
|
| 343 | |
| 344 | #[inline(never)]
|
| 345 | pub fn try_reserve_for_push(&mut self, len: usize) -> Result<(), TryReserveError> {
|
| 346 | self.grow_amortized(len, 1)
|
| 347 | }
|
| 348 |
|
| 349 | |
| 350 | |
| 351 | |
| 352 | |
| 353 | |
| 354 | |
| 355 | |
| 356 | |
| 357 | |
| 358 | |
| 359 | |
| 360 | |
| 361 | |
| 362 | |
| 363 | |
| 364 | |
| 365 | |
| 366 | #[cfg(not(no_global_oom_handling))]
|
| 367 | pub fn reserve_exact(&mut self, len: usize, additional: usize) {
|
| 368 | handle_reserve(self.try_reserve_exact(len, additional));
|
| 369 | }
|
| 370 |
|
| 371 | |
| 372 | pub fn try_reserve_exact(
|
| 373 | &mut self,
|
| 374 | len: usize,
|
| 375 | additional: usize,
|
| 376 | ) -> Result<(), TryReserveError> {
|
| 377 | if self.needs_to_grow(len, additional) { self.grow_exact(len, additional) } else { Ok(()) }
|
| 378 | }
|
| 379 |
|
| 380 | |
| 381 | |
| 382 | |
| 383 | |
| 384 | |
| 385 | |
| 386 | |
| 387 | |
| 388 | |
| 389 | |
| 390 | #[cfg(not(no_global_oom_handling))]
|
| 391 | pub fn shrink_to_fit(&mut self, cap: usize) {
|
| 392 | handle_reserve(self.shrink(cap));
|
| 393 | }
|
| 394 | }
|
| 395 |
|
| 396 | impl<T, A: Allocator> RawVec<T, A> {
|
| 397 | |
| 398 | |
| 399 | fn needs_to_grow(&self, len: usize, additional: usize) -> bool {
|
| 400 | additional > self.capacity().wrapping_sub(len)
|
| 401 | }
|
| 402 |
|
| 403 | fn set_ptr_and_cap(&mut self, ptr: NonNull<[u8]>, cap: usize) {
|
| 404 | |
| 405 | |
| 406 | |
| 407 | self.ptr = unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) };
|
| 408 | self.cap = cap;
|
| 409 | }
|
| 410 |
|
| 411 | |
| 412 | |
| 413 | |
| 414 | |
| 415 | |
| 416 | |
| 417 | |
| 418 | fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
|
| 419 | |
| 420 | debug_assert!(additional > 0);
|
| 421 |
|
| 422 | if mem::size_of::<T>() == 0 {
|
| 423 | |
| 424 | |
| 425 | return Err(CapacityOverflow.into());
|
| 426 | }
|
| 427 |
|
| 428 | |
| 429 | let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;
|
| 430 |
|
| 431 | |
| 432 | |
| 433 | let cap = cmp::max(self.cap * 2, required_cap);
|
| 434 | let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);
|
| 435 |
|
| 436 | let new_layout = Layout::array::<T>(cap);
|
| 437 |
|
| 438 | |
| 439 | let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
|
| 440 | self.set_ptr_and_cap(ptr, cap);
|
| 441 | Ok(())
|
| 442 | }
|
| 443 |
|
| 444 | |
| 445 | |
| 446 | |
| 447 | fn grow_exact(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
|
| 448 | if mem::size_of::<T>() == 0 {
|
| 449 | |
| 450 | |
| 451 | return Err(CapacityOverflow.into());
|
| 452 | }
|
| 453 |
|
| 454 | let cap = len.checked_add(additional).ok_or(CapacityOverflow)?;
|
| 455 | let new_layout = Layout::array::<T>(cap);
|
| 456 |
|
| 457 | |
| 458 | let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
|
| 459 | self.set_ptr_and_cap(ptr, cap);
|
| 460 | Ok(())
|
| 461 | }
|
| 462 |
|
| 463 | #[allow(dead_code)]
|
| 464 | fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> {
|
| 465 | assert!(cap <= self.capacity(), "Tried to shrink to a larger capacity");
|
| 466 |
|
| 467 | let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) };
|
| 468 |
|
| 469 | let ptr = unsafe {
|
| 470 | |
| 471 | |
| 472 | let new_layout = Layout::array::<T>(cap).unwrap_unchecked();
|
| 473 | self.alloc
|
| 474 | .shrink(ptr, layout, new_layout)
|
| 475 | .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })?
|
| 476 | };
|
| 477 | self.set_ptr_and_cap(ptr, cap);
|
| 478 | Ok(())
|
| 479 | }
|
| 480 | }
|
| 481 |
|
| 482 | |
| 483 | |
| 484 | |
| 485 | |
| 486 | #[inline(never)]
|
| 487 | fn finish_grow<A>(
|
| 488 | new_layout: Result<Layout, LayoutError>,
|
| 489 | current_memory: Option<(NonNull<u8>, Layout)>,
|
| 490 | alloc: &mut A,
|
| 491 | ) -> Result<NonNull<[u8]>, TryReserveError>
|
| 492 | where
|
| 493 | A: Allocator,
|
| 494 | {
|
| 495 | |
| 496 | let new_layout = new_layout.map_err(|_| CapacityOverflow)?;
|
| 497 |
|
| 498 | alloc_guard(new_layout.size())?;
|
| 499 |
|
| 500 | let memory = if let Some((ptr, old_layout)) = current_memory {
|
| 501 | debug_assert_eq!(old_layout.align(), new_layout.align());
|
| 502 | unsafe {
|
| 503 | |
| 504 | intrinsics::assume(old_layout.align() == new_layout.align());
|
| 505 | alloc.grow(ptr, old_layout, new_layout)
|
| 506 | }
|
| 507 | } else {
|
| 508 | alloc.allocate(new_layout)
|
| 509 | };
|
| 510 |
|
| 511 | memory.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () }.into())
|
| 512 | }
|
| 513 |
|
| 514 | unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawVec<T, A> {
|
| 515 | |
| 516 | fn drop(&mut self) {
|
| 517 | if let Some((ptr, layout)) = self.current_memory() {
|
| 518 | unsafe { self.alloc.deallocate(ptr, layout) }
|
| 519 | }
|
| 520 | }
|
| 521 | }
|
| 522 |
|
| 523 | |
| 524 | #[cfg(not(no_global_oom_handling))]
|
| 525 | #[inline]
|
| 526 | fn handle_reserve(result: Result<(), TryReserveError>) {
|
| 527 | match result.map_err(|e| e.kind()) {
|
| 528 | Err(CapacityOverflow) => capacity_overflow(),
|
| 529 | Err(AllocError { layout, .. }) => handle_alloc_error(layout),
|
| 530 | Ok(()) => { }
|
| 531 | }
|
| 532 | }
|
| 533 |
|
| 534 | |
| 535 | |
| 536 | |
| 537 | |
| 538 | |
| 539 | |
| 540 | |
| 541 | |
| 542 |
|
| 543 | #[inline]
|
| 544 | fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> {
|
| 545 | if usize::BITS < 64 && alloc_size > isize::MAX as usize {
|
| 546 | Err(CapacityOverflow.into())
|
| 547 | } else {
|
| 548 | Ok(())
|
| 549 | }
|
| 550 | }
|
| 551 |
|
| 552 | |
| 553 | |
| 554 | |
| 555 | #[cfg(not(no_global_oom_handling))]
|
| 556 | fn capacity_overflow() -> ! {
|
| 557 | panic!("capacity overflow");
|
| 558 | }
|