]>
Commit | Line | Data |
---|---|---|
0bf4aa26 | 1 | use smallvec::{Array, SmallVec}; |
dfeec247 | 2 | use std::ptr; |
f2b60f7d | 3 | use thin_vec::ThinVec; |
476ff2be | 4 | |
9fa01778 | 5 | pub trait MapInPlace<T>: Sized { |
dfeec247 XL |
6 | fn map_in_place<F>(&mut self, mut f: F) |
7 | where | |
8 | F: FnMut(T) -> T, | |
9 | { | |
9fa01778 | 10 | self.flat_map_in_place(|e| Some(f(e))) |
92a42be0 SL |
11 | } |
12 | ||
9fa01778 | 13 | fn flat_map_in_place<F, I>(&mut self, f: F) |
dfeec247 XL |
14 | where |
15 | F: FnMut(T) -> I, | |
16 | I: IntoIterator<Item = T>; | |
92a42be0 SL |
17 | } |
18 | ||
f2b60f7d FG |
19 | // The implementation of this method is syntactically identical for all the |
20 | // different vector types. | |
21 | macro_rules! flat_map_in_place { | |
22 | () => { | |
23 | fn flat_map_in_place<F, I>(&mut self, mut f: F) | |
24 | where | |
25 | F: FnMut(T) -> I, | |
26 | I: IntoIterator<Item = T>, | |
27 | { | |
28 | let mut read_i = 0; | |
29 | let mut write_i = 0; | |
30 | unsafe { | |
31 | let mut old_len = self.len(); | |
32 | self.set_len(0); // make sure we just leak elements in case of panic | |
92a42be0 | 33 | |
f2b60f7d FG |
34 | while read_i < old_len { |
35 | // move the read_i'th item out of the vector and map it | |
36 | // to an iterator | |
37 | let e = ptr::read(self.as_ptr().add(read_i)); | |
38 | let iter = f(e).into_iter(); | |
39 | read_i += 1; | |
92a42be0 | 40 | |
f2b60f7d FG |
41 | for e in iter { |
42 | if write_i < read_i { | |
43 | ptr::write(self.as_mut_ptr().add(write_i), e); | |
44 | write_i += 1; | |
45 | } else { | |
46 | // If this is reached we ran out of space | |
47 | // in the middle of the vector. | |
48 | // However, the vector is in a valid state here, | |
49 | // so we just do a somewhat inefficient insert. | |
50 | self.set_len(old_len); | |
51 | self.insert(write_i, e); | |
92a42be0 | 52 | |
f2b60f7d FG |
53 | old_len = self.len(); |
54 | self.set_len(0); | |
92a42be0 | 55 | |
f2b60f7d FG |
56 | read_i += 1; |
57 | write_i += 1; | |
58 | } | |
92a42be0 SL |
59 | } |
60 | } | |
92a42be0 | 61 | |
f2b60f7d FG |
62 | // write_i tracks the number of actually written new items. |
63 | self.set_len(write_i); | |
64 | } | |
92a42be0 | 65 | } |
f2b60f7d | 66 | }; |
92a42be0 | 67 | } |
476ff2be | 68 | |
f2b60f7d FG |
69 | impl<T> MapInPlace<T> for Vec<T> { |
70 | flat_map_in_place!(); | |
71 | } | |
476ff2be | 72 | |
f2b60f7d FG |
73 | impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> { |
74 | flat_map_in_place!(); | |
75 | } | |
476ff2be | 76 | |
f2b60f7d FG |
77 | impl<T> MapInPlace<T> for ThinVec<T> { |
78 | flat_map_in_place!(); | |
476ff2be | 79 | } |