src/libstd/vec_ng.rs

   1 // Copyright 2014 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 // Migrate documentation over from `std::vec` when it is removed.
  12 #[doc(hidden)];
  13
  14 use cast::{forget, transmute};
  15 use clone::Clone;
  16 use cmp::{Eq, Ordering, TotalEq, TotalOrd};
  17 use container::Container;
  18 use iter::{DoubleEndedIterator, FromIterator, Iterator};
  19 use libc::{free, c_void};
  20 use mem::{size_of, move_val_init};
  21 use num;
  22 use num::CheckedMul;
  23 use ops::Drop;
  24 use option::{None, Option, Some};
  25 use ptr::RawPtr;
  26 use ptr;
  27 use rt::global_heap::{malloc_raw, realloc_raw};
  28 use raw::Slice;
  29 use vec::{ImmutableVector, Items, MutItems, MutableVector, RevItems};
  30
  31 pub struct Vec<T> {
  32     priv len: uint,
  33     priv cap: uint,
  34     priv ptr: *mut T
  35 }
  36
  37 impl<T> Vec<T> {
  38     #[inline]
  39     pub fn new() -> Vec<T> {
  40         Vec { len: 0, cap: 0, ptr: 0 as *mut T }
  41     }
  42
  43     pub fn with_capacity(capacity: uint) -> Vec<T> {
  44         if capacity == 0 {
  45             Vec::new()
  46         } else {
  47             let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
  48             let ptr = unsafe { malloc_raw(size) };
  49             Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
  50         }
  51     }
  52
  53     pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
  54         unsafe {
  55             let mut xs = Vec::with_capacity(length);
  56             while xs.len < length {
  57                 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), op(xs.len));
  58                 xs.len += 1;
  59             }
  60             xs
  61         }
  62     }
  63 }
  64
  65 impl<T: Clone> Vec<T> {
  66     pub fn from_elem(length: uint, value: T) -> Vec<T> {
  67         unsafe {
  68             let mut xs = Vec::with_capacity(length);
  69             while xs.len < length {
  70                 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), value.clone());
  71                 xs.len += 1;
  72             }
  73             xs
  74         }
  75     }
  76
  77     #[inline]
  78     pub fn push_all(&mut self, other: &[T]) {
  79         for element in other.iter() {
  80             self.push((*element).clone())
  81         }
  82     }
  83 }
  84
  85 impl<T:Clone> Clone for Vec<T> {
  86     fn clone(&self) -> Vec<T> {
  87         let mut vector = Vec::with_capacity(self.len());
  88         for element in self.iter() {
  89             vector.push((*element).clone())
  90         }
  91         vector
  92     }
  93 }
  94
  95 impl<T> FromIterator<T> for Vec<T> {
  96     fn from_iterator<I:Iterator<T>>(iterator: &mut I) -> Vec<T> {
  97         let (lower, _) = iterator.size_hint();
  98         let mut vector = Vec::with_capacity(lower);
  99         for element in *iterator {
 100             vector.push(element)
 101         }
 102         vector
 103     }
 104 }
 105
 106 impl<T:Eq> Eq for Vec<T> {
 107     #[inline]
 108     fn eq(&self, other: &Vec<T>) -> bool {
 109         self.as_slice() == other.as_slice()
 110     }
 111 }
 112
 113 impl<T:TotalEq> TotalEq for Vec<T> {
 114     #[inline]
 115     fn equals(&self, other: &Vec<T>) -> bool {
 116         self.as_slice().equals(&other.as_slice())
 117     }
 118 }
 119
 120 impl<T:TotalOrd> TotalOrd for Vec<T> {
 121     #[inline]
 122     fn cmp(&self, other: &Vec<T>) -> Ordering {
 123         self.as_slice().cmp(&other.as_slice())
 124     }
 125 }
 126
 127 impl<T> Container for Vec<T> {
 128     #[inline]
 129     fn len(&self) -> uint {
 130         self.len
 131     }
 132 }
 133
 134 impl<T> Vec<T> {
 135     #[inline]
 136     pub fn capacity(&self) -> uint {
 137         self.cap
 138     }
 139
 140     pub fn reserve(&mut self, capacity: uint) {
 141         if capacity >= self.len {
 142             self.reserve_exact(num::next_power_of_two(capacity))
 143         }
 144     }
 145
 146     pub fn reserve_exact(&mut self, capacity: uint) {
 147         if capacity >= self.len {
 148             let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
 149             self.cap = capacity;
 150             unsafe {
 151                 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
 152             }
 153         }
 154     }
 155
 156     pub fn shrink_to_fit(&mut self) {
 157         if self.len == 0 {
 158             unsafe { free(self.ptr as *mut c_void) };
 159             self.cap = 0;
 160             self.ptr = 0 as *mut T;
 161         } else {
 162             unsafe {
 163                 // Overflow check is unnecessary as the vector is already at least this large.
 164                 self.ptr = realloc_raw(self.ptr as *mut u8, self.len * size_of::<T>()) as *mut T;
 165             }
 166             self.cap = self.len;
 167         }
 168     }
 169
 170     #[inline]
 171     pub fn pop(&mut self) -> Option<T> {
 172         if self.len == 0 {
 173             None
 174         } else {
 175             unsafe {
 176                 self.len -= 1;
 177                 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
 178             }
 179         }
 180     }
 181
 182     #[inline]
 183     pub fn push(&mut self, value: T) {
 184         if self.len == self.cap {
 185             if self.cap == 0 { self.cap += 2 }
 186             let old_size = self.cap * size_of::<T>();
 187             self.cap = self.cap * 2;
 188             let size = old_size * 2;
 189             if old_size > size { fail!("capacity overflow") }
 190             unsafe {
 191                 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
 192             }
 193         }
 194
 195         unsafe {
 196             let end = (self.ptr as *T).offset(self.len as int) as *mut T;
 197             move_val_init(&mut *end, value);
 198             self.len += 1;
 199         }
 200     }
 201
 202     pub fn truncate(&mut self, len: uint) {
 203         unsafe {
 204             let mut i = len;
 205             // drop any extra elements
 206             while i < self.len {
 207                 ptr::read(self.as_slice().unsafe_ref(i));
 208                 i += 1;
 209             }
 210         }
 211         self.len = len;
 212     }
 213
 214     #[inline]
 215     pub fn as_slice<'a>(&'a self) -> &'a [T] {
 216         let slice = Slice { data: self.ptr as *T, len: self.len };
 217         unsafe { transmute(slice) }
 218     }
 219
 220     #[inline]
 221     pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
 222         let slice = Slice { data: self.ptr as *T, len: self.len };
 223         unsafe { transmute(slice) }
 224     }
 225
 226     #[inline]
 227     pub fn move_iter(self) -> MoveItems<T> {
 228         unsafe {
 229             let iter = transmute(self.as_slice().iter());
 230             let ptr = self.ptr as *mut c_void;
 231             forget(self);
 232             MoveItems { allocation: ptr, iter: iter }
 233         }
 234     }
 235
 236     #[inline]
 237     pub unsafe fn set_len(&mut self, len: uint) {
 238         self.len = len;
 239     }
 240
 241     #[inline]
 242     pub fn get<'a>(&'a self, index: uint) -> &'a T {
 243         &self.as_slice()[index]
 244     }
 245
 246     #[inline]
 247     pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
 248         &mut self.as_mut_slice()[index]
 249     }
 250
 251     #[inline]
 252     pub fn iter<'a>(&'a self) -> Items<'a,T> {
 253         self.as_slice().iter()
 254     }
 255
 256     #[inline]
 257     pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
 258         self.as_mut_slice().mut_iter()
 259     }
 260
 261     #[inline]
 262     pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
 263         self.as_mut_slice().sort_by(compare)
 264     }
 265
 266     #[inline]
 267     pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
 268         self.as_slice().slice(start, end)
 269     }
 270
 271     #[inline]
 272     pub fn tail<'a>(&'a self) -> &'a [T] {
 273         self.as_slice().tail()
 274     }
 275
 276     #[inline]
 277     pub fn last<'a>(&'a self) -> Option<&'a T> {
 278         self.as_slice().last()
 279     }
 280
 281     #[inline]
 282     pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
 283         self.as_mut_slice().mut_last()
 284     }
 285
 286     #[inline]
 287     pub fn swap_remove(&mut self, index: uint) -> Option<T> {
 288         let length = self.len();
 289         if index < length - 1 {
 290             self.as_mut_slice().swap(index, length - 1);
 291         } else if index >= length {
 292             return None
 293         }
 294         self.pop()
 295     }
 296
 297     #[inline]
 298     pub fn unshift(&mut self, element: T) {
 299         self.insert(0, element)
 300     }
 301
 302     pub fn insert(&mut self, index: uint, element: T) {
 303         let len = self.len();
 304         assert!(index <= len);
 305         // space for the new element
 306         self.reserve(len + 1);
 307
 308         unsafe { // infallible
 309             // The spot to put the new value
 310             {
 311                 let slice = self.as_mut_slice();
 312                 let p = slice.as_mut_ptr().offset(index as int);
 313                 // Shift everything over to make space. (Duplicating the
 314                 // `index`th element into two consecutive places.)
 315                 ptr::copy_memory(p.offset(1), &*p, len - index);
 316                 // Write it in, overwriting the first copy of the `index`th
 317                 // element.
 318                 move_val_init(&mut *p, element);
 319             }
 320             self.set_len(len + 1);
 321         }
 322     }
 323
 324     #[inline]
 325     pub fn rev_iter<'a>(&'a self) -> RevItems<'a,T> {
 326         self.as_slice().rev_iter()
 327     }
 328
 329     #[inline]
 330     pub fn map<U>(&self, f: |t: &T| -> U) -> Vec<U> {
 331         self.iter().map(f).collect()
 332     }
 333
 334     pub fn push_all_move(&mut self, other: Vec<T>) {
 335         for element in other.move_iter() {
 336             self.push(element)
 337         }
 338     }
 339
 340     pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
 341         self.as_slice().slice_from(start)
 342     }
 343 }
 344
 345 #[inline]
 346 pub fn append<T:Clone>(mut first: Vec<T>, second: &[T]) -> Vec<T> {
 347     first.push_all(second);
 348     first
 349 }
 350
 351 #[unsafe_destructor]
 352 impl<T> Drop for Vec<T> {
 353     fn drop(&mut self) {
 354         unsafe {
 355             for x in self.as_mut_slice().iter() {
 356                 ptr::read(x);
 357             }
 358             free(self.ptr as *mut c_void)
 359         }
 360     }
 361 }
 362
 363 pub struct MoveItems<T> {
 364     priv allocation: *mut c_void, // the block of memory allocated for the vector
 365     priv iter: Items<'static, T>
 366 }
 367
 368 impl<T> Iterator<T> for MoveItems<T> {
 369     #[inline]
 370     fn next(&mut self) -> Option<T> {
 371         unsafe {
 372             self.iter.next().map(|x| ptr::read(x))
 373         }
 374     }
 375
 376     #[inline]
 377     fn size_hint(&self) -> (uint, Option<uint>) {
 378         self.iter.size_hint()
 379     }
 380 }
 381
 382 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
 383     #[inline]
 384     fn next_back(&mut self) -> Option<T> {
 385         unsafe {
 386             self.iter.next_back().map(|x| ptr::read(x))
 387         }
 388     }
 389 }
 390
 391 #[unsafe_destructor]
 392 impl<T> Drop for MoveItems<T> {
 393     fn drop(&mut self) {
 394         // destroy the remaining elements
 395         for _x in *self {}
 396         unsafe {
 397             free(self.allocation)
 398         }
 399     }
 400 }