1 //! Parallel iterator types for [slices][std::slice] 2 //! 3 //! You will rarely need to interact with this module directly unless you need 4 //! to name one of the iterator types. 5 //! 6 //! [std::slice]: https://doc.rust-lang.org/stable/std/slice/ 7 8 mod mergesort; 9 mod quicksort; 10 11 mod test; 12 13 use self::mergesort::par_mergesort; 14 use self::quicksort::par_quicksort; 15 use crate::iter::plumbing::*; 16 use crate::iter::*; 17 use crate::split_producer::*; 18 use std::cmp; 19 use std::cmp::Ordering; 20 use std::fmt::{self, Debug}; 21 22 use super::math::div_round_up; 23 24 /// Parallel extensions for slices. 25 pub trait ParallelSlice<T: Sync> { 26 /// Returns a plain slice, which is used to implement the rest of the 27 /// parallel methods. as_parallel_slice(&self) -> &[T]28 fn as_parallel_slice(&self) -> &[T]; 29 30 /// Returns a parallel iterator over subslices separated by elements that 31 /// match the separator. 32 /// 33 /// # Examples 34 /// 35 /// ``` 36 /// use rayon::prelude::*; 37 /// let smallest = [1, 2, 3, 0, 2, 4, 8, 0, 3, 6, 9] 38 /// .par_split(|i| *i == 0) 39 /// .map(|numbers| numbers.iter().min().unwrap()) 40 /// .min(); 41 /// assert_eq!(Some(&1), smallest); 42 /// ``` par_split<P>(&self, separator: P) -> Split<'_, T, P> where P: Fn(&T) -> bool + Sync + Send,43 fn par_split<P>(&self, separator: P) -> Split<'_, T, P> 44 where 45 P: Fn(&T) -> bool + Sync + Send, 46 { 47 Split { 48 slice: self.as_parallel_slice(), 49 separator, 50 } 51 } 52 53 /// Returns a parallel iterator over all contiguous windows of length 54 /// `window_size`. The windows overlap. 55 /// 56 /// # Examples 57 /// 58 /// ``` 59 /// use rayon::prelude::*; 60 /// let windows: Vec<_> = [1, 2, 3].par_windows(2).collect(); 61 /// assert_eq!(vec![[1, 2], [2, 3]], windows); 62 /// ``` par_windows(&self, window_size: usize) -> Windows<'_, T>63 fn par_windows(&self, window_size: usize) -> Windows<'_, T> { 64 Windows { 65 window_size, 66 slice: self.as_parallel_slice(), 67 } 68 } 69 70 /// Returns a parallel iterator over at most `chunk_size` elements of 71 /// `self` at a time. The chunks do not overlap. 72 /// 73 /// If the number of elements in the iterator is not divisible by 74 /// `chunk_size`, the last chunk may be shorter than `chunk_size`. All 75 /// other chunks will have that exact length. 76 /// 77 /// # Examples 78 /// 79 /// ``` 80 /// use rayon::prelude::*; 81 /// let chunks: Vec<_> = [1, 2, 3, 4, 5].par_chunks(2).collect(); 82 /// assert_eq!(chunks, vec![&[1, 2][..], &[3, 4], &[5]]); 83 /// ``` par_chunks(&self, chunk_size: usize) -> Chunks<'_, T>84 fn par_chunks(&self, chunk_size: usize) -> Chunks<'_, T> { 85 assert!(chunk_size != 0, "chunk_size must not be zero"); 86 Chunks { 87 chunk_size, 88 slice: self.as_parallel_slice(), 89 } 90 } 91 92 /// Returns a parallel iterator over `chunk_size` elements of 93 /// `self` at a time. The chunks do not overlap. 94 /// 95 /// If `chunk_size` does not divide the length of the slice, then the 96 /// last up to `chunk_size-1` elements will be omitted and can be 97 /// retrieved from the remainder function of the iterator. 98 /// 99 /// # Examples 100 /// 101 /// ``` 102 /// use rayon::prelude::*; 103 /// let chunks: Vec<_> = [1, 2, 3, 4, 5].par_chunks_exact(2).collect(); 104 /// assert_eq!(chunks, vec![&[1, 2][..], &[3, 4]]); 105 /// ``` par_chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T>106 fn par_chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> { 107 assert!(chunk_size != 0, "chunk_size must not be zero"); 108 let slice = self.as_parallel_slice(); 109 let rem = slice.len() % chunk_size; 110 let len = slice.len() - rem; 111 let (fst, snd) = slice.split_at(len); 112 ChunksExact { 113 chunk_size, 114 slice: fst, 115 rem: snd, 116 } 117 } 118 } 119 120 impl<T: Sync> ParallelSlice<T> for [T] { 121 #[inline] as_parallel_slice(&self) -> &[T]122 fn as_parallel_slice(&self) -> &[T] { 123 self 124 } 125 } 126 127 /// Parallel extensions for mutable slices. 128 pub trait ParallelSliceMut<T: Send> { 129 /// Returns a plain mutable slice, which is used to implement the rest of 130 /// the parallel methods. as_parallel_slice_mut(&mut self) -> &mut [T]131 fn as_parallel_slice_mut(&mut self) -> &mut [T]; 132 133 /// Returns a parallel iterator over mutable subslices separated by 134 /// elements that match the separator. 135 /// 136 /// # Examples 137 /// 138 /// ``` 139 /// use rayon::prelude::*; 140 /// let mut array = [1, 2, 3, 0, 2, 4, 8, 0, 3, 6, 9]; 141 /// array.par_split_mut(|i| *i == 0) 142 /// .for_each(|slice| slice.reverse()); 143 /// assert_eq!(array, [3, 2, 1, 0, 8, 4, 2, 0, 9, 6, 3]); 144 /// ``` par_split_mut<P>(&mut self, separator: P) -> SplitMut<'_, T, P> where P: Fn(&T) -> bool + Sync + Send,145 fn par_split_mut<P>(&mut self, separator: P) -> SplitMut<'_, T, P> 146 where 147 P: Fn(&T) -> bool + Sync + Send, 148 { 149 SplitMut { 150 slice: self.as_parallel_slice_mut(), 151 separator, 152 } 153 } 154 155 /// Returns a parallel iterator over at most `chunk_size` elements of 156 /// `self` at a time. The chunks are mutable and do not overlap. 157 /// 158 /// If the number of elements in the iterator is not divisible by 159 /// `chunk_size`, the last chunk may be shorter than `chunk_size`. All 160 /// other chunks will have that exact length. 161 /// 162 /// # Examples 163 /// 164 /// ``` 165 /// use rayon::prelude::*; 166 /// let mut array = [1, 2, 3, 4, 5]; 167 /// array.par_chunks_mut(2) 168 /// .for_each(|slice| slice.reverse()); 169 /// assert_eq!(array, [2, 1, 4, 3, 5]); 170 /// ``` par_chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T>171 fn par_chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> { 172 assert!(chunk_size != 0, "chunk_size must not be zero"); 173 ChunksMut { 174 chunk_size, 175 slice: self.as_parallel_slice_mut(), 176 } 177 } 178 179 /// Returns a parallel iterator over `chunk_size` elements of 180 /// `self` at a time. The chunks are mutable and do not overlap. 181 /// 182 /// If `chunk_size` does not divide the length of the slice, then the 183 /// last up to `chunk_size-1` elements will be omitted and can be 184 /// retrieved from the remainder function of the iterator. 185 /// 186 /// # Examples 187 /// 188 /// ``` 189 /// use rayon::prelude::*; 190 /// let mut array = [1, 2, 3, 4, 5]; 191 /// array.par_chunks_exact_mut(3) 192 /// .for_each(|slice| slice.reverse()); 193 /// assert_eq!(array, [3, 2, 1, 4, 5]); 194 /// ``` par_chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T>195 fn par_chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> { 196 assert!(chunk_size != 0, "chunk_size must not be zero"); 197 let slice = self.as_parallel_slice_mut(); 198 let rem = slice.len() % chunk_size; 199 let len = slice.len() - rem; 200 let (fst, snd) = slice.split_at_mut(len); 201 ChunksExactMut { 202 chunk_size, 203 slice: fst, 204 rem: snd, 205 } 206 } 207 208 /// Sorts the slice in parallel. 209 /// 210 /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case. 211 /// 212 /// When applicable, unstable sorting is preferred because it is generally faster than stable 213 /// sorting and it doesn't allocate auxiliary memory. 214 /// See [`par_sort_unstable`](#method.par_sort_unstable). 215 /// 216 /// # Current implementation 217 /// 218 /// The current algorithm is an adaptive merge sort inspired by 219 /// [timsort](https://en.wikipedia.org/wiki/Timsort). 220 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of 221 /// two or more sorted sequences concatenated one after another. 222 /// 223 /// Also, it allocates temporary storage the same size as `self`, but for very short slices a 224 /// non-allocating insertion sort is used instead. 225 /// 226 /// In order to sort the slice in parallel, the slice is first divided into smaller chunks and 227 /// all chunks are sorted in parallel. Then, adjacent chunks that together form non-descending 228 /// or descending runs are concatenated. Finally, the remaining chunks are merged together using 229 /// parallel subdivision of chunks and parallel merge operation. 230 /// 231 /// # Examples 232 /// 233 /// ``` 234 /// use rayon::prelude::*; 235 /// 236 /// let mut v = [-5, 4, 1, -3, 2]; 237 /// 238 /// v.par_sort(); 239 /// assert_eq!(v, [-5, -3, 1, 2, 4]); 240 /// ``` par_sort(&mut self) where T: Ord,241 fn par_sort(&mut self) 242 where 243 T: Ord, 244 { 245 par_mergesort(self.as_parallel_slice_mut(), T::lt); 246 } 247 248 /// Sorts the slice in parallel with a comparator function. 249 /// 250 /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case. 251 /// 252 /// When applicable, unstable sorting is preferred because it is generally faster than stable 253 /// sorting and it doesn't allocate auxiliary memory. 254 /// See [`par_sort_unstable_by`](#method.par_sort_unstable_by). 255 /// 256 /// # Current implementation 257 /// 258 /// The current algorithm is an adaptive merge sort inspired by 259 /// [timsort](https://en.wikipedia.org/wiki/Timsort). 260 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of 261 /// two or more sorted sequences concatenated one after another. 262 /// 263 /// Also, it allocates temporary storage the same size as `self`, but for very short slices a 264 /// non-allocating insertion sort is used instead. 265 /// 266 /// In order to sort the slice in parallel, the slice is first divided into smaller chunks and 267 /// all chunks are sorted in parallel. Then, adjacent chunks that together form non-descending 268 /// or descending runs are concatenated. Finally, the remaining chunks are merged together using 269 /// parallel subdivision of chunks and parallel merge operation. 270 /// 271 /// # Examples 272 /// 273 /// ``` 274 /// use rayon::prelude::*; 275 /// 276 /// let mut v = [5, 4, 1, 3, 2]; 277 /// v.par_sort_by(|a, b| a.cmp(b)); 278 /// assert_eq!(v, [1, 2, 3, 4, 5]); 279 /// 280 /// // reverse sorting 281 /// v.par_sort_by(|a, b| b.cmp(a)); 282 /// assert_eq!(v, [5, 4, 3, 2, 1]); 283 /// ``` par_sort_by<F>(&mut self, compare: F) where F: Fn(&T, &T) -> Ordering + Sync,284 fn par_sort_by<F>(&mut self, compare: F) 285 where 286 F: Fn(&T, &T) -> Ordering + Sync, 287 { 288 par_mergesort(self.as_parallel_slice_mut(), |a, b| { 289 compare(a, b) == Ordering::Less 290 }); 291 } 292 293 /// Sorts the slice in parallel with a key extraction function. 294 /// 295 /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case. 296 /// 297 /// When applicable, unstable sorting is preferred because it is generally faster than stable 298 /// sorting and it doesn't allocate auxiliary memory. 299 /// See [`par_sort_unstable_by_key`](#method.par_sort_unstable_by_key). 300 /// 301 /// # Current implementation 302 /// 303 /// The current algorithm is an adaptive merge sort inspired by 304 /// [timsort](https://en.wikipedia.org/wiki/Timsort). 305 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of 306 /// two or more sorted sequences concatenated one after another. 307 /// 308 /// Also, it allocates temporary storage the same size as `self`, but for very short slices a 309 /// non-allocating insertion sort is used instead. 310 /// 311 /// In order to sort the slice in parallel, the slice is first divided into smaller chunks and 312 /// all chunks are sorted in parallel. Then, adjacent chunks that together form non-descending 313 /// or descending runs are concatenated. Finally, the remaining chunks are merged together using 314 /// parallel subdivision of chunks and parallel merge operation. 315 /// 316 /// # Examples 317 /// 318 /// ``` 319 /// use rayon::prelude::*; 320 /// 321 /// let mut v = [-5i32, 4, 1, -3, 2]; 322 /// 323 /// v.par_sort_by_key(|k| k.abs()); 324 /// assert_eq!(v, [1, 2, -3, 4, -5]); 325 /// ``` par_sort_by_key<B, F>(&mut self, f: F) where B: Ord, F: Fn(&T) -> B + Sync,326 fn par_sort_by_key<B, F>(&mut self, f: F) 327 where 328 B: Ord, 329 F: Fn(&T) -> B + Sync, 330 { 331 par_mergesort(self.as_parallel_slice_mut(), |a, b| f(a).lt(&f(b))); 332 } 333 334 /// Sorts the slice in parallel, but may not preserve the order of equal elements. 335 /// 336 /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate), 337 /// and `O(n log n)` worst-case. 338 /// 339 /// # Current implementation 340 /// 341 /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort], 342 /// which is a quicksort variant designed to be very fast on certain kinds of patterns, 343 /// sometimes achieving linear time. It is randomized but deterministic, and falls back to 344 /// heapsort on degenerate inputs. 345 /// 346 /// It is generally faster than stable sorting, except in a few special cases, e.g. when the 347 /// slice consists of several concatenated sorted sequences. 348 /// 349 /// All quicksorts work in two stages: partitioning into two halves followed by recursive 350 /// calls. The partitioning phase is sequential, but the two recursive calls are performed in 351 /// parallel. 352 /// 353 /// [pdqsort]: https://github.com/orlp/pdqsort 354 /// 355 /// # Examples 356 /// 357 /// ``` 358 /// use rayon::prelude::*; 359 /// 360 /// let mut v = [-5, 4, 1, -3, 2]; 361 /// 362 /// v.par_sort_unstable(); 363 /// assert_eq!(v, [-5, -3, 1, 2, 4]); 364 /// ``` par_sort_unstable(&mut self) where T: Ord,365 fn par_sort_unstable(&mut self) 366 where 367 T: Ord, 368 { 369 par_quicksort(self.as_parallel_slice_mut(), T::lt); 370 } 371 372 /// Sorts the slice in parallel with a comparator function, but may not preserve the order of 373 /// equal elements. 374 /// 375 /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate), 376 /// and `O(n log n)` worst-case. 377 /// 378 /// # Current implementation 379 /// 380 /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort], 381 /// which is a quicksort variant designed to be very fast on certain kinds of patterns, 382 /// sometimes achieving linear time. It is randomized but deterministic, and falls back to 383 /// heapsort on degenerate inputs. 384 /// 385 /// It is generally faster than stable sorting, except in a few special cases, e.g. when the 386 /// slice consists of several concatenated sorted sequences. 387 /// 388 /// All quicksorts work in two stages: partitioning into two halves followed by recursive 389 /// calls. The partitioning phase is sequential, but the two recursive calls are performed in 390 /// parallel. 391 /// 392 /// [pdqsort]: https://github.com/orlp/pdqsort 393 /// 394 /// # Examples 395 /// 396 /// ``` 397 /// use rayon::prelude::*; 398 /// 399 /// let mut v = [5, 4, 1, 3, 2]; 400 /// v.par_sort_unstable_by(|a, b| a.cmp(b)); 401 /// assert_eq!(v, [1, 2, 3, 4, 5]); 402 /// 403 /// // reverse sorting 404 /// v.par_sort_unstable_by(|a, b| b.cmp(a)); 405 /// assert_eq!(v, [5, 4, 3, 2, 1]); 406 /// ``` par_sort_unstable_by<F>(&mut self, compare: F) where F: Fn(&T, &T) -> Ordering + Sync,407 fn par_sort_unstable_by<F>(&mut self, compare: F) 408 where 409 F: Fn(&T, &T) -> Ordering + Sync, 410 { 411 par_quicksort(self.as_parallel_slice_mut(), |a, b| { 412 compare(a, b) == Ordering::Less 413 }); 414 } 415 416 /// Sorts the slice in parallel with a key extraction function, but may not preserve the order 417 /// of equal elements. 418 /// 419 /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate), 420 /// and `O(n log n)` worst-case. 421 /// 422 /// # Current implementation 423 /// 424 /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort], 425 /// which is a quicksort variant designed to be very fast on certain kinds of patterns, 426 /// sometimes achieving linear time. It is randomized but deterministic, and falls back to 427 /// heapsort on degenerate inputs. 428 /// 429 /// It is generally faster than stable sorting, except in a few special cases, e.g. when the 430 /// slice consists of several concatenated sorted sequences. 431 /// 432 /// All quicksorts work in two stages: partitioning into two halves followed by recursive 433 /// calls. The partitioning phase is sequential, but the two recursive calls are performed in 434 /// parallel. 435 /// 436 /// [pdqsort]: https://github.com/orlp/pdqsort 437 /// 438 /// # Examples 439 /// 440 /// ``` 441 /// use rayon::prelude::*; 442 /// 443 /// let mut v = [-5i32, 4, 1, -3, 2]; 444 /// 445 /// v.par_sort_unstable_by_key(|k| k.abs()); 446 /// assert_eq!(v, [1, 2, -3, 4, -5]); 447 /// ``` par_sort_unstable_by_key<B, F>(&mut self, f: F) where B: Ord, F: Fn(&T) -> B + Sync,448 fn par_sort_unstable_by_key<B, F>(&mut self, f: F) 449 where 450 B: Ord, 451 F: Fn(&T) -> B + Sync, 452 { 453 par_quicksort(self.as_parallel_slice_mut(), |a, b| f(a).lt(&f(b))); 454 } 455 } 456 457 impl<T: Send> ParallelSliceMut<T> for [T] { 458 #[inline] as_parallel_slice_mut(&mut self) -> &mut [T]459 fn as_parallel_slice_mut(&mut self) -> &mut [T] { 460 self 461 } 462 } 463 464 impl<'data, T: Sync + 'data> IntoParallelIterator for &'data [T] { 465 type Item = &'data T; 466 type Iter = Iter<'data, T>; 467 into_par_iter(self) -> Self::Iter468 fn into_par_iter(self) -> Self::Iter { 469 Iter { slice: self } 470 } 471 } 472 473 impl<'data, T: Send + 'data> IntoParallelIterator for &'data mut [T] { 474 type Item = &'data mut T; 475 type Iter = IterMut<'data, T>; 476 into_par_iter(self) -> Self::Iter477 fn into_par_iter(self) -> Self::Iter { 478 IterMut { slice: self } 479 } 480 } 481 482 /// Parallel iterator over immutable items in a slice 483 #[derive(Debug)] 484 pub struct Iter<'data, T: Sync> { 485 slice: &'data [T], 486 } 487 488 impl<'data, T: Sync> Clone for Iter<'data, T> { clone(&self) -> Self489 fn clone(&self) -> Self { 490 Iter { ..*self } 491 } 492 } 493 494 impl<'data, T: Sync + 'data> ParallelIterator for Iter<'data, T> { 495 type Item = &'data T; 496 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,497 fn drive_unindexed<C>(self, consumer: C) -> C::Result 498 where 499 C: UnindexedConsumer<Self::Item>, 500 { 501 bridge(self, consumer) 502 } 503 opt_len(&self) -> Option<usize>504 fn opt_len(&self) -> Option<usize> { 505 Some(self.len()) 506 } 507 } 508 509 impl<'data, T: Sync + 'data> IndexedParallelIterator for Iter<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,510 fn drive<C>(self, consumer: C) -> C::Result 511 where 512 C: Consumer<Self::Item>, 513 { 514 bridge(self, consumer) 515 } 516 len(&self) -> usize517 fn len(&self) -> usize { 518 self.slice.len() 519 } 520 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,521 fn with_producer<CB>(self, callback: CB) -> CB::Output 522 where 523 CB: ProducerCallback<Self::Item>, 524 { 525 callback.callback(IterProducer { slice: self.slice }) 526 } 527 } 528 529 struct IterProducer<'data, T: Sync> { 530 slice: &'data [T], 531 } 532 533 impl<'data, T: 'data + Sync> Producer for IterProducer<'data, T> { 534 type Item = &'data T; 535 type IntoIter = ::std::slice::Iter<'data, T>; 536 into_iter(self) -> Self::IntoIter537 fn into_iter(self) -> Self::IntoIter { 538 self.slice.iter() 539 } 540 split_at(self, index: usize) -> (Self, Self)541 fn split_at(self, index: usize) -> (Self, Self) { 542 let (left, right) = self.slice.split_at(index); 543 (IterProducer { slice: left }, IterProducer { slice: right }) 544 } 545 } 546 547 /// Parallel iterator over immutable non-overlapping chunks of a slice 548 #[derive(Debug)] 549 pub struct Chunks<'data, T: Sync> { 550 chunk_size: usize, 551 slice: &'data [T], 552 } 553 554 impl<'data, T: Sync> Clone for Chunks<'data, T> { clone(&self) -> Self555 fn clone(&self) -> Self { 556 Chunks { ..*self } 557 } 558 } 559 560 impl<'data, T: Sync + 'data> ParallelIterator for Chunks<'data, T> { 561 type Item = &'data [T]; 562 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,563 fn drive_unindexed<C>(self, consumer: C) -> C::Result 564 where 565 C: UnindexedConsumer<Self::Item>, 566 { 567 bridge(self, consumer) 568 } 569 opt_len(&self) -> Option<usize>570 fn opt_len(&self) -> Option<usize> { 571 Some(self.len()) 572 } 573 } 574 575 impl<'data, T: Sync + 'data> IndexedParallelIterator for Chunks<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,576 fn drive<C>(self, consumer: C) -> C::Result 577 where 578 C: Consumer<Self::Item>, 579 { 580 bridge(self, consumer) 581 } 582 len(&self) -> usize583 fn len(&self) -> usize { 584 div_round_up(self.slice.len(), self.chunk_size) 585 } 586 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,587 fn with_producer<CB>(self, callback: CB) -> CB::Output 588 where 589 CB: ProducerCallback<Self::Item>, 590 { 591 callback.callback(ChunksProducer { 592 chunk_size: self.chunk_size, 593 slice: self.slice, 594 }) 595 } 596 } 597 598 struct ChunksProducer<'data, T: Sync> { 599 chunk_size: usize, 600 slice: &'data [T], 601 } 602 603 impl<'data, T: 'data + Sync> Producer for ChunksProducer<'data, T> { 604 type Item = &'data [T]; 605 type IntoIter = ::std::slice::Chunks<'data, T>; 606 into_iter(self) -> Self::IntoIter607 fn into_iter(self) -> Self::IntoIter { 608 self.slice.chunks(self.chunk_size) 609 } 610 split_at(self, index: usize) -> (Self, Self)611 fn split_at(self, index: usize) -> (Self, Self) { 612 let elem_index = cmp::min(index * self.chunk_size, self.slice.len()); 613 let (left, right) = self.slice.split_at(elem_index); 614 ( 615 ChunksProducer { 616 chunk_size: self.chunk_size, 617 slice: left, 618 }, 619 ChunksProducer { 620 chunk_size: self.chunk_size, 621 slice: right, 622 }, 623 ) 624 } 625 } 626 627 /// Parallel iterator over immutable non-overlapping chunks of a slice 628 #[derive(Debug)] 629 pub struct ChunksExact<'data, T: Sync> { 630 chunk_size: usize, 631 slice: &'data [T], 632 rem: &'data [T], 633 } 634 635 impl<'data, T: Sync> ChunksExact<'data, T> { 636 /// Return the remainder of the original slice that is not going to be 637 /// returned by the iterator. The returned slice has at most `chunk_size-1` 638 /// elements. remainder(&self) -> &'data [T]639 pub fn remainder(&self) -> &'data [T] { 640 self.rem 641 } 642 } 643 644 impl<'data, T: Sync> Clone for ChunksExact<'data, T> { clone(&self) -> Self645 fn clone(&self) -> Self { 646 ChunksExact { ..*self } 647 } 648 } 649 650 impl<'data, T: Sync + 'data> ParallelIterator for ChunksExact<'data, T> { 651 type Item = &'data [T]; 652 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,653 fn drive_unindexed<C>(self, consumer: C) -> C::Result 654 where 655 C: UnindexedConsumer<Self::Item>, 656 { 657 bridge(self, consumer) 658 } 659 opt_len(&self) -> Option<usize>660 fn opt_len(&self) -> Option<usize> { 661 Some(self.len()) 662 } 663 } 664 665 impl<'data, T: Sync + 'data> IndexedParallelIterator for ChunksExact<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,666 fn drive<C>(self, consumer: C) -> C::Result 667 where 668 C: Consumer<Self::Item>, 669 { 670 bridge(self, consumer) 671 } 672 len(&self) -> usize673 fn len(&self) -> usize { 674 self.slice.len() / self.chunk_size 675 } 676 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,677 fn with_producer<CB>(self, callback: CB) -> CB::Output 678 where 679 CB: ProducerCallback<Self::Item>, 680 { 681 callback.callback(ChunksExactProducer { 682 chunk_size: self.chunk_size, 683 slice: self.slice, 684 }) 685 } 686 } 687 688 struct ChunksExactProducer<'data, T: Sync> { 689 chunk_size: usize, 690 slice: &'data [T], 691 } 692 693 impl<'data, T: 'data + Sync> Producer for ChunksExactProducer<'data, T> { 694 type Item = &'data [T]; 695 type IntoIter = ::std::slice::ChunksExact<'data, T>; 696 into_iter(self) -> Self::IntoIter697 fn into_iter(self) -> Self::IntoIter { 698 self.slice.chunks_exact(self.chunk_size) 699 } 700 split_at(self, index: usize) -> (Self, Self)701 fn split_at(self, index: usize) -> (Self, Self) { 702 let elem_index = index * self.chunk_size; 703 let (left, right) = self.slice.split_at(elem_index); 704 ( 705 ChunksExactProducer { 706 chunk_size: self.chunk_size, 707 slice: left, 708 }, 709 ChunksExactProducer { 710 chunk_size: self.chunk_size, 711 slice: right, 712 }, 713 ) 714 } 715 } 716 717 /// Parallel iterator over immutable overlapping windows of a slice 718 #[derive(Debug)] 719 pub struct Windows<'data, T: Sync> { 720 window_size: usize, 721 slice: &'data [T], 722 } 723 724 impl<'data, T: Sync> Clone for Windows<'data, T> { clone(&self) -> Self725 fn clone(&self) -> Self { 726 Windows { ..*self } 727 } 728 } 729 730 impl<'data, T: Sync + 'data> ParallelIterator for Windows<'data, T> { 731 type Item = &'data [T]; 732 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,733 fn drive_unindexed<C>(self, consumer: C) -> C::Result 734 where 735 C: UnindexedConsumer<Self::Item>, 736 { 737 bridge(self, consumer) 738 } 739 opt_len(&self) -> Option<usize>740 fn opt_len(&self) -> Option<usize> { 741 Some(self.len()) 742 } 743 } 744 745 impl<'data, T: Sync + 'data> IndexedParallelIterator for Windows<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,746 fn drive<C>(self, consumer: C) -> C::Result 747 where 748 C: Consumer<Self::Item>, 749 { 750 bridge(self, consumer) 751 } 752 len(&self) -> usize753 fn len(&self) -> usize { 754 assert!(self.window_size >= 1); 755 self.slice.len().saturating_sub(self.window_size - 1) 756 } 757 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,758 fn with_producer<CB>(self, callback: CB) -> CB::Output 759 where 760 CB: ProducerCallback<Self::Item>, 761 { 762 callback.callback(WindowsProducer { 763 window_size: self.window_size, 764 slice: self.slice, 765 }) 766 } 767 } 768 769 struct WindowsProducer<'data, T: Sync> { 770 window_size: usize, 771 slice: &'data [T], 772 } 773 774 impl<'data, T: 'data + Sync> Producer for WindowsProducer<'data, T> { 775 type Item = &'data [T]; 776 type IntoIter = ::std::slice::Windows<'data, T>; 777 into_iter(self) -> Self::IntoIter778 fn into_iter(self) -> Self::IntoIter { 779 self.slice.windows(self.window_size) 780 } 781 split_at(self, index: usize) -> (Self, Self)782 fn split_at(self, index: usize) -> (Self, Self) { 783 let left_index = cmp::min(self.slice.len(), index + (self.window_size - 1)); 784 let left = &self.slice[..left_index]; 785 let right = &self.slice[index..]; 786 ( 787 WindowsProducer { 788 window_size: self.window_size, 789 slice: left, 790 }, 791 WindowsProducer { 792 window_size: self.window_size, 793 slice: right, 794 }, 795 ) 796 } 797 } 798 799 /// Parallel iterator over mutable items in a slice 800 #[derive(Debug)] 801 pub struct IterMut<'data, T: Send> { 802 slice: &'data mut [T], 803 } 804 805 impl<'data, T: Send + 'data> ParallelIterator for IterMut<'data, T> { 806 type Item = &'data mut T; 807 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,808 fn drive_unindexed<C>(self, consumer: C) -> C::Result 809 where 810 C: UnindexedConsumer<Self::Item>, 811 { 812 bridge(self, consumer) 813 } 814 opt_len(&self) -> Option<usize>815 fn opt_len(&self) -> Option<usize> { 816 Some(self.len()) 817 } 818 } 819 820 impl<'data, T: Send + 'data> IndexedParallelIterator for IterMut<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,821 fn drive<C>(self, consumer: C) -> C::Result 822 where 823 C: Consumer<Self::Item>, 824 { 825 bridge(self, consumer) 826 } 827 len(&self) -> usize828 fn len(&self) -> usize { 829 self.slice.len() 830 } 831 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,832 fn with_producer<CB>(self, callback: CB) -> CB::Output 833 where 834 CB: ProducerCallback<Self::Item>, 835 { 836 callback.callback(IterMutProducer { slice: self.slice }) 837 } 838 } 839 840 struct IterMutProducer<'data, T: Send> { 841 slice: &'data mut [T], 842 } 843 844 impl<'data, T: 'data + Send> Producer for IterMutProducer<'data, T> { 845 type Item = &'data mut T; 846 type IntoIter = ::std::slice::IterMut<'data, T>; 847 into_iter(self) -> Self::IntoIter848 fn into_iter(self) -> Self::IntoIter { 849 self.slice.iter_mut() 850 } 851 split_at(self, index: usize) -> (Self, Self)852 fn split_at(self, index: usize) -> (Self, Self) { 853 let (left, right) = self.slice.split_at_mut(index); 854 ( 855 IterMutProducer { slice: left }, 856 IterMutProducer { slice: right }, 857 ) 858 } 859 } 860 861 /// Parallel iterator over mutable non-overlapping chunks of a slice 862 #[derive(Debug)] 863 pub struct ChunksMut<'data, T: Send> { 864 chunk_size: usize, 865 slice: &'data mut [T], 866 } 867 868 impl<'data, T: Send + 'data> ParallelIterator for ChunksMut<'data, T> { 869 type Item = &'data mut [T]; 870 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,871 fn drive_unindexed<C>(self, consumer: C) -> C::Result 872 where 873 C: UnindexedConsumer<Self::Item>, 874 { 875 bridge(self, consumer) 876 } 877 opt_len(&self) -> Option<usize>878 fn opt_len(&self) -> Option<usize> { 879 Some(self.len()) 880 } 881 } 882 883 impl<'data, T: Send + 'data> IndexedParallelIterator for ChunksMut<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,884 fn drive<C>(self, consumer: C) -> C::Result 885 where 886 C: Consumer<Self::Item>, 887 { 888 bridge(self, consumer) 889 } 890 len(&self) -> usize891 fn len(&self) -> usize { 892 div_round_up(self.slice.len(), self.chunk_size) 893 } 894 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,895 fn with_producer<CB>(self, callback: CB) -> CB::Output 896 where 897 CB: ProducerCallback<Self::Item>, 898 { 899 callback.callback(ChunksMutProducer { 900 chunk_size: self.chunk_size, 901 slice: self.slice, 902 }) 903 } 904 } 905 906 struct ChunksMutProducer<'data, T: Send> { 907 chunk_size: usize, 908 slice: &'data mut [T], 909 } 910 911 impl<'data, T: 'data + Send> Producer for ChunksMutProducer<'data, T> { 912 type Item = &'data mut [T]; 913 type IntoIter = ::std::slice::ChunksMut<'data, T>; 914 into_iter(self) -> Self::IntoIter915 fn into_iter(self) -> Self::IntoIter { 916 self.slice.chunks_mut(self.chunk_size) 917 } 918 split_at(self, index: usize) -> (Self, Self)919 fn split_at(self, index: usize) -> (Self, Self) { 920 let elem_index = cmp::min(index * self.chunk_size, self.slice.len()); 921 let (left, right) = self.slice.split_at_mut(elem_index); 922 ( 923 ChunksMutProducer { 924 chunk_size: self.chunk_size, 925 slice: left, 926 }, 927 ChunksMutProducer { 928 chunk_size: self.chunk_size, 929 slice: right, 930 }, 931 ) 932 } 933 } 934 935 /// Parallel iterator over mutable non-overlapping chunks of a slice 936 #[derive(Debug)] 937 pub struct ChunksExactMut<'data, T: Send> { 938 chunk_size: usize, 939 slice: &'data mut [T], 940 rem: &'data mut [T], 941 } 942 943 impl<'data, T: Send> ChunksExactMut<'data, T> { 944 /// Return the remainder of the original slice that is not going to be 945 /// returned by the iterator. The returned slice has at most `chunk_size-1` 946 /// elements. 947 /// 948 /// Note that this has to consume `self` to return the original lifetime of 949 /// the data, which prevents this from actually being used as a parallel 950 /// iterator since that also consumes. This method is provided for parity 951 /// with `std::iter::ChunksExactMut`, but consider calling `remainder()` or 952 /// `take_remainder()` as alternatives. into_remainder(self) -> &'data mut [T]953 pub fn into_remainder(self) -> &'data mut [T] { 954 self.rem 955 } 956 957 /// Return the remainder of the original slice that is not going to be 958 /// returned by the iterator. The returned slice has at most `chunk_size-1` 959 /// elements. 960 /// 961 /// Consider `take_remainder()` if you need access to the data with its 962 /// original lifetime, rather than borrowing through `&mut self` here. remainder(&mut self) -> &mut [T]963 pub fn remainder(&mut self) -> &mut [T] { 964 self.rem 965 } 966 967 /// Return the remainder of the original slice that is not going to be 968 /// returned by the iterator. The returned slice has at most `chunk_size-1` 969 /// elements. Subsequent calls will return an empty slice. take_remainder(&mut self) -> &'data mut [T]970 pub fn take_remainder(&mut self) -> &'data mut [T] { 971 std::mem::replace(&mut self.rem, &mut []) 972 } 973 } 974 975 impl<'data, T: Send + 'data> ParallelIterator for ChunksExactMut<'data, T> { 976 type Item = &'data mut [T]; 977 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,978 fn drive_unindexed<C>(self, consumer: C) -> C::Result 979 where 980 C: UnindexedConsumer<Self::Item>, 981 { 982 bridge(self, consumer) 983 } 984 opt_len(&self) -> Option<usize>985 fn opt_len(&self) -> Option<usize> { 986 Some(self.len()) 987 } 988 } 989 990 impl<'data, T: Send + 'data> IndexedParallelIterator for ChunksExactMut<'data, T> { drive<C>(self, consumer: C) -> C::Result where C: Consumer<Self::Item>,991 fn drive<C>(self, consumer: C) -> C::Result 992 where 993 C: Consumer<Self::Item>, 994 { 995 bridge(self, consumer) 996 } 997 len(&self) -> usize998 fn len(&self) -> usize { 999 self.slice.len() / self.chunk_size 1000 } 1001 with_producer<CB>(self, callback: CB) -> CB::Output where CB: ProducerCallback<Self::Item>,1002 fn with_producer<CB>(self, callback: CB) -> CB::Output 1003 where 1004 CB: ProducerCallback<Self::Item>, 1005 { 1006 callback.callback(ChunksExactMutProducer { 1007 chunk_size: self.chunk_size, 1008 slice: self.slice, 1009 }) 1010 } 1011 } 1012 1013 struct ChunksExactMutProducer<'data, T: Send> { 1014 chunk_size: usize, 1015 slice: &'data mut [T], 1016 } 1017 1018 impl<'data, T: 'data + Send> Producer for ChunksExactMutProducer<'data, T> { 1019 type Item = &'data mut [T]; 1020 type IntoIter = ::std::slice::ChunksExactMut<'data, T>; 1021 into_iter(self) -> Self::IntoIter1022 fn into_iter(self) -> Self::IntoIter { 1023 self.slice.chunks_exact_mut(self.chunk_size) 1024 } 1025 split_at(self, index: usize) -> (Self, Self)1026 fn split_at(self, index: usize) -> (Self, Self) { 1027 let elem_index = index * self.chunk_size; 1028 let (left, right) = self.slice.split_at_mut(elem_index); 1029 ( 1030 ChunksExactMutProducer { 1031 chunk_size: self.chunk_size, 1032 slice: left, 1033 }, 1034 ChunksExactMutProducer { 1035 chunk_size: self.chunk_size, 1036 slice: right, 1037 }, 1038 ) 1039 } 1040 } 1041 1042 /// Parallel iterator over slices separated by a predicate 1043 pub struct Split<'data, T, P> { 1044 slice: &'data [T], 1045 separator: P, 1046 } 1047 1048 impl<'data, T, P: Clone> Clone for Split<'data, T, P> { clone(&self) -> Self1049 fn clone(&self) -> Self { 1050 Split { 1051 separator: self.separator.clone(), 1052 ..*self 1053 } 1054 } 1055 } 1056 1057 impl<'data, T: Debug, P> Debug for Split<'data, T, P> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1058 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1059 f.debug_struct("Split").field("slice", &self.slice).finish() 1060 } 1061 } 1062 1063 impl<'data, T, P> ParallelIterator for Split<'data, T, P> 1064 where 1065 P: Fn(&T) -> bool + Sync + Send, 1066 T: Sync, 1067 { 1068 type Item = &'data [T]; 1069 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,1070 fn drive_unindexed<C>(self, consumer: C) -> C::Result 1071 where 1072 C: UnindexedConsumer<Self::Item>, 1073 { 1074 let producer = SplitProducer::new(self.slice, &self.separator); 1075 bridge_unindexed(producer, consumer) 1076 } 1077 } 1078 1079 /// Implement support for `SplitProducer`. 1080 impl<'data, T, P> Fissile<P> for &'data [T] 1081 where 1082 P: Fn(&T) -> bool, 1083 { length(&self) -> usize1084 fn length(&self) -> usize { 1085 self.len() 1086 } 1087 midpoint(&self, end: usize) -> usize1088 fn midpoint(&self, end: usize) -> usize { 1089 end / 2 1090 } 1091 find(&self, separator: &P, start: usize, end: usize) -> Option<usize>1092 fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize> { 1093 self[start..end].iter().position(separator) 1094 } 1095 rfind(&self, separator: &P, end: usize) -> Option<usize>1096 fn rfind(&self, separator: &P, end: usize) -> Option<usize> { 1097 self[..end].iter().rposition(separator) 1098 } 1099 split_once(self, index: usize) -> (Self, Self)1100 fn split_once(self, index: usize) -> (Self, Self) { 1101 let (left, right) = self.split_at(index); 1102 (left, &right[1..]) // skip the separator 1103 } 1104 fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F where F: Folder<Self>, Self: Send,1105 fn fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F 1106 where 1107 F: Folder<Self>, 1108 Self: Send, 1109 { 1110 let mut split = self.split(separator); 1111 if skip_last { 1112 split.next_back(); 1113 } 1114 folder.consume_iter(split) 1115 } 1116 } 1117 1118 /// Parallel iterator over mutable slices separated by a predicate 1119 pub struct SplitMut<'data, T, P> { 1120 slice: &'data mut [T], 1121 separator: P, 1122 } 1123 1124 impl<'data, T: Debug, P> Debug for SplitMut<'data, T, P> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1125 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1126 f.debug_struct("SplitMut") 1127 .field("slice", &self.slice) 1128 .finish() 1129 } 1130 } 1131 1132 impl<'data, T, P> ParallelIterator for SplitMut<'data, T, P> 1133 where 1134 P: Fn(&T) -> bool + Sync + Send, 1135 T: Send, 1136 { 1137 type Item = &'data mut [T]; 1138 drive_unindexed<C>(self, consumer: C) -> C::Result where C: UnindexedConsumer<Self::Item>,1139 fn drive_unindexed<C>(self, consumer: C) -> C::Result 1140 where 1141 C: UnindexedConsumer<Self::Item>, 1142 { 1143 let producer = SplitProducer::new(self.slice, &self.separator); 1144 bridge_unindexed(producer, consumer) 1145 } 1146 } 1147 1148 /// Implement support for `SplitProducer`. 1149 impl<'data, T, P> Fissile<P> for &'data mut [T] 1150 where 1151 P: Fn(&T) -> bool, 1152 { length(&self) -> usize1153 fn length(&self) -> usize { 1154 self.len() 1155 } 1156 midpoint(&self, end: usize) -> usize1157 fn midpoint(&self, end: usize) -> usize { 1158 end / 2 1159 } 1160 find(&self, separator: &P, start: usize, end: usize) -> Option<usize>1161 fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize> { 1162 self[start..end].iter().position(separator) 1163 } 1164 rfind(&self, separator: &P, end: usize) -> Option<usize>1165 fn rfind(&self, separator: &P, end: usize) -> Option<usize> { 1166 self[..end].iter().rposition(separator) 1167 } 1168 split_once(self, index: usize) -> (Self, Self)1169 fn split_once(self, index: usize) -> (Self, Self) { 1170 let (left, right) = self.split_at_mut(index); 1171 (left, &mut right[1..]) // skip the separator 1172 } 1173 fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F where F: Folder<Self>, Self: Send,1174 fn fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F 1175 where 1176 F: Folder<Self>, 1177 Self: Send, 1178 { 1179 let mut split = self.split_mut(separator); 1180 if skip_last { 1181 split.next_back(); 1182 } 1183 folder.consume_iter(split) 1184 } 1185 } 1186