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 iterator::{Iterator, range};
  16 use option::{Option, Some, None};
  17 use sys;
  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 / sys::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  * This version takes an initial size for the vector.
  37  *
  38  * # Arguments
  39  *
  40  * * size - An 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_sized<A>(size: uint, builder: &fn(push: &fn(v: A))) -> @[A] {
  47     let mut vec = @[];
  48     unsafe { raw::reserve(&mut vec, size); }
  49     builder(|x| unsafe { raw::push(&mut vec, x) });
  50     vec
  51 }
  52
  53 /**
  54  * Builds a vector by calling a provided function with an argument
  55  * function that pushes an element to the back of a vector.
  56  *
  57  * # Arguments
  58  *
  59  * * builder - A function that will construct the vector. It receives
  60  *             as an argument a function that will push an element
  61  *             onto the vector being constructed.
  62  */
  63 #[inline]
  64 pub fn build<A>(builder: &fn(push: &fn(v: A))) -> @[A] {
  65     build_sized(4, builder)
  66 }
  67
  68 /**
  69  * Builds a vector by calling a provided function with an argument
  70  * function that pushes an element to the back of a vector.
  71  * This version takes an initial size for the vector.
  72  *
  73  * # Arguments
  74  *
  75  * * size - An option, maybe containing initial size of the vector to reserve
  76  * * builder - A function that will construct the vector. It receives
  77  *             as an argument a function that will push an element
  78  *             onto the vector being constructed.
  79  */
  80 #[inline]
  81 pub fn build_sized_opt<A>(size: Option<uint>, builder: &fn(push: &fn(v: A))) -> @[A] {
  82     build_sized(size.unwrap_or_default(4), builder)
  83 }
  84
  85 // Appending
  86
  87 /// Iterates over the `rhs` vector, copying each element and appending it to the
  88 /// `lhs`. Afterwards, the `lhs` is then returned for use again.
  89 #[inline]
  90 pub fn append<T:Clone>(lhs: @[T], rhs: &[T]) -> @[T] {
  91     do build_sized(lhs.len() + rhs.len()) |push| {
  92         for x in lhs.iter() {
  93             push((*x).clone());
  94         }
  95         for i in range(0u, rhs.len()) {
  96             push(rhs[i].clone());
  97         }
  98     }
  99 }
 100
 101
 102 /// Apply a function to each element of a vector and return the results
 103 pub fn map<T, U>(v: &[T], f: &fn(x: &T) -> U) -> @[U] {
 104     do build_sized(v.len()) |push| {
 105         for elem in v.iter() {
 106             push(f(elem));
 107         }
 108     }
 109 }
 110
 111 /**
 112  * Creates and initializes an immutable vector.
 113  *
 114  * Creates an immutable vector of size `n_elts` and initializes the elements
 115  * to the value returned by the function `op`.
 116  */
 117 pub fn from_fn<T>(n_elts: uint, op: &fn(uint) -> T) -> @[T] {
 118     do build_sized(n_elts) |push| {
 119         let mut i: uint = 0u;
 120         while i < n_elts { push(op(i)); i += 1u; }
 121     }
 122 }
 123
 124 /**
 125  * Creates and initializes an immutable vector.
 126  *
 127  * Creates an immutable vector of size `n_elts` and initializes the elements
 128  * to the value `t`.
 129  */
 130 pub fn from_elem<T:Clone>(n_elts: uint, t: T) -> @[T] {
 131     do build_sized(n_elts) |push| {
 132         let mut i: uint = 0u;
 133         while i < n_elts {
 134             push(t.clone());
 135             i += 1u;
 136         }
 137     }
 138 }
 139
 140 /**
 141  * Creates and initializes an immutable managed vector by moving all the
 142  * elements from an owned vector.
 143  */
 144 pub fn to_managed_consume<T>(v: ~[T]) -> @[T] {
 145     let mut av = @[];
 146     unsafe {
 147         raw::reserve(&mut av, v.len());
 148         for x in v.consume_iter() {
 149             raw::push(&mut av, x);
 150         }
 151         av
 152     }
 153 }
 154
 155 /**
 156  * Creates and initializes an immutable managed vector by copying all the
 157  * elements of a slice.
 158  */
 159 pub fn to_managed<T:Clone>(v: &[T]) -> @[T] {
 160     from_fn(v.len(), |i| v[i].clone())
 161 }
 162
 163 impl<T> Clone for @[T] {
 164     fn clone(&self) -> @[T] {
 165         *self
 166     }
 167 }
 168
 169 #[cfg(not(test))]
 170 pub mod traits {
 171     use at_vec::append;
 172     use clone::Clone;
 173     use ops::Add;
 174     use vec::Vector;
 175
 176     impl<'self,T:Clone, V: Vector<T>> Add<V,@[T]> for @[T] {
 177         #[inline]
 178         fn add(&self, rhs: &V) -> @[T] {
 179             append(*self, rhs.as_slice())
 180         }
 181     }
 182 }
 183
 184 #[cfg(test)]
 185 pub mod traits {}
 186
 187 pub mod raw {
 188     use at_vec::capacity;
 189     use cast;
 190     use cast::{transmute, transmute_copy};
 191     use libc;
 192     use ptr;
 193     use sys;
 194     use uint;
 195     use unstable::intrinsics::{move_val_init, TyDesc};
 196     use unstable::intrinsics;
 197     use unstable::raw::{Box, Vec};
 198
 199     /**
 200      * Sets the length of a vector
 201      *
 202      * This will explicitly set the size of the vector, without actually
 203      * modifing its buffers, so it is up to the caller to ensure that
 204      * the vector is actually the specified size.
 205      */
 206     #[inline]
 207     pub unsafe fn set_len<T>(v: &mut @[T], new_len: uint) {
 208         let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
 209         (*repr).data.fill = new_len * sys::size_of::<T>();
 210     }
 211
 212     /**
 213      * Pushes a new value onto this vector.
 214      */
 215     #[inline]
 216     pub unsafe fn push<T>(v: &mut @[T], initval: T) {
 217         let full = {
 218             let repr: *Box<Vec<T>> = cast::transmute_copy(v);
 219             (*repr).data.alloc > (*repr).data.fill
 220         };
 221         if full {
 222             push_fast(v, initval);
 223         } else {
 224             push_slow(v, initval);
 225         }
 226     }
 227
 228     #[inline] // really pretty please
 229     unsafe fn push_fast<T>(v: &mut @[T], initval: T) {
 230         let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
 231         let amt = v.len();
 232         (*repr).data.fill += sys::size_of::<T>();
 233         let p = ptr::offset(&(*repr).data.data as *T, amt as int) as *mut T;
 234         move_val_init(&mut(*p), initval);
 235     }
 236
 237     unsafe fn push_slow<T>(v: &mut @[T], initval: T) {
 238         reserve_at_least(v, v.len() + 1u);
 239         push_fast(v, initval);
 240     }
 241
 242     /**
 243      * Reserves capacity for exactly `n` elements in the given vector.
 244      *
 245      * If the capacity for `v` is already equal to or greater than the
 246      * requested capacity, then no action is taken.
 247      *
 248      * # Arguments
 249      *
 250      * * v - A vector
 251      * * n - The number of elements to reserve space for
 252      */
 253     pub unsafe fn reserve<T>(v: &mut @[T], n: uint) {
 254         // Only make the (slow) call into the runtime if we have to
 255         if capacity(*v) < n {
 256             let ptr: *mut *mut Box<Vec<()>> = transmute(v);
 257             let ty = intrinsics::get_tydesc::<T>();
 258             // XXX transmute shouldn't be necessary
 259             let ty = cast::transmute(ty);
 260             return reserve_raw(ty, ptr, n);
 261         }
 262     }
 263
 264     // Implementation detail. Shouldn't be public
 265     #[allow(missing_doc)]
 266     pub fn reserve_raw(ty: *TyDesc, ptr: *mut *mut Box<Vec<()>>, n: uint) {
 267
 268         unsafe {
 269             let size_in_bytes = n * (*ty).size;
 270             if size_in_bytes > (**ptr).data.alloc {
 271                 let total_size = size_in_bytes + sys::size_of::<Vec<()>>();
 272                 (*ptr) = local_realloc(*ptr as *(), total_size) as *mut Box<Vec<()>>;
 273                 (**ptr).data.alloc = size_in_bytes;
 274             }
 275         }
 276
 277         fn local_realloc(ptr: *(), size: uint) -> *() {
 278             use rt;
 279             use rt::OldTaskContext;
 280             use rt::local::Local;
 281             use rt::task::Task;
 282
 283             if rt::context() == OldTaskContext {
 284                 unsafe {
 285                     return rust_local_realloc(ptr, size as libc::size_t);
 286                 }
 287
 288                 extern {
 289                     #[fast_ffi]
 290                     fn rust_local_realloc(ptr: *(), size: libc::size_t) -> *();
 291                 }
 292             } else {
 293                 do Local::borrow::<Task, *()> |task| {
 294                     task.heap.realloc(ptr as *libc::c_void, size) as *()
 295                 }
 296             }
 297         }
 298     }
 299
 300     /**
 301      * Reserves capacity for at least `n` elements in the given vector.
 302      *
 303      * This function will over-allocate in order to amortize the
 304      * allocation costs in scenarios where the caller may need to
 305      * repeatedly reserve additional space.
 306      *
 307      * If the capacity for `v` is already equal to or greater than the
 308      * requested capacity, then no action is taken.
 309      *
 310      * # Arguments
 311      *
 312      * * v - A vector
 313      * * n - The number of elements to reserve space for
 314      */
 315     pub unsafe fn reserve_at_least<T>(v: &mut @[T], n: uint) {
 316         reserve(v, uint::next_power_of_two(n));
 317     }
 318 }
 319
 320 #[cfg(test)]
 321 mod test {
 322     use super::*;
 323     use prelude::*;
 324
 325     #[test]
 326     fn test() {
 327         // Some code that could use that, then:
 328         fn seq_range(lo: uint, hi: uint) -> @[uint] {
 329             do build |push| {
 330                 for i in range(lo, hi) {
 331                     push(i);
 332                 }
 333             }
 334         }
 335
 336         assert_eq!(seq_range(10, 15), @[10, 11, 12, 13, 14]);
 337         assert_eq!(from_fn(5, |x| x+1), @[1, 2, 3, 4, 5]);
 338         assert_eq!(from_elem(5, 3.14), @[3.14, 3.14, 3.14, 3.14, 3.14]);
 339     }
 340
 341     #[test]
 342     fn append_test() {
 343         assert_eq!(@[1,2,3] + &[4,5,6], @[1,2,3,4,5,6]);
 344     }
 345
 346     #[test]
 347     fn test_to_managed_consume() {
 348         assert_eq!(to_managed_consume::<int>(~[]), @[]);
 349         assert_eq!(to_managed_consume(~[true]), @[true]);
 350         assert_eq!(to_managed_consume(~[1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
 351         assert_eq!(to_managed_consume(~[~"abc", ~"123"]), @[~"abc", ~"123"]);
 352         assert_eq!(to_managed_consume(~[~[42]]), @[~[42]]);
 353     }
 354
 355     #[test]
 356     fn test_to_managed() {
 357         assert_eq!(to_managed::<int>([]), @[]);
 358         assert_eq!(to_managed([true]), @[true]);
 359         assert_eq!(to_managed([1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
 360         assert_eq!(to_managed([@"abc", @"123"]), @[@"abc", @"123"]);
 361         assert_eq!(to_managed([@[42]]), @[@[42]]);
 362     }
 363 }