rayon/slice/
mod.rs

Help
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
8mod mergesort;
9mod quicksort;
10
11mod test;
12
13use self::mergesort::par_mergesort;
14use self::quicksort::par_quicksort;
15use crate::iter::plumbing::*;
16use crate::iter::*;
17use crate::split_producer::*;
18use std::cmp;
19use std::cmp::Ordering;
20use std::fmt::{self, Debug};
21
22use super::math::div_round_up;
23
24/// Parallel extensions for slices.
25pub trait ParallelSlice<T: Sync> {
26    /// Returns a plain slice, which is used to implement the rest of the
27    /// parallel methods.
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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
120impl<T: Sync> ParallelSlice<T> for [T] {
121    #[inline]
122    fn as_parallel_slice(&self) -> &[T] {
123        self
124    }
125}
126
127/// Parallel extensions for mutable slices.
128pub trait ParallelSliceMut<T: Send> {
129    /// Returns a plain mutable slice, which is used to implement the rest of
130    /// the parallel methods.
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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    /// ```
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
457impl<T: Send> ParallelSliceMut<T> for [T] {
458    #[inline]
459    fn as_parallel_slice_mut(&mut self) -> &mut [T] {
460        self
461    }
462}
463
464impl<'data, T: Sync + 'data> IntoParallelIterator for &'data [T] {
465    type Item = &'data T;
466    type Iter = Iter<'data, T>;
467
468    fn into_par_iter(self) -> Self::Iter {
469        Iter { slice: self }
470    }
471}
472
473impl<'data, T: Send + 'data> IntoParallelIterator for &'data mut [T] {
474    type Item = &'data mut T;
475    type Iter = IterMut<'data, T>;
476
477    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)]
484pub struct Iter<'data, T: Sync> {
485    slice: &'data [T],
486}
487
488impl<'data, T: Sync> Clone for Iter<'data, T> {
489    fn clone(&self) -> Self {
490        Iter { ..*self }
491    }
492}
493
494impl<'data, T: Sync + 'data> ParallelIterator for Iter<'data, T> {
495    type Item = &'data T;
496
497    fn drive_unindexed<C>(self, consumer: C) -> C::Result
498    where
499        C: UnindexedConsumer<Self::Item>,
500    {
501        bridge(self, consumer)
502    }
503
504    fn opt_len(&self) -> Option<usize> {
505        Some(self.len())
506    }
507}
508
509impl<'data, T: Sync + 'data> IndexedParallelIterator for Iter<'data, T> {
510    fn drive<C>(self, consumer: C) -> C::Result
511    where
512        C: Consumer<Self::Item>,
513    {
514        bridge(self, consumer)
515    }
516
517    fn len(&self) -> usize {
518        self.slice.len()
519    }
520
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
529struct IterProducer<'data, T: Sync> {
530    slice: &'data [T],
531}
532
533impl<'data, T: 'data + Sync> Producer for IterProducer<'data, T> {
534    type Item = &'data T;
535    type IntoIter = ::std::slice::Iter<'data, T>;
536
537    fn into_iter(self) -> Self::IntoIter {
538        self.slice.iter()
539    }
540
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)]
549pub struct Chunks<'data, T: Sync> {
550    chunk_size: usize,
551    slice: &'data [T],
552}
553
554impl<'data, T: Sync> Clone for Chunks<'data, T> {
555    fn clone(&self) -> Self {
556        Chunks { ..*self }
557    }
558}
559
560impl<'data, T: Sync + 'data> ParallelIterator for Chunks<'data, T> {
561    type Item = &'data [T];
562
563    fn drive_unindexed<C>(self, consumer: C) -> C::Result
564    where
565        C: UnindexedConsumer<Self::Item>,
566    {
567        bridge(self, consumer)
568    }
569
570    fn opt_len(&self) -> Option<usize> {
571        Some(self.len())
572    }
573}
574
575impl<'data, T: Sync + 'data> IndexedParallelIterator for Chunks<'data, T> {
576    fn drive<C>(self, consumer: C) -> C::Result
577    where
578        C: Consumer<Self::Item>,
579    {
580        bridge(self, consumer)
581    }
582
583    fn len(&self) -> usize {
584        div_round_up(self.slice.len(), self.chunk_size)
585    }
586
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
598struct ChunksProducer<'data, T: Sync> {
599    chunk_size: usize,
600    slice: &'data [T],
601}
602
603impl<'data, T: 'data + Sync> Producer for ChunksProducer<'data, T> {
604    type Item = &'data [T];
605    type IntoIter = ::std::slice::Chunks<'data, T>;
606
607    fn into_iter(self) -> Self::IntoIter {
608        self.slice.chunks(self.chunk_size)
609    }
610
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)]
629pub struct ChunksExact<'data, T: Sync> {
630    chunk_size: usize,
631    slice: &'data [T],
632    rem: &'data [T],
633}
634
635impl<'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.
639    pub fn remainder(&self) -> &'data [T] {
640        self.rem
641    }
642}
643
644impl<'data, T: Sync> Clone for ChunksExact<'data, T> {
645    fn clone(&self) -> Self {
646        ChunksExact { ..*self }
647    }
648}
649
650impl<'data, T: Sync + 'data> ParallelIterator for ChunksExact<'data, T> {
651    type Item = &'data [T];
652
653    fn drive_unindexed<C>(self, consumer: C) -> C::Result
654    where
655        C: UnindexedConsumer<Self::Item>,
656    {
657        bridge(self, consumer)
658    }
659
660    fn opt_len(&self) -> Option<usize> {
661        Some(self.len())
662    }
663}
664
665impl<'data, T: Sync + 'data> IndexedParallelIterator for ChunksExact<'data, T> {
666    fn drive<C>(self, consumer: C) -> C::Result
667    where
668        C: Consumer<Self::Item>,
669    {
670        bridge(self, consumer)
671    }
672
673    fn len(&self) -> usize {
674        self.slice.len() / self.chunk_size
675    }
676
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
688struct ChunksExactProducer<'data, T: Sync> {
689    chunk_size: usize,
690    slice: &'data [T],
691}
692
693impl<'data, T: 'data + Sync> Producer for ChunksExactProducer<'data, T> {
694    type Item = &'data [T];
695    type IntoIter = ::std::slice::ChunksExact<'data, T>;
696
697    fn into_iter(self) -> Self::IntoIter {
698        self.slice.chunks_exact(self.chunk_size)
699    }
700
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)]
719pub struct Windows<'data, T: Sync> {
720    window_size: usize,
721    slice: &'data [T],
722}
723
724impl<'data, T: Sync> Clone for Windows<'data, T> {
725    fn clone(&self) -> Self {
726        Windows { ..*self }
727    }
728}
729
730impl<'data, T: Sync + 'data> ParallelIterator for Windows<'data, T> {
731    type Item = &'data [T];
732
733    fn drive_unindexed<C>(self, consumer: C) -> C::Result
734    where
735        C: UnindexedConsumer<Self::Item>,
736    {
737        bridge(self, consumer)
738    }
739
740    fn opt_len(&self) -> Option<usize> {
741        Some(self.len())
742    }
743}
744
745impl<'data, T: Sync + 'data> IndexedParallelIterator for Windows<'data, T> {
746    fn drive<C>(self, consumer: C) -> C::Result
747    where
748        C: Consumer<Self::Item>,
749    {
750        bridge(self, consumer)
751    }
752
753    fn len(&self) -> usize {
754        assert!(self.window_size >= 1);
755        self.slice.len().saturating_sub(self.window_size - 1)
756    }
757
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
769struct WindowsProducer<'data, T: Sync> {
770    window_size: usize,
771    slice: &'data [T],
772}
773
774impl<'data, T: 'data + Sync> Producer for WindowsProducer<'data, T> {
775    type Item = &'data [T];
776    type IntoIter = ::std::slice::Windows<'data, T>;
777
778    fn into_iter(self) -> Self::IntoIter {
779        self.slice.windows(self.window_size)
780    }
781
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)]
801pub struct IterMut<'data, T: Send> {
802    slice: &'data mut [T],
803}
804
805impl<'data, T: Send + 'data> ParallelIterator for IterMut<'data, T> {
806    type Item = &'data mut T;
807
808    fn drive_unindexed<C>(self, consumer: C) -> C::Result
809    where
810        C: UnindexedConsumer<Self::Item>,
811    {
812        bridge(self, consumer)
813    }
814
815    fn opt_len(&self) -> Option<usize> {
816        Some(self.len())
817    }
818}
819
820impl<'data, T: Send + 'data> IndexedParallelIterator for IterMut<'data, T> {
821    fn drive<C>(self, consumer: C) -> C::Result
822    where
823        C: Consumer<Self::Item>,
824    {
825        bridge(self, consumer)
826    }
827
828    fn len(&self) -> usize {
829        self.slice.len()
830    }
831
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
840struct IterMutProducer<'data, T: Send> {
841    slice: &'data mut [T],
842}
843
844impl<'data, T: 'data + Send> Producer for IterMutProducer<'data, T> {
845    type Item = &'data mut T;
846    type IntoIter = ::std::slice::IterMut<'data, T>;
847
848    fn into_iter(self) -> Self::IntoIter {
849        self.slice.iter_mut()
850    }
851
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)]
863pub struct ChunksMut<'data, T: Send> {
864    chunk_size: usize,
865    slice: &'data mut [T],
866}
867
868impl<'data, T: Send + 'data> ParallelIterator for ChunksMut<'data, T> {
869    type Item = &'data mut [T];
870
871    fn drive_unindexed<C>(self, consumer: C) -> C::Result
872    where
873        C: UnindexedConsumer<Self::Item>,
874    {
875        bridge(self, consumer)
876    }
877
878    fn opt_len(&self) -> Option<usize> {
879        Some(self.len())
880    }
881}
882
883impl<'data, T: Send + 'data> IndexedParallelIterator for ChunksMut<'data, T> {
884    fn drive<C>(self, consumer: C) -> C::Result
885    where
886        C: Consumer<Self::Item>,
887    {
888        bridge(self, consumer)
889    }
890
891    fn len(&self) -> usize {
892        div_round_up(self.slice.len(), self.chunk_size)
893    }
894
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
906struct ChunksMutProducer<'data, T: Send> {
907    chunk_size: usize,
908    slice: &'data mut [T],
909}
910
911impl<'data, T: 'data + Send> Producer for ChunksMutProducer<'data, T> {
912    type Item = &'data mut [T];
913    type IntoIter = ::std::slice::ChunksMut<'data, T>;
914
915    fn into_iter(self) -> Self::IntoIter {
916        self.slice.chunks_mut(self.chunk_size)
917    }
918
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)]
937pub struct ChunksExactMut<'data, T: Send> {
938    chunk_size: usize,
939    slice: &'data mut [T],
940    rem: &'data mut [T],
941}
942
943impl<'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.
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.
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.
970    pub fn take_remainder(&mut self) -> &'data mut [T] {
971        std::mem::replace(&mut self.rem, &mut [])
972    }
973}
974
975impl<'data, T: Send + 'data> ParallelIterator for ChunksExactMut<'data, T> {
976    type Item = &'data mut [T];
977
978    fn drive_unindexed<C>(self, consumer: C) -> C::Result
979    where
980        C: UnindexedConsumer<Self::Item>,
981    {
982        bridge(self, consumer)
983    }
984
985    fn opt_len(&self) -> Option<usize> {
986        Some(self.len())
987    }
988}
989
990impl<'data, T: Send + 'data> IndexedParallelIterator for ChunksExactMut<'data, T> {
991    fn drive<C>(self, consumer: C) -> C::Result
992    where
993        C: Consumer<Self::Item>,
994    {
995        bridge(self, consumer)
996    }
997
998    fn len(&self) -> usize {
999        self.slice.len() / self.chunk_size
1000    }
1001
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
1013struct ChunksExactMutProducer<'data, T: Send> {
1014    chunk_size: usize,
1015    slice: &'data mut [T],
1016}
1017
1018impl<'data, T: 'data + Send> Producer for ChunksExactMutProducer<'data, T> {
1019    type Item = &'data mut [T];
1020    type IntoIter = ::std::slice::ChunksExactMut<'data, T>;
1021
1022    fn into_iter(self) -> Self::IntoIter {
1023        self.slice.chunks_exact_mut(self.chunk_size)
1024    }
1025
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
1043pub struct Split<'data, T, P> {
1044    slice: &'data [T],
1045    separator: P,
1046}
1047
1048impl<'data, T, P: Clone> Clone for Split<'data, T, P> {
1049    fn clone(&self) -> Self {
1050        Split {
1051            separator: self.separator.clone(),
1052            ..*self
1053        }
1054    }
1055}
1056
1057impl<'data, T: Debug, P> Debug for Split<'data, T, P> {
1058    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1059        f.debug_struct("Split").field("slice", &self.slice).finish()
1060    }
1061}
1062
1063impl<'data, T, P> ParallelIterator for Split<'data, T, P>
1064where
1065    P: Fn(&T) -> bool + Sync + Send,
1066    T: Sync,
1067{
1068    type Item = &'data [T];
1069
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`.
1080impl<'data, T, P> Fissile<P> for &'data [T]
1081where
1082    P: Fn(&T) -> bool,
1083{
1084    fn length(&self) -> usize {
1085        self.len()
1086    }
1087
1088    fn midpoint(&self, end: usize) -> usize {
1089        end / 2
1090    }
1091
1092    fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize> {
1093        self[start..end].iter().position(separator)
1094    }
1095
1096    fn rfind(&self, separator: &P, end: usize) -> Option<usize> {
1097        self[..end].iter().rposition(separator)
1098    }
1099
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
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
1119pub struct SplitMut<'data, T, P> {
1120    slice: &'data mut [T],
1121    separator: P,
1122}
1123
1124impl<'data, T: Debug, P> Debug for SplitMut<'data, T, P> {
1125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1126        f.debug_struct("SplitMut")
1127            .field("slice", &self.slice)
1128            .finish()
1129    }
1130}
1131
1132impl<'data, T, P> ParallelIterator for SplitMut<'data, T, P>
1133where
1134    P: Fn(&T) -> bool + Sync + Send,
1135    T: Send,
1136{
1137    type Item = &'data mut [T];
1138
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`.
1149impl<'data, T, P> Fissile<P> for &'data mut [T]
1150where
1151    P: Fn(&T) -> bool,
1152{
1153    fn length(&self) -> usize {
1154        self.len()
1155    }
1156
1157    fn midpoint(&self, end: usize) -> usize {
1158        end / 2
1159    }
1160
1161    fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize> {
1162        self[start..end].iter().position(separator)
1163    }
1164
1165    fn rfind(&self, separator: &P, end: usize) -> Option<usize> {
1166        self[..end].iter().rposition(separator)
1167    }
1168
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
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}
rayon/slice/mod.rs

rayon/slice/
mod.rs
