splice.rs - source
Description: Source of the Rust file `library/alloc/src/collections/vec_deque/splice.rs`.

#
alloc/collections/vec_deque/
splice.rs

    1use core::alloc::Allocator;
    2
    3use crate::alloc::Global;
    4use crate::collections::vec_deque::Drain;
    5use crate::vec::Vec;
    6
    7/// A splicing iterator for `VecDeque`.
    8///
    9/// This struct is created by [`VecDeque::splice()`][super::VecDeque::splice].
    10/// See its documentation for more.
    11///
    12/// # Example
    13///
    14/// ```
    15/// # #![feature(deque_extend_front)]
    16/// # use std::collections::VecDeque;
    17///
    18/// let mut v = VecDeque::from(vec![0, 1, 2]);
    19/// let new = [7, 8];
    20/// let iter: std::collections::vec_deque::Splice<'_, _> = v.splice(1.., new);
    21/// ```
    22#[unstable(feature = "deque_extend_front", issue = "146975")]
    23#[derive(Debug)]
    24pub struct Splice<
    25    'a,
    26    I: Iterator + 'a,
    27    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
    28> {
    29    pub(super) drain: Drain<'a, I::Item, A>,
    30    pub(super) replace_with: I,
    31}
    32
    33#[unstable(feature = "deque_extend_front", issue = "146975")]
    34impl<I: Iterator, A: Allocator> Iterator for Splice<'_, I, A> {
    35    type Item = I::Item;
    36
    37    fn next(&mut self) -> Option<Self::Item> {
    38        self.drain.next()
    39    }
    40
    41    fn size_hint(&self) -> (usize, Option<usize>) {
    42        self.drain.size_hint()
    43    }
    44}
    45
    46#[unstable(feature = "deque_extend_front", issue = "146975")]
    47impl<I: Iterator, A: Allocator> DoubleEndedIterator for Splice<'_, I, A> {
    48    fn next_back(&mut self) -> Option<Self::Item> {
    49        self.drain.next_back()
    50    }
    51}
    52
    53#[unstable(feature = "deque_extend_front", issue = "146975")]
    54impl<I: Iterator, A: Allocator> ExactSizeIterator for Splice<'_, I, A> {}
    55
    56// See also: [`crate::vec::Splice`].
    57#[unstable(feature = "deque_extend_front", issue = "146975")]
    58impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> {
    59    fn drop(&mut self) {
    60        // This will set drain.remaining to 0, so its drop won't try to read deallocated memory on
    61        // drop.
    62        self.drain.by_ref().for_each(drop);
    63
    64        // At this point draining is done and the only remaining tasks are splicing
    65        // and moving things into the final place.
    66
    67        unsafe {
    68            let tail_len = self.drain.tail_len; // #elements behind the drain
    69
    70            if tail_len == 0 {
    71                self.drain.deque.as_mut().extend(self.replace_with.by_ref());
    72                return;
    73            }
    74
    75            // First fill the range left by drain().
    76            if !self.drain.fill(&mut self.replace_with) {
    77                return;
    78            }
    79
    80            // There may be more elements. Use the lower bound as an estimate.
    81            // FIXME: Is the upper bound a better guess? Or something else?
    82            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
    83            if lower_bound > 0 {
    84                self.drain.move_tail(lower_bound);
    85                if !self.drain.fill(&mut self.replace_with) {
    86                    return;
    87                }
    88            }
    89
    90            // Collect any remaining elements.
    91            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
    92            let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
    93            // Now we have an exact count.
    94            if collected.len() > 0 {
    95                self.drain.move_tail(collected.len());
    96                let filled = self.drain.fill(&mut collected);
    97                debug_assert!(filled);
    98                debug_assert_eq!(collected.len(), 0);
    99            }
    100        }
    101        // Let `Drain::drop` move the tail back if necessary and restore `deque.len`.
    102    }
    103}
    104
    105/// Private helper methods for `Splice::drop`
    106impl<T, A: Allocator> Drain<'_, T, A> {
    107    /// The range from `self.deque.len` to `self.deque.len + self.drain_len` contains elements that
    108    /// have been moved out.
    109    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
    110    /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
    111    ///
    112    /// # Safety
    113    ///
    114    /// self.deque must be valid. self.deque.len and self.deque.len + self.drain_len must be less
    115    /// than twice the deque's capacity.
    116    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
    117        let deque = unsafe { self.deque.as_mut() };
    118        let range_start = deque.len;
    119        let range_end = range_start + self.drain_len;
    120
    121        for idx in range_start..range_end {
    122            if let Some(new_item) = replace_with.next() {
    123                let index = deque.to_physical_idx(idx);
    124                unsafe { deque.buffer_write(index, new_item) };
    125                deque.len += 1;
    126                self.drain_len -= 1;
    127            } else {
    128                return false;
    129            }
    130        }
    131        true
    132    }
    133
    134    /// Makes room for inserting more elements before the tail.
    135    ///
    136    /// # Safety
    137    ///
    138    /// self.deque must be valid.
    139    unsafe fn move_tail(&mut self, additional: usize) {
    140        let deque = unsafe { self.deque.as_mut() };
    141        let tail_start = deque.len + self.drain_len;
    142        deque.buf.reserve(tail_start + self.tail_len, additional);
    143
    144        let new_tail_start = tail_start + additional;
    145        unsafe {
    146            deque.wrap_copy(tail_start, new_tail_start, self.tail_len);
    147        }
    148        self.drain_len += additional;
    149    }
    150}