Debian Codegraph @

.cargo/vendor/bumpalo/src/collections/vec.rs

raw
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
91 use super::raw_vec::RawVec;
92 use crate::collections::CollectionAllocErr;
93 use crate::Bump;
94 use core::borrow::{Borrow, BorrowMut};
95 use core::cmp::Ordering;
96 use core::fmt;
97 use core::hash::{self, Hash};
98 use core::iter::FusedIterator;
99 use core::marker::PhantomData;
100 use core::mem;
101 use core::ops;
102 use core::ops::Bound::{Excluded, Included, Unbounded};
103 use core::ops::{Index, IndexMut, RangeBounds};
104 use core::ptr;
105 use core::ptr::NonNull;
106 use core::slice;
107 #[cfg(feature = "std")]
108 use std::io;
109
110 unsafe fn arith_offset<T>(p: *const T, offset: isize) -> *const T {
111 p.offset(offset)
112 }
113
114 fn partition_dedup_by<T, F>(s: &mut [T], mut same_bucket: F) -> (&mut [T], &mut [T])
115 where
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
203 unsafe fn offset_from<T>(p: *const T, origin: *const T) -> isize
204 where
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 &bump; 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]
255 macro_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 &mdash; 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
522 pub struct Vec<'bump, T: 'bump> {
523 buf: RawVec<'bump, T>,
524 len: usize,
525 }
526
527 ////////////////////////////////////////////////////////////////////////////////
528 // Inherent methods
529 ////////////////////////////////////////////////////////////////////////////////
530
531 impl<'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 &bump; 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")]
1681 impl<'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
1712 impl<'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
1780 impl<'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}`.
1907 trait ExtendWith<T> {
1908 fn next(&mut self) -> T;
1909 fn last(self) -> T;
1910 }
1911
1912 struct ExtendElement<T>(T);
1913 impl<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
1922 impl<'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
1958 struct SetLenOnDrop<'a> {
1959 len: &'a mut usize,
1960 local_len: usize,
1961 }
1962
1963 impl<'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
1983 impl<'a> Drop for SetLenOnDrop<'a> {
1984 #[inline]
1985 fn drop(&mut self) {
1986 *self.len = self.local_len;
1987 }
1988 }
1989
1990 impl<'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
2019 impl<'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
2039 impl<'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
2046 impl<'bump, T, I> Index<I> for Vec<'bump, T>
2047 where
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
2058 impl<'bump, T, I> IndexMut<I> for Vec<'bump, T>
2059 where
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
2068 impl<'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
2080 impl<'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
2090 impl<'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
2131 impl<'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
2140 impl<'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
2149 impl<'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
2161 impl<'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
2220 impl<'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
2226 macro_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
2248 macro_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.
2267 impl<'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
2274 impl<'bump, T: 'bump + Eq> Eq for Vec<'bump, T> {}
2275
2276 /// Implements ordering of vectors, lexicographically.
2277 impl<'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
2284 impl<'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
2290 impl<'bump, T: 'bump> AsRef<Vec<'bump, T>> for Vec<'bump, T> {
2291 fn as_ref(&self) -> &Vec<'bump, T> {
2292 self
2293 }
2294 }
2295
2296 impl<'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
2302 impl<'bump, T: 'bump> AsRef<[T]> for Vec<'bump, T> {
2303 fn as_ref(&self) -> &[T] {
2304 self
2305 }
2306 }
2307
2308 impl<'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")]
2315 impl<'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
2321 impl<'bump, T: 'bump> Borrow<[T]> for Vec<'bump, T> {
2322 #[inline]
2323 fn borrow(&self) -> &[T] {
2324 &self[..]
2325 }
2326 }
2327
2328 impl<'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
2335 impl<'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
2373 pub struct IntoIter<'bump, T> {
2374 phantom: PhantomData<&'bump [T]>,
2375 ptr: *const T,
2376 end: *const T,
2377 }
2378
2379 impl<'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
2385 impl<'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
2427 unsafe impl<'bump, T: Send> Send for IntoIter<'bump, T> {}
2428 unsafe impl<'bump, T: Sync> Sync for IntoIter<'bump, T> {}
2429
2430 impl<'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
2471 impl<'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
2492 impl<'bump, T: 'bump> ExactSizeIterator for IntoIter<'bump, T> {}
2493
2494 impl<'bump, T: 'bump> FusedIterator for IntoIter<'bump, T> {}
2495
2496 impl<'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.
2506 pub 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
2516 impl<'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
2522 unsafe impl<'a, 'bump, T: Sync> Sync for Drain<'a, 'bump, T> {}
2523 unsafe impl<'a, 'bump, T: Send> Send for Drain<'a, 'bump, T> {}
2524
2525 impl<'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
2540 impl<'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
2549 impl<'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
2571 impl<'a, 'bump, T> ExactSizeIterator for Drain<'a, 'bump, T> {}
2572
2573 impl<'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)]
2580 pub struct Splice<'a, 'bump, I: Iterator + 'a + 'bump> {
2581 drain: Drain<'a, 'bump, I::Item>,
2582 replace_with: I,
2583 }
2584
2585 impl<'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
2597 impl<'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
2603 impl<'a, 'bump, I: Iterator> ExactSizeIterator for Splice<'a, 'bump, I> {}
2604
2605 impl<'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`
2648 impl<'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)]
2687 pub struct DrainFilter<'a, 'bump: 'a, T: 'a + 'bump, F>
2688 where
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
2698 impl<'a, 'bump, T, F> Iterator for DrainFilter<'a, 'bump, T, F>
2699 where
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
2732 impl<'a, 'bump, T, F> Drop for DrainFilter<'a, 'bump, T, F>
2733 where
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")]
2745 impl<'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")]
2765 mod 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 }