rayon/
split_producer.rs

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, const INCL: bool = false> {
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
16pub(super) type SplitInclusiveProducer<'p, P, V> = SplitProducer<'p, P, V, true>;
17
18/// Helper trait so `&str`, `&[T]`, and `&mut [T]` can share `SplitProducer`.
19pub(super) trait Fissile<P>: Sized {
20    fn length(&self) -> usize;
21    fn midpoint(&self, end: usize) -> usize;
22    fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize>;
23    fn rfind(&self, separator: &P, end: usize) -> Option<usize>;
24    fn split_once<const INCL: bool>(self, index: usize) -> (Self, Self);
25    fn fold_splits<F, const INCL: bool>(self, separator: &P, folder: F, skip_last: bool) -> F
26    where
27        F: Folder<Self>,
28        Self: Send;
29}
30
31impl<'p, P, V> SplitProducer<'p, P, V>
32where
33    V: Fissile<P> + Send,
34{
35    pub(super) fn new(data: V, separator: &'p P) -> Self {
36        SplitProducer {
37            tail: data.length(),
38            data,
39            separator,
40        }
41    }
42}
43
44impl<'p, P, V> SplitInclusiveProducer<'p, P, V>
45where
46    V: Fissile<P> + Send,
47{
48    pub(super) fn new_incl(data: V, separator: &'p P) -> Self {
49        SplitProducer {
50            tail: data.length(),
51            data,
52            separator,
53        }
54    }
55}
56
57impl<'p, P, V, const INCL: bool> SplitProducer<'p, P, V, INCL>
58where
59    V: Fissile<P> + Send,
60{
61    /// Common `fold_with` implementation, integrating `SplitTerminator`'s
62    /// need to sometimes skip its final empty item.
63    pub(super) fn fold_with<F>(self, folder: F, skip_last: bool) -> F
64    where
65        F: Folder<V>,
66    {
67        let SplitProducer {
68            data,
69            separator,
70            tail,
71        } = self;
72
73        if tail == data.length() {
74            // No tail section, so just let `fold_splits` handle it.
75            data.fold_splits::<F, INCL>(separator, folder, skip_last)
76        } else if let Some(index) = data.rfind(separator, tail) {
77            // We found the last separator to complete the tail, so
78            // end with that slice after `fold_splits` finds the rest.
79            let (left, right) = data.split_once::<INCL>(index);
80            let folder = left.fold_splits::<F, INCL>(separator, folder, false);
81            if skip_last || folder.full() {
82                folder
83            } else {
84                folder.consume(right)
85            }
86        } else {
87            // We know there are no separators at all.  Return our whole data.
88            if skip_last {
89                folder
90            } else {
91                folder.consume(data)
92            }
93        }
94    }
95}
96
97impl<'p, P, V, const INCL: bool> UnindexedProducer for SplitProducer<'p, P, V, INCL>
98where
99    V: Fissile<P> + Send,
100    P: Sync,
101{
102    type Item = V;
103
104    fn split(self) -> (Self, Option<Self>) {
105        // Look forward for the separator, and failing that look backward.
106        let mid = self.data.midpoint(self.tail);
107        let index = match self.data.find(self.separator, mid, self.tail) {
108            Some(i) => Some(mid + i),
109            None => self.data.rfind(self.separator, mid),
110        };
111
112        if let Some(index) = index {
113            let len = self.data.length();
114            let (left, right) = self.data.split_once::<INCL>(index);
115
116            let (left_tail, right_tail) = if index < mid {
117                // If we scanned backwards to find the separator, everything in
118                // the right side is exhausted, with no separators left to find.
119                (index, 0)
120            } else {
121                let right_index = len - right.length();
122                (mid, self.tail - right_index)
123            };
124
125            // Create the left split before the separator.
126            let left = SplitProducer {
127                data: left,
128                tail: left_tail,
129                ..self
130            };
131
132            // Create the right split following the separator.
133            let right = SplitProducer {
134                data: right,
135                tail: right_tail,
136                ..self
137            };
138
139            (left, Some(right))
140        } else {
141            // The search is exhausted, no more separators...
142            (SplitProducer { tail: 0, ..self }, None)
143        }
144    }
145
146    fn fold_with<F>(self, folder: F) -> F
147    where
148        F: Folder<Self::Item>,
149    {
150        self.fold_with(folder, false)
151    }
152}
rayon/split_producer.rs

rayon/
split_producer.rs
