flex_alloc/vec/
splice.rs

1use core::iter::{FusedIterator, Peekable};
2use core::marker::PhantomData;
3use core::ops::Range;
4use core::ptr;
5
6use super::buffer::VecBuffer;
7use super::drain::Drain;
8use super::index_panic;
9use crate::capacity::{Grow, Index};
10
11/// A struct used to manage an active `splice` operation for a `Vec` instance
12pub struct Splice<'s, I, B, G>
13where
14    I: Iterator,
15    B: VecBuffer<Item = I::Item>,
16    G: Grow,
17{
18    drain: Drain<'s, B>,
19    extend: Peekable<I>,
20    _pd: PhantomData<G>,
21}
22
23impl<'s, I, B, G> Splice<'s, I, B, G>
24where
25    I: Iterator,
26    B: VecBuffer<Item = I::Item>,
27    G: Grow,
28{
29    pub(super) fn new(vec: &'s mut B, extend: I, range: Range<usize>) -> Self {
30        let drain = Drain::new(vec, range);
31        Self {
32            drain,
33            extend: extend.peekable(),
34            _pd: PhantomData,
35        }
36    }
37
38    /// Check if the segment to be removed has remaining items
39    pub const fn is_empty(&self) -> bool {
40        self.drain.is_empty()
41    }
42
43    /// Get the number of remaining items in the segment to be removed
44    pub const fn len(&self) -> usize {
45        self.drain.len()
46    }
47}
48
49impl<'s, I, B, G> Iterator for Splice<'s, I, B, G>
50where
51    I: Iterator,
52    B: VecBuffer<Item = I::Item>,
53    G: Grow,
54{
55    type Item = I::Item;
56
57    fn next(&mut self) -> Option<Self::Item> {
58        self.drain.next()
59    }
60
61    #[inline]
62    fn count(self) -> usize
63    where
64        Self: Sized,
65    {
66        self.len()
67    }
68
69    #[inline]
70    fn size_hint(&self) -> (usize, Option<usize>) {
71        self.drain.size_hint()
72    }
73}
74
75impl<'s, I, B, G> DoubleEndedIterator for Splice<'s, I, B, G>
76where
77    I: Iterator,
78    B: VecBuffer<Item = I::Item>,
79    G: Grow,
80{
81    fn next_back(&mut self) -> Option<Self::Item> {
82        self.drain.next_back()
83    }
84}
85
86impl<'s, I, B, G> ExactSizeIterator for Splice<'s, I, B, G>
87where
88    I: Iterator,
89    B: VecBuffer<Item = I::Item>,
90    G: Grow,
91{
92}
93
94impl<'s, I, B, G> FusedIterator for Splice<'s, I, B, G>
95where
96    I: Iterator,
97    B: VecBuffer<Item = I::Item>,
98    G: Grow,
99{
100}
101
102impl<'s, I, B, G> Drop for Splice<'s, I, B, G>
103where
104    I: Iterator,
105    B: VecBuffer<Item = I::Item>,
106    G: Grow,
107{
108    fn drop(&mut self) {
109        self.drain.clear_remain();
110
111        while self.extend.peek().is_some() {
112            for index in self.drain.range.clone() {
113                if let Some(item) = self.extend.next() {
114                    unsafe { self.drain.buf.uninit_index(index) }.write(item);
115                    self.drain.range.start = index + 1;
116                } else {
117                    // iterator exhausted, Drain will move tail if necessary and set length
118                    return;
119                }
120            }
121
122            let mut buf_cap = self.drain.buf.capacity();
123            let (min_remain, max_remain) = self.extend.size_hint();
124            let cap_remain = buf_cap.to_usize() - self.drain.range.end - self.drain.tail_length;
125            if min_remain > cap_remain {
126                let new_cap =
127                    B::Index::try_from_usize(buf_cap.to_usize() + min_remain - cap_remain)
128                        .expect("exceeded range of capacity");
129                let new_cap = G::next_capacity::<B::Item, _>(buf_cap, new_cap);
130                match self.drain.buf.grow_buffer(new_cap, false) {
131                    Ok(_) => (),
132                    Err(err) => err.panic(),
133                }
134                buf_cap = new_cap;
135            }
136
137            // FIXME some values of size_hint could lead to more tail shifts than necessary,
138            // unless we proactively move the tail further?
139            if self.drain.tail_length > 0 {
140                let new_tail = self
141                    .drain
142                    .range
143                    .end
144                    .saturating_add(max_remain.unwrap_or_default().max(min_remain))
145                    .min(buf_cap.to_usize());
146                let ins_count = new_tail - self.drain.range.end;
147                if ins_count < min_remain {
148                    index_panic();
149                }
150                unsafe {
151                    let head = self.drain.buf.data_ptr_mut().add(self.drain.range.end);
152                    ptr::copy(head, head.add(ins_count), self.drain.tail_length);
153                }
154                self.drain.range.end += ins_count;
155            }
156        }
157    }
158}
flex_alloc/vec/splice.rs

flex_alloc/vec/
splice.rs
