src/libsyntax/util/move_map.rs

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