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.
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.
14 use container::Container;
15 use iterator::Iterator;
16 use option::{Option, Some, None};
18 use unstable::raw::Repr;
19 use vec::{ImmutableVector, OwnedVector};
21 /// Code for dealing with @-vectors. This is pretty incomplete, and
22 /// contains a bunch of duplication from the code for ~-vectors.
24 /// Returns the number of elements the vector can hold without reallocating
26 pub fn capacity<T>(v: @[T]) -> uint {
29 (*box).data.alloc / sys::size_of::<T>()
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.
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.
46 pub fn build_sized<A>(size: uint, builder: &fn(push: &fn(v: A))) -> @[A] {
48 unsafe { raw::reserve(&mut vec, size); }
49 builder(|x| unsafe { raw::push(&mut vec, x) });
54 * Builds a vector by calling a provided function with an argument
55 * function that pushes an element to the back of a vector.
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.
64 pub fn build<A>(builder: &fn(push: &fn(v: A))) -> @[A] {
65 build_sized(4, builder)
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.
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.
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)
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.
90 pub fn append<T:Clone>(lhs: @[T], rhs: &[T]) -> @[T] {
91 do build_sized(lhs.len() + rhs.len()) |push| {
95 for elt in rhs.iter() {
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() {
112 * Creates and initializes an immutable vector.
114 * Creates an immutable vector of size `n_elts` and initializes the elements
115 * to the value returned by the function `op`.
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; }
125 * Creates and initializes an immutable vector.
127 * Creates an immutable vector of size `n_elts` and initializes the elements
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;
141 * Creates and initializes an immutable managed vector by moving all the
142 * elements from an owned vector.
144 pub fn to_managed_consume<T>(v: ~[T]) -> @[T] {
147 raw::reserve(&mut av, v.len());
148 for x in v.consume_iter() {
149 raw::push(&mut av, x);
156 * Creates and initializes an immutable managed vector by copying all the
157 * elements of a slice.
159 pub fn to_managed<T:Clone>(v: &[T]) -> @[T] {
160 from_fn(v.len(), |i| v[i].clone())
163 impl<T> Clone for @[T] {
164 fn clone(&self) -> @[T] {
176 impl<'self,T:Clone, V: Vector<T>> Add<V,@[T]> for @[T] {
178 fn add(&self, rhs: &V) -> @[T] {
179 append(*self, rhs.as_slice())
188 use at_vec::capacity;
190 use cast::{transmute, transmute_copy};
195 use unstable::intrinsics::{move_val_init, TyDesc};
196 use unstable::intrinsics;
197 use unstable::raw::{Box, Vec};
200 * Sets the length of a vector
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.
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>();
213 * Pushes a new value onto this vector.
216 pub unsafe fn push<T>(v: &mut @[T], initval: T) {
218 let repr: *Box<Vec<T>> = cast::transmute_copy(v);
219 (*repr).data.alloc > (*repr).data.fill
222 push_fast(v, initval);
224 push_slow(v, initval);
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);
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);
237 unsafe fn push_slow<T>(v: &mut @[T], initval: T) {
238 reserve_at_least(v, v.len() + 1u);
239 push_fast(v, initval);
243 * Reserves capacity for exactly `n` elements in the given vector.
245 * If the capacity for `v` is already equal to or greater than the
246 * requested capacity, then no action is taken.
251 * * n - The number of elements to reserve space for
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);
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) {
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;
277 fn local_realloc(ptr: *(), size: uint) -> *() {
279 use rt::OldTaskContext;
280 use rt::local::Local;
283 if rt::context() == OldTaskContext {
285 return rust_local_realloc(ptr, size as libc::size_t);
290 fn rust_local_realloc(ptr: *(), size: libc::size_t) -> *();
293 do Local::borrow::<Task, *()> |task| {
294 task.heap.realloc(ptr as *libc::c_void, size) as *()
301 * Reserves capacity for at least `n` elements in the given vector.
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.
307 * If the capacity for `v` is already equal to or greater than the
308 * requested capacity, then no action is taken.
313 * * n - The number of elements to reserve space for
315 pub unsafe fn reserve_at_least<T>(v: &mut @[T], n: uint) {
316 reserve(v, uint::next_power_of_two(n));
327 // Some code that could use that, then:
328 fn seq_range(lo: uint, hi: uint) -> @[uint] {
330 for i in range(lo, hi) {
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]);
343 assert_eq!(@[1,2,3] + &[4,5,6], @[1,2,3,4,5,6]);
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]]);
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]]);