1 use super::noop::NoopConsumer;
2 use super::{IntoParallelIterator, ParallelExtend, ParallelIterator};
3
4 use std::borrow::Cow;
5 use std::collections::LinkedList;
6 use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
7 use std::collections::{BinaryHeap, VecDeque};
8 use std::hash::{BuildHasher, Hash};
9
10 /// Performs a generic `par_extend` by collecting to a `LinkedList<Vec<_>>` in
11 /// parallel, then extending the collection sequentially.
extend<C, I, F>(collection: &mut C, par_iter: I, reserve: F) where I: IntoParallelIterator, F: FnOnce(&mut C, &LinkedList<Vec<I::Item>>), C: Extend<I::Item>,12 fn extend<C, I, F>(collection: &mut C, par_iter: I, reserve: F)
13 where
14 I: IntoParallelIterator,
15 F: FnOnce(&mut C, &LinkedList<Vec<I::Item>>),
16 C: Extend<I::Item>,
17 {
18 let list = collect(par_iter);
19 reserve(collection, &list);
20 for vec in list {
21 collection.extend(vec);
22 }
23 }
24
collect<I>(par_iter: I) -> LinkedList<Vec<I::Item>> where I: IntoParallelIterator,25 pub(super) fn collect<I>(par_iter: I) -> LinkedList<Vec<I::Item>>
26 where
27 I: IntoParallelIterator,
28 {
29 par_iter
30 .into_par_iter()
31 .fold(Vec::new, vec_push)
32 .map(as_list)
33 .reduce(LinkedList::new, list_append)
34 }
35
vec_push<T>(mut vec: Vec<T>, elem: T) -> Vec<T>36 fn vec_push<T>(mut vec: Vec<T>, elem: T) -> Vec<T> {
37 vec.push(elem);
38 vec
39 }
40
as_list<T>(item: T) -> LinkedList<T>41 fn as_list<T>(item: T) -> LinkedList<T> {
42 let mut list = LinkedList::new();
43 list.push_back(item);
44 list
45 }
46
list_append<T>(mut list1: LinkedList<T>, mut list2: LinkedList<T>) -> LinkedList<T>47 fn list_append<T>(mut list1: LinkedList<T>, mut list2: LinkedList<T>) -> LinkedList<T> {
48 list1.append(&mut list2);
49 list1
50 }
51
52 /// Computes the total length of a `LinkedList<Vec<_>>`.
len<T>(list: &LinkedList<Vec<T>>) -> usize53 pub(super) fn len<T>(list: &LinkedList<Vec<T>>) -> usize {
54 list.iter().map(Vec::len).sum()
55 }
56
no_reserve<C, T>(_: &mut C, _: &LinkedList<Vec<T>>)57 fn no_reserve<C, T>(_: &mut C, _: &LinkedList<Vec<T>>) {}
58
heap_reserve<T: Ord, U>(heap: &mut BinaryHeap<T>, list: &LinkedList<Vec<U>>)59 fn heap_reserve<T: Ord, U>(heap: &mut BinaryHeap<T>, list: &LinkedList<Vec<U>>) {
60 heap.reserve(len(list));
61 }
62
63 /// Extends a binary heap with items from a parallel iterator.
64 impl<T> ParallelExtend<T> for BinaryHeap<T>
65 where
66 T: Ord + Send,
67 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>,68 fn par_extend<I>(&mut self, par_iter: I)
69 where
70 I: IntoParallelIterator<Item = T>,
71 {
72 extend(self, par_iter, heap_reserve);
73 }
74 }
75
76 /// Extends a binary heap with copied items from a parallel iterator.
77 impl<'a, T> ParallelExtend<&'a T> for BinaryHeap<T>
78 where
79 T: 'a + Copy + Ord + Send + Sync,
80 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,81 fn par_extend<I>(&mut self, par_iter: I)
82 where
83 I: IntoParallelIterator<Item = &'a T>,
84 {
85 extend(self, par_iter, heap_reserve);
86 }
87 }
88
89 /// Extends a B-tree map with items from a parallel iterator.
90 impl<K, V> ParallelExtend<(K, V)> for BTreeMap<K, V>
91 where
92 K: Ord + Send,
93 V: Send,
94 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = (K, V)>,95 fn par_extend<I>(&mut self, par_iter: I)
96 where
97 I: IntoParallelIterator<Item = (K, V)>,
98 {
99 extend(self, par_iter, no_reserve);
100 }
101 }
102
103 /// Extends a B-tree map with copied items from a parallel iterator.
104 impl<'a, K: 'a, V: 'a> ParallelExtend<(&'a K, &'a V)> for BTreeMap<K, V>
105 where
106 K: Copy + Ord + Send + Sync,
107 V: Copy + Send + Sync,
108 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = (&'a K, &'a V)>,109 fn par_extend<I>(&mut self, par_iter: I)
110 where
111 I: IntoParallelIterator<Item = (&'a K, &'a V)>,
112 {
113 extend(self, par_iter, no_reserve);
114 }
115 }
116
117 /// Extends a B-tree set with items from a parallel iterator.
118 impl<T> ParallelExtend<T> for BTreeSet<T>
119 where
120 T: Ord + Send,
121 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>,122 fn par_extend<I>(&mut self, par_iter: I)
123 where
124 I: IntoParallelIterator<Item = T>,
125 {
126 extend(self, par_iter, no_reserve);
127 }
128 }
129
130 /// Extends a B-tree set with copied items from a parallel iterator.
131 impl<'a, T> ParallelExtend<&'a T> for BTreeSet<T>
132 where
133 T: 'a + Copy + Ord + Send + Sync,
134 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,135 fn par_extend<I>(&mut self, par_iter: I)
136 where
137 I: IntoParallelIterator<Item = &'a T>,
138 {
139 extend(self, par_iter, no_reserve);
140 }
141 }
142
map_reserve<K, V, S, U>(map: &mut HashMap<K, V, S>, list: &LinkedList<Vec<U>>) where K: Eq + Hash, S: BuildHasher,143 fn map_reserve<K, V, S, U>(map: &mut HashMap<K, V, S>, list: &LinkedList<Vec<U>>)
144 where
145 K: Eq + Hash,
146 S: BuildHasher,
147 {
148 map.reserve(len(list));
149 }
150
151 /// Extends a hash map with items from a parallel iterator.
152 impl<K, V, S> ParallelExtend<(K, V)> for HashMap<K, V, S>
153 where
154 K: Eq + Hash + Send,
155 V: Send,
156 S: BuildHasher + Send,
157 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = (K, V)>,158 fn par_extend<I>(&mut self, par_iter: I)
159 where
160 I: IntoParallelIterator<Item = (K, V)>,
161 {
162 // See the map_collect benchmarks in rayon-demo for different strategies.
163 extend(self, par_iter, map_reserve);
164 }
165 }
166
167 /// Extends a hash map with copied items from a parallel iterator.
168 impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S>
169 where
170 K: Copy + Eq + Hash + Send + Sync,
171 V: Copy + Send + Sync,
172 S: BuildHasher + Send,
173 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = (&'a K, &'a V)>,174 fn par_extend<I>(&mut self, par_iter: I)
175 where
176 I: IntoParallelIterator<Item = (&'a K, &'a V)>,
177 {
178 extend(self, par_iter, map_reserve);
179 }
180 }
181
set_reserve<T, S, U>(set: &mut HashSet<T, S>, list: &LinkedList<Vec<U>>) where T: Eq + Hash, S: BuildHasher,182 fn set_reserve<T, S, U>(set: &mut HashSet<T, S>, list: &LinkedList<Vec<U>>)
183 where
184 T: Eq + Hash,
185 S: BuildHasher,
186 {
187 set.reserve(len(list));
188 }
189
190 /// Extends a hash set with items from a parallel iterator.
191 impl<T, S> ParallelExtend<T> for HashSet<T, S>
192 where
193 T: Eq + Hash + Send,
194 S: BuildHasher + Send,
195 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>,196 fn par_extend<I>(&mut self, par_iter: I)
197 where
198 I: IntoParallelIterator<Item = T>,
199 {
200 extend(self, par_iter, set_reserve);
201 }
202 }
203
204 /// Extends a hash set with copied items from a parallel iterator.
205 impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S>
206 where
207 T: 'a + Copy + Eq + Hash + Send + Sync,
208 S: BuildHasher + Send,
209 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,210 fn par_extend<I>(&mut self, par_iter: I)
211 where
212 I: IntoParallelIterator<Item = &'a T>,
213 {
214 extend(self, par_iter, set_reserve);
215 }
216 }
217
list_push_back<T>(mut list: LinkedList<T>, elem: T) -> LinkedList<T>218 fn list_push_back<T>(mut list: LinkedList<T>, elem: T) -> LinkedList<T> {
219 list.push_back(elem);
220 list
221 }
222
223 /// Extends a linked list with items from a parallel iterator.
224 impl<T> ParallelExtend<T> for LinkedList<T>
225 where
226 T: Send,
227 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>,228 fn par_extend<I>(&mut self, par_iter: I)
229 where
230 I: IntoParallelIterator<Item = T>,
231 {
232 let mut list = par_iter
233 .into_par_iter()
234 .fold(LinkedList::new, list_push_back)
235 .reduce(LinkedList::new, list_append);
236 self.append(&mut list);
237 }
238 }
239
240 /// Extends a linked list with copied items from a parallel iterator.
241 impl<'a, T> ParallelExtend<&'a T> for LinkedList<T>
242 where
243 T: 'a + Copy + Send + Sync,
244 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,245 fn par_extend<I>(&mut self, par_iter: I)
246 where
247 I: IntoParallelIterator<Item = &'a T>,
248 {
249 self.par_extend(par_iter.into_par_iter().cloned())
250 }
251 }
252
string_push(mut string: String, ch: char) -> String253 fn string_push(mut string: String, ch: char) -> String {
254 string.push(ch);
255 string
256 }
257
258 /// Extends a string with characters from a parallel iterator.
259 impl ParallelExtend<char> for String {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = char>,260 fn par_extend<I>(&mut self, par_iter: I)
261 where
262 I: IntoParallelIterator<Item = char>,
263 {
264 // This is like `extend`, but `Vec<char>` is less efficient to deal
265 // with than `String`, so instead collect to `LinkedList<String>`.
266 let list: LinkedList<_> = par_iter
267 .into_par_iter()
268 .fold(String::new, string_push)
269 .map(as_list)
270 .reduce(LinkedList::new, list_append);
271
272 self.reserve(list.iter().map(String::len).sum());
273 self.extend(list)
274 }
275 }
276
277 /// Extends a string with copied characters from a parallel iterator.
278 impl<'a> ParallelExtend<&'a char> for String {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a char>,279 fn par_extend<I>(&mut self, par_iter: I)
280 where
281 I: IntoParallelIterator<Item = &'a char>,
282 {
283 self.par_extend(par_iter.into_par_iter().cloned())
284 }
285 }
286
string_reserve<T: AsRef<str>>(string: &mut String, list: &LinkedList<Vec<T>>)287 fn string_reserve<T: AsRef<str>>(string: &mut String, list: &LinkedList<Vec<T>>) {
288 let len = list.iter().flatten().map(T::as_ref).map(str::len).sum();
289 string.reserve(len);
290 }
291
292 /// Extends a string with string slices from a parallel iterator.
293 impl<'a> ParallelExtend<&'a str> for String {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a str>,294 fn par_extend<I>(&mut self, par_iter: I)
295 where
296 I: IntoParallelIterator<Item = &'a str>,
297 {
298 extend(self, par_iter, string_reserve);
299 }
300 }
301
302 /// Extends a string with strings from a parallel iterator.
303 impl ParallelExtend<String> for String {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = String>,304 fn par_extend<I>(&mut self, par_iter: I)
305 where
306 I: IntoParallelIterator<Item = String>,
307 {
308 extend(self, par_iter, string_reserve);
309 }
310 }
311
312 /// Extends a string with string slices from a parallel iterator.
313 impl<'a> ParallelExtend<Cow<'a, str>> for String {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = Cow<'a, str>>,314 fn par_extend<I>(&mut self, par_iter: I)
315 where
316 I: IntoParallelIterator<Item = Cow<'a, str>>,
317 {
318 extend(self, par_iter, string_reserve);
319 }
320 }
321
deque_reserve<T, U>(deque: &mut VecDeque<T>, list: &LinkedList<Vec<U>>)322 fn deque_reserve<T, U>(deque: &mut VecDeque<T>, list: &LinkedList<Vec<U>>) {
323 deque.reserve(len(list));
324 }
325
326 /// Extends a deque with items from a parallel iterator.
327 impl<T> ParallelExtend<T> for VecDeque<T>
328 where
329 T: Send,
330 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = T>,331 fn par_extend<I>(&mut self, par_iter: I)
332 where
333 I: IntoParallelIterator<Item = T>,
334 {
335 extend(self, par_iter, deque_reserve);
336 }
337 }
338
339 /// Extends a deque with copied items from a parallel iterator.
340 impl<'a, T> ParallelExtend<&'a T> for VecDeque<T>
341 where
342 T: 'a + Copy + Send + Sync,
343 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,344 fn par_extend<I>(&mut self, par_iter: I)
345 where
346 I: IntoParallelIterator<Item = &'a T>,
347 {
348 extend(self, par_iter, deque_reserve);
349 }
350 }
351
352 // See the `collect` module for the `Vec<T>` implementation.
353 // impl<T> ParallelExtend<T> for Vec<T>
354
355 /// Extends a vector with copied items from a parallel iterator.
356 impl<'a, T> ParallelExtend<&'a T> for Vec<T>
357 where
358 T: 'a + Copy + Send + Sync,
359 {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = &'a T>,360 fn par_extend<I>(&mut self, par_iter: I)
361 where
362 I: IntoParallelIterator<Item = &'a T>,
363 {
364 self.par_extend(par_iter.into_par_iter().cloned())
365 }
366 }
367
368 /// Collapses all unit items from a parallel iterator into one.
369 impl ParallelExtend<()> for () {
par_extend<I>(&mut self, par_iter: I) where I: IntoParallelIterator<Item = ()>,370 fn par_extend<I>(&mut self, par_iter: I)
371 where
372 I: IntoParallelIterator<Item = ()>,
373 {
374 par_iter.into_par_iter().drive_unindexed(NoopConsumer)
375 }
376 }
377