src/vendor/rayon/src/split_producer.rs

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