1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
use crate::alloc::{Allocator, Global};
use core::mem::{ManuallyDrop, SizedTypeProperties};
use core::ptr;
use core::slice;
use super::Vec;
/// 使用闭包确定是否应删除元素的迭代器。
///
/// 该结构体由 [`Vec::drain_filter`] 创建。
/// 有关更多信息,请参见其文档。
///
/// # Example
///
/// ```
/// #![feature(drain_filter)]
///
/// let mut v = vec![0, 1, 2];
/// let iter: std::vec::DrainFilter<'_, _, _> = v.drain_filter(|x| *x % 2 == 0);
/// ```
#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
#[derive(Debug)]
pub struct DrainFilter<
'a,
T,
F,
#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> where
F: FnMut(&mut T) -> bool,
{
pub(super) vec: &'a mut Vec<T, A>,
/// `next` 的下一次调用将检查的项的索引。
pub(super) idx: usize,
/// 到目前为止已耗尽 (removed) 的项数。
pub(super) del: usize,
/// draining 之前 `vec` 的原始长度。
pub(super) old_len: usize,
/// 过滤器测试谓词。
pub(super) pred: F,
/// 指示 panic 的标志已出现在过滤器测试谓词中。
/// 这在丢弃实现中用作一个提示,以防止消耗 `DrainFilter` 的其余部分。
/// 任何未处理的项目将在 `vec` 中后移,但过滤谓词不会丢弃或测试其他任何项目。
///
///
pub(super) panic_flag: bool,
}
impl<T, F, A: Allocator> DrainFilter<'_, T, F, A>
where
F: FnMut(&mut T) -> bool,
{
/// 返回底层分配器的引用。
#[unstable(feature = "allocator_api", issue = "32838")]
#[inline]
pub fn allocator(&self) -> &A {
self.vec.allocator()
}
/// 在源 `Vec` 中保留未屈服的元素。
///
/// # Examples
///
/// ```
/// #![feature(drain_filter)]
/// #![feature(drain_keep_rest)]
///
/// let mut vec = vec!['a', 'b', 'c'];
/// let mut drain = vec.drain_filter(|_| true);
///
/// assert_eq!(drain.next().unwrap(), 'a');
///
/// // 这个调用将 'b' 和 'c' 保存在 vec 中。
/// drain.keep_rest();
///
/// // 如果我们不调用 `keep_rest()`,`vec` 将为空。
/////
/// assert_eq!(vec, ['b', 'c']);
/// ```
#[unstable(feature = "drain_keep_rest", issue = "101122")]
pub fn keep_rest(self) {
// 此时布局如下所示:
//
// _____________________/-- old_len
// / \
// [kept] [yielded] [tail] \_______/ ^-- idx \-- del
//
// 通常 `Drop` impl 会丢弃 [tail] (通过 .for_each(drop), ie still calling `pred`)
//
// 1. 在 [kept] 之后移动 [tail]
// 2. 将原始 vec 的长度更新为 `old_len - del` a.
// 对于 ZST,这是我们唯一想做的事情
// 3.
// 不要*不要*丢弃自己,因为一切都已经处于一致状态,没有什么可做的
//
let mut this = ManuallyDrop::new(self);
unsafe {
// ZST 没有身份,所以我们不需要移动它们。
if !T::IS_ZST && this.idx < this.old_len && this.del > 0 {
let ptr = this.vec.as_mut_ptr();
let src = ptr.add(this.idx);
let dst = src.sub(this.del);
let tail_len = this.old_len - this.idx;
src.copy_to(dst, tail_len);
}
let new_len = this.old_len - this.del;
this.vec.set_len(new_len);
}
}
}
#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Iterator for DrainFilter<'_, T, F, A>
where
F: FnMut(&mut T) -> bool,
{
type Item = T;
fn next(&mut self) -> Option<T> {
unsafe {
while self.idx < self.old_len {
let i = self.idx;
let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
self.panic_flag = true;
let drained = (self.pred)(&mut v[i]);
self.panic_flag = false;
// 在谓词被调用之后更新索引。
// 如果索引先于谓词 panics 进行更新,则该索引处的元素将被泄漏。
//
self.idx += 1;
if drained {
self.del += 1;
return Some(ptr::read(&v[i]));
} else if self.del > 0 {
let del = self.del;
let src: *const T = &v[i];
let dst: *mut T = &mut v[i - del];
ptr::copy_nonoverlapping(src, dst, 1);
}
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.old_len - self.idx))
}
}
#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Drop for DrainFilter<'_, T, F, A>
where
F: FnMut(&mut T) -> bool,
{
fn drop(&mut self) {
struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator>
where
F: FnMut(&mut T) -> bool,
{
drain: &'b mut DrainFilter<'a, T, F, A>,
}
impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A>
where
F: FnMut(&mut T) -> bool,
{
fn drop(&mut self) {
unsafe {
if self.drain.idx < self.drain.old_len && self.drain.del > 0 {
// 这是一个非常混乱的状态,实际上并没有一件明显正确的事情要做。
// 我们不想继续尝试执行 `pred`,因此我们只回移了所有未处理的元素,并告诉 vec 它们仍然存在。
//
// 需要回退以防止在谓词发生 panic 之前对最后一个成功排出的项进行双重丢弃。
//
//
let ptr = self.drain.vec.as_mut_ptr();
let src = ptr.add(self.drain.idx);
let dst = src.sub(self.drain.del);
let tail_len = self.drain.old_len - self.drain.idx;
src.copy_to(dst, tail_len);
}
self.drain.vec.set_len(self.drain.old_len - self.drain.del);
}
}
}
let backshift = BackshiftOnDrop { drain: self };
// 如果过滤谓词尚未 panic,请尝试消耗所有剩余的元素。
// 无论是否已经 panic 或这里的消耗量 panics,我们都会回退所有剩余的元素。
//
if !backshift.drain.panic_flag {
backshift.drain.for_each(drop);
}
}
}