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