rayon/
split_producer.rs

Help
1//! Common splitter for strings and slices
2//!
3//! This module is private, so these items are effectively `pub(super)`
4
5use crate::iter::plumbing::{Folder, UnindexedProducer};
6
7/// Common producer for splitting on a predicate.
8pub(super) struct SplitProducer<'p, P, V> {
9    data: V,
10    separator: &'p P,
11
12    /// Marks the endpoint beyond which we've already found no separators.
13    tail: usize,
14}
15
16/// Helper trait so `&str`, `&[T]`, and `&mut [T]` can share `SplitProducer`.
17pub(super) trait Fissile<P>: Sized {
18    fn length(&self) -> usize;
19    fn midpoint(&self, end: usize) -> usize;
20    fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize>;
21    fn rfind(&self, separator: &P, end: usize) -> Option<usize>;
22    fn split_once(self, index: usize) -> (Self, Self);
23    fn fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F
24    where
25        F: Folder<Self>,
26        Self: Send;
27}
28
29impl<'p, P, V> SplitProducer<'p, P, V>
30where
31    V: Fissile<P> + Send,
32{
33    pub(super) fn new(data: V, separator: &'p P) -> Self {
34        SplitProducer {
35            tail: data.length(),
36            data,
37            separator,
38        }
39    }
40
41    /// Common `fold_with` implementation, integrating `SplitTerminator`'s
42    /// need to sometimes skip its final empty item.
43    pub(super) fn fold_with<F>(self, folder: F, skip_last: bool) -> F
44    where
45        F: Folder<V>,
46    {
47        let SplitProducer {
48            data,
49            separator,
50            tail,
51        } = self;
52
53        if tail == data.length() {
54            // No tail section, so just let `fold_splits` handle it.
55            data.fold_splits(separator, folder, skip_last)
56        } else if let Some(index) = data.rfind(separator, tail) {
57            // We found the last separator to complete the tail, so
58            // end with that slice after `fold_splits` finds the rest.
59            let (left, right) = data.split_once(index);
60            let folder = left.fold_splits(separator, folder, false);
61            if skip_last || folder.full() {
62                folder
63            } else {
64                folder.consume(right)
65            }
66        } else {
67            // We know there are no separators at all.  Return our whole data.
68            if skip_last {
69                folder
70            } else {
71                folder.consume(data)
72            }
73        }
74    }
75}
76
77impl<'p, P, V> UnindexedProducer for SplitProducer<'p, P, V>
78where
79    V: Fissile<P> + Send,
80    P: Sync,
81{
82    type Item = V;
83
84    fn split(self) -> (Self, Option<Self>) {
85        // Look forward for the separator, and failing that look backward.
86        let mid = self.data.midpoint(self.tail);
87        let index = match self.data.find(self.separator, mid, self.tail) {
88            Some(i) => Some(mid + i),
89            None => self.data.rfind(self.separator, mid),
90        };
91
92        if let Some(index) = index {
93            let len = self.data.length();
94            let (left, right) = self.data.split_once(index);
95
96            let (left_tail, right_tail) = if index < mid {
97                // If we scanned backwards to find the separator, everything in
98                // the right side is exhausted, with no separators left to find.
99                (index, 0)
100            } else {
101                let right_index = len - right.length();
102                (mid, self.tail - right_index)
103            };
104
105            // Create the left split before the separator.
106            let left = SplitProducer {
107                data: left,
108                tail: left_tail,
109                ..self
110            };
111
112            // Create the right split following the separator.
113            let right = SplitProducer {
114                data: right,
115                tail: right_tail,
116                ..self
117            };
118
119            (left, Some(right))
120        } else {
121            // The search is exhausted, no more separators...
122            (SplitProducer { tail: 0, ..self }, None)
123        }
124    }
125
126    fn fold_with<F>(self, folder: F) -> F
127    where
128        F: Folder<Self::Item>,
129    {
130        self.fold_with(folder, false)
131    }
132}
rayon/split_producer.rs

rayon/
split_producer.rs
