Drain

Let’s move on to Drain. Drain is largely the same as IntoIter, except thatinstead of consuming the Vec, it borrows the Vec and leaves its allocationuntouched. For now we’ll only implement the “basic” full-range version.

  1. use std::marker::PhantomData;
  2. struct Drain<'a, T: 'a> {
  3. // Need to bound the lifetime here, so we do it with `&'a mut Vec<T>`
  4. // because that's semantically what we contain. We're "just" calling
  5. // `pop()` and `remove(0)`.
  6. vec: PhantomData<&'a mut Vec<T>>,
  7. start: *const T,
  8. end: *const T,
  9. }
  10. impl<'a, T> Iterator for Drain<'a, T> {
  11. type Item = T;
  12. fn next(&mut self) -> Option<T> {
  13. if self.start == self.end {
  14. None

— wait, this is seeming familiar. Let’s do some more compression. BothIntoIter and Drain have the exact same structure, let’s just factor it out.

  1. struct RawValIter<T> {
  2. start: *const T,
  3. end: *const T,
  4. }
  5. impl<T> RawValIter<T> {
  6. // unsafe to construct because it has no associated lifetimes.
  7. // This is necessary to store a RawValIter in the same struct as
  8. // its actual allocation. OK since it's a private implementation
  9. // detail.
  10. unsafe fn new(slice: &[T]) -> Self {
  11. RawValIter {
  12. start: slice.as_ptr(),
  13. end: if slice.len() == 0 {
  14. // if `len = 0`, then this is not actually allocated memory.
  15. // Need to avoid offsetting because that will give wrong
  16. // information to LLVM via GEP.
  17. slice.as_ptr()
  18. } else {
  19. slice.as_ptr().offset(slice.len() as isize)
  20. }
  21. }
  22. }
  23. }
  24. // Iterator and DoubleEndedIterator impls identical to IntoIter.

And IntoIter becomes the following:

  1. pub struct IntoIter<T> {
  2. _buf: RawVec<T>, // we don't actually care about this. Just need it to live.
  3. iter: RawValIter<T>,
  4. }
  5. impl<T> Iterator for IntoIter<T> {
  6. type Item = T;
  7. fn next(&mut self) -> Option<T> { self.iter.next() }
  8. fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
  9. }
  10. impl<T> DoubleEndedIterator for IntoIter<T> {
  11. fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
  12. }
  13. impl<T> Drop for IntoIter<T> {
  14. fn drop(&mut self) {
  15. for _ in &mut self.iter {}
  16. }
  17. }
  18. impl<T> Vec<T> {
  19. pub fn into_iter(self) -> IntoIter<T> {
  20. unsafe {
  21. let iter = RawValIter::new(&self);
  22. let buf = ptr::read(&self.buf);
  23. mem::forget(self);
  24. IntoIter {
  25. iter: iter,
  26. _buf: buf,
  27. }
  28. }
  29. }
  30. }

Note that I’ve left a few quirks in this design to make upgrading Drain to workwith arbitrary subranges a bit easier. In particular we could have RawValIterdrain itself on drop, but that won’t work right for a more complex Drain.We also take a slice to simplify Drain initialization.

Alright, now Drain is really easy:

  1. use std::marker::PhantomData;
  2. pub struct Drain<'a, T: 'a> {
  3. vec: PhantomData<&'a mut Vec<T>>,
  4. iter: RawValIter<T>,
  5. }
  6. impl<'a, T> Iterator for Drain<'a, T> {
  7. type Item = T;
  8. fn next(&mut self) -> Option<T> { self.iter.next() }
  9. fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
  10. }
  11. impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
  12. fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
  13. }
  14. impl<'a, T> Drop for Drain<'a, T> {
  15. fn drop(&mut self) {
  16. for _ in &mut self.iter {}
  17. }
  18. }
  19. impl<T> Vec<T> {
  20. pub fn drain(&mut self) -> Drain<T> {
  21. unsafe {
  22. let iter = RawValIter::new(&self);
  23. // this is a mem::forget safety thing. If Drain is forgotten, we just
  24. // leak the whole Vec's contents. Also we need to do this *eventually*
  25. // anyway, so why not do it now?
  26. self.len = 0;
  27. Drain {
  28. iter: iter,
  29. vec: PhantomData,
  30. }
  31. }
  32. }
  33. }

For more details on the mem::forget problem, see thesection on leaks.