(index<- ) ./libstd/vec.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri May 9 13:02:28 2014
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 //! An owned, growable vector.
12
13 use cast::{forget, transmute};
14 use clone::Clone;
15 use cmp::{Ord, Eq, Ordering, TotalEq, TotalOrd};
16 use container::{Container, Mutable};
17 use default::Default;
18 use fmt;
19 use iter::{DoubleEndedIterator, FromIterator, Extendable, Iterator, range};
20 use libc::{free, c_void};
21 use mem::{size_of, move_val_init};
22 use mem;
23 use num;
24 use num::{CheckedMul, CheckedAdd};
25 use ops::{Add, Drop};
26 use option::{None, Option, Some, Expect};
27 use ptr::RawPtr;
28 use ptr;
29 use rt::global_heap::{malloc_raw, realloc_raw};
30 use raw::Slice;
31 use RawVec = raw::Vec;
32 use slice::{ImmutableEqVector, ImmutableVector, Items, MutItems, MutableVector};
33 use slice::{MutableTotalOrdVector, OwnedVector, Vector};
34 use slice::{MutableVectorAllocating};
35
36 /// An owned, growable vector.
37 ///
38 /// # Examples
39 ///
40 /// ```rust
41 /// # use std::vec::Vec;
42 /// let mut vec = Vec::new();
43 /// vec.push(1);
44 /// vec.push(2);
45 ///
46 /// assert_eq!(vec.len(), 2);
47 /// assert_eq!(vec.get(0), &1);
48 ///
49 /// assert_eq!(vec.pop(), Some(2));
50 /// assert_eq!(vec.len(), 1);
51 /// ```
52 ///
53 /// The `vec!` macro is provided to make initialization more convenient:
54 ///
55 /// ```rust
56 /// let mut vec = vec!(1, 2, 3);
57 /// vec.push(4);
58 /// assert_eq!(vec, vec!(1, 2, 3, 4));
59 /// ```
60 #[unsafe_no_drop_flag]
61 pub struct Vec<T> {
62 len: uint,
63 cap: uint,
64 ptr: *mut T
65 }
66
67 impl<T> Vec<T> {
68 /// Constructs a new, empty `Vec`.
69 ///
70 /// The vector will not allocate until elements are pushed onto it.
71 ///
72 /// # Example
73 ///
74 /// ```rust
75 /// # use std::vec::Vec;
76 /// let mut vec: Vec<int> = Vec::new();
77 /// ```
78 #[inline]
79 pub fn new() -> Vec<T> {
80 Vec { len: 0, cap: 0, ptr: 0 as *mut T }
81 }
82
83 /// Constructs a new, empty `Vec` with the specified capacity.
84 ///
85 /// The vector will be able to hold exactly `capacity` elements without
86 /// reallocating. If `capacity` is 0, the vector will not allocate.
87 ///
88 /// # Example
89 ///
90 /// ```rust
91 /// # use std::vec::Vec;
92 /// let vec: Vec<int> = Vec::with_capacity(10);
93 /// ```
94 pub fn with_capacity(capacity: uint) -> Vec<T> {
95 if capacity == 0 {
96 Vec::new()
97 } else {
98 let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
99 let ptr = unsafe { malloc_raw(size) };
100 Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
101 }
102 }
103
104 /// Creates and initializes a `Vec`.
105 ///
106 /// Creates a `Vec` of size `length` and initializes the elements to the
107 /// value returned by the closure `op`.
108 ///
109 /// # Example
110 ///
111 /// ```rust
112 /// # use std::vec::Vec;
113 /// let vec = Vec::from_fn(3, |idx| idx * 2);
114 /// assert_eq!(vec, vec!(0, 2, 4));
115 /// ```
116 pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
117 unsafe {
118 let mut xs = Vec::with_capacity(length);
119 while xs.len < length {
120 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), op(xs.len));
121 xs.len += 1;
122 }
123 xs
124 }
125 }
126
127 /// Create a `Vec<T>` directly from the raw constituents.
128 ///
129 /// This is highly unsafe:
130 ///
131 /// - if `ptr` is null, then `length` and `capacity` should be 0
132 /// - `ptr` must point to an allocation of size `capacity`
133 /// - there must be `length` valid instances of type `T` at the
134 /// beginning of that allocation
135 /// - `ptr` must be allocated by the default `Vec` allocator
136 pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut T) -> Vec<T> {
137 Vec { len: length, cap: capacity, ptr: ptr }
138 }
139
140 /// Consumes the `Vec`, partitioning it based on a predicate.
141 ///
142 /// Partitions the `Vec` into two `Vec`s `(A,B)`, where all elements of `A`
143 /// satisfy `f` and all elements of `B` do not. The order of elements is
144 /// preserved.
145 ///
146 /// # Example
147 ///
148 /// ```rust
149 /// let vec = vec!(1, 2, 3, 4);
150 /// let (even, odd) = vec.partition(|&n| n % 2 == 0);
151 /// assert_eq!(even, vec!(2, 4));
152 /// assert_eq!(odd, vec!(1, 3));
153 /// ```
154 #[inline]
155 pub fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
156 let mut lefts = Vec::new();
157 let mut rights = Vec::new();
158
159 for elt in self.move_iter() {
160 if f(&elt) {
161 lefts.push(elt);
162 } else {
163 rights.push(elt);
164 }
165 }
166
167 (lefts, rights)
168 }
169 }
170
171 impl<T: Clone> Vec<T> {
172 /// Iterates over the `second` vector, copying each element and appending it to
173 /// the `first`. Afterwards, the `first` is then returned for use again.
174 ///
175 /// # Example
176 ///
177 /// ```rust
178 /// let vec = vec!(1, 2);
179 /// let vec = vec.append([3, 4]);
180 /// assert_eq!(vec, vec!(1, 2, 3, 4));
181 /// ```
182 #[inline]
183 pub fn append(mut self, second: &[T]) -> Vec<T> {
184 self.push_all(second);
185 self
186 }
187
188 /// Constructs a `Vec` by cloning elements of a slice.
189 ///
190 /// # Example
191 ///
192 /// ```rust
193 /// # use std::vec::Vec;
194 /// let slice = [1, 2, 3];
195 /// let vec = Vec::from_slice(slice);
196 /// ```
197 pub fn from_slice(values: &[T]) -> Vec<T> {
198 values.iter().map(|x| x.clone()).collect()
199 }
200
201 /// Constructs a `Vec` with copies of a value.
202 ///
203 /// Creates a `Vec` with `length` copies of `value`.
204 ///
205 /// # Example
206 /// ```rust
207 /// # use std::vec::Vec;
208 /// let vec = Vec::from_elem(3, "hi");
209 /// println!("{}", vec); // prints [hi, hi, hi]
210 /// ```
211 pub fn from_elem(length: uint, value: T) -> Vec<T> {
212 unsafe {
213 let mut xs = Vec::with_capacity(length);
214 while xs.len < length {
215 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), value.clone());
216 xs.len += 1;
217 }
218 xs
219 }
220 }
221
222 /// Appends all elements in a slice to the `Vec`.
223 ///
224 /// Iterates over the slice `other`, clones each element, and then appends
225 /// it to this `Vec`. The `other` vector is traversed in-order.
226 ///
227 /// # Example
228 ///
229 /// ```rust
230 /// let mut vec = vec!(1);
231 /// vec.push_all([2, 3, 4]);
232 /// assert_eq!(vec, vec!(1, 2, 3, 4));
233 /// ```
234 #[inline]
235 pub fn push_all(&mut self, other: &[T]) {
236 self.extend(other.iter().map(|e| e.clone()));
237 }
238
239 /// Grows the `Vec` in-place.
240 ///
241 /// Adds `n` copies of `value` to the `Vec`.
242 ///
243 /// # Example
244 ///
245 /// ```rust
246 /// let mut vec = vec!("hello");
247 /// vec.grow(2, &("world"));
248 /// assert_eq!(vec, vec!("hello", "world", "world"));
249 /// ```
250 pub fn grow(&mut self, n: uint, value: &T) {
251 let new_len = self.len() + n;
252 self.reserve(new_len);
253 let mut i: uint = 0u;
254
255 while i < n {
256 self.push((*value).clone());
257 i += 1u;
258 }
259 }
260
261 /// Sets the value of a vector element at a given index, growing the vector
262 /// as needed.
263 ///
264 /// Sets the element at position `index` to `value`. If `index` is past the
265 /// end of the vector, expands the vector by replicating `initval` to fill
266 /// the intervening space.
267 ///
268 /// # Example
269 ///
270 /// ```rust
271 /// let mut vec = vec!("a", "b", "c");
272 /// vec.grow_set(1, &("fill"), "d");
273 /// vec.grow_set(4, &("fill"), "e");
274 /// assert_eq!(vec, vec!("a", "d", "c", "fill", "e"));
275 /// ```
276 pub fn grow_set(&mut self, index: uint, initval: &T, value: T) {
277 let l = self.len();
278 if index >= l {
279 self.grow(index - l + 1u, initval);
280 }
281 *self.get_mut(index) = value;
282 }
283
284 /// Partitions a vector based on a predicate.
285 ///
286 /// Clones the elements of the vector, partitioning them into two `Vec`s
287 /// `(A,B)`, where all elements of `A` satisfy `f` and all elements of `B`
288 /// do not. The order of elements is preserved.
289 ///
290 /// # Example
291 ///
292 /// ```rust
293 /// let vec = vec!(1, 2, 3, 4);
294 /// let (even, odd) = vec.partitioned(|&n| n % 2 == 0);
295 /// assert_eq!(even, vec!(2, 4));
296 /// assert_eq!(odd, vec!(1, 3));
297 /// ```
298 pub fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
299 let mut lefts = Vec::new();
300 let mut rights = Vec::new();
301
302 for elt in self.iter() {
303 if f(elt) {
304 lefts.push(elt.clone());
305 } else {
306 rights.push(elt.clone());
307 }
308 }
309
310 (lefts, rights)
311 }
312 }
313
314 impl<T:Clone> Clone for Vec<T> {
315 fn clone(&self) -> Vec<T> {
316 let len = self.len;
317 let mut vector = Vec::with_capacity(len);
318 // Unsafe code so this can be optimised to a memcpy (or something
319 // similarly fast) when T is Copy. LLVM is easily confused, so any
320 // extra operations during the loop can prevent this optimisation
321 {
322 let this_slice = self.as_slice();
323 while vector.len < len {
324 unsafe {
325 mem::move_val_init(
326 vector.as_mut_slice().unsafe_mut_ref(vector.len),
327 this_slice.unsafe_ref(vector.len).clone());
328 }
329 vector.len += 1;
330 }
331 }
332 vector
333 }
334
335 fn clone_from(&mut self, other: &Vec<T>) {
336 // drop anything in self that will not be overwritten
337 if self.len() > other.len() {
338 self.truncate(other.len())
339 }
340
341 // reuse the contained values' allocations/resources.
342 for (place, thing) in self.mut_iter().zip(other.iter()) {
343 place.clone_from(thing)
344 }
345
346 // self.len <= other.len due to the truncate above, so the
347 // slice here is always in-bounds.
348 let len = self.len();
349 self.extend(other.slice_from(len).iter().map(|x| x.clone()));
350 }
351 }
352
353 impl<T> FromIterator<T> for Vec<T> {
354 fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
355 let (lower, _) = iterator.size_hint();
356 let mut vector = Vec::with_capacity(lower);
357 for element in iterator {
358 vector.push(element)
359 }
360 vector
361 }
362 }
363
364 impl<T> Extendable<T> for Vec<T> {
365 fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
366 let (lower, _) = iterator.size_hint();
367 self.reserve_additional(lower);
368 for element in iterator {
369 self.push(element)
370 }
371 }
372 }
373
374 impl<T: Eq> Eq for Vec<T> {
375 #[inline]
376 fn eq(&self, other: &Vec<T>) -> bool {
377 self.as_slice() == other.as_slice()
378 }
379 }
380
381 impl<T: Ord> Ord for Vec<T> {
382 #[inline]
383 fn lt(&self, other: &Vec<T>) -> bool {
384 self.as_slice() < other.as_slice()
385 }
386 }
387
388 impl<T: TotalEq> TotalEq for Vec<T> {}
389
390 impl<T: TotalOrd> TotalOrd for Vec<T> {
391 #[inline]
392 fn cmp(&self, other: &Vec<T>) -> Ordering {
393 self.as_slice().cmp(&other.as_slice())
394 }
395 }
396
397 impl<T> Container for Vec<T> {
398 #[inline]
399 fn len(&self) -> uint {
400 self.len
401 }
402 }
403
404 impl<T> Vec<T> {
405 /// Returns the number of elements the vector can hold without
406 /// reallocating.
407 ///
408 /// # Example
409 ///
410 /// ```rust
411 /// # use std::vec::Vec;
412 /// let vec: Vec<int> = Vec::with_capacity(10);
413 /// assert_eq!(vec.capacity(), 10);
414 /// ```
415 #[inline]
416 pub fn capacity(&self) -> uint {
417 self.cap
418 }
419
420 /// Reserves capacity for at least `n` additional elements in the given
421 /// vector.
422 ///
423 /// # Failure
424 ///
425 /// Fails if the new capacity overflows `uint`.
426 ///
427 /// # Example
428 ///
429 /// ```rust
430 /// # use std::vec::Vec;
431 /// let mut vec: Vec<int> = vec!(1);
432 /// vec.reserve_additional(10);
433 /// assert!(vec.capacity() >= 11);
434 /// ```
435 pub fn reserve_additional(&mut self, extra: uint) {
436 if self.cap - self.len < extra {
437 match self.len.checked_add(&extra) {
438 None => fail!("Vec::reserve_additional: `uint` overflow"),
439 Some(new_cap) => self.reserve(new_cap)
440 }
441 }
442 }
443
444 /// Reserves capacity for at least `n` elements in the given vector.
445 ///
446 /// This function will over-allocate in order to amortize the allocation
447 /// costs in scenarios where the caller may need to repeatedly reserve
448 /// additional space.
449 ///
450 /// If the capacity for `self` is already equal to or greater than the
451 /// requested capacity, then no action is taken.
452 ///
453 /// # Example
454 ///
455 /// ```rust
456 /// let mut vec = vec!(1, 2, 3);
457 /// vec.reserve(10);
458 /// assert!(vec.capacity() >= 10);
459 /// ```
460 pub fn reserve(&mut self, capacity: uint) {
461 if capacity >= self.len {
462 self.reserve_exact(num::next_power_of_two(capacity))
463 }
464 }
465
466 /// Reserves capacity for exactly `capacity` elements in the given vector.
467 ///
468 /// If the capacity for `self` is already equal to or greater than the
469 /// requested capacity, then no action is taken.
470 ///
471 /// # Example
472 ///
473 /// ```rust
474 /// # use std::vec::Vec;
475 /// let mut vec: Vec<int> = Vec::with_capacity(10);
476 /// vec.reserve_exact(11);
477 /// assert_eq!(vec.capacity(), 11);
478 /// ```
479 pub fn reserve_exact(&mut self, capacity: uint) {
480 if capacity > self.cap {
481 let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
482 self.cap = capacity;
483 unsafe {
484 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
485 }
486 }
487 }
488
489 /// Shrink the capacity of the vector to match the length
490 ///
491 /// # Example
492 ///
493 /// ```rust
494 /// let mut vec = vec!(1, 2, 3);
495 /// vec.shrink_to_fit();
496 /// assert_eq!(vec.capacity(), vec.len());
497 /// ```
498 pub fn shrink_to_fit(&mut self) {
499 if self.len == 0 {
500 unsafe { free(self.ptr as *mut c_void) };
501 self.cap = 0;
502 self.ptr = 0 as *mut T;
503 } else {
504 unsafe {
505 // Overflow check is unnecessary as the vector is already at least this large.
506 self.ptr = realloc_raw(self.ptr as *mut u8, self.len * size_of::<T>()) as *mut T;
507 }
508 self.cap = self.len;
509 }
510 }
511
512 /// Remove the last element from a vector and return it, or `None` if it is
513 /// empty.
514 ///
515 /// # Example
516 ///
517 /// ```rust
518 /// let mut vec = vec!(1, 2, 3);
519 /// assert_eq!(vec.pop(), Some(3));
520 /// assert_eq!(vec, vec!(1, 2));
521 /// ```
522 #[inline]
523 pub fn pop(&mut self) -> Option<T> {
524 if self.len == 0 {
525 None
526 } else {
527 unsafe {
528 self.len -= 1;
529 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
530 }
531 }
532 }
533
534 /// Append an element to a vector.
535 ///
536 /// # Failure
537 ///
538 /// Fails if the number of elements in the vector overflows a `uint`.
539 ///
540 /// # Example
541 ///
542 /// ```rust
543 /// let mut vec = vec!(1, 2);
544 /// vec.push(3);
545 /// assert_eq!(vec, vec!(1, 2, 3));
546 /// ```
547 #[inline]
548 pub fn push(&mut self, value: T) {
549 if self.len == self.cap {
550 if self.cap == 0 { self.cap += 2 }
551 let old_size = self.cap * size_of::<T>();
552 self.cap = self.cap * 2;
553 let size = old_size * 2;
554 if old_size > size { fail!("capacity overflow") }
555 unsafe {
556 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
557 }
558 }
559
560 unsafe {
561 let end = (self.ptr as *T).offset(self.len as int) as *mut T;
562 move_val_init(&mut *end, value);
563 self.len += 1;
564 }
565 }
566
567 /// Appends one element to the vector provided. The vector itself is then
568 /// returned for use again.
569 ///
570 /// # Example
571 ///
572 /// ```rust
573 /// let vec = vec!(1, 2);
574 /// let vec = vec.append_one(3);
575 /// assert_eq!(vec, vec!(1, 2, 3));
576 /// ```
577 #[inline]
578 pub fn append_one(mut self, x: T) -> Vec<T> {
579 self.push(x);
580 self
581 }
582
583 /// Shorten a vector, dropping excess elements.
584 ///
585 /// If `len` is greater than the vector's current length, this has no
586 /// effect.
587 ///
588 /// # Example
589 ///
590 /// ```rust
591 /// let mut vec = vec!(1, 2, 3, 4);
592 /// vec.truncate(2);
593 /// assert_eq!(vec, vec!(1, 2));
594 /// ```
595 pub fn truncate(&mut self, len: uint) {
596 unsafe {
597 let mut i = len;
598 // drop any extra elements
599 while i < self.len {
600 ptr::read(self.as_slice().unsafe_ref(i));
601 i += 1;
602 }
603 }
604 self.len = len;
605 }
606
607 /// Work with `self` as a mutable slice.
608 ///
609 /// # Example
610 ///
611 /// ```rust
612 /// fn foo(slice: &mut [int]) {}
613 ///
614 /// let mut vec = vec!(1, 2);
615 /// foo(vec.as_mut_slice());
616 /// ```
617 #[inline]
618 pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
619 unsafe {
620 transmute(Slice { data: self.as_mut_ptr() as *T, len: self.len })
621 }
622 }
623
624 /// Creates a consuming iterator, that is, one that moves each
625 /// value out of the vector (from start to end). The vector cannot
626 /// be used after calling this.
627 ///
628 /// # Example
629 ///
630 /// ```rust
631 /// let v = vec!("a".to_owned(), "b".to_owned());
632 /// for s in v.move_iter() {
633 /// // s has type ~str, not &~str
634 /// println!("{}", s);
635 /// }
636 /// ```
637 #[inline]
638 pub fn move_iter(self) -> MoveItems<T> {
639 unsafe {
640 let iter = transmute(self.as_slice().iter());
641 let ptr = self.ptr as *mut c_void;
642 forget(self);
643 MoveItems { allocation: ptr, iter: iter }
644 }
645 }
646
647
648 /// Sets the length of a vector.
649 ///
650 /// This will explicitly set the size of the vector, without actually
651 /// modifying its buffers, so it is up to the caller to ensure that the
652 /// vector is actually the specified size.
653 #[inline]
654 pub unsafe fn set_len(&mut self, len: uint) {
655 self.len = len;
656 }
657
658 /// Returns a reference to the value at index `index`.
659 ///
660 /// # Failure
661 ///
662 /// Fails if `index` is out of bounds
663 ///
664 /// # Example
665 ///
666 /// ```rust
667 /// let vec = vec!(1, 2, 3);
668 /// assert!(vec.get(1) == &2);
669 /// ```
670 #[inline]
671 pub fn get<'a>(&'a self, index: uint) -> &'a T {
672 &self.as_slice()[index]
673 }
674
675 /// Returns a mutable reference to the value at index `index`.
676 ///
677 /// # Failure
678 ///
679 /// Fails if `index` is out of bounds
680 ///
681 /// # Example
682 ///
683 /// ```rust
684 /// let mut vec = vec!(1, 2, 3);
685 /// *vec.get_mut(1) = 4;
686 /// assert_eq!(vec, vec!(1, 4, 3));
687 /// ```
688 #[inline]
689 pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
690 &mut self.as_mut_slice()[index]
691 }
692
693 /// Returns an iterator over references to the elements of the vector in
694 /// order.
695 ///
696 /// # Example
697 ///
698 /// ```rust
699 /// let vec = vec!(1, 2, 3);
700 /// for num in vec.iter() {
701 /// println!("{}", *num);
702 /// }
703 /// ```
704 #[inline]
705 pub fn iter<'a>(&'a self) -> Items<'a,T> {
706 self.as_slice().iter()
707 }
708
709
710 /// Returns an iterator over mutable references to the elements of the
711 /// vector in order.
712 ///
713 /// # Example
714 ///
715 /// ```rust
716 /// let mut vec = vec!(1, 2, 3);
717 /// for num in vec.mut_iter() {
718 /// *num = 0;
719 /// }
720 /// ```
721 #[inline]
722 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
723 self.as_mut_slice().mut_iter()
724 }
725
726 /// Sort the vector, in place, using `compare` to compare elements.
727 ///
728 /// This sort is `O(n log n)` worst-case and stable, but allocates
729 /// approximately `2 * n`, where `n` is the length of `self`.
730 ///
731 /// # Example
732 ///
733 /// ```rust
734 /// let mut v = vec!(5i, 4, 1, 3, 2);
735 /// v.sort_by(|a, b| a.cmp(b));
736 /// assert_eq!(v, vec!(1, 2, 3, 4, 5));
737 ///
738 /// // reverse sorting
739 /// v.sort_by(|a, b| b.cmp(a));
740 /// assert_eq!(v, vec!(5, 4, 3, 2, 1));
741 /// ```
742 #[inline]
743 pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
744 self.as_mut_slice().sort_by(compare)
745 }
746
747 /// Returns a slice of `self` between `start` and `end`.
748 ///
749 /// # Failure
750 ///
751 /// Fails when `start` or `end` point outside the bounds of `self`, or when
752 /// `start` > `end`.
753 ///
754 /// # Example
755 ///
756 /// ```rust
757 /// let vec = vec!(1, 2, 3, 4);
758 /// assert!(vec.slice(0, 2) == [1, 2]);
759 /// ```
760 #[inline]
761 pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
762 self.as_slice().slice(start, end)
763 }
764
765 /// Returns a slice containing all but the first element of the vector.
766 ///
767 /// # Failure
768 ///
769 /// Fails when the vector is empty.
770 ///
771 /// # Example
772 ///
773 /// ```rust
774 /// let vec = vec!(1, 2, 3);
775 /// assert!(vec.tail() == [2, 3]);
776 /// ```
777 #[inline]
778 pub fn tail<'a>(&'a self) -> &'a [T] {
779 self.as_slice().tail()
780 }
781
782 /// Returns all but the first `n' elements of a vector.
783 ///
784 /// # Failure
785 ///
786 /// Fails when there are fewer than `n` elements in the vector.
787 ///
788 /// # Example
789 ///
790 /// ```rust
791 /// let vec = vec!(1, 2, 3, 4);
792 /// assert!(vec.tailn(2) == [3, 4]);
793 /// ```
794 #[inline]
795 pub fn tailn<'a>(&'a self, n: uint) -> &'a [T] {
796 self.as_slice().tailn(n)
797 }
798
799 /// Returns a reference to the last element of a vector, or `None` if it is
800 /// empty.
801 ///
802 /// # Example
803 ///
804 /// ```rust
805 /// let vec = vec!(1, 2, 3);
806 /// assert!(vec.last() == Some(&3));
807 /// ```
808 #[inline]
809 pub fn last<'a>(&'a self) -> Option<&'a T> {
810 self.as_slice().last()
811 }
812
813 /// Returns a mutable reference to the last element of a vector, or `None`
814 /// if it is empty.
815 ///
816 /// # Example
817 ///
818 /// ```rust
819 /// let mut vec = vec!(1, 2, 3);
820 /// *vec.mut_last().unwrap() = 4;
821 /// assert_eq!(vec, vec!(1, 2, 4));
822 /// ```
823 #[inline]
824 pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
825 self.as_mut_slice().mut_last()
826 }
827
828 /// Remove an element from anywhere in the vector and return it, replacing
829 /// it with the last element. This does not preserve ordering, but is O(1).
830 ///
831 /// Returns `None` if `index` is out of bounds.
832 ///
833 /// # Example
834 /// ```rust
835 /// let mut v = vec!("foo".to_owned(), "bar".to_owned(), "baz".to_owned(), "qux".to_owned());
836 ///
837 /// assert_eq!(v.swap_remove(1), Some("bar".to_owned()));
838 /// assert_eq!(v, vec!("foo".to_owned(), "qux".to_owned(), "baz".to_owned()));
839 ///
840 /// assert_eq!(v.swap_remove(0), Some("foo".to_owned()));
841 /// assert_eq!(v, vec!("baz".to_owned(), "qux".to_owned()));
842 ///
843 /// assert_eq!(v.swap_remove(2), None);
844 /// ```
845 #[inline]
846 pub fn swap_remove(&mut self, index: uint) -> Option<T> {
847 let length = self.len();
848 if index < length - 1 {
849 self.as_mut_slice().swap(index, length - 1);
850 } else if index >= length {
851 return None
852 }
853 self.pop()
854 }
855
856 /// Prepend an element to the vector.
857 ///
858 /// # Warning
859 ///
860 /// This is an O(n) operation as it requires copying every element in the
861 /// vector.
862 ///
863 /// # Example
864 ///
865 /// ```rust
866 /// let mut vec = vec!(1, 2, 3);
867 /// vec.unshift(4);
868 /// assert_eq!(vec, vec!(4, 1, 2, 3));
869 /// ```
870 #[inline]
871 pub fn unshift(&mut self, element: T) {
872 self.insert(0, element)
873 }
874
875 /// Removes the first element from a vector and returns it, or `None` if
876 /// the vector is empty.
877 ///
878 /// # Warning
879 ///
880 /// This is an O(n) operation as it requires copying every element in the
881 /// vector.
882 ///
883 /// # Example
884 ///
885 /// ```rust
886 /// let mut vec = vec!(1, 2, 3);
887 /// assert!(vec.shift() == Some(1));
888 /// assert_eq!(vec, vec!(2, 3));
889 /// ```
890 #[inline]
891 pub fn shift(&mut self) -> Option<T> {
892 self.remove(0)
893 }
894
895 /// Insert an element at position `index` within the vector, shifting all
896 /// elements after position i one position to the right.
897 ///
898 /// # Failure
899 ///
900 /// Fails if `index` is out of bounds of the vector.
901 ///
902 /// # Example
903 ///
904 /// ```rust
905 /// let mut vec = vec!(1, 2, 3);
906 /// vec.insert(1, 4);
907 /// assert_eq!(vec, vec!(1, 4, 2, 3));
908 /// ```
909 pub fn insert(&mut self, index: uint, element: T) {
910 let len = self.len();
911 assert!(index <= len);
912 // space for the new element
913 self.reserve(len + 1);
914
915 unsafe { // infallible
916 // The spot to put the new value
917 {
918 let p = self.as_mut_ptr().offset(index as int);
919 // Shift everything over to make space. (Duplicating the
920 // `index`th element into two consecutive places.)
921 ptr::copy_memory(p.offset(1), &*p, len - index);
922 // Write it in, overwriting the first copy of the `index`th
923 // element.
924 move_val_init(&mut *p, element);
925 }
926 self.set_len(len + 1);
927 }
928 }
929
930 /// Remove and return the element at position `index` within the vector,
931 /// shifting all elements after position `index` one position to the left.
932 /// Returns `None` if `i` is out of bounds.
933 ///
934 /// # Example
935 ///
936 /// ```rust
937 /// let mut v = vec!(1, 2, 3);
938 /// assert_eq!(v.remove(1), Some(2));
939 /// assert_eq!(v, vec!(1, 3));
940 ///
941 /// assert_eq!(v.remove(4), None);
942 /// // v is unchanged:
943 /// assert_eq!(v, vec!(1, 3));
944 /// ```
945 pub fn remove(&mut self, index: uint) -> Option<T> {
946 let len = self.len();
947 if index < len {
948 unsafe { // infallible
949 let ret;
950 {
951 // the place we are taking from.
952 let ptr = self.as_mut_ptr().offset(index as int);
953 // copy it out, unsafely having a copy of the value on
954 // the stack and in the vector at the same time.
955 ret = Some(ptr::read(ptr as *T));
956
957 // Shift everything down to fill in that spot.
958 ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);
959 }
960 self.set_len(len - 1);
961 ret
962 }
963 } else {
964 None
965 }
966 }
967
968 /// Takes ownership of the vector `other`, moving all elements into
969 /// the current vector. This does not copy any elements, and it is
970 /// illegal to use the `other` vector after calling this method
971 /// (because it is moved here).
972 ///
973 /// # Example
974 ///
975 /// ```rust
976 /// let mut vec = vec!(box 1);
977 /// vec.push_all_move(vec!(box 2, box 3, box 4));
978 /// assert_eq!(vec, vec!(box 1, box 2, box 3, box 4));
979 /// ```
980 pub fn push_all_move(&mut self, other: Vec<T>) {
981 self.extend(other.move_iter());
982 }
983
984 /// Returns a mutable slice of `self` between `start` and `end`.
985 ///
986 /// # Failure
987 ///
988 /// Fails when `start` or `end` point outside the bounds of `self`, or when
989 /// `start` > `end`.
990 ///
991 /// # Example
992 ///
993 /// ```rust
994 /// let mut vec = vec!(1, 2, 3, 4);
995 /// assert!(vec.mut_slice(0, 2) == [1, 2]);
996 /// ```
997 #[inline]
998 pub fn mut_slice<'a>(&'a mut self, start: uint, end: uint)
999 -> &'a mut [T] {
1000 self.as_mut_slice().mut_slice(start, end)
1001 }
1002
1003 /// Returns a mutable slice of self from `start` to the end of the vec.
1004 ///
1005 /// # Failure
1006 ///
1007 /// Fails when `start` points outside the bounds of self.
1008 ///
1009 /// # Example
1010 ///
1011 /// ```rust
1012 /// let mut vec = vec!(1, 2, 3, 4);
1013 /// assert!(vec.mut_slice_from(2) == [3, 4]);
1014 /// ```
1015 #[inline]
1016 pub fn mut_slice_from<'a>(&'a mut self, start: uint) -> &'a mut [T] {
1017 self.as_mut_slice().mut_slice_from(start)
1018 }
1019
1020 /// Returns a mutable slice of self from the start of the vec to `end`.
1021 ///
1022 /// # Failure
1023 ///
1024 /// Fails when `end` points outside the bounds of self.
1025 ///
1026 /// # Example
1027 ///
1028 /// ```rust
1029 /// let mut vec = vec!(1, 2, 3, 4);
1030 /// assert!(vec.mut_slice_to(2) == [1, 2]);
1031 /// ```
1032 #[inline]
1033 pub fn mut_slice_to<'a>(&'a mut self, end: uint) -> &'a mut [T] {
1034 self.as_mut_slice().mut_slice_to(end)
1035 }
1036
1037 /// Returns a pair of mutable slices that divides the vec at an index.
1038 ///
1039 /// The first will contain all indices from `[0, mid)` (excluding
1040 /// the index `mid` itself) and the second will contain all
1041 /// indices from `[mid, len)` (excluding the index `len` itself).
1042 ///
1043 /// # Failure
1044 ///
1045 /// Fails if `mid > len`.
1046 ///
1047 /// # Example
1048 ///
1049 /// ```rust
1050 /// let mut vec = vec!(1, 2, 3, 4, 5, 6);
1051 ///
1052 /// // scoped to restrict the lifetime of the borrows
1053 /// {
1054 /// let (left, right) = vec.mut_split_at(0);
1055 /// assert!(left == &mut []);
1056 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1057 /// }
1058 ///
1059 /// {
1060 /// let (left, right) = vec.mut_split_at(2);
1061 /// assert!(left == &mut [1, 2]);
1062 /// assert!(right == &mut [3, 4, 5, 6]);
1063 /// }
1064 ///
1065 /// {
1066 /// let (left, right) = vec.mut_split_at(6);
1067 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1068 /// assert!(right == &mut []);
1069 /// }
1070 /// ```
1071 #[inline]
1072 pub fn mut_split_at<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1073 self.as_mut_slice().mut_split_at(mid)
1074 }
1075
1076 /// Reverse the order of elements in a vector, in place.
1077 ///
1078 /// # Example
1079 ///
1080 /// ```rust
1081 /// let mut v = vec!(1, 2, 3);
1082 /// v.reverse();
1083 /// assert_eq!(v, vec!(3, 2, 1));
1084 /// ```
1085 #[inline]
1086 pub fn reverse(&mut self) {
1087 self.as_mut_slice().reverse()
1088 }
1089
1090 /// Returns a slice of `self` from `start` to the end of the vec.
1091 ///
1092 /// # Failure
1093 ///
1094 /// Fails when `start` points outside the bounds of self.
1095 ///
1096 /// # Example
1097 ///
1098 /// ```rust
1099 /// let vec = vec!(1, 2, 3);
1100 /// assert!(vec.slice_from(1) == [2, 3]);
1101 /// ```
1102 #[inline]
1103 pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
1104 self.as_slice().slice_from(start)
1105 }
1106
1107 /// Returns a slice of self from the start of the vec to `end`.
1108 ///
1109 /// # Failure
1110 ///
1111 /// Fails when `end` points outside the bounds of self.
1112 ///
1113 /// # Example
1114 ///
1115 /// ```rust
1116 /// let vec = vec!(1, 2, 3);
1117 /// assert!(vec.slice_to(2) == [1, 2]);
1118 /// ```
1119 #[inline]
1120 pub fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
1121 self.as_slice().slice_to(end)
1122 }
1123
1124 /// Returns a slice containing all but the last element of the vector.
1125 ///
1126 /// # Failure
1127 ///
1128 /// Fails if the vector is empty
1129 #[inline]
1130 pub fn init<'a>(&'a self) -> &'a [T] {
1131 self.slice(0, self.len() - 1)
1132 }
1133
1134
1135 /// Returns an unsafe pointer to the vector's buffer.
1136 ///
1137 /// The caller must ensure that the vector outlives the pointer this
1138 /// function returns, or else it will end up pointing to garbage.
1139 ///
1140 /// Modifying the vector may cause its buffer to be reallocated, which
1141 /// would also make any pointers to it invalid.
1142 #[inline]
1143 pub fn as_ptr(&self) -> *T {
1144 // If we have a 0-sized vector, then the base pointer should not be NULL
1145 // because an iterator over the slice will attempt to yield the base
1146 // pointer as the first element in the vector, but this will end up
1147 // being Some(NULL) which is optimized to None.
1148 if mem::size_of::<T>() == 0 {
1149 1 as *T
1150 } else {
1151 self.ptr as *T
1152 }
1153 }
1154
1155 /// Returns a mutable unsafe pointer to the vector's buffer.
1156 ///
1157 /// The caller must ensure that the vector outlives the pointer this
1158 /// function returns, or else it will end up pointing to garbage.
1159 ///
1160 /// Modifying the vector may cause its buffer to be reallocated, which
1161 /// would also make any pointers to it invalid.
1162 #[inline]
1163 pub fn as_mut_ptr(&mut self) -> *mut T {
1164 // see above for the 0-size check
1165 if mem::size_of::<T>() == 0 {
1166 1 as *mut T
1167 } else {
1168 self.ptr
1169 }
1170 }
1171
1172 /// Retains only the elements specified by the predicate.
1173 ///
1174 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1175 /// This method operates in place and preserves the order the retained elements.
1176 ///
1177 /// # Example
1178 ///
1179 /// ```rust
1180 /// let mut vec = vec!(1i, 2, 3, 4);
1181 /// vec.retain(|x| x%2 == 0);
1182 /// assert_eq!(vec, vec!(2, 4));
1183 /// ```
1184 pub fn retain(&mut self, f: |&T| -> bool) {
1185 let len = self.len();
1186 let mut del = 0u;
1187 {
1188 let v = self.as_mut_slice();
1189
1190 for i in range(0u, len) {
1191 if !f(&v[i]) {
1192 del += 1;
1193 } else if del > 0 {
1194 v.swap(i-del, i);
1195 }
1196 }
1197 }
1198 if del > 0 {
1199 self.truncate(len - del);
1200 }
1201 }
1202
1203 /// Expands a vector in place, initializing the new elements to the result of a function.
1204 ///
1205 /// The vector is grown by `n` elements. The i-th new element are initialized to the value
1206 /// returned by `f(i)` where `i` is in the range [0, n).
1207 ///
1208 /// # Example
1209 ///
1210 /// ```rust
1211 /// let mut vec = vec!(0u, 1);
1212 /// vec.grow_fn(3, |i| i);
1213 /// assert_eq!(vec, vec!(0, 1, 0, 1, 2));
1214 /// ```
1215 pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
1216 self.reserve_additional(n);
1217 for i in range(0u, n) {
1218 self.push(f(i));
1219 }
1220 }
1221 }
1222
1223 impl<T:TotalOrd> Vec<T> {
1224 /// Sorts the vector in place.
1225 ///
1226 /// This sort is `O(n log n)` worst-case and stable, but allocates
1227 /// approximately `2 * n`, where `n` is the length of `self`.
1228 ///
1229 /// # Example
1230 ///
1231 /// ```rust
1232 /// let mut vec = vec!(3i, 1, 2);
1233 /// vec.sort();
1234 /// assert_eq!(vec, vec!(1, 2, 3));
1235 /// ```
1236 pub fn sort(&mut self) {
1237 self.as_mut_slice().sort()
1238 }
1239 }
1240
1241 impl<T> Mutable for Vec<T> {
1242 #[inline]
1243 fn clear(&mut self) {
1244 self.truncate(0)
1245 }
1246 }
1247
1248 impl<T:Eq> Vec<T> {
1249 /// Return true if a vector contains an element with the given value
1250 ///
1251 /// # Example
1252 ///
1253 /// ```rust
1254 /// let vec = vec!(1, 2, 3);
1255 /// assert!(vec.contains(&1));
1256 /// ```
1257 pub fn contains(&self, x: &T) -> bool {
1258 self.as_slice().contains(x)
1259 }
1260
1261 /// Remove consecutive repeated elements in the vector.
1262 ///
1263 /// If the vector is sorted, this removes all duplicates.
1264 ///
1265 /// # Example
1266 ///
1267 /// ```rust
1268 /// let mut vec = vec!(1, 2, 2, 3, 2);
1269 /// vec.dedup();
1270 /// assert_eq!(vec, vec!(1, 2, 3, 2));
1271 /// ```
1272 pub fn dedup(&mut self) {
1273 unsafe {
1274 // Although we have a mutable reference to `self`, we cannot make
1275 // *arbitrary* changes. The `Eq` comparisons could fail, so we
1276 // must ensure that the vector is in a valid state at all time.
1277 //
1278 // The way that we handle this is by using swaps; we iterate
1279 // over all the elements, swapping as we go so that at the end
1280 // the elements we wish to keep are in the front, and those we
1281 // wish to reject are at the back. We can then truncate the
1282 // vector. This operation is still O(n).
1283 //
1284 // Example: We start in this state, where `r` represents "next
1285 // read" and `w` represents "next_write`.
1286 //
1287 // r
1288 // +---+---+---+---+---+---+
1289 // | 0 | 1 | 1 | 2 | 3 | 3 |
1290 // +---+---+---+---+---+---+
1291 // w
1292 //
1293 // Comparing self[r] against self[w-1], this is not a duplicate, so
1294 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1295 // r and w, leaving us with:
1296 //
1297 // r
1298 // +---+---+---+---+---+---+
1299 // | 0 | 1 | 1 | 2 | 3 | 3 |
1300 // +---+---+---+---+---+---+
1301 // w
1302 //
1303 // Comparing self[r] against self[w-1], this value is a duplicate,
1304 // so we increment `r` but leave everything else unchanged:
1305 //
1306 // r
1307 // +---+---+---+---+---+---+
1308 // | 0 | 1 | 1 | 2 | 3 | 3 |
1309 // +---+---+---+---+---+---+
1310 // w
1311 //
1312 // Comparing self[r] against self[w-1], this is not a duplicate,
1313 // so swap self[r] and self[w] and advance r and w:
1314 //
1315 // r
1316 // +---+---+---+---+---+---+
1317 // | 0 | 1 | 2 | 1 | 3 | 3 |
1318 // +---+---+---+---+---+---+
1319 // w
1320 //
1321 // Not a duplicate, repeat:
1322 //
1323 // r
1324 // +---+---+---+---+---+---+
1325 // | 0 | 1 | 2 | 3 | 1 | 3 |
1326 // +---+---+---+---+---+---+
1327 // w
1328 //
1329 // Duplicate, advance r. End of vec. Truncate to w.
1330
1331 let ln = self.len();
1332 if ln < 1 { return; }
1333
1334 // Avoid bounds checks by using unsafe pointers.
1335 let p = self.as_mut_slice().as_mut_ptr();
1336 let mut r = 1;
1337 let mut w = 1;
1338
1339 while r < ln {
1340 let p_r = p.offset(r as int);
1341 let p_wm1 = p.offset((w - 1) as int);
1342 if *p_r != *p_wm1 {
1343 if r != w {
1344 let p_w = p_wm1.offset(1);
1345 mem::swap(&mut *p_r, &mut *p_w);
1346 }
1347 w += 1;
1348 }
1349 r += 1;
1350 }
1351
1352 self.truncate(w);
1353 }
1354 }
1355 }
1356
1357 impl<T> Vector<T> for Vec<T> {
1358 /// Work with `self` as a slice.
1359 ///
1360 /// # Example
1361 ///
1362 /// ```rust
1363 /// fn foo(slice: &[int]) {}
1364 ///
1365 /// let vec = vec!(1, 2);
1366 /// foo(vec.as_slice());
1367 /// ```
1368 #[inline]
1369 fn as_slice<'a>(&'a self) -> &'a [T] {
1370 unsafe { transmute(Slice { data: self.as_ptr(), len: self.len }) }
1371 }
1372 }
1373
1374 impl<T: Clone, V: Vector<T>> Add<V, Vec<T>> for Vec<T> {
1375 #[inline]
1376 fn add(&self, rhs: &V) -> Vec<T> {
1377 let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
1378 res.push_all(self.as_slice());
1379 res.push_all(rhs.as_slice());
1380 res
1381 }
1382 }
1383
1384 #[unsafe_destructor]
1385 impl<T> Drop for Vec<T> {
1386 fn drop(&mut self) {
1387 // This is (and should always remain) a no-op if the fields are
1388 // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1389 unsafe {
1390 for x in self.as_mut_slice().iter() {
1391 ptr::read(x);
1392 }
1393 free(self.ptr as *mut c_void)
1394 }
1395 }
1396 }
1397
1398 impl<T> Default for Vec<T> {
1399 fn default() -> Vec<T> {
1400 Vec::new()
1401 }
1402 }
1403
1404 impl<T:fmt::Show> fmt::Show for Vec<T> {
1405 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1406 self.as_slice().fmt(f)
1407 }
1408 }
1409
1410 /// An iterator that moves out of a vector.
1411 pub struct MoveItems<T> {
1412 allocation: *mut c_void, // the block of memory allocated for the vector
1413 iter: Items<'static, T>
1414 }
1415
1416 impl<T> Iterator<T> for MoveItems<T> {
1417 #[inline]
1418 fn next(&mut self) -> Option<T> {
1419 unsafe {
1420 self.iter.next().map(|x| ptr::read(x))
1421 }
1422 }
1423
1424 #[inline]
1425 fn size_hint(&self) -> (uint, Option<uint>) {
1426 self.iter.size_hint()
1427 }
1428 }
1429
1430 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
1431 #[inline]
1432 fn next_back(&mut self) -> Option<T> {
1433 unsafe {
1434 self.iter.next_back().map(|x| ptr::read(x))
1435 }
1436 }
1437 }
1438
1439 #[unsafe_destructor]
1440 impl<T> Drop for MoveItems<T> {
1441 fn drop(&mut self) {
1442 // destroy the remaining elements
1443 for _x in *self {}
1444 unsafe {
1445 free(self.allocation)
1446 }
1447 }
1448 }
1449
1450 /**
1451 * Convert an iterator of pairs into a pair of vectors.
1452 *
1453 * Returns a tuple containing two vectors where the i-th element of the first
1454 * vector contains the first element of the i-th tuple of the input iterator,
1455 * and the i-th element of the second vector contains the second element
1456 * of the i-th tuple of the input iterator.
1457 */
1458 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (Vec<T>, Vec<U>) {
1459 let (lo, _) = iter.size_hint();
1460 let mut ts = Vec::with_capacity(lo);
1461 let mut us = Vec::with_capacity(lo);
1462 for (t, u) in iter {
1463 ts.push(t);
1464 us.push(u);
1465 }
1466 (ts, us)
1467 }
1468
1469 /// Mechanism to convert from a `Vec<T>` to a `[T]`.
1470 ///
1471 /// In a post-DST world this will be used to convert to any `Ptr<[T]>`.
1472 ///
1473 /// This could be implemented on more types than just pointers to vectors, but
1474 /// the recommended approach for those types is to implement `FromIterator`.
1475 // FIXME(#12938): Update doc comment when DST lands
1476 pub trait FromVec<T> {
1477 /// Convert a `Vec<T>` into the receiver type.
1478 fn from_vec(v: Vec<T>) -> Self;
1479 }
1480
1481 impl<T> FromVec<T> for ~[T] {
1482 fn from_vec(mut v: Vec<T>) -> ~[T] {
1483 let len = v.len();
1484 let data_size = len.checked_mul(&mem::size_of::<T>());
1485 let data_size = data_size.expect("overflow in from_vec()");
1486 let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
1487 let size = size.expect("overflow in from_vec()");
1488
1489 // In a post-DST world, we can attempt to reuse the Vec allocation by calling
1490 // shrink_to_fit() on it. That may involve a reallocation+memcpy, but that's no
1491 // diffrent than what we're doing manually here.
1492
1493 let vp = v.as_mut_ptr();
1494
1495 unsafe {
1496 let ret = malloc_raw(size) as *mut RawVec<()>;
1497
1498 (*ret).fill = len * mem::nonzero_size_of::<T>();
1499 (*ret).alloc = len * mem::nonzero_size_of::<T>();
1500
1501 ptr::copy_nonoverlapping_memory(&mut (*ret).data as *mut _ as *mut u8,
1502 vp as *u8, data_size);
1503
1504 // we've transferred ownership of the contents from v, but we can't drop it
1505 // as it still needs to free its own allocation.
1506 v.set_len(0);
1507
1508 transmute(ret)
1509 }
1510 }
1511 }
1512
1513 /// Unsafe operations
1514 pub mod raw {
1515 use super::Vec;
1516 use ptr;
1517
1518 /// Constructs a vector from an unsafe pointer to a buffer.
1519 ///
1520 /// The elements of the buffer are copied into the vector without cloning,
1521 /// as if `ptr::read()` were called on them.
1522 #[inline]
1523 pub unsafe fn from_buf<T>(ptr: *T, elts: uint) -> Vec<T> {
1524 let mut dst = Vec::with_capacity(elts);
1525 dst.set_len(elts);
1526 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(), ptr, elts);
1527 dst
1528 }
1529 }
1530
1531
1532 #[cfg(test)]
1533 mod tests {
1534 use prelude::*;
1535 use mem::size_of;
1536 use kinds::marker;
1537 use super::{unzip, raw, FromVec};
1538
1539 #[test]
1540 fn test_small_vec_struct() {
1541 assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
1542 }
1543
1544 #[test]
1545 fn test_double_drop() {
1546 struct TwoVec<T> {
1547 x: Vec<T>,
1548 y: Vec<T>
1549 }
1550
1551 struct DropCounter<'a> {
1552 count: &'a mut int
1553 }
1554
1555 #[unsafe_destructor]
1556 impl<'a> Drop for DropCounter<'a> {
1557 fn drop(&mut self) {
1558 *self.count += 1;
1559 }
1560 }
1561
1562 let mut count_x @ mut count_y = 0;
1563 {
1564 let mut tv = TwoVec {
1565 x: Vec::new(),
1566 y: Vec::new()
1567 };
1568 tv.x.push(DropCounter {count: &mut count_x});
1569 tv.y.push(DropCounter {count: &mut count_y});
1570
1571 // If Vec had a drop flag, here is where it would be zeroed.
1572 // Instead, it should rely on its internal state to prevent
1573 // doing anything significant when dropped multiple times.
1574 drop(tv.x);
1575
1576 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
1577 }
1578
1579 assert_eq!(count_x, 1);
1580 assert_eq!(count_y, 1);
1581 }
1582
1583 #[test]
1584 fn test_reserve_additional() {
1585 let mut v = Vec::new();
1586 assert_eq!(v.capacity(), 0);
1587
1588 v.reserve_additional(2);
1589 assert!(v.capacity() >= 2);
1590
1591 for i in range(0, 16) {
1592 v.push(i);
1593 }
1594
1595 assert!(v.capacity() >= 16);
1596 v.reserve_additional(16);
1597 assert!(v.capacity() >= 32);
1598
1599 v.push(16);
1600
1601 v.reserve_additional(16);
1602 assert!(v.capacity() >= 33)
1603 }
1604
1605 #[test]
1606 fn test_extend() {
1607 let mut v = Vec::new();
1608 let mut w = Vec::new();
1609
1610 v.extend(range(0, 3));
1611 for i in range(0, 3) { w.push(i) }
1612
1613 assert_eq!(v, w);
1614
1615 v.extend(range(3, 10));
1616 for i in range(3, 10) { w.push(i) }
1617
1618 assert_eq!(v, w);
1619 }
1620
1621 #[test]
1622 fn test_mut_slice_from() {
1623 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1624 {
1625 let slice = values.mut_slice_from(2);
1626 assert!(slice == [3, 4, 5]);
1627 for p in slice.mut_iter() {
1628 *p += 2;
1629 }
1630 }
1631
1632 assert!(values.as_slice() == [1, 2, 5, 6, 7]);
1633 }
1634
1635 #[test]
1636 fn test_mut_slice_to() {
1637 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1638 {
1639 let slice = values.mut_slice_to(2);
1640 assert!(slice == [1, 2]);
1641 for p in slice.mut_iter() {
1642 *p += 1;
1643 }
1644 }
1645
1646 assert!(values.as_slice() == [2, 3, 3, 4, 5]);
1647 }
1648
1649 #[test]
1650 fn test_mut_split_at() {
1651 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1652 {
1653 let (left, right) = values.mut_split_at(2);
1654 assert!(left.slice(0, left.len()) == [1, 2]);
1655 for p in left.mut_iter() {
1656 *p += 1;
1657 }
1658
1659 assert!(right.slice(0, right.len()) == [3, 4, 5]);
1660 for p in right.mut_iter() {
1661 *p += 2;
1662 }
1663 }
1664
1665 assert!(values == Vec::from_slice([2u8, 3, 5, 6, 7]));
1666 }
1667
1668 #[test]
1669 fn test_clone() {
1670 let v: Vec<int> = vec!();
1671 let w = vec!(1, 2, 3);
1672
1673 assert_eq!(v, v.clone());
1674
1675 let z = w.clone();
1676 assert_eq!(w, z);
1677 // they should be disjoint in memory.
1678 assert!(w.as_ptr() != z.as_ptr())
1679 }
1680
1681 #[test]
1682 fn test_clone_from() {
1683 let mut v = vec!();
1684 let three = vec!(box 1, box 2, box 3);
1685 let two = vec!(box 4, box 5);
1686 // zero, long
1687 v.clone_from(&three);
1688 assert_eq!(v, three);
1689
1690 // equal
1691 v.clone_from(&three);
1692 assert_eq!(v, three);
1693
1694 // long, short
1695 v.clone_from(&two);
1696 assert_eq!(v, two);
1697
1698 // short, long
1699 v.clone_from(&three);
1700 assert_eq!(v, three)
1701 }
1702
1703 #[test]
1704 fn test_grow_fn() {
1705 let mut v = Vec::from_slice([0u, 1]);
1706 v.grow_fn(3, |i| i);
1707 assert!(v == Vec::from_slice([0u, 1, 0, 1, 2]));
1708 }
1709
1710 #[test]
1711 fn test_retain() {
1712 let mut vec = Vec::from_slice([1u, 2, 3, 4]);
1713 vec.retain(|x| x%2 == 0);
1714 assert!(vec == Vec::from_slice([2u, 4]));
1715 }
1716
1717 #[test]
1718 fn zero_sized_values() {
1719 let mut v = Vec::new();
1720 assert_eq!(v.len(), 0);
1721 v.push(());
1722 assert_eq!(v.len(), 1);
1723 v.push(());
1724 assert_eq!(v.len(), 2);
1725 assert_eq!(v.pop(), Some(()));
1726 assert_eq!(v.pop(), Some(()));
1727 assert_eq!(v.pop(), None);
1728
1729 assert_eq!(v.iter().len(), 0);
1730 v.push(());
1731 assert_eq!(v.iter().len(), 1);
1732 v.push(());
1733 assert_eq!(v.iter().len(), 2);
1734
1735 for &() in v.iter() {}
1736
1737 assert_eq!(v.mut_iter().len(), 2);
1738 v.push(());
1739 assert_eq!(v.mut_iter().len(), 3);
1740 v.push(());
1741 assert_eq!(v.mut_iter().len(), 4);
1742
1743 for &() in v.mut_iter() {}
1744 unsafe { v.set_len(0); }
1745 assert_eq!(v.mut_iter().len(), 0);
1746 }
1747
1748 #[test]
1749 fn test_partition() {
1750 assert_eq!(vec![].partition(|x: &int| *x < 3), (vec![], vec![]));
1751 assert_eq!(vec![1, 2, 3].partition(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1752 assert_eq!(vec![1, 2, 3].partition(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1753 assert_eq!(vec![1, 2, 3].partition(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1754 }
1755
1756 #[test]
1757 fn test_partitioned() {
1758 assert_eq!(vec![].partitioned(|x: &int| *x < 3), (vec![], vec![]))
1759 assert_eq!(vec![1, 2, 3].partitioned(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1760 assert_eq!(vec![1, 2, 3].partitioned(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1761 assert_eq!(vec![1, 2, 3].partitioned(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1762 }
1763
1764 #[test]
1765 fn test_zip_unzip() {
1766 let z1 = vec![(1, 4), (2, 5), (3, 6)];
1767
1768 let (left, right) = unzip(z1.iter().map(|&x| x));
1769
1770 let (left, right) = (left.as_slice(), right.as_slice());
1771 assert_eq!((1, 4), (left[0], right[0]));
1772 assert_eq!((2, 5), (left[1], right[1]));
1773 assert_eq!((3, 6), (left[2], right[2]));
1774 }
1775
1776 #[test]
1777 fn test_unsafe_ptrs() {
1778 unsafe {
1779 // Test on-stack copy-from-buf.
1780 let a = [1, 2, 3];
1781 let ptr = a.as_ptr();
1782 let b = raw::from_buf(ptr, 3u);
1783 assert_eq!(b, vec![1, 2, 3]);
1784
1785 // Test on-heap copy-from-buf.
1786 let c = box [1, 2, 3, 4, 5];
1787 let ptr = c.as_ptr();
1788 let d = raw::from_buf(ptr, 5u);
1789 assert_eq!(d, vec![1, 2, 3, 4, 5]);
1790 }
1791 }
1792
1793 #[test]
1794 fn test_from_vec() {
1795 let a = vec![1u, 2, 3];
1796 let b: ~[uint] = FromVec::from_vec(a);
1797 assert_eq!(b.as_slice(), &[1u, 2, 3]);
1798
1799 let a = vec![];
1800 let b: ~[u8] = FromVec::from_vec(a);
1801 assert_eq!(b.as_slice(), &[]);
1802
1803 let a = vec!["one".to_owned(), "two".to_owned()];
1804 let b: ~[~str] = FromVec::from_vec(a);
1805 assert_eq!(b.as_slice(), &["one".to_owned(), "two".to_owned()]);
1806
1807 struct Foo {
1808 x: uint,
1809 nocopy: marker::NoCopy
1810 }
1811
1812 let a = vec![Foo{x: 42, nocopy: marker::NoCopy}, Foo{x: 84, nocopy: marker::NoCopy}];
1813 let b: ~[Foo] = FromVec::from_vec(a);
1814 assert_eq!(b.len(), 2);
1815 assert_eq!(b[0].x, 42);
1816 assert_eq!(b[1].x, 84);
1817 }
1818 }