vendor/rustc-rayon/src/iter/extend.rs

   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 /// Perform a generic `par_extend` by collecting to a `LinkedList<Vec<_>>` in
  11 /// parallel, then extending the collection sequentially.
  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
  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
  36 fn vec_push<T>(mut vec: Vec<T>, elem: T) -> Vec<T> {
  37     vec.push(elem);
  38     vec
  39 }
  40
  41 fn as_list<T>(item: T) -> LinkedList<T> {
  42     let mut list = LinkedList::new();
  43     list.push_back(item);
  44     list
  45 }
  46
  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 /// Compute the total length of a `LinkedList<Vec<_>>`.
  53 pub(super) fn len<T>(list: &LinkedList<Vec<T>>) -> usize {
  54     list.iter().map(Vec::len).sum()
  55 }
  56
  57 fn no_reserve<C, T>(_: &mut C, _: &LinkedList<Vec<T>>) {}
  58
  59 fn heap_reserve<T: Ord, U>(heap: &mut BinaryHeap<T>, list: &LinkedList<Vec<U>>) {
  60     heap.reserve(len(list));
  61 }
  62
  63 /// Extend a binary heap with items from a parallel iterator.
  64 impl<T> ParallelExtend<T> for BinaryHeap<T>
  65 where
  66     T: Ord + Send,
  67 {
  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 /// Extend 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 {
  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 /// Extend 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 {
  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 /// Extend 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 {
 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 /// Extend 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 {
 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 /// Extend 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 {
 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
 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 /// Extend 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 {
 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 /// Extend 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 {
 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
 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 /// Extend 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 {
 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 /// Extend 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 {
 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
 218 fn list_push_back<T>(mut list: LinkedList<T>, elem: T) -> LinkedList<T> {
 219     list.push_back(elem);
 220     list
 221 }
 222
 223 /// Extend a linked list with items from a parallel iterator.
 224 impl<T> ParallelExtend<T> for LinkedList<T>
 225 where
 226     T: Send,
 227 {
 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 /// Extend 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 {
 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
 253 fn string_push(mut string: String, ch: char) -> String {
 254     string.push(ch);
 255     string
 256 }
 257
 258 /// Extend a string with characters from a parallel iterator.
 259 impl ParallelExtend<char> for String {
 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 /// Extend a string with copied characters from a parallel iterator.
 278 impl<'a> ParallelExtend<&'a char> for String {
 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
 287 fn string_reserve<T: AsRef<str>>(string: &mut String, list: &LinkedList<Vec<T>>) {
 288     let len = list
 289         .iter()
 290         .flat_map(|vec| vec)
 291         .map(T::as_ref)
 292         .map(str::len)
 293         .sum();
 294     string.reserve(len);
 295 }
 296
 297 /// Extend a string with string slices from a parallel iterator.
 298 impl<'a> ParallelExtend<&'a str> for String {
 299     fn par_extend<I>(&mut self, par_iter: I)
 300     where
 301         I: IntoParallelIterator<Item = &'a str>,
 302     {
 303         extend(self, par_iter, string_reserve);
 304     }
 305 }
 306
 307 /// Extend a string with strings from a parallel iterator.
 308 impl ParallelExtend<String> for String {
 309     fn par_extend<I>(&mut self, par_iter: I)
 310     where
 311         I: IntoParallelIterator<Item = String>,
 312     {
 313         extend(self, par_iter, string_reserve);
 314     }
 315 }
 316
 317 /// Extend a string with string slices from a parallel iterator.
 318 impl<'a> ParallelExtend<Cow<'a, str>> for String {
 319     fn par_extend<I>(&mut self, par_iter: I)
 320     where
 321         I: IntoParallelIterator<Item = Cow<'a, str>>,
 322     {
 323         extend(self, par_iter, string_reserve);
 324     }
 325 }
 326
 327 fn deque_reserve<T, U>(deque: &mut VecDeque<T>, list: &LinkedList<Vec<U>>) {
 328     deque.reserve(len(list));
 329 }
 330
 331 /// Extend a deque with items from a parallel iterator.
 332 impl<T> ParallelExtend<T> for VecDeque<T>
 333 where
 334     T: Send,
 335 {
 336     fn par_extend<I>(&mut self, par_iter: I)
 337     where
 338         I: IntoParallelIterator<Item = T>,
 339     {
 340         extend(self, par_iter, deque_reserve);
 341     }
 342 }
 343
 344 /// Extend a deque with copied items from a parallel iterator.
 345 impl<'a, T> ParallelExtend<&'a T> for VecDeque<T>
 346 where
 347     T: 'a + Copy + Send + Sync,
 348 {
 349     fn par_extend<I>(&mut self, par_iter: I)
 350     where
 351         I: IntoParallelIterator<Item = &'a T>,
 352     {
 353         extend(self, par_iter, deque_reserve);
 354     }
 355 }
 356
 357 // See the `collect` module for the `Vec<T>` implementation.
 358 // impl<T> ParallelExtend<T> for Vec<T>
 359
 360 /// Extend a vector with copied items from a parallel iterator.
 361 impl<'a, T> ParallelExtend<&'a T> for Vec<T>
 362 where
 363     T: 'a + Copy + Send + Sync,
 364 {
 365     fn par_extend<I>(&mut self, par_iter: I)
 366     where
 367         I: IntoParallelIterator<Item = &'a T>,
 368     {
 369         self.par_extend(par_iter.into_par_iter().cloned())
 370     }
 371 }
 372
 373 /// Collapses all unit items from a parallel iterator into one.
 374 impl ParallelExtend<()> for () {
 375     fn par_extend<I>(&mut self, par_iter: I)
 376     where
 377         I: IntoParallelIterator<Item = ()>,
 378     {
 379         par_iter.into_par_iter().drive_unindexed(NoopConsumer)
 380     }
 381 }