src/libsyntax/util/move_map.rs

   1 use std::ptr;
   2 use smallvec::{Array, SmallVec};
   3
   4 pub trait MoveMap<T>: Sized {
   5     fn move_map<F>(self, mut f: F) -> Self where F: FnMut(T) -> T {
   6         self.move_flat_map(|e| Some(f(e)))
   7     }
   8
   9     fn move_flat_map<F, I>(self, f: F) -> Self
  10         where F: FnMut(T) -> I,
  11               I: IntoIterator<Item=T>;
  12 }
  13
  14 impl<T> MoveMap<T> for Vec<T> {
  15     fn move_flat_map<F, I>(mut self, mut f: F) -> Self
  16         where F: FnMut(T) -> I,
  17               I: IntoIterator<Item=T>
  18     {
  19         let mut read_i = 0;
  20         let mut write_i = 0;
  21         unsafe {
  22             let mut old_len = self.len();
  23             self.set_len(0); // make sure we just leak elements in case of panic
  24
  25             while read_i < old_len {
  26                 // move the read_i'th item out of the vector and map it
  27                 // to an iterator
  28                 let e = ptr::read(self.get_unchecked(read_i));
  29                 let iter = f(e).into_iter();
  30                 read_i += 1;
  31
  32                 for e in iter {
  33                     if write_i < read_i {
  34                         ptr::write(self.get_unchecked_mut(write_i), e);
  35                         write_i += 1;
  36                     } else {
  37                         // If this is reached we ran out of space
  38                         // in the middle of the vector.
  39                         // However, the vector is in a valid state here,
  40                         // so we just do a somewhat inefficient insert.
  41                         self.set_len(old_len);
  42                         self.insert(write_i, e);
  43
  44                         old_len = self.len();
  45                         self.set_len(0);
  46
  47                         read_i += 1;
  48                         write_i += 1;
  49                     }
  50                 }
  51             }
  52
  53             // write_i tracks the number of actually written new items.
  54             self.set_len(write_i);
  55         }
  56
  57         self
  58     }
  59 }
  60
  61 impl<T> MoveMap<T> for ::ptr::P<[T]> {
  62     fn move_flat_map<F, I>(self, f: F) -> Self
  63         where F: FnMut(T) -> I,
  64               I: IntoIterator<Item=T>
  65     {
  66         ::ptr::P::from_vec(self.into_vec().move_flat_map(f))
  67     }
  68 }
  69
  70 impl<T, A: Array<Item = T>> MoveMap<T> for SmallVec<A> {
  71     fn move_flat_map<F, I>(mut self, mut f: F) -> Self
  72         where F: FnMut(T) -> I,
  73               I: IntoIterator<Item=T>
  74     {
  75         let mut read_i = 0;
  76         let mut write_i = 0;
  77         unsafe {
  78             let mut old_len = self.len();
  79             self.set_len(0); // make sure we just leak elements in case of panic
  80
  81             while read_i < old_len {
  82                 // move the read_i'th item out of the vector and map it
  83                 // to an iterator
  84                 let e = ptr::read(self.get_unchecked(read_i));
  85                 let iter = f(e).into_iter();
  86                 read_i += 1;
  87
  88                 for e in iter {
  89                     if write_i < read_i {
  90                         ptr::write(self.get_unchecked_mut(write_i), e);
  91                         write_i += 1;
  92                     } else {
  93                         // If this is reached we ran out of space
  94                         // in the middle of the vector.
  95                         // However, the vector is in a valid state here,
  96                         // so we just do a somewhat inefficient insert.
  97                         self.set_len(old_len);
  98                         self.insert(write_i, e);
  99
 100                         old_len = self.len();
 101                         self.set_len(0);
 102
 103                         read_i += 1;
 104                         write_i += 1;
 105                     }
 106                 }
 107             }
 108
 109             // write_i tracks the number of actually written new items.
 110             self.set_len(write_i);
 111         }
 112
 113         self
 114     }
 115 }