library/alloc/src/collections/vec_deque/drain.rs

   1 use core::iter::FusedIterator;
   2 use core::ptr::{self, NonNull};
   3 use core::{fmt, mem};
   4
   5 use super::{count, Iter, VecDeque};
   6
   7 /// A draining iterator over the elements of a `VecDeque`.
   8 ///
   9 /// This `struct` is created by the [`drain`] method on [`VecDeque`]. See its
  10 /// documentation for more.
  11 ///
  12 /// [`drain`]: VecDeque::drain
  13 #[stable(feature = "drain", since = "1.6.0")]
  14 pub struct Drain<'a, T: 'a> {
  15     pub(crate) after_tail: usize,
  16     pub(crate) after_head: usize,
  17     pub(crate) iter: Iter<'a, T>,
  18     pub(crate) deque: NonNull<VecDeque<T>>,
  19 }
  20
  21 #[stable(feature = "collection_debug", since = "1.17.0")]
  22 impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
  23     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  24         f.debug_tuple("Drain")
  25             .field(&self.after_tail)
  26             .field(&self.after_head)
  27             .field(&self.iter)
  28             .finish()
  29     }
  30 }
  31
  32 #[stable(feature = "drain", since = "1.6.0")]
  33 unsafe impl<T: Sync> Sync for Drain<'_, T> {}
  34 #[stable(feature = "drain", since = "1.6.0")]
  35 unsafe impl<T: Send> Send for Drain<'_, T> {}
  36
  37 #[stable(feature = "drain", since = "1.6.0")]
  38 impl<T> Drop for Drain<'_, T> {
  39     fn drop(&mut self) {
  40         struct DropGuard<'r, 'a, T>(&'r mut Drain<'a, T>);
  41
  42         impl<'r, 'a, T> Drop for DropGuard<'r, 'a, T> {
  43             fn drop(&mut self) {
  44                 self.0.for_each(drop);
  45
  46                 let source_deque = unsafe { self.0.deque.as_mut() };
  47
  48                 // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
  49                 //
  50                 //        T   t   h   H
  51                 // [. . . o o x x o o . . .]
  52                 //
  53                 let orig_tail = source_deque.tail;
  54                 let drain_tail = source_deque.head;
  55                 let drain_head = self.0.after_tail;
  56                 let orig_head = self.0.after_head;
  57
  58                 let tail_len = count(orig_tail, drain_tail, source_deque.cap());
  59                 let head_len = count(drain_head, orig_head, source_deque.cap());
  60
  61                 // Restore the original head value
  62                 source_deque.head = orig_head;
  63
  64                 match (tail_len, head_len) {
  65                     (0, 0) => {
  66                         source_deque.head = 0;
  67                         source_deque.tail = 0;
  68                     }
  69                     (0, _) => {
  70                         source_deque.tail = drain_head;
  71                     }
  72                     (_, 0) => {
  73                         source_deque.head = drain_tail;
  74                     }
  75                     _ => unsafe {
  76                         if tail_len <= head_len {
  77                             source_deque.tail = source_deque.wrap_sub(drain_head, tail_len);
  78                             source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
  79                         } else {
  80                             source_deque.head = source_deque.wrap_add(drain_tail, head_len);
  81                             source_deque.wrap_copy(drain_tail, drain_head, head_len);
  82                         }
  83                     },
  84                 }
  85             }
  86         }
  87
  88         while let Some(item) = self.next() {
  89             let guard = DropGuard(self);
  90             drop(item);
  91             mem::forget(guard);
  92         }
  93
  94         DropGuard(self);
  95     }
  96 }
  97
  98 #[stable(feature = "drain", since = "1.6.0")]
  99 impl<T> Iterator for Drain<'_, T> {
 100     type Item = T;
 101
 102     #[inline]
 103     fn next(&mut self) -> Option<T> {
 104         self.iter.next().map(|elt| unsafe { ptr::read(elt) })
 105     }
 106
 107     #[inline]
 108     fn size_hint(&self) -> (usize, Option<usize>) {
 109         self.iter.size_hint()
 110     }
 111 }
 112
 113 #[stable(feature = "drain", since = "1.6.0")]
 114 impl<T> DoubleEndedIterator for Drain<'_, T> {
 115     #[inline]
 116     fn next_back(&mut self) -> Option<T> {
 117         self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
 118     }
 119 }
 120
 121 #[stable(feature = "drain", since = "1.6.0")]
 122 impl<T> ExactSizeIterator for Drain<'_, T> {}
 123
 124 #[stable(feature = "fused", since = "1.26.0")]
 125 impl<T> FusedIterator for Drain<'_, T> {}