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
#![allow(clippy::redundant_else)]
use core::ptr;
use super::{TailVec, VecLike};
impl<T, V: VecLike<T = T>> TailVec<'_, T, V> {
/// Retains only the elements specified by the predicate.
///
/// In other words, remove all elements `e` such that `f(&e)` returns `false`.
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// # Examples
///
/// ```
/// # use tailvec::*;
/// let mut vec = vec![0, 1, 2, 3, 4];
/// let (_, mut rest) = vec.split_tail(1);
/// assert_eq!(rest, &mut [1, 2, 3, 4]);
///
/// rest.retain(|n| *n % 2 == 0);
/// assert_eq!({rest}, [2, 4]);
/// assert_eq!(vec, [0, 2, 4]);
/// ```
///
/// Because the elements are visited exactly once in the original order,
/// external state may be used to decide which elements to keep.
///
/// ```
/// # use tailvec::*;
/// let mut vec = vec![0, 1, 2, 3, 4, 5];
/// let (_, mut rest) = vec.split_tail(1);
/// assert_eq!(rest, &mut [1, 2, 3, 4, 5]);
///
/// let keep = [false, true, true, false, true];
/// let mut iter = keep.iter();
/// rest.retain(|_| *iter.next().unwrap());
/// assert_eq!({rest}, [2, 3, 5]);
/// assert_eq!(vec, [0, 2, 3, 5]);
/// ```
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(&T) -> bool,
{
self.retain_mut(|ele| {
f(ele)
});
}
/// Retains only the elements specified by the predicate, passing a mutable reference to it.
///
/// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// # Examples
///
/// ```
/// # use tailvec::*;
/// let mut vec = vec![0, 1, 2, 3, 4];
/// let (_, mut rest) = vec.split_tail(1);
/// assert_eq!(rest, &mut [1, 2, 3, 4]);
///
/// rest.retain_mut(|x| if *x <= 3 {
/// *x += 1;
/// true
/// } else {
/// false
/// });
/// assert_eq!({rest}, [2, 3, 4]);
/// assert_eq!(vec, [0, 2, 3, 4]);
/// ```
pub fn retain_mut<F>(&mut self, mut f: F)
where F: FnMut(&mut T) -> bool,
{
struct Guard<'a, 'b, V: VecLike> {
this: &'b mut TailVec<'a, V::T, V>,
orig_len: usize,
proced_len: usize,
deleted_cnt: usize,
}
impl<V: VecLike> Drop for Guard<'_, '_, V> {
fn drop(&mut self) {
let Self {
ref mut this,
orig_len,
proced_len,
deleted_cnt,
} = *self;
unsafe {
if deleted_cnt > 0 {
let ptr = this.parts()
.as_mut_ptr();
let src = ptr.add(proced_len);
let dst = src.sub(deleted_cnt);
let count = orig_len - proced_len;
ptr::copy(src, dst, count);
}
this.set_len(orig_len - deleted_cnt);
}
}
}
impl<V: VecLike> Guard<'_, '_, V> {
fn run<F, const DELETED: bool>(&mut self, f: &mut F)
where F: FnMut(&mut V::T) -> bool,
{
let parts = unsafe {
self.this.parts().as_mut_ptr()
};
// SAFETY: 代码逻辑基本来自`alloc::Vec::retain_mut`
while self.proced_len != self.orig_len {
let cur = unsafe {
&mut *parts.add(self.proced_len)
};
if !f(unsafe { cur.assume_init_mut() }) {
self.proced_len += 1;
self.deleted_cnt += 1;
unsafe { ptr::drop_in_place(cur) }
if DELETED {
continue;
} else {
break;
}
}
if DELETED {
unsafe {
let hole_slot = parts
.add(self.proced_len - self.deleted_cnt);
ptr::copy_nonoverlapping(cur, hole_slot, 1);
}
}
self.proced_len += 1;
}
}
}
let orig_len = self.len();
unsafe { self.set_len(0) }
let mut g = Guard {
this: self,
orig_len,
proced_len: 0,
deleted_cnt: 0,
};
g.run::<F, false>(&mut f);
g.run::<F, true>(&mut f);
drop(g);
}
}