src/libstd/at_vec.rs

   1 // Copyright 2012 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 //! Managed vectors
  12
  13 use clone::Clone;
  14 use container::Container;
  15 use iter::{Iterator, FromIterator};
  16 use option::{Option, Some, None};
  17 use mem;
  18 use unstable::raw::Repr;
  19 use vec::{ImmutableVector, OwnedVector};
  20
  21 /// Code for dealing with @-vectors. This is pretty incomplete, and
  22 /// contains a bunch of duplication from the code for ~-vectors.
  23
  24 /// Returns the number of elements the vector can hold without reallocating
  25 #[inline]
  26 pub fn capacity<T>(v: @[T]) -> uint {
  27     unsafe {
  28         let box = v.repr();
  29         (*box).data.alloc / mem::size_of::<T>()
  30     }
  31 }
  32
  33 /**
  34  * Builds a vector by calling a provided function with an argument
  35  * function that pushes an element to the back of a vector.
  36  * The initial size for the vector may optionally be specified
  37  *
  38  * # Arguments
  39  *
  40  * * size - An option, maybe containing initial size of the vector to reserve
  41  * * builder - A function that will construct the vector. It receives
  42  *             as an argument a function that will push an element
  43  *             onto the vector being constructed.
  44  */
  45 #[inline]
  46 pub fn build<A>(size: Option<uint>, builder: |push: |v: A||) -> @[A] {
  47     let mut vec = @[];
  48     unsafe { raw::reserve(&mut vec, size.unwrap_or(4)); }
  49     builder(|x| unsafe { raw::push(&mut vec, x) });
  50     vec
  51 }
  52
  53 // Appending
  54
  55 /// Iterates over the `rhs` vector, copying each element and appending it to the
  56 /// `lhs`. Afterwards, the `lhs` is then returned for use again.
  57 #[inline]
  58 pub fn append<T:Clone>(lhs: @[T], rhs: &[T]) -> @[T] {
  59     build(Some(lhs.len() + rhs.len()), |push| {
  60         for x in lhs.iter() {
  61             push((*x).clone());
  62         }
  63         for elt in rhs.iter() {
  64             push(elt.clone());
  65         }
  66     })
  67 }
  68
  69
  70 /// Apply a function to each element of a vector and return the results
  71 pub fn map<T, U>(v: &[T], f: |x: &T| -> U) -> @[U] {
  72     build(Some(v.len()), |push| {
  73         for elem in v.iter() {
  74             push(f(elem));
  75         }
  76     })
  77 }
  78
  79 /**
  80  * Creates and initializes an immutable vector.
  81  *
  82  * Creates an immutable vector of size `n_elts` and initializes the elements
  83  * to the value returned by the function `op`.
  84  */
  85 pub fn from_fn<T>(n_elts: uint, op: |uint| -> T) -> @[T] {
  86     build(Some(n_elts), |push| {
  87         let mut i: uint = 0u;
  88         while i < n_elts { push(op(i)); i += 1u; }
  89     })
  90 }
  91
  92 /**
  93  * Creates and initializes an immutable vector.
  94  *
  95  * Creates an immutable vector of size `n_elts` and initializes the elements
  96  * to the value `t`.
  97  */
  98 pub fn from_elem<T:Clone>(n_elts: uint, t: T) -> @[T] {
  99     build(Some(n_elts), |push| {
 100         let mut i: uint = 0u;
 101         while i < n_elts {
 102             push(t.clone());
 103             i += 1u;
 104         }
 105     })
 106 }
 107
 108 /**
 109  * Creates and initializes an immutable managed vector by moving all the
 110  * elements from an owned vector.
 111  */
 112 pub fn to_managed_move<T>(v: ~[T]) -> @[T] {
 113     let mut av = @[];
 114     unsafe {
 115         raw::reserve(&mut av, v.len());
 116         for x in v.move_iter() {
 117             raw::push(&mut av, x);
 118         }
 119         av
 120     }
 121 }
 122
 123 /**
 124  * Creates and initializes an immutable managed vector by copying all the
 125  * elements of a slice.
 126  */
 127 pub fn to_managed<T:Clone>(v: &[T]) -> @[T] {
 128     from_fn(v.len(), |i| v[i].clone())
 129 }
 130
 131 impl<T> Clone for @[T] {
 132     fn clone(&self) -> @[T] {
 133         *self
 134     }
 135 }
 136
 137 impl<A> FromIterator<A> for @[A] {
 138     fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> @[A] {
 139         let (lower, _) = iterator.size_hint();
 140         build(Some(lower), |push| {
 141             for x in *iterator {
 142                 push(x);
 143             }
 144         })
 145     }
 146 }
 147
 148 #[cfg(not(test))]
 149 #[allow(missing_doc)]
 150 pub mod traits {
 151     use at_vec::append;
 152     use clone::Clone;
 153     use ops::Add;
 154     use vec::Vector;
 155
 156     impl<'self,T:Clone, V: Vector<T>> Add<V,@[T]> for @[T] {
 157         #[inline]
 158         fn add(&self, rhs: &V) -> @[T] {
 159             append(*self, rhs.as_slice())
 160         }
 161     }
 162 }
 163
 164 #[cfg(test)]
 165 pub mod traits {}
 166
 167 #[allow(missing_doc)]
 168 pub mod raw {
 169     use at_vec::capacity;
 170     use cast;
 171     use cast::{transmute, transmute_copy};
 172     use ptr;
 173     use mem;
 174     use uint;
 175     use unstable::intrinsics::{move_val_init, TyDesc};
 176     use unstable::intrinsics;
 177     use unstable::raw::{Box, Vec};
 178
 179     /**
 180      * Sets the length of a vector
 181      *
 182      * This will explicitly set the size of the vector, without actually
 183      * modifying its buffers, so it is up to the caller to ensure that
 184      * the vector is actually the specified size.
 185      */
 186     #[inline]
 187     pub unsafe fn set_len<T>(v: &mut @[T], new_len: uint) {
 188         let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
 189         (*repr).data.fill = new_len * mem::size_of::<T>();
 190     }
 191
 192     /**
 193      * Pushes a new value onto this vector.
 194      */
 195     #[inline]
 196     pub unsafe fn push<T>(v: &mut @[T], initval: T) {
 197         let full = {
 198             let repr: *Box<Vec<T>> = cast::transmute_copy(v);
 199             (*repr).data.alloc > (*repr).data.fill
 200         };
 201         if full {
 202             push_fast(v, initval);
 203         } else {
 204             push_slow(v, initval);
 205         }
 206     }
 207
 208     #[inline] // really pretty please
 209     unsafe fn push_fast<T>(v: &mut @[T], initval: T) {
 210         let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
 211         let amt = v.len();
 212         (*repr).data.fill += mem::size_of::<T>();
 213         let p = ptr::offset(&(*repr).data.data as *T, amt as int) as *mut T;
 214         move_val_init(&mut(*p), initval);
 215     }
 216
 217     unsafe fn push_slow<T>(v: &mut @[T], initval: T) {
 218         reserve_at_least(v, v.len() + 1u);
 219         push_fast(v, initval);
 220     }
 221
 222     /**
 223      * Reserves capacity for exactly `n` elements in the given vector.
 224      *
 225      * If the capacity for `v` is already equal to or greater than the
 226      * requested capacity, then no action is taken.
 227      *
 228      * # Arguments
 229      *
 230      * * v - A vector
 231      * * n - The number of elements to reserve space for
 232      */
 233     pub unsafe fn reserve<T>(v: &mut @[T], n: uint) {
 234         // Only make the (slow) call into the runtime if we have to
 235         if capacity(*v) < n {
 236             let ptr: *mut *mut Box<Vec<()>> = transmute(v);
 237             let ty = intrinsics::get_tydesc::<T>();
 238             return reserve_raw(ty, ptr, n);
 239         }
 240     }
 241
 242     // Implementation detail. Shouldn't be public
 243     #[allow(missing_doc)]
 244     pub fn reserve_raw(ty: *TyDesc, ptr: *mut *mut Box<Vec<()>>, n: uint) {
 245         // check for `uint` overflow
 246         unsafe {
 247             if n > (**ptr).data.alloc / (*ty).size {
 248                 let alloc = n * (*ty).size;
 249                 let total_size = alloc + mem::size_of::<Vec<()>>();
 250                 if alloc / (*ty).size != n || total_size < alloc {
 251                     fail!("vector size is too large: {}", n);
 252                 }
 253                 (*ptr) = local_realloc(*ptr as *(), total_size) as *mut Box<Vec<()>>;
 254                 (**ptr).data.alloc = alloc;
 255             }
 256         }
 257
 258         fn local_realloc(ptr: *(), size: uint) -> *() {
 259             use rt::local::Local;
 260             use rt::task::Task;
 261
 262             Local::borrow(|task: &mut Task| {
 263                 task.heap.realloc(ptr as *mut Box<()>, size) as *()
 264             })
 265         }
 266     }
 267
 268     /**
 269      * Reserves capacity for at least `n` elements in the given vector.
 270      *
 271      * This function will over-allocate in order to amortize the
 272      * allocation costs in scenarios where the caller may need to
 273      * repeatedly reserve additional space.
 274      *
 275      * If the capacity for `v` is already equal to or greater than the
 276      * requested capacity, then no action is taken.
 277      *
 278      * # Arguments
 279      *
 280      * * v - A vector
 281      * * n - The number of elements to reserve space for
 282      */
 283     pub unsafe fn reserve_at_least<T>(v: &mut @[T], n: uint) {
 284         reserve(v, uint::next_power_of_two(n));
 285     }
 286 }
 287
 288 #[cfg(test)]
 289 mod test {
 290     use super::*;
 291     use prelude::*;
 292     use bh = extra::test::BenchHarness;
 293
 294     #[test]
 295     fn test() {
 296         // Some code that could use that, then:
 297         fn seq_range(lo: uint, hi: uint) -> @[uint] {
 298             build(None, |push| {
 299                 for i in range(lo, hi) {
 300                     push(i);
 301                 }
 302             })
 303         }
 304
 305         assert_eq!(seq_range(10, 15), @[10, 11, 12, 13, 14]);
 306         assert_eq!(from_fn(5, |x| x+1), @[1, 2, 3, 4, 5]);
 307         assert_eq!(from_elem(5, 3.14), @[3.14, 3.14, 3.14, 3.14, 3.14]);
 308     }
 309
 310     #[test]
 311     fn append_test() {
 312         assert_eq!(@[1,2,3] + &[4,5,6], @[1,2,3,4,5,6]);
 313     }
 314
 315     #[test]
 316     fn test_to_managed_move() {
 317         assert_eq!(to_managed_move::<int>(~[]), @[]);
 318         assert_eq!(to_managed_move(~[true]), @[true]);
 319         assert_eq!(to_managed_move(~[1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
 320         assert_eq!(to_managed_move(~[~"abc", ~"123"]), @[~"abc", ~"123"]);
 321         assert_eq!(to_managed_move(~[~[42]]), @[~[42]]);
 322     }
 323
 324     #[test]
 325     fn test_to_managed() {
 326         assert_eq!(to_managed::<int>([]), @[]);
 327         assert_eq!(to_managed([true]), @[true]);
 328         assert_eq!(to_managed([1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
 329         assert_eq!(to_managed([@"abc", @"123"]), @[@"abc", @"123"]);
 330         assert_eq!(to_managed([@[42]]), @[@[42]]);
 331     }
 332
 333     #[bench]
 334     fn bench_capacity(b: &mut bh) {
 335         let x = @[1, 2, 3];
 336         b.iter(|| {
 337             let _ = capacity(x);
 338         });
 339     }
 340
 341     #[bench]
 342     fn bench_build_sized(b: &mut bh) {
 343         let len = 64;
 344         b.iter(|| {
 345             build(Some(len), |push| for i in range(0, 1024) { push(i) });
 346         });
 347     }
 348
 349     #[bench]
 350     fn bench_build(b: &mut bh) {
 351         b.iter(|| {
 352             for i in range(0, 95) {
 353                 build(None, |push| push(i));
 354             }
 355         });
 356     }
 357
 358     #[bench]
 359     fn bench_append(b: &mut bh) {
 360         let lhs = @[7, ..128];
 361         let rhs = range(0, 256).to_owned_vec();
 362         b.iter(|| {
 363             let _ = append(lhs, rhs);
 364         })
 365     }
 366
 367     #[bench]
 368     fn bench_map(b: &mut bh) {
 369         let elts = range(0, 256).to_owned_vec();
 370         b.iter(|| {
 371             let _ = map(elts, |x| x*2);
 372         })
 373     }
 374
 375     #[bench]
 376     fn bench_from_fn(b: &mut bh) {
 377         b.iter(|| {
 378             let _ = from_fn(1024, |x| x);
 379         });
 380     }
 381
 382     #[bench]
 383     fn bench_from_elem(b: &mut bh) {
 384         b.iter(|| {
 385             let _ = from_elem(1024, 0u64);
 386         });
 387     }
 388
 389     #[bench]
 390     fn bench_to_managed_move(b: &mut bh) {
 391         b.iter(|| {
 392             let elts = range(0, 1024).to_owned_vec(); // yikes! can't move out of capture, though
 393             to_managed_move(elts);
 394         })
 395     }
 396
 397     #[bench]
 398     fn bench_to_managed(b: &mut bh) {
 399         let elts = range(0, 1024).to_owned_vec();
 400         b.iter(|| {
 401             let _ = to_managed(elts);
 402         });
 403     }
 404
 405     #[bench]
 406     fn bench_clone(b: &mut bh) {
 407         let elts = to_managed(range(0, 1024).to_owned_vec());
 408         b.iter(|| {
 409             let _ = elts.clone();
 410         });
 411     }
 412 }