(index<- ) ./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;
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 * 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: &fn(push: &fn(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 do 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: &fn(x: &T) -> U) -> @[U] {
72 do 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: &fn(uint) -> T) -> @[T] {
86 do 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 do 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 #[cfg(not(test))]
138 #[allow(missing_doc)]
139 pub mod traits {
140 use at_vec::append;
141 use clone::Clone;
142 use ops::Add;
143 use vec::Vector;
144
145 impl<'self,T:Clone, V: Vector<T>> Add<V,@[T]> for @[T] {
146 #[inline]
147 fn add(&self, rhs: &V) -> @[T] {
148 append(*self, rhs.as_slice())
149 }
150 }
151 }
152
153 #[cfg(test)]
154 pub mod traits {}
155
156 #[allow(missing_doc)]
157 pub mod raw {
158 use at_vec::capacity;
159 use cast;
160 use cast::{transmute, transmute_copy};
161 use libc;
162 use ptr;
163 use sys;
164 use uint;
165 use unstable::intrinsics::{move_val_init, TyDesc};
166 use unstable::intrinsics;
167 use unstable::raw::{Box, Vec};
168
169 /**
170 * Sets the length of a vector
171 *
172 * This will explicitly set the size of the vector, without actually
173 * modifying its buffers, so it is up to the caller to ensure that
174 * the vector is actually the specified size.
175 */
176 #[inline]
177 pub unsafe fn set_len<T>(v: &mut @[T], new_len: uint) {
178 let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
179 (*repr).data.fill = new_len * sys::size_of::<T>();
180 }
181
182 /**
183 * Pushes a new value onto this vector.
184 */
185 #[inline]
186 pub unsafe fn push<T>(v: &mut @[T], initval: T) {
187 let full = {
188 let repr: *Box<Vec<T>> = cast::transmute_copy(v);
189 (*repr).data.alloc > (*repr).data.fill
190 };
191 if full {
192 push_fast(v, initval);
193 } else {
194 push_slow(v, initval);
195 }
196 }
197
198 #[inline] // really pretty please
199 unsafe fn push_fast<T>(v: &mut @[T], initval: T) {
200 let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
201 let amt = v.len();
202 (*repr).data.fill += sys::size_of::<T>();
203 let p = ptr::offset(&(*repr).data.data as *T, amt as int) as *mut T;
204 move_val_init(&mut(*p), initval);
205 }
206
207 unsafe fn push_slow<T>(v: &mut @[T], initval: T) {
208 reserve_at_least(v, v.len() + 1u);
209 push_fast(v, initval);
210 }
211
212 /**
213 * Reserves capacity for exactly `n` elements in the given vector.
214 *
215 * If the capacity for `v` is already equal to or greater than the
216 * requested capacity, then no action is taken.
217 *
218 * # Arguments
219 *
220 * * v - A vector
221 * * n - The number of elements to reserve space for
222 */
223 pub unsafe fn reserve<T>(v: &mut @[T], n: uint) {
224 // Only make the (slow) call into the runtime if we have to
225 if capacity(*v) < n {
226 let ptr: *mut *mut Box<Vec<()>> = transmute(v);
227 let ty = intrinsics::get_tydesc::<T>();
228 return reserve_raw(ty, ptr, n);
229 }
230 }
231
232 // Implementation detail. Shouldn't be public
233 #[allow(missing_doc)]
234 pub fn reserve_raw(ty: *TyDesc, ptr: *mut *mut Box<Vec<()>>, n: uint) {
235 // check for `uint` overflow
236 unsafe {
237 if n > (**ptr).data.alloc / (*ty).size {
238 let alloc = n * (*ty).size;
239 let total_size = alloc + sys::size_of::<Vec<()>>();
240 if alloc / (*ty).size != n || total_size < alloc {
241 fail2!("vector size is too large: {}", n);
242 }
243 (*ptr) = local_realloc(*ptr as *(), total_size) as *mut Box<Vec<()>>;
244 (**ptr).data.alloc = alloc;
245 }
246 }
247
248 fn local_realloc(ptr: *(), size: uint) -> *() {
249 use rt::local::Local;
250 use rt::task::Task;
251
252 do Local::borrow |task: &mut Task| {
253 task.heap.realloc(ptr as *libc::c_void, size) as *()
254 }
255 }
256 }
257
258 /**
259 * Reserves capacity for at least `n` elements in the given vector.
260 *
261 * This function will over-allocate in order to amortize the
262 * allocation costs in scenarios where the caller may need to
263 * repeatedly reserve additional space.
264 *
265 * If the capacity for `v` is already equal to or greater than the
266 * requested capacity, then no action is taken.
267 *
268 * # Arguments
269 *
270 * * v - A vector
271 * * n - The number of elements to reserve space for
272 */
273 pub unsafe fn reserve_at_least<T>(v: &mut @[T], n: uint) {
274 reserve(v, uint::next_power_of_two(n));
275 }
276 }
277
278 #[cfg(test)]
279 mod test {
280 use super::*;
281 use prelude::*;
282 use bh = extra::test::BenchHarness;
283
284 #[test]
285 fn test() {
286 // Some code that could use that, then:
287 fn seq_range(lo: uint, hi: uint) -> @[uint] {
288 do build(None) |push| {
289 for i in range(lo, hi) {
290 push(i);
291 }
292 }
293 }
294
295 assert_eq!(seq_range(10, 15), @[10, 11, 12, 13, 14]);
296 assert_eq!(from_fn(5, |x| x+1), @[1, 2, 3, 4, 5]);
297 assert_eq!(from_elem(5, 3.14), @[3.14, 3.14, 3.14, 3.14, 3.14]);
298 }
299
300 #[test]
301 fn append_test() {
302 assert_eq!(@[1,2,3] + &[4,5,6], @[1,2,3,4,5,6]);
303 }
304
305 #[test]
306 fn test_to_managed_move() {
307 assert_eq!(to_managed_move::<int>(~[]), @[]);
308 assert_eq!(to_managed_move(~[true]), @[true]);
309 assert_eq!(to_managed_move(~[1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
310 assert_eq!(to_managed_move(~[~"abc", ~"123"]), @[~"abc", ~"123"]);
311 assert_eq!(to_managed_move(~[~[42]]), @[~[42]]);
312 }
313
314 #[test]
315 fn test_to_managed() {
316 assert_eq!(to_managed::<int>([]), @[]);
317 assert_eq!(to_managed([true]), @[true]);
318 assert_eq!(to_managed([1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
319 assert_eq!(to_managed([@"abc", @"123"]), @[@"abc", @"123"]);
320 assert_eq!(to_managed([@[42]]), @[@[42]]);
321 }
322
323 #[bench]
324 fn bench_capacity(b: &mut bh) {
325 let x = @[1, 2, 3];
326 do b.iter {
327 capacity(x);
328 }
329 }
330
331 #[bench]
332 fn bench_build_sized(b: &mut bh) {
333 let len = 64;
334 do b.iter {
335 build(Some(len), |push| for i in range(0, 1024) { push(i) });
336 }
337 }
338
339 #[bench]
340 fn bench_build(b: &mut bh) {
341 do b.iter {
342 for i in range(0, 95) {
343 build(None, |push| push(i));
344 }
345 }
346 }
347
348 #[bench]
349 fn bench_append(b: &mut bh) {
350 let lhs = @[7, ..128];
351 let rhs = range(0, 256).to_owned_vec();
352 do b.iter {
353 append(lhs, rhs);
354 }
355 }
356
357 #[bench]
358 fn bench_map(b: &mut bh) {
359 let elts = range(0, 256).to_owned_vec();
360 do b.iter {
361 map(elts, |x| x*2);
362 }
363 }
364
365 #[bench]
366 fn bench_from_fn(b: &mut bh) {
367 do b.iter {
368 from_fn(1024, |x| x);
369 }
370 }
371
372 #[bench]
373 fn bench_from_elem(b: &mut bh) {
374 do b.iter {
375 from_elem(1024, 0u64);
376 }
377 }
378
379 #[bench]
380 fn bench_to_managed_move(b: &mut bh) {
381 do b.iter {
382 let elts = range(0, 1024).to_owned_vec(); // yikes! can't move out of capture, though
383 to_managed_move(elts);
384 }
385 }
386
387 #[bench]
388 fn bench_to_managed(b: &mut bh) {
389 let elts = range(0, 1024).to_owned_vec();
390 do b.iter {
391 to_managed(elts);
392 }
393 }
394
395 #[bench]
396 fn bench_clone(b: &mut bh) {
397 let elts = to_managed(range(0, 1024).to_owned_vec());
398 do b.iter {
399 elts.clone();
400 }
401 }
402 }
libstd/at_vec.rs:223:4-223:4 -fn- definition:
pub unsafe fn reserve<T>(v: &mut @[T], n: uint) {
// Only make the (slow) call into the runtime if we have to
references:-48: unsafe { raw::reserve(&mut vec, size.unwrap_or(4)); }
274: reserve(v, uint::next_power_of_two(n));
115: raw::reserve(&mut av, v.len());
libstd/at_vec.rs:186:4-186:4 -fn- definition:
pub unsafe fn push<T>(v: &mut @[T], initval: T) {
let full = {
references:-49: builder(|x| unsafe { raw::push(&mut vec, x) });
117: raw::push(&mut av, x);
libstd/at_vec.rs:57:10-57:10 -fn- definition:
#[inline]
pub fn append<T:Clone>(lhs: @[T], rhs: &[T]) -> @[T] {
references:-148: append(*self, rhs.as_slice())
libstd/at_vec.rs:45:10-45:10 -fn- definition:
#[inline]
pub fn build<A>(size: Option<uint>, builder: &fn(push: &fn(v: A))) -> @[A] {
references:-99: do build(Some(n_elts)) |push| {
72: do build(Some(v.len())) |push| {
59: do build(Some(lhs.len() + rhs.len())) |push| {
86: do build(Some(n_elts)) |push| {
libstd/at_vec.rs:84:4-84:4 -fn- definition:
*/
pub fn from_fn<T>(n_elts: uint, op: &fn(uint) -> T) -> @[T] {
references:-128: from_fn(v.len(), |i| v[i].clone())
libstd/at_vec.rs:248:8-248:8 -fn- definition:
fn local_realloc(ptr: *(), size: uint) -> *() {
use rt::local::Local;
references:-243: (*ptr) = local_realloc(*ptr as *(), total_size) as *mut Box<Vec<()>>;
libstd/at_vec.rs:199:4-199:4 -fn- definition:
unsafe fn push_fast<T>(v: &mut @[T], initval: T) {
let repr: *mut Box<Vec<T>> = cast::transmute_copy(v);
references:-192: push_fast(v, initval);
209: push_fast(v, initval);
libstd/at_vec.rs:273:4-273:4 -fn- definition:
pub unsafe fn reserve_at_least<T>(v: &mut @[T], n: uint) {
reserve(v, uint::next_power_of_two(n));
references:-208: reserve_at_least(v, v.len() + 1u);
libstd/at_vec.rs:234:4-234:4 -fn- definition:
pub fn reserve_raw(ty: *TyDesc, ptr: *mut *mut Box<Vec<()>>, n: uint) {
// check for `uint` overflow
references:-228: return reserve_raw(ty, ptr, n);
libstd/vec.rs:
1406: ::at_vec::raw::reserve_raw(td, ptr, n);
libstd/at_vec.rs:207:4-207:4 -fn- definition:
unsafe fn push_slow<T>(v: &mut @[T], initval: T) {
reserve_at_least(v, v.len() + 1u);
references:-194: push_slow(v, initval);
libstd/at_vec.rs:126:4-126:4 -fn- definition:
*/
pub fn to_managed<T:Clone>(v: &[T]) -> @[T] {
references:-libstd/str.rs:
2114: cast::transmute(at_vec::to_managed(*v))
libstd/at_vec.rs:25:10-25:10 -fn- definition:
#[inline]
pub fn capacity<T>(v: @[T]) -> uint {
references:-225: if capacity(*v) < n {