bumpalo/collections/vec.rs
1// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A contiguous growable array type with heap-allocated contents, written
12//! [`Vec<'bump, T>`].
13//!
14//! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and
15//! `O(1)` pop (from the end).
16//!
17//! This module is a fork of the [`std::vec`] module, that uses a bump allocator.
18//!
19//! [`std::vec`]: https://doc.rust-lang.org/std/vec/index.html
20//!
21//! # Examples
22//!
23//! You can explicitly create a [`Vec<'bump, T>`] with [`new_in`]:
24//!
25//! ```
26//! use bumpalo::{Bump, collections::Vec};
27//!
28//! let b = Bump::new();
29//! let v: Vec<i32> = Vec::new_in(&b);
30//! ```
31//!
32//! ... or by using the [`vec!`] macro:
33//!
34//! ```
35//! use bumpalo::{Bump, collections::Vec};
36//!
37//! let b = Bump::new();
38//!
39//! let v: Vec<i32> = bumpalo::vec![in &b];
40//!
41//! let v = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
42//!
43//! let v = bumpalo::vec![in &b; 0; 10]; // ten zeroes
44//! ```
45//!
46//! You can [`push`] values onto the end of a vector (which will grow the vector
47//! as needed):
48//!
49//! ```
50//! use bumpalo::{Bump, collections::Vec};
51//!
52//! let b = Bump::new();
53//!
54//! let mut v = bumpalo::vec![in &b; 1, 2];
55//!
56//! v.push(3);
57//! ```
58//!
59//! Popping values works in much the same way:
60//!
61//! ```
62//! use bumpalo::{Bump, collections::Vec};
63//!
64//! let b = Bump::new();
65//!
66//! let mut v = bumpalo::vec![in &b; 1, 2];
67//!
68//! assert_eq!(v.pop(), Some(2));
69//! ```
70//!
71//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
72//!
73//! ```
74//! use bumpalo::{Bump, collections::Vec};
75//!
76//! let b = Bump::new();
77//!
78//! let mut v = bumpalo::vec![in &b; 1, 2, 3];
79//! assert_eq!(v[2], 3);
80//! v[1] += 5;
81//! assert_eq!(v, [1, 7, 3]);
82//! ```
83//!
84//! [`Vec<'bump, T>`]: struct.Vec.html
85//! [`new_in`]: struct.Vec.html#method.new_in
86//! [`push`]: struct.Vec.html#method.push
87//! [`Index`]: https://doc.rust-lang.org/std/ops/trait.Index.html
88//! [`IndexMut`]: https://doc.rust-lang.org/std/ops/trait.IndexMut.html
89//! [`vec!`]: ../../macro.vec.html
90
91use super::raw_vec::RawVec;
92use crate::collections::CollectionAllocErr;
93use crate::Bump;
94use core::borrow::{Borrow, BorrowMut};
95use core::cmp::Ordering;
96use core::fmt;
97use core::hash::{self, Hash};
98use core::iter::FusedIterator;
99use core::marker::PhantomData;
100use core::mem;
101use core::ops;
102use core::ops::Bound::{Excluded, Included, Unbounded};
103use core::ops::{Index, IndexMut, RangeBounds};
104use core::ptr;
105use core::ptr::NonNull;
106use core::slice;
107#[cfg(feature = "std")]
108use std::io;
109
110unsafe fn arith_offset<T>(p: *const T, offset: isize) -> *const T {
111 p.offset(offset)
112}
113
114fn partition_dedup_by<T, F>(s: &mut [T], mut same_bucket: F) -> (&mut [T], &mut [T])
115where
116 F: FnMut(&mut T, &mut T) -> bool,
117{
118 // Although we have a mutable reference to `s`, we cannot make
119 // *arbitrary* changes. The `same_bucket` calls could panic, so we
120 // must ensure that the slice is in a valid state at all times.
121 //
122 // The way that we handle this is by using swaps; we iterate
123 // over all the elements, swapping as we go so that at the end
124 // the elements we wish to keep are in the front, and those we
125 // wish to reject are at the back. We can then split the slice.
126 // This operation is still O(n).
127 //
128 // Example: We start in this state, where `r` represents "next
129 // read" and `w` represents "next_write`.
130 //
131 // r
132 // +---+---+---+---+---+---+
133 // | 0 | 1 | 1 | 2 | 3 | 3 |
134 // +---+---+---+---+---+---+
135 // w
136 //
137 // Comparing s[r] against s[w-1], this is not a duplicate, so
138 // we swap s[r] and s[w] (no effect as r==w) and then increment both
139 // r and w, leaving us with:
140 //
141 // r
142 // +---+---+---+---+---+---+
143 // | 0 | 1 | 1 | 2 | 3 | 3 |
144 // +---+---+---+---+---+---+
145 // w
146 //
147 // Comparing s[r] against s[w-1], this value is a duplicate,
148 // so we increment `r` but leave everything else unchanged:
149 //
150 // r
151 // +---+---+---+---+---+---+
152 // | 0 | 1 | 1 | 2 | 3 | 3 |
153 // +---+---+---+---+---+---+
154 // w
155 //
156 // Comparing s[r] against s[w-1], this is not a duplicate,
157 // so swap s[r] and s[w] and advance r and w:
158 //
159 // r
160 // +---+---+---+---+---+---+
161 // | 0 | 1 | 2 | 1 | 3 | 3 |
162 // +---+---+---+---+---+---+
163 // w
164 //
165 // Not a duplicate, repeat:
166 //
167 // r
168 // +---+---+---+---+---+---+
169 // | 0 | 1 | 2 | 3 | 1 | 3 |
170 // +---+---+---+---+---+---+
171 // w
172 //
173 // Duplicate, advance r. End of slice. Split at w.
174
175 let len = s.len();
176 if len <= 1 {
177 return (s, &mut []);
178 }
179
180 let ptr = s.as_mut_ptr();
181 let mut next_read: usize = 1;
182 let mut next_write: usize = 1;
183
184 unsafe {
185 // Avoid bounds checks by using raw pointers.
186 while next_read < len {
187 let ptr_read = ptr.add(next_read);
188 let prev_ptr_write = ptr.add(next_write - 1);
189 if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
190 if next_read != next_write {
191 let ptr_write = prev_ptr_write.offset(1);
192 mem::swap(&mut *ptr_read, &mut *ptr_write);
193 }
194 next_write += 1;
195 }
196 next_read += 1;
197 }
198 }
199
200 s.split_at_mut(next_write)
201}
202
203unsafe fn offset_from<T>(p: *const T, origin: *const T) -> isize
204where
205 T: Sized,
206{
207 let pointee_size = mem::size_of::<T>();
208 assert!(0 < pointee_size && pointee_size <= isize::max_value() as usize);
209
210 // This is the same sequence that Clang emits for pointer subtraction.
211 // It can be neither `nsw` nor `nuw` because the input is treated as
212 // unsigned but then the output is treated as signed, so neither works.
213 let d = isize::wrapping_sub(p as _, origin as _);
214 d / (pointee_size as isize)
215}
216
217/// Creates a [`Vec`] containing the arguments.
218///
219/// `vec!` allows `Vec`s to be defined with the same syntax as array expressions.
220/// There are two forms of this macro:
221///
222/// - Create a [`Vec`] containing a given list of elements:
223///
224/// ```
225/// use bumpalo::Bump;
226///
227/// let b = Bump::new();
228/// let v = bumpalo::vec![in &b; 1, 2, 3];
229/// assert_eq!(v, [1, 2, 3]);
230/// ```
231///
232/// - Create a [`Vec`] from a given element and size:
233///
234/// ```
235/// use bumpalo::Bump;
236///
237/// let b = Bump::new();
238/// let v = bumpalo::vec![in &b; 1; 3];
239/// assert_eq!(v, [1, 1, 1]);
240/// ```
241///
242/// Note that unlike array expressions, this syntax supports all elements
243/// which implement [`Clone`] and the number of elements doesn't have to be
244/// a constant.
245///
246/// This will use `clone` to duplicate an expression, so one should be careful
247/// using this with types having a non-standard `Clone` implementation. For
248/// example, `bumpalo::vec![in ≎ Rc::new(1); 5]` will create a vector of five references
249/// to the same boxed integer value, not five references pointing to independently
250/// boxed integers.
251///
252/// [`Vec`]: collections/vec/struct.Vec.html
253/// [`Clone`]: https://doc.rust-lang.org/std/clone/trait.Clone.html
254#[macro_export]
255macro_rules! vec {
256 (in $bump:expr; $elem:expr; $n:expr) => {{
257 let n = $n;
258 let mut v = $crate::collections::Vec::with_capacity_in(n, $bump);
259 if n > 0 {
260 let elem = $elem;
261 for _ in 0..n - 1 {
262 v.push(elem.clone());
263 }
264 v.push(elem);
265 }
266 v
267 }};
268 (in $bump:expr) => { $crate::collections::Vec::new_in($bump) };
269 (in $bump:expr; $($x:expr),*) => {{
270 let mut v = $crate::collections::Vec::new_in($bump);
271 $( v.push($x); )*
272 v
273 }};
274 (in $bump:expr; $($x:expr,)*) => (bumpalo::vec![in $bump; $($x),*])
275}
276
277/// A contiguous growable array type, written `Vec<'bump, T>` but pronounced 'vector'.
278///
279/// # Examples
280///
281/// ```
282/// use bumpalo::{Bump, collections::Vec};
283///
284/// let b = Bump::new();
285///
286/// let mut vec = Vec::new_in(&b);
287/// vec.push(1);
288/// vec.push(2);
289///
290/// assert_eq!(vec.len(), 2);
291/// assert_eq!(vec[0], 1);
292///
293/// assert_eq!(vec.pop(), Some(2));
294/// assert_eq!(vec.len(), 1);
295///
296/// vec[0] = 7;
297/// assert_eq!(vec[0], 7);
298///
299/// vec.extend([1, 2, 3].iter().cloned());
300///
301/// for x in &vec {
302/// println!("{}", x);
303/// }
304/// assert_eq!(vec, [7, 1, 2, 3]);
305/// ```
306///
307/// The [`vec!`] macro is provided to make initialization more convenient:
308///
309/// ```
310/// use bumpalo::{Bump, collections::Vec};
311///
312/// let b = Bump::new();
313///
314/// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
315/// vec.push(4);
316/// assert_eq!(vec, [1, 2, 3, 4]);
317/// ```
318///
319/// It can also initialize each element of a `Vec<'bump, T>` with a given value.
320/// This may be more efficient than performing allocation and initialization
321/// in separate steps, especially when initializing a vector of zeros:
322///
323/// ```
324/// use bumpalo::{Bump, collections::Vec};
325///
326/// let b = Bump::new();
327///
328/// let vec = bumpalo::vec![in &b; 0; 5];
329/// assert_eq!(vec, [0, 0, 0, 0, 0]);
330///
331/// // The following is equivalent, but potentially slower:
332/// let mut vec1 = Vec::with_capacity_in(5, &b);
333/// vec1.resize(5, 0);
334/// ```
335///
336/// Use a `Vec<'bump, T>` as an efficient stack:
337///
338/// ```
339/// use bumpalo::{Bump, collections::Vec};
340///
341/// let b = Bump::new();
342///
343/// let mut stack = Vec::new_in(&b);
344///
345/// stack.push(1);
346/// stack.push(2);
347/// stack.push(3);
348///
349/// while let Some(top) = stack.pop() {
350/// // Prints 3, 2, 1
351/// println!("{}", top);
352/// }
353/// ```
354///
355/// # Indexing
356///
357/// The `Vec` type allows to access values by index, because it implements the
358/// [`Index`] trait. An example will be more explicit:
359///
360/// ```
361/// use bumpalo::{Bump, collections::Vec};
362///
363/// let b = Bump::new();
364///
365/// let v = bumpalo::vec![in &b; 0, 2, 4, 6];
366/// println!("{}", v[1]); // it will display '2'
367/// ```
368///
369/// However be careful: if you try to access an index which isn't in the `Vec`,
370/// your software will panic! You cannot do this:
371///
372/// ```should_panic
373/// use bumpalo::{Bump, collections::Vec};
374///
375/// let b = Bump::new();
376///
377/// let v = bumpalo::vec![in &b; 0, 2, 4, 6];
378/// println!("{}", v[6]); // it will panic!
379/// ```
380///
381/// In conclusion: always check if the index you want to get really exists
382/// before doing it.
383///
384/// # Slicing
385///
386/// A `Vec` can be mutable. Slices, on the other hand, are read-only objects.
387/// To get a slice, use `&`. Example:
388///
389/// ```
390/// use bumpalo::{Bump, collections::Vec};
391///
392/// fn read_slice(slice: &[usize]) {
393/// // ...
394/// }
395///
396/// let b = Bump::new();
397///
398/// let v = bumpalo::vec![in &b; 0, 1];
399/// read_slice(&v);
400///
401/// // ... and that's all!
402/// // you can also do it like this:
403/// let x : &[usize] = &v;
404/// ```
405///
406/// In Rust, it's more common to pass slices as arguments rather than vectors
407/// when you just want to provide a read access. The same goes for [`String`] and
408/// [`&str`].
409///
410/// # Capacity and reallocation
411///
412/// The capacity of a vector is the amount of space allocated for any future
413/// elements that will be added onto the vector. This is not to be confused with
414/// the *length* of a vector, which specifies the number of actual elements
415/// within the vector. If a vector's length exceeds its capacity, its capacity
416/// will automatically be increased, but its elements will have to be
417/// reallocated.
418///
419/// For example, a vector with capacity 10 and length 0 would be an empty vector
420/// with space for 10 more elements. Pushing 10 or fewer elements onto the
421/// vector will not change its capacity or cause reallocation to occur. However,
422/// if the vector's length is increased to 11, it will have to reallocate, which
423/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity_in`]
424/// whenever possible to specify how big the vector is expected to get.
425///
426/// # Guarantees
427///
428/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
429/// about its design. This ensures that it's as low-overhead as possible in
430/// the general case, and can be correctly manipulated in primitive ways
431/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<'bump, T>`.
432/// If additional type parameters are added (e.g. to support custom allocators),
433/// overriding their defaults may change the behavior.
434///
435/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
436/// triplet. No more, no less. The order of these fields is completely
437/// unspecified, and you should use the appropriate methods to modify these.
438/// The pointer will never be null, so this type is null-pointer-optimized.
439///
440/// However, the pointer may not actually point to allocated memory. In particular,
441/// if you construct a `Vec` with capacity 0 via [`Vec::new_in`], [`bumpalo::vec![in bump]`][`vec!`],
442/// [`Vec::with_capacity_in(0)`][`Vec::with_capacity_in`], or by calling [`shrink_to_fit`]
443/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
444/// types inside a `Vec`, it will not allocate space for them. *Note that in this case
445/// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only
446/// if <code>[`mem::size_of::<T>`]\() * capacity() > 0</code>. In general, `Vec`'s allocation
447/// details are very subtle — if you intend to allocate memory using a `Vec`
448/// and use it for something else (either to pass to unsafe code, or to build your
449/// own memory-backed collection), be sure to deallocate this memory by using
450/// `from_raw_parts` to recover the `Vec` and then dropping it.
451///
452/// If a `Vec` *has* allocated memory, then the memory it points to is
453/// in the [`Bump`] arena used to construct it, and its
454/// pointer points to [`len`] initialized, contiguous elements in order (what
455/// you would see if you coerced it to a slice), followed by <code>[`capacity`] -
456/// [`len`]</code> logically uninitialized, contiguous elements.
457///
458/// `Vec` will never perform a "small optimization" where elements are actually
459/// stored on the stack for two reasons:
460///
461/// * It would make it more difficult for unsafe code to correctly manipulate
462/// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
463/// only moved, and it would be more difficult to determine if a `Vec` had
464/// actually allocated memory.
465///
466/// * It would penalize the general case, incurring an additional branch
467/// on every access.
468///
469/// `Vec` will never automatically shrink itself, even if completely empty. This
470/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
471/// and then filling it back up to the same [`len`] should incur no calls to
472/// the allocator. If you wish to free up unused memory, use
473/// [`shrink_to_fit`][`shrink_to_fit`].
474///
475/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
476/// sufficient. [`push`] and [`insert`] *will* (re)allocate if
477/// <code>[`len`] == [`capacity`]</code>. That is, the reported capacity is completely
478/// accurate, and can be relied on. It can even be used to manually free the memory
479/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
480/// when not necessary.
481///
482/// `Vec` does not guarantee any particular growth strategy when reallocating
483/// when full, nor when [`reserve`] is called. The current strategy is basic
484/// and it may prove desirable to use a non-constant growth factor. Whatever
485/// strategy is used will of course guarantee `O(1)` amortized [`push`].
486///
487/// `bumpalo::vec![in bump; x; n]`, `bumpalo::vec![in bump; a, b, c, d]`, and
488/// [`Vec::with_capacity_in(n)`][`Vec::with_capacity_in`], will all produce a
489/// `Vec` with exactly the requested capacity. If <code>[`len`] == [`capacity`]</code>, (as
490/// is the case for the [`vec!`] macro), then a `Vec<'bump, T>` can be converted
491/// to and from a [`Box<[T]>`][owned slice] without reallocating or moving the
492/// elements.
493///
494/// `Vec` will not specifically overwrite any data that is removed from it,
495/// but also won't specifically preserve it. Its uninitialized memory is
496/// scratch space that it may use however it wants. It will generally just do
497/// whatever is most efficient or otherwise easy to implement. Do not rely on
498/// removed data to be erased for security purposes. Even if you drop a `Vec`, its
499/// buffer may simply be reused by another `Vec`. Even if you zero a `Vec`'s memory
500/// first, that may not actually happen because the optimizer does not consider
501/// this a side-effect that must be preserved. There is one case which we will
502/// not break, however: using `unsafe` code to write to the excess capacity,
503/// and then increasing the length to match, is always valid.
504///
505/// `Vec` does not currently guarantee the order in which elements are dropped.
506/// The order has changed in the past and may change again.
507///
508/// [`vec!`]: ../../macro.vec.html
509/// [`Index`]: https://doc.rust-lang.org/std/ops/trait.Index.html
510/// [`String`]: ../string/struct.String.html
511/// [`&str`]: https://doc.rust-lang.org/std/primitive.str.html
512/// [`Vec::with_capacity_in`]: struct.Vec.html#method.with_capacity_in
513/// [`Vec::new_in`]: struct.Vec.html#method.new_in
514/// [`shrink_to_fit`]: struct.Vec.html#method.shrink_to_fit
515/// [`capacity`]: struct.Vec.html#method.capacity
516/// [`mem::size_of::<T>`]: https://doc.rust-lang.org/std/mem/fn.size_of.html
517/// [`len`]: struct.Vec.html#method.len
518/// [`push`]: struct.Vec.html#method.push
519/// [`insert`]: struct.Vec.html#method.insert
520/// [`reserve`]: struct.Vec.html#method.reserve
521/// [owned slice]: https://doc.rust-lang.org/std/boxed/struct.Box.html
522pub struct Vec<'bump, T: 'bump> {
523 buf: RawVec<'bump, T>,
524 len: usize,
525}
526
527////////////////////////////////////////////////////////////////////////////////
528// Inherent methods
529////////////////////////////////////////////////////////////////////////////////
530
531impl<'bump, T: 'bump> Vec<'bump, T> {
532 /// Constructs a new, empty `Vec<'bump, T>`.
533 ///
534 /// The vector will not allocate until elements are pushed onto it.
535 ///
536 /// # Examples
537 ///
538 /// ```
539 /// # #![allow(unused_mut)]
540 /// use bumpalo::{Bump, collections::Vec};
541 ///
542 /// let b = Bump::new();
543 /// let mut vec: Vec<i32> = Vec::new_in(&b);
544 /// ```
545 #[inline]
546 pub fn new_in(bump: &'bump Bump) -> Vec<'bump, T> {
547 Vec {
548 buf: RawVec::new_in(bump),
549 len: 0,
550 }
551 }
552
553 /// Constructs a new, empty `Vec<'bump, T>` with the specified capacity.
554 ///
555 /// The vector will be able to hold exactly `capacity` elements without
556 /// reallocating. If `capacity` is 0, the vector will not allocate.
557 ///
558 /// It is important to note that although the returned vector has the
559 /// *capacity* specified, the vector will have a zero *length*. For an
560 /// explanation of the difference between length and capacity, see
561 /// *[Capacity and reallocation]*.
562 ///
563 /// [Capacity and reallocation]: #capacity-and-reallocation
564 ///
565 /// # Examples
566 ///
567 /// ```
568 /// use bumpalo::{Bump, collections::Vec};
569 ///
570 /// let b = Bump::new();
571 ///
572 /// let mut vec = Vec::with_capacity_in(10, &b);
573 ///
574 /// // The vector contains no items, even though it has capacity for more
575 /// assert_eq!(vec.len(), 0);
576 ///
577 /// // These are all done without reallocating...
578 /// for i in 0..10 {
579 /// vec.push(i);
580 /// }
581 ///
582 /// // ...but this may make the vector reallocate
583 /// vec.push(11);
584 /// ```
585 #[inline]
586 pub fn with_capacity_in(capacity: usize, bump: &'bump Bump) -> Vec<'bump, T> {
587 Vec {
588 buf: RawVec::with_capacity_in(capacity, bump),
589 len: 0,
590 }
591 }
592
593 /// Construct a new `Vec` from the given iterator's items.
594 ///
595 /// # Examples
596 ///
597 /// ```
598 /// use bumpalo::{Bump, collections::Vec};
599 /// use std::iter;
600 ///
601 /// let b = Bump::new();
602 /// let v = Vec::from_iter_in(iter::repeat(7).take(3), &b);
603 /// assert_eq!(v, [7, 7, 7]);
604 /// ```
605 pub fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, bump: &'bump Bump) -> Vec<'bump, T> {
606 let mut v = Vec::new_in(bump);
607 v.extend(iter);
608 v
609 }
610
611 /// Creates a `Vec<'bump, T>` directly from the raw components of another vector.
612 ///
613 /// # Safety
614 ///
615 /// This is highly unsafe, due to the number of invariants that aren't
616 /// checked:
617 ///
618 /// * `ptr` needs to have been previously allocated via [`String`]/`Vec<'bump, T>`
619 /// (at least, it's highly likely to be incorrect if it wasn't).
620 /// * `ptr`'s `T` needs to have the same size and alignment as it was allocated with.
621 /// * `length` needs to be less than or equal to `capacity`.
622 /// * `capacity` needs to be the capacity that the pointer was allocated with.
623 ///
624 /// Violating these may cause problems like corrupting the allocator's
625 /// internal data structures. For example it is **not** safe
626 /// to build a `Vec<u8>` from a pointer to a C `char` array and a `size_t`.
627 ///
628 /// The ownership of `ptr` is effectively transferred to the
629 /// `Vec<'bump, T>` which may then deallocate, reallocate or change the
630 /// contents of memory pointed to by the pointer at will. Ensure
631 /// that nothing else uses the pointer after calling this
632 /// function.
633 ///
634 /// [`String`]: ../string/struct.String.html
635 ///
636 /// # Examples
637 ///
638 /// ```
639 /// use bumpalo::{Bump, collections::Vec};
640 ///
641 /// use std::ptr;
642 /// use std::mem;
643 ///
644 /// let b = Bump::new();
645 ///
646 /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
647 ///
648 /// // Pull out the various important pieces of information about `v`
649 /// let p = v.as_mut_ptr();
650 /// let len = v.len();
651 /// let cap = v.capacity();
652 ///
653 /// unsafe {
654 /// // Cast `v` into the void: no destructor run, so we are in
655 /// // complete control of the allocation to which `p` points.
656 /// mem::forget(v);
657 ///
658 /// // Overwrite memory with 4, 5, 6
659 /// for i in 0..len as isize {
660 /// ptr::write(p.offset(i), 4 + i);
661 /// }
662 ///
663 /// // Put everything back together into a Vec
664 /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, &b);
665 /// assert_eq!(rebuilt, [4, 5, 6]);
666 /// }
667 /// ```
668 pub unsafe fn from_raw_parts_in(
669 ptr: *mut T,
670 length: usize,
671 capacity: usize,
672 bump: &'bump Bump,
673 ) -> Vec<'bump, T> {
674 Vec {
675 buf: RawVec::from_raw_parts_in(ptr, capacity, bump),
676 len: length,
677 }
678 }
679
680 /// Returns a shared reference to the allocator backing this `Vec`.
681 ///
682 /// # Examples
683 ///
684 /// ```
685 /// use bumpalo::{Bump, collections::Vec};
686 ///
687 /// // uses the same allocator as the provided `Vec`
688 /// fn add_strings<'bump>(vec: &mut Vec<'bump, &'bump str>) {
689 /// for string in ["foo", "bar", "baz"] {
690 /// vec.push(vec.bump().alloc_str(string));
691 /// }
692 /// }
693 /// ```
694 #[inline]
695 #[must_use]
696 pub fn bump(&self) -> &'bump Bump {
697 self.buf.bump()
698 }
699
700 /// Returns the number of elements the vector can hold without
701 /// reallocating.
702 ///
703 /// # Examples
704 ///
705 /// ```
706 /// use bumpalo::{Bump, collections::Vec};
707 ///
708 /// let b = Bump::new();
709 /// let vec: Vec<i32> = Vec::with_capacity_in(10, &b);
710 /// assert_eq!(vec.capacity(), 10);
711 /// ```
712 #[inline]
713 pub fn capacity(&self) -> usize {
714 self.buf.cap()
715 }
716
717 /// Reserves capacity for at least `additional` more elements to be inserted
718 /// in the given `Vec<'bump, T>`. The collection may reserve more space to avoid
719 /// frequent reallocations. After calling `reserve`, capacity will be
720 /// greater than or equal to `self.len() + additional`. Does nothing if
721 /// capacity is already sufficient.
722 ///
723 /// # Panics
724 ///
725 /// Panics if the new capacity overflows `usize`.
726 ///
727 /// # Examples
728 ///
729 /// ```
730 /// use bumpalo::{Bump, collections::Vec};
731 ///
732 /// let b = Bump::new();
733 /// let mut vec = bumpalo::vec![in &b; 1];
734 /// vec.reserve(10);
735 /// assert!(vec.capacity() >= 11);
736 /// ```
737 pub fn reserve(&mut self, additional: usize) {
738 self.buf.reserve(self.len, additional);
739 }
740
741 /// Reserves the minimum capacity for exactly `additional` more elements to
742 /// be inserted in the given `Vec<'bump, T>`. After calling `reserve_exact`,
743 /// capacity will be greater than or equal to `self.len() + additional`.
744 /// Does nothing if the capacity is already sufficient.
745 ///
746 /// Note that the allocator may give the collection more space than it
747 /// requests. Therefore capacity can not be relied upon to be precisely
748 /// minimal. Prefer `reserve` if future insertions are expected.
749 ///
750 /// # Panics
751 ///
752 /// Panics if the new capacity overflows `usize`.
753 ///
754 /// # Examples
755 ///
756 /// ```
757 /// use bumpalo::{Bump, collections::Vec};
758 ///
759 /// let b = Bump::new();
760 /// let mut vec = bumpalo::vec![in &b; 1];
761 /// vec.reserve_exact(10);
762 /// assert!(vec.capacity() >= 11);
763 /// ```
764 pub fn reserve_exact(&mut self, additional: usize) {
765 self.buf.reserve_exact(self.len, additional);
766 }
767
768 /// Attempts to reserve capacity for at least `additional` more elements to be inserted
769 /// in the given `Vec<'bump, T>`. The collection may reserve more space to avoid
770 /// frequent reallocations. After calling `try_reserve`, capacity will be
771 /// greater than or equal to `self.len() + additional`. Does nothing if
772 /// capacity is already sufficient.
773 ///
774 /// # Panics
775 ///
776 /// Panics if the new capacity overflows `usize`.
777 ///
778 /// # Examples
779 ///
780 /// ```
781 /// use bumpalo::{Bump, collections::Vec};
782 ///
783 /// let b = Bump::new();
784 /// let mut vec = bumpalo::vec![in &b; 1];
785 /// vec.try_reserve(10).unwrap();
786 /// assert!(vec.capacity() >= 11);
787 /// ```
788 pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
789 self.buf.try_reserve(self.len, additional)
790 }
791
792 /// Attempts to reserve the minimum capacity for exactly `additional` more elements to
793 /// be inserted in the given `Vec<'bump, T>`. After calling `try_reserve_exact`,
794 /// capacity will be greater than or equal to `self.len() + additional`.
795 /// Does nothing if the capacity is already sufficient.
796 ///
797 /// Note that the allocator may give the collection more space than it
798 /// requests. Therefore capacity can not be relied upon to be precisely
799 /// minimal. Prefer `try_reserve` if future insertions are expected.
800 ///
801 /// # Panics
802 ///
803 /// Panics if the new capacity overflows `usize`.
804 ///
805 /// # Examples
806 ///
807 /// ```
808 /// use bumpalo::{Bump, collections::Vec};
809 ///
810 /// let b = Bump::new();
811 /// let mut vec = bumpalo::vec![in &b; 1];
812 /// vec.try_reserve_exact(10).unwrap();
813 /// assert!(vec.capacity() >= 11);
814 /// ```
815 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
816 self.buf.try_reserve_exact(self.len, additional)
817 }
818
819 /// Shrinks the capacity of the vector as much as possible.
820 ///
821 /// It will drop down as close as possible to the length but the allocator
822 /// may still inform the vector that there is space for a few more elements.
823 ///
824 /// # Examples
825 ///
826 /// ```
827 /// use bumpalo::{Bump, collections::Vec};
828 ///
829 /// let b = Bump::new();
830 ///
831 /// let mut vec = Vec::with_capacity_in(10, &b);
832 /// vec.extend([1, 2, 3].iter().cloned());
833 /// assert_eq!(vec.capacity(), 10);
834 /// vec.shrink_to_fit();
835 /// assert!(vec.capacity() >= 3);
836 /// ```
837 pub fn shrink_to_fit(&mut self) {
838 if self.capacity() != self.len {
839 self.buf.shrink_to_fit(self.len);
840 }
841 }
842
843 /// Converts the vector into `&'bump [T]`.
844 ///
845 /// # Examples
846 ///
847 /// ```
848 /// use bumpalo::{Bump, collections::Vec};
849 ///
850 /// let b = Bump::new();
851 /// let v = bumpalo::vec![in &b; 1, 2, 3];
852 ///
853 /// let slice = v.into_bump_slice();
854 /// assert_eq!(slice, [1, 2, 3]);
855 /// ```
856 pub fn into_bump_slice(self) -> &'bump [T] {
857 unsafe {
858 let ptr = self.as_ptr();
859 let len = self.len();
860 mem::forget(self);
861 slice::from_raw_parts(ptr, len)
862 }
863 }
864
865 /// Converts the vector into `&'bump mut [T]`.
866 ///
867 /// # Examples
868 ///
869 /// ```
870 /// use bumpalo::{Bump, collections::Vec};
871 ///
872 /// let b = Bump::new();
873 /// let v = bumpalo::vec![in &b; 1, 2, 3];
874 ///
875 /// let mut slice = v.into_bump_slice_mut();
876 ///
877 /// slice[0] = 3;
878 /// slice[2] = 1;
879 ///
880 /// assert_eq!(slice, [3, 2, 1]);
881 /// ```
882 pub fn into_bump_slice_mut(mut self) -> &'bump mut [T] {
883 let ptr = self.as_mut_ptr();
884 let len = self.len();
885 mem::forget(self);
886
887 unsafe { slice::from_raw_parts_mut(ptr, len) }
888 }
889
890 /// Shortens the vector, keeping the first `len` elements and dropping
891 /// the rest.
892 ///
893 /// If `len` is greater than the vector's current length, this has no
894 /// effect.
895 ///
896 /// The [`drain`] method can emulate `truncate`, but causes the excess
897 /// elements to be returned instead of dropped.
898 ///
899 /// Note that this method has no effect on the allocated capacity
900 /// of the vector.
901 ///
902 /// # Examples
903 ///
904 /// Truncating a five element vector to two elements:
905 ///
906 /// ```
907 /// use bumpalo::{Bump, collections::Vec};
908 ///
909 /// let b = Bump::new();
910 ///
911 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
912 /// vec.truncate(2);
913 /// assert_eq!(vec, [1, 2]);
914 /// ```
915 ///
916 /// No truncation occurs when `len` is greater than the vector's current
917 /// length:
918 ///
919 /// ```
920 /// use bumpalo::{Bump, collections::Vec};
921 ///
922 /// let b = Bump::new();
923 ///
924 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
925 /// vec.truncate(8);
926 /// assert_eq!(vec, [1, 2, 3]);
927 /// ```
928 ///
929 /// Truncating when `len == 0` is equivalent to calling the [`clear`]
930 /// method.
931 ///
932 /// ```
933 /// use bumpalo::{Bump, collections::Vec};
934 ///
935 /// let b = Bump::new();
936 ///
937 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
938 /// vec.truncate(0);
939 /// assert_eq!(vec, []);
940 /// ```
941 ///
942 /// [`clear`]: #method.clear
943 /// [`drain`]: #method.drain
944 pub fn truncate(&mut self, len: usize) {
945 let current_len = self.len;
946 unsafe {
947 let mut ptr = self.as_mut_ptr().add(self.len);
948 // Set the final length at the end, keeping in mind that
949 // dropping an element might panic. Works around a missed
950 // optimization, as seen in the following issue:
951 // https://github.com/rust-lang/rust/issues/51802
952 let mut local_len = SetLenOnDrop::new(&mut self.len);
953
954 // drop any extra elements
955 for _ in len..current_len {
956 local_len.decrement_len(1);
957 ptr = ptr.offset(-1);
958 ptr::drop_in_place(ptr);
959 }
960 }
961 }
962
963 /// Extracts a slice containing the entire vector.
964 ///
965 /// Equivalent to `&s[..]`.
966 ///
967 /// # Examples
968 ///
969 /// ```
970 /// use bumpalo::{Bump, collections::Vec};
971 /// use std::io::{self, Write};
972 ///
973 /// let b = Bump::new();
974 ///
975 /// let buffer = bumpalo::vec![in &b; 1, 2, 3, 5, 8];
976 /// io::sink().write(buffer.as_slice()).unwrap();
977 /// ```
978 #[inline]
979 pub fn as_slice(&self) -> &[T] {
980 self
981 }
982
983 /// Extracts a mutable slice of the entire vector.
984 ///
985 /// Equivalent to `&mut s[..]`.
986 ///
987 /// # Examples
988 ///
989 /// ```
990 /// use bumpalo::{Bump, collections::Vec};
991 /// use std::io::{self, Read};
992 ///
993 /// let b = Bump::new();
994 /// let mut buffer = bumpalo::vec![in &b; 0; 3];
995 /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
996 /// ```
997 #[inline]
998 pub fn as_mut_slice(&mut self) -> &mut [T] {
999 self
1000 }
1001
1002 /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1003 /// valid for zero sized reads if the vector didn't allocate.
1004 ///
1005 /// The caller must ensure that the vector outlives the pointer this
1006 /// function returns, or else it will end up pointing to garbage.
1007 /// Modifying the vector may cause its buffer to be reallocated,
1008 /// which would also make any pointers to it invalid.
1009 ///
1010 /// The caller must also ensure that the memory the pointer (non-transitively) points to
1011 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1012 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1013 ///
1014 /// # Examples
1015 ///
1016 /// ```
1017 /// use bumpalo::{Bump, collections::Vec};
1018 ///
1019 /// let bump = Bump::new();
1020 ///
1021 /// let x = bumpalo::vec![in ≎ 1, 2, 4];
1022 /// let x_ptr = x.as_ptr();
1023 ///
1024 /// unsafe {
1025 /// for i in 0..x.len() {
1026 /// assert_eq!(*x_ptr.add(i), 1 << i);
1027 /// }
1028 /// }
1029 /// ```
1030 ///
1031 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1032 #[inline]
1033 pub fn as_ptr(&self) -> *const T {
1034 // We shadow the slice method of the same name to avoid going through
1035 // `deref`, which creates an intermediate reference.
1036 let ptr = self.buf.ptr();
1037 unsafe {
1038 if ptr.is_null() {
1039 core::hint::unreachable_unchecked();
1040 }
1041 }
1042 ptr
1043 }
1044
1045 /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
1046 /// raw pointer valid for zero sized reads if the vector didn't allocate.
1047 ///
1048 /// The caller must ensure that the vector outlives the pointer this
1049 /// function returns, or else it will end up pointing to garbage.
1050 /// Modifying the vector may cause its buffer to be reallocated,
1051 /// which would also make any pointers to it invalid.
1052 ///
1053 /// # Examples
1054 ///
1055 /// ```
1056 /// use bumpalo::{Bump, collections::Vec};
1057 ///
1058 /// let bump = Bump::new();
1059 ///
1060 /// // Allocate vector big enough for 4 elements.
1061 /// let size = 4;
1062 /// let mut x: Vec<i32> = Vec::with_capacity_in(size, &bump);
1063 /// let x_ptr = x.as_mut_ptr();
1064 ///
1065 /// // Initialize elements via raw pointer writes, then set length.
1066 /// unsafe {
1067 /// for i in 0..size {
1068 /// x_ptr.add(i).write(i as i32);
1069 /// }
1070 /// x.set_len(size);
1071 /// }
1072 /// assert_eq!(&*x, &[0, 1, 2, 3]);
1073 /// ```
1074 #[inline]
1075 pub fn as_mut_ptr(&mut self) -> *mut T {
1076 // We shadow the slice method of the same name to avoid going through
1077 // `deref_mut`, which creates an intermediate reference.
1078 let ptr = self.buf.ptr();
1079 unsafe {
1080 if ptr.is_null() {
1081 core::hint::unreachable_unchecked();
1082 }
1083 }
1084 ptr
1085 }
1086
1087 /// Sets the length of a vector.
1088 ///
1089 /// This will explicitly set the size of the vector, without actually
1090 /// modifying its buffers, so it is up to the caller to ensure that the
1091 /// vector is actually the specified size.
1092 ///
1093 /// # Safety
1094 ///
1095 /// - `new_len` must be less than or equal to [`capacity()`].
1096 /// - The elements at `old_len..new_len` must be initialized.
1097 ///
1098 /// [`capacity()`]: struct.Vec.html#method.capacity
1099 ///
1100 /// # Examples
1101 ///
1102 /// ```
1103 /// use bumpalo::{Bump, collections::Vec};
1104 ///
1105 /// use std::ptr;
1106 ///
1107 /// let b = Bump::new();
1108 ///
1109 /// let mut vec = bumpalo::vec![in &b; 'r', 'u', 's', 't'];
1110 ///
1111 /// unsafe {
1112 /// ptr::drop_in_place(&mut vec[3]);
1113 /// vec.set_len(3);
1114 /// }
1115 /// assert_eq!(vec, ['r', 'u', 's']);
1116 /// ```
1117 ///
1118 /// In this example, there is a memory leak since the memory locations
1119 /// owned by the inner vectors were not freed prior to the `set_len` call:
1120 ///
1121 /// ```
1122 /// use bumpalo::{Bump, collections::Vec};
1123 ///
1124 /// let b = Bump::new();
1125 ///
1126 /// let mut vec = bumpalo::vec![in &b;
1127 /// bumpalo::vec![in &b; 1, 0, 0],
1128 /// bumpalo::vec![in &b; 0, 1, 0],
1129 /// bumpalo::vec![in &b; 0, 0, 1]];
1130 /// unsafe {
1131 /// vec.set_len(0);
1132 /// }
1133 /// ```
1134 ///
1135 /// In this example, the vector gets expanded from zero to four items
1136 /// but we directly initialize uninitialized memory:
1137 ///
1138 // TODO: rely upon `spare_capacity_mut`
1139 /// ```
1140 /// use bumpalo::{Bump, collections::Vec};
1141 ///
1142 /// let len = 4;
1143 /// let b = Bump::new();
1144 ///
1145 /// let mut vec: Vec<u8> = Vec::with_capacity_in(len, &b);
1146 ///
1147 /// for i in 0..len {
1148 /// // SAFETY: we initialize memory via `pointer::write`
1149 /// unsafe { vec.as_mut_ptr().add(i).write(b'a') }
1150 /// }
1151 ///
1152 /// unsafe {
1153 /// vec.set_len(len);
1154 /// }
1155 ///
1156 /// assert_eq!(b"aaaa", &*vec);
1157 /// ```
1158 #[inline]
1159 pub unsafe fn set_len(&mut self, new_len: usize) {
1160 self.len = new_len;
1161 }
1162
1163 /// Removes an element from the vector and returns it.
1164 ///
1165 /// The removed element is replaced by the last element of the vector.
1166 ///
1167 /// This does not preserve ordering, but is O(1).
1168 ///
1169 /// # Panics
1170 ///
1171 /// Panics if `index` is out of bounds.
1172 ///
1173 /// # Examples
1174 ///
1175 /// ```
1176 /// use bumpalo::{Bump, collections::Vec};
1177 ///
1178 /// let b = Bump::new();
1179 ///
1180 /// let mut v = bumpalo::vec![in &b; "foo", "bar", "baz", "qux"];
1181 ///
1182 /// assert_eq!(v.swap_remove(1), "bar");
1183 /// assert_eq!(v, ["foo", "qux", "baz"]);
1184 ///
1185 /// assert_eq!(v.swap_remove(0), "foo");
1186 /// assert_eq!(v, ["baz", "qux"]);
1187 /// ```
1188 #[inline]
1189 pub fn swap_remove(&mut self, index: usize) -> T {
1190 unsafe {
1191 // We replace self[index] with the last element. Note that if the
1192 // bounds check on hole succeeds there must be a last element (which
1193 // can be self[index] itself).
1194 let hole: *mut T = &mut self[index];
1195 let last = ptr::read(self.get_unchecked(self.len - 1));
1196 self.len -= 1;
1197 ptr::replace(hole, last)
1198 }
1199 }
1200
1201 /// Inserts an element at position `index` within the vector, shifting all
1202 /// elements after it to the right.
1203 ///
1204 /// # Panics
1205 ///
1206 /// Panics if `index > len`.
1207 ///
1208 /// # Examples
1209 ///
1210 /// ```
1211 /// use bumpalo::{Bump, collections::Vec};
1212 ///
1213 /// let b = Bump::new();
1214 ///
1215 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1216 /// vec.insert(1, 4);
1217 /// assert_eq!(vec, [1, 4, 2, 3]);
1218 /// vec.insert(4, 5);
1219 /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1220 /// ```
1221 pub fn insert(&mut self, index: usize, element: T) {
1222 let len = self.len();
1223 assert!(index <= len);
1224
1225 // space for the new element
1226 if len == self.buf.cap() {
1227 self.reserve(1);
1228 }
1229
1230 unsafe {
1231 // infallible
1232 // The spot to put the new value
1233 {
1234 let p = self.as_mut_ptr().add(index);
1235 // Shift everything over to make space. (Duplicating the
1236 // `index`th element into two consecutive places.)
1237 ptr::copy(p, p.offset(1), len - index);
1238 // Write it in, overwriting the first copy of the `index`th
1239 // element.
1240 ptr::write(p, element);
1241 }
1242 self.set_len(len + 1);
1243 }
1244 }
1245
1246 /// Removes and returns the element at position `index` within the vector,
1247 /// shifting all elements after it to the left.
1248 ///
1249 /// # Panics
1250 ///
1251 /// Panics if `index` is out of bounds.
1252 ///
1253 /// # Examples
1254 ///
1255 /// ```
1256 /// use bumpalo::{Bump, collections::Vec};
1257 ///
1258 /// let b = Bump::new();
1259 ///
1260 /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1261 /// assert_eq!(v.remove(1), 2);
1262 /// assert_eq!(v, [1, 3]);
1263 /// ```
1264 pub fn remove(&mut self, index: usize) -> T {
1265 let len = self.len();
1266 assert!(index < len);
1267 unsafe {
1268 // infallible
1269 let ret;
1270 {
1271 // the place we are taking from.
1272 let ptr = self.as_mut_ptr().add(index);
1273 // copy it out, unsafely having a copy of the value on
1274 // the stack and in the vector at the same time.
1275 ret = ptr::read(ptr);
1276
1277 // Shift everything down to fill in that spot.
1278 ptr::copy(ptr.offset(1), ptr, len - index - 1);
1279 }
1280 self.set_len(len - 1);
1281 ret
1282 }
1283 }
1284
1285 /// Retains only the elements specified by the predicate.
1286 ///
1287 /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
1288 /// This method operates in place and preserves the order of the retained
1289 /// elements.
1290 ///
1291 /// # Examples
1292 ///
1293 /// ```
1294 /// use bumpalo::{Bump, collections::Vec};
1295 ///
1296 /// let b = Bump::new();
1297 ///
1298 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4];
1299 /// vec.retain(|&x| x % 2 == 0);
1300 /// assert_eq!(vec, [2, 4]);
1301 /// ```
1302 pub fn retain<F>(&mut self, mut f: F)
1303 where
1304 F: FnMut(&T) -> bool,
1305 {
1306 self.drain_filter(|x| !f(x));
1307 }
1308
1309 /// Creates an iterator that removes the elements in the vector
1310 /// for which the predicate returns `true` and yields the removed items.
1311 ///
1312 /// # Examples
1313 ///
1314 /// ```
1315 /// use bumpalo::Bump;
1316 /// use bumpalo::collections::{CollectIn, Vec};
1317 ///
1318 /// let b = Bump::new();
1319 ///
1320 /// let mut numbers = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
1321 ///
1322 /// let evens: Vec<_> = numbers.drain_filter(|x| *x % 2 == 0).collect_in(&b);
1323 ///
1324 /// assert_eq!(numbers, &[1, 3, 5]);
1325 /// assert_eq!(evens, &[2, 4]);
1326 /// ```
1327 pub fn drain_filter<'a, F>(&'a mut self, filter: F) -> DrainFilter<'a, 'bump, T, F>
1328 where
1329 F: FnMut(&mut T) -> bool,
1330 {
1331 let old_len = self.len();
1332
1333 // Guard against us getting leaked (leak amplification)
1334 unsafe {
1335 self.set_len(0);
1336 }
1337
1338 DrainFilter {
1339 vec: self,
1340 idx: 0,
1341 del: 0,
1342 old_len,
1343 pred: filter,
1344 }
1345 }
1346
1347 /// Removes all but the first of consecutive elements in the vector that resolve to the same
1348 /// key.
1349 ///
1350 /// If the vector is sorted, this removes all duplicates.
1351 ///
1352 /// # Examples
1353 ///
1354 /// ```
1355 /// use bumpalo::{Bump, collections::Vec};
1356 ///
1357 /// let b = Bump::new();
1358 ///
1359 /// let mut vec = bumpalo::vec![in &b; 10, 20, 21, 30, 20];
1360 ///
1361 /// vec.dedup_by_key(|i| *i / 10);
1362 ///
1363 /// assert_eq!(vec, [10, 20, 30, 20]);
1364 /// ```
1365 #[inline]
1366 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1367 where
1368 F: FnMut(&mut T) -> K,
1369 K: PartialEq,
1370 {
1371 self.dedup_by(|a, b| key(a) == key(b))
1372 }
1373
1374 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
1375 /// relation.
1376 ///
1377 /// The `same_bucket` function is passed references to two elements from the vector and
1378 /// must determine if the elements compare equal. The elements are passed in opposite order
1379 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
1380 ///
1381 /// If the vector is sorted, this removes all duplicates.
1382 ///
1383 /// # Examples
1384 ///
1385 /// ```
1386 /// use bumpalo::{Bump, collections::Vec};
1387 ///
1388 /// let b = Bump::new();
1389 ///
1390 /// let mut vec = bumpalo::vec![in &b; "foo", "bar", "Bar", "baz", "bar"];
1391 ///
1392 /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1393 ///
1394 /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1395 /// ```
1396 pub fn dedup_by<F>(&mut self, same_bucket: F)
1397 where
1398 F: FnMut(&mut T, &mut T) -> bool,
1399 {
1400 let len = {
1401 let (dedup, _) = partition_dedup_by(self.as_mut_slice(), same_bucket);
1402 dedup.len()
1403 };
1404 self.truncate(len);
1405 }
1406
1407 /// Appends an element to the back of a vector.
1408 ///
1409 /// # Panics
1410 ///
1411 /// Panics if the number of elements in the vector overflows a `usize`.
1412 ///
1413 /// # Examples
1414 ///
1415 /// ```
1416 /// use bumpalo::{Bump, collections::Vec};
1417 ///
1418 /// let b = Bump::new();
1419 ///
1420 /// let mut vec = bumpalo::vec![in &b; 1, 2];
1421 /// vec.push(3);
1422 /// assert_eq!(vec, [1, 2, 3]);
1423 /// ```
1424 #[inline]
1425 pub fn push(&mut self, value: T) {
1426 // This will panic or abort if we would allocate > isize::MAX bytes
1427 // or if the length increment would overflow for zero-sized types.
1428 if self.len == self.buf.cap() {
1429 self.reserve(1);
1430 }
1431 unsafe {
1432 let end = self.buf.ptr().add(self.len);
1433 ptr::write(end, value);
1434 self.len += 1;
1435 }
1436 }
1437
1438 /// Removes the last element from a vector and returns it, or [`None`] if it
1439 /// is empty.
1440 ///
1441 /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
1442 ///
1443 /// # Examples
1444 ///
1445 /// ```
1446 /// use bumpalo::{Bump, collections::Vec};
1447 ///
1448 /// let b = Bump::new();
1449 ///
1450 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1451 /// assert_eq!(vec.pop(), Some(3));
1452 /// assert_eq!(vec, [1, 2]);
1453 /// ```
1454 #[inline]
1455 pub fn pop(&mut self) -> Option<T> {
1456 if self.len == 0 {
1457 None
1458 } else {
1459 unsafe {
1460 self.len -= 1;
1461 Some(ptr::read(self.as_ptr().add(self.len())))
1462 }
1463 }
1464 }
1465
1466 /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1467 ///
1468 /// # Panics
1469 ///
1470 /// Panics if the number of elements in the vector overflows a `usize`.
1471 ///
1472 /// # Examples
1473 ///
1474 /// ```
1475 /// use bumpalo::{Bump, collections::Vec};
1476 ///
1477 /// let b = Bump::new();
1478 ///
1479 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1480 /// let mut vec2 = bumpalo::vec![in &b; 4, 5, 6];
1481 /// vec.append(&mut vec2);
1482 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
1483 /// assert_eq!(vec2, []);
1484 /// ```
1485 #[inline]
1486 pub fn append(&mut self, other: &mut Self) {
1487 unsafe {
1488 self.append_elements(other.as_slice() as _);
1489 other.set_len(0);
1490 }
1491 }
1492
1493 /// Appends elements to `Self` from other buffer.
1494 #[inline]
1495 unsafe fn append_elements(&mut self, other: *const [T]) {
1496 let count = (*other).len();
1497 self.reserve(count);
1498 let len = self.len();
1499 ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count);
1500 self.len += count;
1501 }
1502
1503 /// Creates a draining iterator that removes the specified range in the vector
1504 /// and yields the removed items.
1505 ///
1506 /// Note 1: The element range is removed even if the iterator is only
1507 /// partially consumed or not consumed at all.
1508 ///
1509 /// Note 2: It is unspecified how many elements are removed from the vector
1510 /// if the `Drain` value is leaked.
1511 ///
1512 /// # Panics
1513 ///
1514 /// Panics if the starting point is greater than the end point or if
1515 /// the end point is greater than the length of the vector.
1516 ///
1517 /// # Examples
1518 ///
1519 /// ```
1520 /// use bumpalo::Bump;
1521 /// use bumpalo::collections::{CollectIn, Vec};
1522 ///
1523 /// let b = Bump::new();
1524 ///
1525 /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1526 ///
1527 /// let u: Vec<_> = v.drain(1..).collect_in(&b);
1528 ///
1529 /// assert_eq!(v, &[1]);
1530 /// assert_eq!(u, &[2, 3]);
1531 ///
1532 /// // A full range clears the vector
1533 /// v.drain(..);
1534 /// assert_eq!(v, &[]);
1535 /// ```
1536 pub fn drain<R>(&mut self, range: R) -> Drain<T>
1537 where
1538 R: RangeBounds<usize>,
1539 {
1540 // Memory safety
1541 //
1542 // When the Drain is first created, it shortens the length of
1543 // the source vector to make sure no uninitialized or moved-from elements
1544 // are accessible at all if the Drain's destructor never gets to run.
1545 //
1546 // Drain will ptr::read out the values to remove.
1547 // When finished, remaining tail of the vec is copied back to cover
1548 // the hole, and the vector length is restored to the new length.
1549 //
1550 let len = self.len();
1551 let start = match range.start_bound() {
1552 Included(&n) => n,
1553 Excluded(&n) => n + 1,
1554 Unbounded => 0,
1555 };
1556 let end = match range.end_bound() {
1557 Included(&n) => n + 1,
1558 Excluded(&n) => n,
1559 Unbounded => len,
1560 };
1561 assert!(start <= end);
1562 assert!(end <= len);
1563
1564 unsafe {
1565 // set self.vec length's to start, to be safe in case Drain is leaked
1566 self.set_len(start);
1567 // Use the borrow in the IterMut to indicate borrowing behavior of the
1568 // whole Drain iterator (like &mut T).
1569 let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start);
1570 Drain {
1571 tail_start: end,
1572 tail_len: len - end,
1573 iter: range_slice.iter(),
1574 vec: NonNull::from(self),
1575 }
1576 }
1577 }
1578
1579 /// Clears the vector, removing all values.
1580 ///
1581 /// Note that this method has no effect on the allocated capacity
1582 /// of the vector.
1583 ///
1584 /// # Examples
1585 ///
1586 /// ```
1587 /// use bumpalo::{Bump, collections::Vec};
1588 ///
1589 /// let b = Bump::new();
1590 ///
1591 /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1592 ///
1593 /// v.clear();
1594 ///
1595 /// assert!(v.is_empty());
1596 /// ```
1597 #[inline]
1598 pub fn clear(&mut self) {
1599 self.truncate(0)
1600 }
1601
1602 /// Returns the number of elements in the vector, also referred to
1603 /// as its 'length'.
1604 ///
1605 /// # Examples
1606 ///
1607 /// ```
1608 /// use bumpalo::{Bump, collections::Vec};
1609 ///
1610 /// let b = Bump::new();
1611 ///
1612 /// let a = bumpalo::vec![in &b; 1, 2, 3];
1613 /// assert_eq!(a.len(), 3);
1614 /// ```
1615 #[inline]
1616 pub fn len(&self) -> usize {
1617 self.len
1618 }
1619
1620 /// Returns `true` if the vector contains no elements.
1621 ///
1622 /// # Examples
1623 ///
1624 /// ```
1625 /// use bumpalo::{Bump, collections::Vec};
1626 ///
1627 /// let b = Bump::new();
1628 ///
1629 /// let mut v = Vec::new_in(&b);
1630 /// assert!(v.is_empty());
1631 ///
1632 /// v.push(1);
1633 /// assert!(!v.is_empty());
1634 /// ```
1635 pub fn is_empty(&self) -> bool {
1636 self.len() == 0
1637 }
1638
1639 /// Splits the collection into two at the given index.
1640 ///
1641 /// Returns a newly allocated vector. `self` contains elements `[0, at)`,
1642 /// and the returned vector contains elements `[at, len)`.
1643 ///
1644 /// Note that the capacity of `self` does not change.
1645 ///
1646 /// # Panics
1647 ///
1648 /// Panics if `at > len`.
1649 ///
1650 /// # Examples
1651 ///
1652 /// ```
1653 /// use bumpalo::{Bump, collections::Vec};
1654 ///
1655 /// let b = Bump::new();
1656 ///
1657 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1658 /// let vec2 = vec.split_off(1);
1659 /// assert_eq!(vec, [1]);
1660 /// assert_eq!(vec2, [2, 3]);
1661 /// ```
1662 #[inline]
1663 pub fn split_off(&mut self, at: usize) -> Self {
1664 assert!(at <= self.len(), "`at` out of bounds");
1665
1666 let other_len = self.len - at;
1667 let mut other = Vec::with_capacity_in(other_len, self.buf.bump());
1668
1669 // Unsafely `set_len` and copy items to `other`.
1670 unsafe {
1671 self.set_len(at);
1672 other.set_len(other_len);
1673
1674 ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
1675 }
1676 other
1677 }
1678}
1679
1680#[cfg(feature = "boxed")]
1681impl<'bump, T> Vec<'bump, T> {
1682 /// Converts the vector into [`Box<[T]>`][owned slice].
1683 ///
1684 /// Note that this will drop any excess capacity.
1685 ///
1686 /// [owned slice]: ../../boxed/struct.Box.html
1687 ///
1688 /// # Examples
1689 ///
1690 /// ```
1691 /// use bumpalo::{Bump, collections::Vec, vec};
1692 ///
1693 /// let b = Bump::new();
1694 ///
1695 /// let v = vec![in &b; 1, 2, 3];
1696 ///
1697 /// let slice = v.into_boxed_slice();
1698 /// ```
1699 pub fn into_boxed_slice(mut self) -> crate::boxed::Box<'bump, [T]> {
1700 use crate::boxed::Box;
1701
1702 // Unlike `alloc::vec::Vec` shrinking here isn't necessary as `bumpalo::boxed::Box` doesn't own memory.
1703 unsafe {
1704 let slice = slice::from_raw_parts_mut(self.as_mut_ptr(), self.len);
1705 let output: Box<'bump, [T]> = Box::from_raw(slice);
1706 mem::forget(self);
1707 output
1708 }
1709 }
1710}
1711
1712impl<'bump, T: 'bump + Clone> Vec<'bump, T> {
1713 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
1714 ///
1715 /// If `new_len` is greater than `len`, the `Vec` is extended by the
1716 /// difference, with each additional slot filled with `value`.
1717 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
1718 ///
1719 /// This method requires [`Clone`] to be able clone the passed value. If
1720 /// you need more flexibility (or want to rely on [`Default`] instead of
1721 /// [`Clone`]), use [`resize_with`].
1722 ///
1723 /// # Examples
1724 ///
1725 /// ```
1726 /// use bumpalo::{Bump, collections::Vec};
1727 ///
1728 /// let b = Bump::new();
1729 ///
1730 /// let mut vec = bumpalo::vec![in &b; "hello"];
1731 /// vec.resize(3, "world");
1732 /// assert_eq!(vec, ["hello", "world", "world"]);
1733 ///
1734 /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4];
1735 /// vec.resize(2, 0);
1736 /// assert_eq!(vec, [1, 2]);
1737 /// ```
1738 ///
1739 /// [`Clone`]: https://doc.rust-lang.org/std/clone/trait.Clone.html
1740 /// [`Default`]: https://doc.rust-lang.org/std/default/trait.Default.html
1741 /// [`resize_with`]: #method.resize_with
1742 pub fn resize(&mut self, new_len: usize, value: T) {
1743 let len = self.len();
1744
1745 if new_len > len {
1746 self.extend_with(new_len - len, ExtendElement(value))
1747 } else {
1748 self.truncate(new_len);
1749 }
1750 }
1751
1752 /// Clones and appends all elements in a slice to the `Vec`.
1753 ///
1754 /// Iterates over the slice `other`, clones each element, and then appends
1755 /// it to this `Vec`. The `other` vector is traversed in-order.
1756 ///
1757 /// Note that this function is same as [`extend`] except that it is
1758 /// specialized to work with slices instead. If and when Rust gets
1759 /// specialization this function will likely be deprecated (but still
1760 /// available).
1761 ///
1762 /// # Examples
1763 ///
1764 /// ```
1765 /// use bumpalo::{Bump, collections::Vec};
1766 ///
1767 /// let b = Bump::new();
1768 ///
1769 /// let mut vec = bumpalo::vec![in &b; 1];
1770 /// vec.extend_from_slice(&[2, 3, 4]);
1771 /// assert_eq!(vec, [1, 2, 3, 4]);
1772 /// ```
1773 ///
1774 /// [`extend`]: #method.extend
1775 pub fn extend_from_slice(&mut self, other: &[T]) {
1776 self.extend(other.iter().cloned())
1777 }
1778}
1779
1780impl<'bump, T: 'bump + Copy> Vec<'bump, T> {
1781 /// Helper method to copy all of the items in `other` and append them to the end of `self`.
1782 ///
1783 /// SAFETY:
1784 /// * The caller is responsible for:
1785 /// * calling [`reserve`](Self::reserve) beforehand to guarantee that there is enough
1786 /// capacity to store `other.len()` more items.
1787 /// * guaranteeing that `self` and `other` do not overlap.
1788 unsafe fn extend_from_slice_copy_unchecked(&mut self, other: &[T]) {
1789 let old_len = self.len();
1790 debug_assert!(old_len + other.len() <= self.capacity());
1791
1792 // SAFETY:
1793 // * `src` is valid for reads of `other.len()` values by virtue of being a `&[T]`.
1794 // * `dst` is valid for writes of `other.len()` bytes because the caller of this
1795 // method is required to `reserve` capacity to store at least `other.len()` items
1796 // beforehand.
1797 // * Because `src` is a `&[T]` and dst is a `&[T]` within the `Vec<T>`,
1798 // `copy_nonoverlapping`'s alignment requirements are met.
1799 // * Caller is required to guarantee that the source and destination ranges cannot overlap
1800 unsafe {
1801 let src = other.as_ptr();
1802 let dst = self.as_mut_ptr().add(old_len);
1803 ptr::copy_nonoverlapping(src, dst, other.len());
1804 self.set_len(old_len + other.len());
1805 }
1806 }
1807
1808
1809 /// Copies all elements in the slice `other` and appends them to the `Vec`.
1810 ///
1811 /// Note that this function is same as [`extend_from_slice`] except that it is optimized for
1812 /// slices of types that implement the `Copy` trait. If and when Rust gets specialization
1813 /// this function will likely be deprecated (but still available).
1814 ///
1815 /// To copy and append the data from multiple source slices at once, see
1816 /// [`extend_from_slices_copy`].
1817 ///
1818 /// # Examples
1819 ///
1820 /// ```
1821 /// use bumpalo::{Bump, collections::Vec};
1822 ///
1823 /// let b = Bump::new();
1824 ///
1825 /// let mut vec = bumpalo::vec![in &b; 1];
1826 /// vec.extend_from_slice_copy(&[2, 3, 4]);
1827 /// assert_eq!(vec, [1, 2, 3, 4]);
1828 /// ```
1829 ///
1830 /// ```
1831 /// use bumpalo::{Bump, collections::Vec};
1832 ///
1833 /// let b = Bump::new();
1834 ///
1835 /// let mut vec = bumpalo::vec![in &b; 'H' as u8];
1836 /// vec.extend_from_slice_copy("ello, world!".as_bytes());
1837 /// assert_eq!(vec, "Hello, world!".as_bytes());
1838 /// ```
1839 ///
1840 /// [`extend_from_slice`]: #method.extend_from_slice
1841 /// [`extend_from_slices`]: #method.extend_from_slices
1842 pub fn extend_from_slice_copy(&mut self, other: &[T]) {
1843 // Reserve space in the Vec for the values to be added
1844 self.reserve(other.len());
1845
1846 // Copy values into the space that was just reserved
1847 // SAFETY:
1848 // * `self` has enough capacity to store `other.len()` more items as `self.reserve(other.len())`
1849 // above guarantees that.
1850 // * Source and destination data ranges cannot overlap as we just reserved the destination
1851 // range from the bump.
1852 unsafe {
1853 self.extend_from_slice_copy_unchecked(other);
1854 }
1855 }
1856
1857 /// For each slice in `slices`, copies all elements in the slice and appends them to the `Vec`.
1858 ///
1859 /// This method is equivalent to calling [`extend_from_slice_copy`] in a loop, but is able
1860 /// to precompute the total amount of space to reserve in advance. This reduces the potential
1861 /// maximum number of reallocations needed from one-per-slice to just one.
1862 ///
1863 /// # Examples
1864 ///
1865 /// ```
1866 /// use bumpalo::{Bump, collections::Vec};
1867 ///
1868 /// let b = Bump::new();
1869 ///
1870 /// let mut vec = bumpalo::vec![in &b; 1];
1871 /// vec.extend_from_slices_copy(&[&[2, 3], &[], &[4]]);
1872 /// assert_eq!(vec, [1, 2, 3, 4]);
1873 /// ```
1874 ///
1875 /// ```
1876 /// use bumpalo::{Bump, collections::Vec};
1877 ///
1878 /// let b = Bump::new();
1879 ///
1880 /// let mut vec = bumpalo::vec![in &b; 'H' as u8];
1881 /// vec.extend_from_slices_copy(&["ello,".as_bytes(), &[], " world!".as_bytes()]);
1882 /// assert_eq!(vec, "Hello, world!".as_bytes());
1883 /// ```
1884 ///
1885 /// [`extend_from_slice_copy`]: #method.extend_from_slice_copy
1886 pub fn extend_from_slices_copy(&mut self, slices: &[&[T]]) {
1887 // Reserve the total amount of capacity we'll need to safely append the aggregated contents
1888 // of each slice in `slices`.
1889 let capacity_to_reserve: usize = slices.iter().map(|slice| slice.len()).sum();
1890 self.reserve(capacity_to_reserve);
1891
1892 // SAFETY:
1893 // * `dst` is valid for writes of `capacity_to_reserve` items as
1894 // `self.reserve(capacity_to_reserve)` above guarantees that.
1895 // * Source and destination ranges cannot overlap as we just reserved the destination
1896 // range from the bump.
1897 unsafe {
1898 // Copy the contents of each slice onto the end of `self`
1899 slices.iter().for_each(|slice| {
1900 self.extend_from_slice_copy_unchecked(slice);
1901 });
1902 }
1903 }
1904}
1905
1906// This code generalises `extend_with_{element,default}`.
1907trait ExtendWith<T> {
1908 fn next(&mut self) -> T;
1909 fn last(self) -> T;
1910}
1911
1912struct ExtendElement<T>(T);
1913impl<T: Clone> ExtendWith<T> for ExtendElement<T> {
1914 fn next(&mut self) -> T {
1915 self.0.clone()
1916 }
1917 fn last(self) -> T {
1918 self.0
1919 }
1920}
1921
1922impl<'bump, T: 'bump> Vec<'bump, T> {
1923 /// Extend the vector by `n` values, using the given generator.
1924 fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) {
1925 self.reserve(n);
1926
1927 unsafe {
1928 let mut ptr = self.as_mut_ptr().add(self.len());
1929 // Use SetLenOnDrop to work around bug where compiler
1930 // may not realize the store through `ptr` through self.set_len()
1931 // don't alias.
1932 let mut local_len = SetLenOnDrop::new(&mut self.len);
1933
1934 // Write all elements except the last one
1935 for _ in 1..n {
1936 ptr::write(ptr, value.next());
1937 ptr = ptr.offset(1);
1938 // Increment the length in every step in case next() panics
1939 local_len.increment_len(1);
1940 }
1941
1942 if n > 0 {
1943 // We can write the last element directly without cloning needlessly
1944 ptr::write(ptr, value.last());
1945 local_len.increment_len(1);
1946 }
1947
1948 // len set by scope guard
1949 }
1950 }
1951}
1952
1953// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
1954//
1955// The idea is: The length field in SetLenOnDrop is a local variable
1956// that the optimizer will see does not alias with any stores through the Vec's data
1957// pointer. This is a workaround for alias analysis issue #32155
1958struct SetLenOnDrop<'a> {
1959 len: &'a mut usize,
1960 local_len: usize,
1961}
1962
1963impl<'a> SetLenOnDrop<'a> {
1964 #[inline]
1965 fn new(len: &'a mut usize) -> Self {
1966 SetLenOnDrop {
1967 local_len: *len,
1968 len,
1969 }
1970 }
1971
1972 #[inline]
1973 fn increment_len(&mut self, increment: usize) {
1974 self.local_len += increment;
1975 }
1976
1977 #[inline]
1978 fn decrement_len(&mut self, decrement: usize) {
1979 self.local_len -= decrement;
1980 }
1981}
1982
1983impl<'a> Drop for SetLenOnDrop<'a> {
1984 #[inline]
1985 fn drop(&mut self) {
1986 *self.len = self.local_len;
1987 }
1988}
1989
1990impl<'bump, T: 'bump + PartialEq> Vec<'bump, T> {
1991 /// Removes consecutive repeated elements in the vector according to the
1992 /// [`PartialEq`] trait implementation.
1993 ///
1994 /// If the vector is sorted, this removes all duplicates.
1995 ///
1996 /// # Examples
1997 ///
1998 /// ```
1999 /// use bumpalo::{Bump, collections::Vec};
2000 ///
2001 /// let b = Bump::new();
2002 ///
2003 /// let mut vec = bumpalo::vec![in &b; 1, 2, 2, 3, 2];
2004 ///
2005 /// vec.dedup();
2006 ///
2007 /// assert_eq!(vec, [1, 2, 3, 2]);
2008 /// ```
2009 #[inline]
2010 pub fn dedup(&mut self) {
2011 self.dedup_by(|a, b| a == b)
2012 }
2013}
2014
2015////////////////////////////////////////////////////////////////////////////////
2016// Common trait implementations for Vec
2017////////////////////////////////////////////////////////////////////////////////
2018
2019impl<'bump, T: 'bump + Clone> Clone for Vec<'bump, T> {
2020 #[cfg(not(test))]
2021 fn clone(&self) -> Vec<'bump, T> {
2022 let mut v = Vec::with_capacity_in(self.len(), self.buf.bump());
2023 v.extend(self.iter().cloned());
2024 v
2025 }
2026
2027 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
2028 // required for this method definition, is not available. Instead use the
2029 // `slice::to_vec` function which is only available with cfg(test)
2030 // NB see the slice::hack module in slice.rs for more information
2031 #[cfg(test)]
2032 fn clone(&self) -> Vec<'bump, T> {
2033 let mut v = Vec::new_in(self.buf.bump());
2034 v.extend(self.iter().cloned());
2035 v
2036 }
2037}
2038
2039impl<'bump, T: 'bump + Hash> Hash for Vec<'bump, T> {
2040 #[inline]
2041 fn hash<H: hash::Hasher>(&self, state: &mut H) {
2042 Hash::hash(&**self, state)
2043 }
2044}
2045
2046impl<'bump, T, I> Index<I> for Vec<'bump, T>
2047where
2048 I: ::core::slice::SliceIndex<[T]>,
2049{
2050 type Output = I::Output;
2051
2052 #[inline]
2053 fn index(&self, index: I) -> &Self::Output {
2054 Index::index(&**self, index)
2055 }
2056}
2057
2058impl<'bump, T, I> IndexMut<I> for Vec<'bump, T>
2059where
2060 I: ::core::slice::SliceIndex<[T]>,
2061{
2062 #[inline]
2063 fn index_mut(&mut self, index: I) -> &mut Self::Output {
2064 IndexMut::index_mut(&mut **self, index)
2065 }
2066}
2067
2068impl<'bump, T: 'bump> ops::Deref for Vec<'bump, T> {
2069 type Target = [T];
2070
2071 fn deref(&self) -> &[T] {
2072 unsafe {
2073 let p = self.buf.ptr();
2074 // assume(!p.is_null());
2075 slice::from_raw_parts(p, self.len)
2076 }
2077 }
2078}
2079
2080impl<'bump, T: 'bump> ops::DerefMut for Vec<'bump, T> {
2081 fn deref_mut(&mut self) -> &mut [T] {
2082 unsafe {
2083 let ptr = self.buf.ptr();
2084 // assume(!ptr.is_null());
2085 slice::from_raw_parts_mut(ptr, self.len)
2086 }
2087 }
2088}
2089
2090impl<'bump, T: 'bump> IntoIterator for Vec<'bump, T> {
2091 type Item = T;
2092 type IntoIter = IntoIter<'bump, T>;
2093
2094 /// Creates a consuming iterator, that is, one that moves each value out of
2095 /// the vector (from start to end). The vector cannot be used after calling
2096 /// this.
2097 ///
2098 /// # Examples
2099 ///
2100 /// ```
2101 /// use bumpalo::{Bump, collections::Vec};
2102 ///
2103 /// let b = Bump::new();
2104 ///
2105 /// let v = bumpalo::vec![in &b; "a".to_string(), "b".to_string()];
2106 /// for s in v.into_iter() {
2107 /// // s has type String, not &String
2108 /// println!("{}", s);
2109 /// }
2110 /// ```
2111 #[inline]
2112 fn into_iter(mut self) -> IntoIter<'bump, T> {
2113 unsafe {
2114 let begin = self.as_mut_ptr();
2115 // assume(!begin.is_null());
2116 let end = if mem::size_of::<T>() == 0 {
2117 arith_offset(begin as *const i8, self.len() as isize) as *const T
2118 } else {
2119 begin.add(self.len()) as *const T
2120 };
2121 mem::forget(self);
2122 IntoIter {
2123 phantom: PhantomData,
2124 ptr: begin,
2125 end,
2126 }
2127 }
2128 }
2129}
2130
2131impl<'a, 'bump, T> IntoIterator for &'a Vec<'bump, T> {
2132 type Item = &'a T;
2133 type IntoIter = slice::Iter<'a, T>;
2134
2135 fn into_iter(self) -> slice::Iter<'a, T> {
2136 self.iter()
2137 }
2138}
2139
2140impl<'a, 'bump, T> IntoIterator for &'a mut Vec<'bump, T> {
2141 type Item = &'a mut T;
2142 type IntoIter = slice::IterMut<'a, T>;
2143
2144 fn into_iter(self) -> slice::IterMut<'a, T> {
2145 self.iter_mut()
2146 }
2147}
2148
2149impl<'bump, T: 'bump> Extend<T> for Vec<'bump, T> {
2150 #[inline]
2151 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2152 let iter = iter.into_iter();
2153 self.reserve(iter.size_hint().0);
2154
2155 for t in iter {
2156 self.push(t);
2157 }
2158 }
2159}
2160
2161impl<'bump, T: 'bump> Vec<'bump, T> {
2162 /// Creates a splicing iterator that replaces the specified range in the vector
2163 /// with the given `replace_with` iterator and yields the removed items.
2164 /// `replace_with` does not need to be the same length as `range`.
2165 ///
2166 /// Note 1: The element range is removed even if the iterator is not
2167 /// consumed until the end.
2168 ///
2169 /// Note 2: It is unspecified how many elements are removed from the vector,
2170 /// if the `Splice` value is leaked.
2171 ///
2172 /// Note 3: The input iterator `replace_with` is only consumed
2173 /// when the `Splice` value is dropped.
2174 ///
2175 /// Note 4: This is optimal if:
2176 ///
2177 /// * The tail (elements in the vector after `range`) is empty,
2178 /// * or `replace_with` yields fewer elements than `range`’s length
2179 /// * or the lower bound of its `size_hint()` is exact.
2180 ///
2181 /// Otherwise, a temporary vector is allocated and the tail is moved twice.
2182 ///
2183 /// # Panics
2184 ///
2185 /// Panics if the starting point is greater than the end point or if
2186 /// the end point is greater than the length of the vector.
2187 ///
2188 /// # Examples
2189 ///
2190 /// ```
2191 /// use bumpalo::{Bump, collections::Vec};
2192 ///
2193 /// let b = Bump::new();
2194 ///
2195 /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
2196 /// let new = [7, 8];
2197 /// let u: Vec<_> = Vec::from_iter_in(v.splice(..2, new.iter().cloned()), &b);
2198 /// assert_eq!(v, &[7, 8, 3]);
2199 /// assert_eq!(u, &[1, 2]);
2200 /// ```
2201 #[inline]
2202 pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<I::IntoIter>
2203 where
2204 R: RangeBounds<usize>,
2205 I: IntoIterator<Item = T>,
2206 {
2207 Splice {
2208 drain: self.drain(range),
2209 replace_with: replace_with.into_iter(),
2210 }
2211 }
2212}
2213
2214/// Extend implementation that copies elements out of references before pushing them onto the Vec.
2215///
2216/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
2217/// append the entire slice at once.
2218///
2219/// [`copy_from_slice`]: https://doc.rust-lang.org/std/primitive.slice.html#method.copy_from_slice
2220impl<'a, 'bump, T: 'a + Copy> Extend<&'a T> for Vec<'bump, T> {
2221 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2222 self.extend(iter.into_iter().cloned())
2223 }
2224}
2225
2226macro_rules! __impl_slice_eq1 {
2227 ($Lhs: ty, $Rhs: ty) => {
2228 __impl_slice_eq1! { $Lhs, $Rhs, Sized }
2229 };
2230 ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2231 impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs
2232 where
2233 A: PartialEq<B>,
2234 {
2235 #[inline]
2236 fn eq(&self, other: &$Rhs) -> bool {
2237 self[..] == other[..]
2238 }
2239 }
2240 };
2241}
2242
2243__impl_slice_eq1! { Vec<'a, A>, Vec<'b, B> }
2244__impl_slice_eq1! { Vec<'a, A>, &'b [B] }
2245__impl_slice_eq1! { Vec<'a, A>, &'b mut [B] }
2246// __impl_slice_eq1! { Cow<'a, [A]>, Vec<'b, B>, Clone }
2247
2248macro_rules! __impl_slice_eq1_array {
2249 ($Lhs: ty, $Rhs: ty) => {
2250 impl<'a, 'b, A, B, const N: usize> PartialEq<$Rhs> for $Lhs
2251 where
2252 A: PartialEq<B>,
2253 {
2254 #[inline]
2255 fn eq(&self, other: &$Rhs) -> bool {
2256 self[..] == other[..]
2257 }
2258 }
2259 };
2260}
2261
2262__impl_slice_eq1_array! { Vec<'a, A>, [B; N] }
2263__impl_slice_eq1_array! { Vec<'a, A>, &'b [B; N] }
2264__impl_slice_eq1_array! { Vec<'a, A>, &'b mut [B; N] }
2265
2266/// Implements comparison of vectors, lexicographically.
2267impl<'bump, T: 'bump + PartialOrd> PartialOrd for Vec<'bump, T> {
2268 #[inline]
2269 fn partial_cmp(&self, other: &Vec<'bump, T>) -> Option<Ordering> {
2270 PartialOrd::partial_cmp(&**self, &**other)
2271 }
2272}
2273
2274impl<'bump, T: 'bump + Eq> Eq for Vec<'bump, T> {}
2275
2276/// Implements ordering of vectors, lexicographically.
2277impl<'bump, T: 'bump + Ord> Ord for Vec<'bump, T> {
2278 #[inline]
2279 fn cmp(&self, other: &Vec<'bump, T>) -> Ordering {
2280 Ord::cmp(&**self, &**other)
2281 }
2282}
2283
2284impl<'bump, T: 'bump + fmt::Debug> fmt::Debug for Vec<'bump, T> {
2285 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2286 fmt::Debug::fmt(&**self, f)
2287 }
2288}
2289
2290impl<'bump, T: 'bump> AsRef<Vec<'bump, T>> for Vec<'bump, T> {
2291 fn as_ref(&self) -> &Vec<'bump, T> {
2292 self
2293 }
2294}
2295
2296impl<'bump, T: 'bump> AsMut<Vec<'bump, T>> for Vec<'bump, T> {
2297 fn as_mut(&mut self) -> &mut Vec<'bump, T> {
2298 self
2299 }
2300}
2301
2302impl<'bump, T: 'bump> AsRef<[T]> for Vec<'bump, T> {
2303 fn as_ref(&self) -> &[T] {
2304 self
2305 }
2306}
2307
2308impl<'bump, T: 'bump> AsMut<[T]> for Vec<'bump, T> {
2309 fn as_mut(&mut self) -> &mut [T] {
2310 self
2311 }
2312}
2313
2314#[cfg(feature = "boxed")]
2315impl<'bump, T: 'bump> From<Vec<'bump, T>> for crate::boxed::Box<'bump, [T]> {
2316 fn from(v: Vec<'bump, T>) -> crate::boxed::Box<'bump, [T]> {
2317 v.into_boxed_slice()
2318 }
2319}
2320
2321impl<'bump, T: 'bump> Borrow<[T]> for Vec<'bump, T> {
2322 #[inline]
2323 fn borrow(&self) -> &[T] {
2324 &self[..]
2325 }
2326}
2327
2328impl<'bump, T: 'bump> BorrowMut<[T]> for Vec<'bump, T> {
2329 #[inline]
2330 fn borrow_mut(&mut self) -> &mut [T] {
2331 &mut self[..]
2332 }
2333}
2334
2335impl<'bump, T> Drop for Vec<'bump, T> {
2336 fn drop(&mut self) {
2337 unsafe {
2338 // use drop for [T]
2339 // use a raw slice to refer to the elements of the vector as weakest necessary type;
2340 // could avoid questions of validity in certain cases
2341 ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
2342 }
2343 // RawVec handles deallocation
2344 }
2345}
2346
2347////////////////////////////////////////////////////////////////////////////////
2348// Clone-on-write
2349////////////////////////////////////////////////////////////////////////////////
2350
2351// impl<'a, 'bump, T: Clone> From<Vec<'bump, T>> for Cow<'a, [T]> {
2352// fn from(v: Vec<'bump, T>) -> Cow<'a, [T]> {
2353// Cow::Owned(v)
2354// }
2355// }
2356
2357// impl<'a, 'bump, T: Clone> From<&'a Vec<'bump, T>> for Cow<'a, [T]> {
2358// fn from(v: &'a Vec<'bump, T>) -> Cow<'a, [T]> {
2359// Cow::Borrowed(v.as_slice())
2360// }
2361// }
2362
2363////////////////////////////////////////////////////////////////////////////////
2364// Iterators
2365////////////////////////////////////////////////////////////////////////////////
2366
2367/// An iterator that moves out of a vector.
2368///
2369/// This `struct` is created by the [`Vec::into_iter`] method
2370/// (provided by the [`IntoIterator`] trait).
2371///
2372/// [`IntoIterator`]: https://doc.rust-lang.org/std/iter/trait.IntoIterator.html
2373pub struct IntoIter<'bump, T> {
2374 phantom: PhantomData<&'bump [T]>,
2375 ptr: *const T,
2376 end: *const T,
2377}
2378
2379impl<'bump, T: fmt::Debug> fmt::Debug for IntoIter<'bump, T> {
2380 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2381 f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
2382 }
2383}
2384
2385impl<'bump, T: 'bump> IntoIter<'bump, T> {
2386 /// Returns the remaining items of this iterator as a slice.
2387 ///
2388 /// # Examples
2389 ///
2390 /// ```
2391 /// use bumpalo::{Bump, collections::Vec};
2392 ///
2393 /// let b = Bump::new();
2394 ///
2395 /// let vec = bumpalo::vec![in &b; 'a', 'b', 'c'];
2396 /// let mut into_iter = vec.into_iter();
2397 /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2398 /// let _ = into_iter.next().unwrap();
2399 /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
2400 /// ```
2401 pub fn as_slice(&self) -> &[T] {
2402 unsafe { slice::from_raw_parts(self.ptr, self.len()) }
2403 }
2404
2405 /// Returns the remaining items of this iterator as a mutable slice.
2406 ///
2407 /// # Examples
2408 ///
2409 /// ```
2410 /// use bumpalo::{Bump, collections::Vec};
2411 ///
2412 /// let b = Bump::new();
2413 ///
2414 /// let vec = bumpalo::vec![in &b; 'a', 'b', 'c'];
2415 /// let mut into_iter = vec.into_iter();
2416 /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2417 /// into_iter.as_mut_slice()[2] = 'z';
2418 /// assert_eq!(into_iter.next().unwrap(), 'a');
2419 /// assert_eq!(into_iter.next().unwrap(), 'b');
2420 /// assert_eq!(into_iter.next().unwrap(), 'z');
2421 /// ```
2422 pub fn as_mut_slice(&mut self) -> &mut [T] {
2423 unsafe { slice::from_raw_parts_mut(self.ptr as *mut T, self.len()) }
2424 }
2425}
2426
2427unsafe impl<'bump, T: Send> Send for IntoIter<'bump, T> {}
2428unsafe impl<'bump, T: Sync> Sync for IntoIter<'bump, T> {}
2429
2430impl<'bump, T: 'bump> Iterator for IntoIter<'bump, T> {
2431 type Item = T;
2432
2433 #[inline]
2434 fn next(&mut self) -> Option<T> {
2435 unsafe {
2436 if self.ptr as *const _ == self.end {
2437 None
2438 } else if mem::size_of::<T>() == 0 {
2439 // purposefully don't use 'ptr.offset' because for
2440 // vectors with 0-size elements this would return the
2441 // same pointer.
2442 self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;
2443
2444 // Make up a value of this ZST.
2445 Some(mem::zeroed())
2446 } else {
2447 let old = self.ptr;
2448 self.ptr = self.ptr.offset(1);
2449
2450 Some(ptr::read(old))
2451 }
2452 }
2453 }
2454
2455 #[inline]
2456 fn size_hint(&self) -> (usize, Option<usize>) {
2457 let exact = if mem::size_of::<T>() == 0 {
2458 (self.end as usize).wrapping_sub(self.ptr as usize)
2459 } else {
2460 unsafe { offset_from(self.end, self.ptr) as usize }
2461 };
2462 (exact, Some(exact))
2463 }
2464
2465 #[inline]
2466 fn count(self) -> usize {
2467 self.len()
2468 }
2469}
2470
2471impl<'bump, T: 'bump> DoubleEndedIterator for IntoIter<'bump, T> {
2472 #[inline]
2473 fn next_back(&mut self) -> Option<T> {
2474 unsafe {
2475 if self.end == self.ptr {
2476 None
2477 } else if mem::size_of::<T>() == 0 {
2478 // See above for why 'ptr.offset' isn't used
2479 self.end = arith_offset(self.end as *const i8, -1) as *mut T;
2480
2481 // Make up a value of this ZST.
2482 Some(mem::zeroed())
2483 } else {
2484 self.end = self.end.offset(-1);
2485
2486 Some(ptr::read(self.end))
2487 }
2488 }
2489 }
2490}
2491
2492impl<'bump, T: 'bump> ExactSizeIterator for IntoIter<'bump, T> {}
2493
2494impl<'bump, T: 'bump> FusedIterator for IntoIter<'bump, T> {}
2495
2496impl<'bump, T> Drop for IntoIter<'bump, T> {
2497 fn drop(&mut self) {
2498 // drop all remaining elements
2499 self.for_each(drop);
2500 }
2501}
2502
2503/// A draining iterator for `Vec<'bump, T>`.
2504///
2505/// This `struct` is created by the [`Vec::drain`] method.
2506pub struct Drain<'a, 'bump, T: 'a + 'bump> {
2507 /// Index of tail to preserve
2508 tail_start: usize,
2509 /// Length of tail
2510 tail_len: usize,
2511 /// Current remaining range to remove
2512 iter: slice::Iter<'a, T>,
2513 vec: NonNull<Vec<'bump, T>>,
2514}
2515
2516impl<'a, 'bump, T: 'a + 'bump + fmt::Debug> fmt::Debug for Drain<'a, 'bump, T> {
2517 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2518 f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
2519 }
2520}
2521
2522unsafe impl<'a, 'bump, T: Sync> Sync for Drain<'a, 'bump, T> {}
2523unsafe impl<'a, 'bump, T: Send> Send for Drain<'a, 'bump, T> {}
2524
2525impl<'a, 'bump, T> Iterator for Drain<'a, 'bump, T> {
2526 type Item = T;
2527
2528 #[inline]
2529 fn next(&mut self) -> Option<T> {
2530 self.iter
2531 .next()
2532 .map(|elt| unsafe { ptr::read(elt as *const _) })
2533 }
2534
2535 fn size_hint(&self) -> (usize, Option<usize>) {
2536 self.iter.size_hint()
2537 }
2538}
2539
2540impl<'a, 'bump, T> DoubleEndedIterator for Drain<'a, 'bump, T> {
2541 #[inline]
2542 fn next_back(&mut self) -> Option<T> {
2543 self.iter
2544 .next_back()
2545 .map(|elt| unsafe { ptr::read(elt as *const _) })
2546 }
2547}
2548
2549impl<'a, 'bump, T> Drop for Drain<'a, 'bump, T> {
2550 fn drop(&mut self) {
2551 // exhaust self first
2552 self.for_each(drop);
2553
2554 if self.tail_len > 0 {
2555 unsafe {
2556 let source_vec = self.vec.as_mut();
2557 // memmove back untouched tail, update to new length
2558 let start = source_vec.len();
2559 let tail = self.tail_start;
2560 if tail != start {
2561 let src = source_vec.as_ptr().add(tail);
2562 let dst = source_vec.as_mut_ptr().add(start);
2563 ptr::copy(src, dst, self.tail_len);
2564 }
2565 source_vec.set_len(start + self.tail_len);
2566 }
2567 }
2568 }
2569}
2570
2571impl<'a, 'bump, T> ExactSizeIterator for Drain<'a, 'bump, T> {}
2572
2573impl<'a, 'bump, T> FusedIterator for Drain<'a, 'bump, T> {}
2574
2575/// A splicing iterator for `Vec`.
2576///
2577/// This struct is created by the [`Vec::splice`] method. See its
2578/// documentation for more information.
2579#[derive(Debug)]
2580pub struct Splice<'a, 'bump, I: Iterator + 'a + 'bump> {
2581 drain: Drain<'a, 'bump, I::Item>,
2582 replace_with: I,
2583}
2584
2585impl<'a, 'bump, I: Iterator> Iterator for Splice<'a, 'bump, I> {
2586 type Item = I::Item;
2587
2588 fn next(&mut self) -> Option<Self::Item> {
2589 self.drain.next()
2590 }
2591
2592 fn size_hint(&self) -> (usize, Option<usize>) {
2593 self.drain.size_hint()
2594 }
2595}
2596
2597impl<'a, 'bump, I: Iterator> DoubleEndedIterator for Splice<'a, 'bump, I> {
2598 fn next_back(&mut self) -> Option<Self::Item> {
2599 self.drain.next_back()
2600 }
2601}
2602
2603impl<'a, 'bump, I: Iterator> ExactSizeIterator for Splice<'a, 'bump, I> {}
2604
2605impl<'a, 'bump, I: Iterator> Drop for Splice<'a, 'bump, I> {
2606 fn drop(&mut self) {
2607 self.drain.by_ref().for_each(drop);
2608
2609 unsafe {
2610 if self.drain.tail_len == 0 {
2611 self.drain.vec.as_mut().extend(self.replace_with.by_ref());
2612 return;
2613 }
2614
2615 // First fill the range left by drain().
2616 if !self.drain.fill(&mut self.replace_with) {
2617 return;
2618 }
2619
2620 // There may be more elements. Use the lower bound as an estimate.
2621 // FIXME: Is the upper bound a better guess? Or something else?
2622 let (lower_bound, _upper_bound) = self.replace_with.size_hint();
2623 if lower_bound > 0 {
2624 self.drain.move_tail(lower_bound);
2625 if !self.drain.fill(&mut self.replace_with) {
2626 return;
2627 }
2628 }
2629
2630 // Collect any remaining elements.
2631 // This is a zero-length vector which does not allocate if `lower_bound` was exact.
2632 let mut collected = Vec::new_in(self.drain.vec.as_ref().buf.bump());
2633 collected.extend(self.replace_with.by_ref());
2634 let mut collected = collected.into_iter();
2635 // Now we have an exact count.
2636 if collected.len() > 0 {
2637 self.drain.move_tail(collected.len());
2638 let filled = self.drain.fill(&mut collected);
2639 debug_assert!(filled);
2640 debug_assert_eq!(collected.len(), 0);
2641 }
2642 }
2643 // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
2644 }
2645}
2646
2647/// Private helper methods for `Splice::drop`
2648impl<'a, 'bump, T> Drain<'a, 'bump, T> {
2649 /// The range from `self.vec.len` to `self.tail_start` contains elements
2650 /// that have been moved out.
2651 /// Fill that range as much as possible with new elements from the `replace_with` iterator.
2652 /// Return whether we filled the entire range. (`replace_with.next()` didn’t return `None`.)
2653 unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
2654 let vec = self.vec.as_mut();
2655 let range_start = vec.len;
2656 let range_end = self.tail_start;
2657 let range_slice =
2658 slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start);
2659
2660 for place in range_slice {
2661 if let Some(new_item) = replace_with.next() {
2662 ptr::write(place, new_item);
2663 vec.len += 1;
2664 } else {
2665 return false;
2666 }
2667 }
2668 true
2669 }
2670
2671 /// Make room for inserting more elements before the tail.
2672 unsafe fn move_tail(&mut self, extra_capacity: usize) {
2673 let vec = self.vec.as_mut();
2674 let used_capacity = self.tail_start + self.tail_len;
2675 vec.buf.reserve(used_capacity, extra_capacity);
2676
2677 let new_tail_start = self.tail_start + extra_capacity;
2678 let src = vec.as_ptr().add(self.tail_start);
2679 let dst = vec.as_mut_ptr().add(new_tail_start);
2680 ptr::copy(src, dst, self.tail_len);
2681 self.tail_start = new_tail_start;
2682 }
2683}
2684
2685/// An iterator produced by calling [`Vec::drain_filter`].
2686#[derive(Debug)]
2687pub struct DrainFilter<'a, 'bump: 'a, T: 'a + 'bump, F>
2688where
2689 F: FnMut(&mut T) -> bool,
2690{
2691 vec: &'a mut Vec<'bump, T>,
2692 idx: usize,
2693 del: usize,
2694 old_len: usize,
2695 pred: F,
2696}
2697
2698impl<'a, 'bump, T, F> Iterator for DrainFilter<'a, 'bump, T, F>
2699where
2700 F: FnMut(&mut T) -> bool,
2701{
2702 type Item = T;
2703
2704 fn next(&mut self) -> Option<T> {
2705 unsafe {
2706 while self.idx != self.old_len {
2707 let i = self.idx;
2708 self.idx += 1;
2709 let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
2710 if (self.pred)(&mut v[i]) {
2711 self.del += 1;
2712 return Some(ptr::read(&v[i]));
2713 } else if self.del > 0 {
2714 let del = self.del;
2715 let src: *const T = &v[i];
2716 let dst: *mut T = &mut v[i - del];
2717 // This is safe because self.vec has length 0
2718 // thus its elements will not have Drop::drop
2719 // called on them in the event of a panic.
2720 ptr::copy_nonoverlapping(src, dst, 1);
2721 }
2722 }
2723 None
2724 }
2725 }
2726
2727 fn size_hint(&self) -> (usize, Option<usize>) {
2728 (0, Some(self.old_len - self.idx))
2729 }
2730}
2731
2732impl<'a, 'bump, T, F> Drop for DrainFilter<'a, 'bump, T, F>
2733where
2734 F: FnMut(&mut T) -> bool,
2735{
2736 fn drop(&mut self) {
2737 self.for_each(drop);
2738 unsafe {
2739 self.vec.set_len(self.old_len - self.del);
2740 }
2741 }
2742}
2743
2744#[cfg(feature = "std")]
2745impl<'bump> io::Write for Vec<'bump, u8> {
2746 #[inline]
2747 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
2748 self.extend_from_slice_copy(buf);
2749 Ok(buf.len())
2750 }
2751
2752 #[inline]
2753 fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
2754 self.extend_from_slice_copy(buf);
2755 Ok(())
2756 }
2757
2758 #[inline]
2759 fn flush(&mut self) -> io::Result<()> {
2760 Ok(())
2761 }
2762}
2763
2764#[cfg(feature = "serde")]
2765mod serialize {
2766 use super::*;
2767
2768 use serde::{ser::SerializeSeq, Serialize, Serializer};
2769
2770 impl<'a, T> Serialize for Vec<'a, T>
2771 where
2772 T: Serialize,
2773 {
2774 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
2775 where
2776 S: Serializer,
2777 {
2778 let mut seq = serializer.serialize_seq(Some(self.len))?;
2779 for e in self.iter() {
2780 seq.serialize_element(e)?;
2781 }
2782 seq.end()
2783 }
2784 }
2785
2786}