1 // Copyright 2012-2014 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.
11 //! Slice management and manipulation
13 //! For more details `std::slice`.
15 #![stable(feature = "rust1", since = "1.0.0")]
16 #![doc(primitive = "slice")]
18 // How this module is organized.
20 // The library infrastructure for slices is fairly messy. There's
21 // a lot of stuff defined here. Let's keep it clean.
23 // Since slices don't support inherent methods; all operations
24 // on them are defined on traits, which are then reexported from
25 // the prelude for convenience. So there are a lot of traits here.
27 // The layout of this file is thus:
29 // * Slice-specific 'extension' traits and their implementations. This
30 // is where most of the slice API resides.
31 // * Implementations of a few common traits with important slice ops.
32 // * Definitions of a bunch of iterators.
34 // * The `raw` and `bytes` submodules.
35 // * Boilerplate trait implementations.
39 use cmp
::{Ordering, PartialEq, PartialOrd, Eq, Ord}
;
40 use cmp
::Ordering
::{Less, Equal, Greater}
;
43 use intrinsics
::assume
;
45 use ops
::{FnMut, self, Index}
;
48 use option
::Option
::{None, Some}
;
50 use result
::Result
::{Ok, Err}
;
54 use marker
::{Send, Sync, self}
;
56 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
57 use raw
::Slice
as RawSlice
;
64 /// Extension methods for slices.
65 #[allow(missing_docs)] // docs in libcollections
70 fn split_at
<'a
>(&'a
self, mid
: usize) -> (&'a
[Self::Item
], &'a
[Self::Item
]);
71 fn iter
<'a
>(&'a
self) -> Iter
<'a
, Self::Item
>;
72 fn split
<'a
, P
>(&'a
self, pred
: P
) -> Split
<'a
, Self::Item
, P
>
73 where P
: FnMut(&Self::Item
) -> bool
;
74 fn splitn
<'a
, P
>(&'a
self, n
: usize, pred
: P
) -> SplitN
<'a
, Self::Item
, P
>
75 where P
: FnMut(&Self::Item
) -> bool
;
76 fn rsplitn
<'a
, P
>(&'a
self, n
: usize, pred
: P
) -> RSplitN
<'a
, Self::Item
, P
>
77 where P
: FnMut(&Self::Item
) -> bool
;
78 fn windows
<'a
>(&'a
self, size
: usize) -> Windows
<'a
, Self::Item
>;
79 fn chunks
<'a
>(&'a
self, size
: usize) -> Chunks
<'a
, Self::Item
>;
80 fn get
<'a
>(&'a
self, index
: usize) -> Option
<&'a
Self::Item
>;
81 fn first
<'a
>(&'a
self) -> Option
<&'a
Self::Item
>;
82 fn tail
<'a
>(&'a
self) -> &'a
[Self::Item
];
83 fn init
<'a
>(&'a
self) -> &'a
[Self::Item
];
84 fn last
<'a
>(&'a
self) -> Option
<&'a
Self::Item
>;
85 unsafe fn get_unchecked
<'a
>(&'a
self, index
: usize) -> &'a
Self::Item
;
86 fn as_ptr(&self) -> *const Self::Item
;
87 fn binary_search_by
<F
>(&self, f
: F
) -> Result
<usize, usize> where
88 F
: FnMut(&Self::Item
) -> Ordering
;
89 fn len(&self) -> usize;
90 fn is_empty(&self) -> bool { self.len() == 0 }
91 fn get_mut
<'a
>(&'a
mut self, index
: usize) -> Option
<&'a
mut Self::Item
>;
92 fn iter_mut
<'a
>(&'a
mut self) -> IterMut
<'a
, Self::Item
>;
93 fn first_mut
<'a
>(&'a
mut self) -> Option
<&'a
mut Self::Item
>;
94 fn tail_mut
<'a
>(&'a
mut self) -> &'a
mut [Self::Item
];
95 fn init_mut
<'a
>(&'a
mut self) -> &'a
mut [Self::Item
];
96 fn last_mut
<'a
>(&'a
mut self) -> Option
<&'a
mut Self::Item
>;
97 fn split_mut
<'a
, P
>(&'a
mut self, pred
: P
) -> SplitMut
<'a
, Self::Item
, P
>
98 where P
: FnMut(&Self::Item
) -> bool
;
99 fn splitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> SplitNMut
<Self::Item
, P
>
100 where P
: FnMut(&Self::Item
) -> bool
;
101 fn rsplitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> RSplitNMut
<Self::Item
, P
>
102 where P
: FnMut(&Self::Item
) -> bool
;
103 fn chunks_mut
<'a
>(&'a
mut self, chunk_size
: usize) -> ChunksMut
<'a
, Self::Item
>;
104 fn swap(&mut self, a
: usize, b
: usize);
105 fn split_at_mut
<'a
>(&'a
mut self, mid
: usize) -> (&'a
mut [Self::Item
], &'a
mut [Self::Item
]);
106 fn reverse(&mut self);
107 unsafe fn get_unchecked_mut
<'a
>(&'a
mut self, index
: usize) -> &'a
mut Self::Item
;
108 fn as_mut_ptr(&mut self) -> *mut Self::Item
;
110 fn position_elem(&self, t
: &Self::Item
) -> Option
<usize> where Self::Item
: PartialEq
;
112 fn rposition_elem(&self, t
: &Self::Item
) -> Option
<usize> where Self::Item
: PartialEq
;
114 fn contains(&self, x
: &Self::Item
) -> bool
where Self::Item
: PartialEq
;
116 fn starts_with(&self, needle
: &[Self::Item
]) -> bool
where Self::Item
: PartialEq
;
118 fn ends_with(&self, needle
: &[Self::Item
]) -> bool
where Self::Item
: PartialEq
;
120 fn binary_search(&self, x
: &Self::Item
) -> Result
<usize, usize> where Self::Item
: Ord
;
121 fn next_permutation(&mut self) -> bool
where Self::Item
: Ord
;
122 fn prev_permutation(&mut self) -> bool
where Self::Item
: Ord
;
124 fn clone_from_slice(&mut self, &[Self::Item
]) -> usize where Self::Item
: Clone
;
127 #[unstable(feature = "core")]
128 impl<T
> SliceExt
for [T
] {
132 fn split_at(&self, mid
: usize) -> (&[T
], &[T
]) {
133 (&self[..mid
], &self[mid
..])
137 fn iter
<'a
>(&'a
self) -> Iter
<'a
, T
> {
139 let p
= self.as_ptr();
140 assume(!p
.is_null());
141 if mem
::size_of
::<T
>() == 0 {
143 end
: ((p
as usize).wrapping_add(self.len())) as *const T
,
144 _marker
: marker
::PhantomData
}
147 end
: p
.offset(self.len() as isize),
148 _marker
: marker
::PhantomData
}
154 fn split
<'a
, P
>(&'a
self, pred
: P
) -> Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
163 fn splitn
<'a
, P
>(&'a
self, n
: usize, pred
: P
) -> SplitN
<'a
, T
, P
> where
164 P
: FnMut(&T
) -> bool
,
167 inner
: GenericSplitN
{
168 iter
: self.split(pred
),
176 fn rsplitn
<'a
, P
>(&'a
self, n
: usize, pred
: P
) -> RSplitN
<'a
, T
, P
> where
177 P
: FnMut(&T
) -> bool
,
180 inner
: GenericSplitN
{
181 iter
: self.split(pred
),
189 fn windows(&self, size
: usize) -> Windows
<T
> {
191 Windows { v: self, size: size }
195 fn chunks(&self, size
: usize) -> Chunks
<T
> {
197 Chunks { v: self, size: size }
201 fn get(&self, index
: usize) -> Option
<&T
> {
202 if index
< self.len() { Some(&self[index]) }
else { None }
206 fn first(&self) -> Option
<&T
> {
207 if self.is_empty() { None }
else { Some(&self[0]) }
211 fn tail(&self) -> &[T
] { &self[1..] }
214 fn init(&self) -> &[T
] {
215 &self[..self.len() - 1]
219 fn last(&self) -> Option
<&T
> {
220 if self.is_empty() { None }
else { Some(&self[self.len() - 1]) }
224 unsafe fn get_unchecked(&self, index
: usize) -> &T
{
225 transmute(self.repr().data
.offset(index
as isize))
229 fn as_ptr(&self) -> *const T
{
233 #[unstable(feature = "core")]
234 fn binary_search_by
<F
>(&self, mut f
: F
) -> Result
<usize, usize> where
235 F
: FnMut(&T
) -> Ordering
237 let mut base
: usize = 0;
238 let mut lim
: usize = self.len();
241 let ix
= base
+ (lim
>> 1);
243 Equal
=> return Ok(ix
),
256 fn len(&self) -> usize { self.repr().len }
259 fn get_mut(&mut self, index
: usize) -> Option
<&mut T
> {
260 if index
< self.len() { Some(&mut self[index]) }
else { None }
264 fn split_at_mut(&mut self, mid
: usize) -> (&mut [T
], &mut [T
]) {
266 let self2
: &mut [T
] = mem
::transmute_copy(&self);
268 (ops
::IndexMut
::index_mut(self, ops
::RangeTo { end: mid }
),
269 ops
::IndexMut
::index_mut(self2
, ops
::RangeFrom { start: mid }
))
274 fn iter_mut
<'a
>(&'a
mut self) -> IterMut
<'a
, T
> {
276 let p
= self.as_mut_ptr();
277 assume(!p
.is_null());
278 if mem
::size_of
::<T
>() == 0 {
280 end
: ((p
as usize).wrapping_add(self.len())) as *mut T
,
281 _marker
: marker
::PhantomData
}
284 end
: p
.offset(self.len() as isize),
285 _marker
: marker
::PhantomData
}
291 fn last_mut(&mut self) -> Option
<&mut T
> {
292 let len
= self.len();
293 if len
== 0 { return None; }
294 Some(&mut self[len
- 1])
298 fn first_mut(&mut self) -> Option
<&mut T
> {
299 if self.is_empty() { None }
else { Some(&mut self[0]) }
303 fn tail_mut(&mut self) -> &mut [T
] {
308 fn init_mut(&mut self) -> &mut [T
] {
309 let len
= self.len();
310 &mut self[.. (len
- 1)]
314 fn split_mut
<'a
, P
>(&'a
mut self, pred
: P
) -> SplitMut
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
315 SplitMut { v: self, pred: pred, finished: false }
319 fn splitn_mut
<'a
, P
>(&'a
mut self, n
: usize, pred
: P
) -> SplitNMut
<'a
, T
, P
> where
323 inner
: GenericSplitN
{
324 iter
: self.split_mut(pred
),
332 fn rsplitn_mut
<'a
, P
>(&'a
mut self, n
: usize, pred
: P
) -> RSplitNMut
<'a
, T
, P
> where
333 P
: FnMut(&T
) -> bool
,
336 inner
: GenericSplitN
{
337 iter
: self.split_mut(pred
),
345 fn chunks_mut(&mut self, chunk_size
: usize) -> ChunksMut
<T
> {
346 assert
!(chunk_size
> 0);
347 ChunksMut { v: self, chunk_size: chunk_size }
351 fn swap(&mut self, a
: usize, b
: usize) {
353 // Can't take two mutable loans from one vector, so instead just cast
354 // them to their raw pointers to do the swap
355 let pa
: *mut T
= &mut self[a
];
356 let pb
: *mut T
= &mut self[b
];
361 fn reverse(&mut self) {
362 let mut i
: usize = 0;
365 // Unsafe swap to avoid the bounds check in safe swap.
367 let pa
: *mut T
= self.get_unchecked_mut(i
);
368 let pb
: *mut T
= self.get_unchecked_mut(ln
- i
- 1);
376 unsafe fn get_unchecked_mut(&mut self, index
: usize) -> &mut T
{
377 transmute((self.repr().data
as *mut T
).offset(index
as isize))
381 fn as_mut_ptr(&mut self) -> *mut T
{
382 self.repr().data
as *mut T
386 fn position_elem(&self, x
: &T
) -> Option
<usize> where T
: PartialEq
{
387 self.iter().position(|y
| *x
== *y
)
391 fn rposition_elem(&self, t
: &T
) -> Option
<usize> where T
: PartialEq
{
392 self.iter().rposition(|x
| *x
== *t
)
396 fn contains(&self, x
: &T
) -> bool
where T
: PartialEq
{
397 self.iter().any(|elt
| *x
== *elt
)
401 fn starts_with(&self, needle
: &[T
]) -> bool
where T
: PartialEq
{
402 let n
= needle
.len();
403 self.len() >= n
&& needle
== &self[..n
]
407 fn ends_with(&self, needle
: &[T
]) -> bool
where T
: PartialEq
{
408 let (m
, n
) = (self.len(), needle
.len());
409 m
>= n
&& needle
== &self[m
-n
..]
412 #[unstable(feature = "core")]
413 fn binary_search(&self, x
: &T
) -> Result
<usize, usize> where T
: Ord
{
414 self.binary_search_by(|p
| p
.cmp(x
))
417 #[unstable(feature = "core")]
418 fn next_permutation(&mut self) -> bool
where T
: Ord
{
419 // These cases only have 1 permutation each, so we can't do anything.
420 if self.len() < 2 { return false; }
422 // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
423 let mut i
= self.len() - 1;
424 while i
> 0 && self[i
-1] >= self[i
] {
428 // If that is the entire vector, this is the last-ordered permutation.
433 // Step 2: Find the rightmost element larger than the pivot (i-1)
434 let mut j
= self.len() - 1;
435 while j
>= i
&& self[j
] <= self[i
-1] {
439 // Step 3: Swap that element with the pivot
442 // Step 4: Reverse the (previously) weakly decreasing part
448 #[unstable(feature = "core")]
449 fn prev_permutation(&mut self) -> bool
where T
: Ord
{
450 // These cases only have 1 permutation each, so we can't do anything.
451 if self.len() < 2 { return false; }
453 // Step 1: Identify the longest, rightmost weakly increasing part of the vector
454 let mut i
= self.len() - 1;
455 while i
> 0 && self[i
-1] <= self[i
] {
459 // If that is the entire vector, this is the first-ordered permutation.
464 // Step 2: Reverse the weakly increasing part
467 // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
468 let mut j
= self.len() - 1;
469 while j
>= i
&& self[j
-1] < self[i
-1] {
473 // Step 4: Swap that element with the pivot
480 fn clone_from_slice(&mut self, src
: &[T
]) -> usize where T
: Clone
{
481 let min
= cmp
::min(self.len(), src
.len());
482 let dst
= &mut self[.. min
];
483 let src
= &src
[.. min
];
485 dst
[i
].clone_from(&src
[i
]);
491 #[stable(feature = "rust1", since = "1.0.0")]
492 impl<T
> ops
::Index
<usize> for [T
] {
495 fn index(&self, index
: usize) -> &T
{
496 assert
!(index
< self.len());
498 unsafe { mem::transmute(self.repr().data.offset(index as isize)) }
502 #[stable(feature = "rust1", since = "1.0.0")]
503 impl<T
> ops
::IndexMut
<usize> for [T
] {
505 fn index_mut(&mut self, index
: usize) -> &mut T
{
506 assert
!(index
< self.len());
508 unsafe { mem::transmute(self.repr().data.offset(index as isize)) }
512 #[stable(feature = "rust1", since = "1.0.0")]
513 impl<T
> ops
::Index
<ops
::Range
<usize>> for [T
] {
517 fn index(&self, index
: ops
::Range
<usize>) -> &[T
] {
518 assert
!(index
.start
<= index
.end
);
519 assert
!(index
.end
<= self.len());
522 self.as_ptr().offset(index
.start
as isize),
523 index
.end
- index
.start
528 #[stable(feature = "rust1", since = "1.0.0")]
529 impl<T
> ops
::Index
<ops
::RangeTo
<usize>> for [T
] {
533 fn index(&self, index
: ops
::RangeTo
<usize>) -> &[T
] {
534 self.index(ops
::Range{ start: 0, end: index.end }
)
537 #[stable(feature = "rust1", since = "1.0.0")]
538 impl<T
> ops
::Index
<ops
::RangeFrom
<usize>> for [T
] {
542 fn index(&self, index
: ops
::RangeFrom
<usize>) -> &[T
] {
543 self.index(ops
::Range{ start: index.start, end: self.len() }
)
546 #[stable(feature = "rust1", since = "1.0.0")]
547 impl<T
> ops
::Index
<RangeFull
> for [T
] {
551 fn index(&self, _index
: RangeFull
) -> &[T
] {
556 #[stable(feature = "rust1", since = "1.0.0")]
557 impl<T
> ops
::IndexMut
<ops
::Range
<usize>> for [T
] {
559 fn index_mut(&mut self, index
: ops
::Range
<usize>) -> &mut [T
] {
560 assert
!(index
.start
<= index
.end
);
561 assert
!(index
.end
<= self.len());
564 self.as_mut_ptr().offset(index
.start
as isize),
565 index
.end
- index
.start
570 #[stable(feature = "rust1", since = "1.0.0")]
571 impl<T
> ops
::IndexMut
<ops
::RangeTo
<usize>> for [T
] {
573 fn index_mut(&mut self, index
: ops
::RangeTo
<usize>) -> &mut [T
] {
574 self.index_mut(ops
::Range{ start: 0, end: index.end }
)
577 #[stable(feature = "rust1", since = "1.0.0")]
578 impl<T
> ops
::IndexMut
<ops
::RangeFrom
<usize>> for [T
] {
580 fn index_mut(&mut self, index
: ops
::RangeFrom
<usize>) -> &mut [T
] {
581 let len
= self.len();
582 self.index_mut(ops
::Range{ start: index.start, end: len }
)
585 #[stable(feature = "rust1", since = "1.0.0")]
586 impl<T
> ops
::IndexMut
<RangeFull
> for [T
] {
588 fn index_mut(&mut self, _index
: RangeFull
) -> &mut [T
] {
594 ////////////////////////////////////////////////////////////////////////////////
596 ////////////////////////////////////////////////////////////////////////////////
598 #[stable(feature = "rust1", since = "1.0.0")]
599 impl<'a
, T
> Default
for &'a
[T
] {
600 #[stable(feature = "rust1", since = "1.0.0")]
601 fn default() -> &'a
[T
] { &[] }
608 #[stable(feature = "rust1", since = "1.0.0")]
609 impl<'a
, T
> IntoIterator
for &'a
[T
] {
611 type IntoIter
= Iter
<'a
, T
>;
613 fn into_iter(self) -> Iter
<'a
, T
> {
618 #[stable(feature = "rust1", since = "1.0.0")]
619 impl<'a
, T
> IntoIterator
for &'a
mut [T
] {
620 type Item
= &'a
mut T
;
621 type IntoIter
= IterMut
<'a
, T
>;
623 fn into_iter(self) -> IterMut
<'a
, T
> {
629 fn size_from_ptr
<T
>(_
: *const T
) -> usize {
634 // Use macros to be generic over const/mut
635 macro_rules
! slice_offset
{
636 ($ptr
:expr
, $by
:expr
) => {{
638 if size_from_ptr(ptr
) == 0 {
639 transmute((ptr
as isize).wrapping_add($by
))
646 macro_rules
! slice_ref
{
649 if size_from_ptr(ptr
) == 0 {
650 // Use a non-null pointer value
658 // The shared definition of the `Iter` and `IterMut` iterators
659 macro_rules
! iterator
{
660 (struct $name
:ident
-> $ptr
:ty
, $elem
:ty
) => {
661 #[stable(feature = "rust1", since = "1.0.0")]
662 impl<'a
, T
> Iterator
for $name
<'a
, T
> {
666 fn next(&mut self) -> Option
<$elem
> {
667 // could be implemented with slices, but this avoids bounds checks
669 if mem
::size_of
::<T
>() != 0 {
670 assume(!self.ptr
.is_null());
671 assume(!self.end
.is_null());
673 if self.ptr
== self.end
{
677 self.ptr
= slice_offset
!(self.ptr
, 1);
678 Some(slice_ref
!(old
))
684 fn size_hint(&self) -> (usize, Option
<usize>) {
685 let diff
= (self.end
as usize).wrapping_sub(self.ptr
as usize);
686 let size
= mem
::size_of
::<T
>();
687 let exact
= diff
/ (if size
== 0 {1}
else {size}
);
692 fn count(self) -> usize {
697 fn nth(&mut self, n
: usize) -> Option
<$elem
> {
698 // Call helper method. Can't put the definition here because mut versus const.
703 fn last(mut self) -> Option
<$elem
> {
708 #[stable(feature = "rust1", since = "1.0.0")]
709 impl<'a
, T
> DoubleEndedIterator
for $name
<'a
, T
> {
711 fn next_back(&mut self) -> Option
<$elem
> {
712 // could be implemented with slices, but this avoids bounds checks
714 if mem
::size_of
::<T
>() != 0 {
715 assume(!self.ptr
.is_null());
716 assume(!self.end
.is_null());
718 if self.end
== self.ptr
{
721 self.end
= slice_offset
!(self.end
, -1);
722 Some(slice_ref
!(self.end
))
730 macro_rules
! make_slice
{
731 ($start
: expr
, $end
: expr
) => {{
733 let diff
= ($end
as usize).wrapping_sub(start
as usize);
734 if size_from_ptr(start
) == 0 {
735 // use a non-null pointer value
736 unsafe { from_raw_parts(1 as *const _, diff) }
738 let len
= diff
/ size_from_ptr(start
);
739 unsafe { from_raw_parts(start, len) }
744 macro_rules
! make_mut_slice
{
745 ($start
: expr
, $end
: expr
) => {{
747 let diff
= ($end
as usize).wrapping_sub(start
as usize);
748 if size_from_ptr(start
) == 0 {
749 // use a non-null pointer value
750 unsafe { from_raw_parts_mut(1 as *mut _, diff) }
752 let len
= diff
/ size_from_ptr(start
);
753 unsafe { from_raw_parts_mut(start, len) }
758 /// Immutable slice iterator
759 #[stable(feature = "rust1", since = "1.0.0")]
760 pub struct Iter
<'a
, T
: 'a
> {
763 _marker
: marker
::PhantomData
<&'a T
>,
766 unsafe impl<'a
, T
: Sync
> Sync
for Iter
<'a
, T
> {}
767 unsafe impl<'a
, T
: Sync
> Send
for Iter
<'a
, T
> {}
769 impl<'a
, T
> Iter
<'a
, T
> {
770 /// View the underlying data as a subslice of the original data.
772 /// This has the same lifetime as the original slice, and so the
773 /// iterator can continue to be used while this exists.
774 #[unstable(feature = "core")]
775 pub fn as_slice(&self) -> &'a
[T
] {
776 make_slice
!(self.ptr
, self.end
)
779 // Helper function for Iter::nth
780 fn iter_nth(&mut self, n
: usize) -> Option
<&'a T
> {
781 match self.as_slice().get(n
) {
782 Some(elem_ref
) => unsafe {
783 self.ptr
= slice_offset
!(self.ptr
, (n
as isize).wrapping_add(1));
784 Some(slice_ref
!(elem_ref
))
794 iterator
!{struct Iter -> *const T, &'a T}
796 #[stable(feature = "rust1", since = "1.0.0")]
797 impl<'a
, T
> ExactSizeIterator
for Iter
<'a
, T
> {}
799 #[stable(feature = "rust1", since = "1.0.0")]
800 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
801 fn clone(&self) -> Iter
<'a
, T
> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
}
804 #[unstable(feature = "core", reason = "trait is experimental")]
805 impl<'a
, T
> RandomAccessIterator
for Iter
<'a
, T
> {
807 fn indexable(&self) -> usize {
808 let (exact
, _
) = self.size_hint();
813 fn idx(&mut self, index
: usize) -> Option
<&'a T
> {
815 if index
< self.indexable() {
816 Some(slice_ref
!(self.ptr
.offset(index
as isize)))
824 /// Mutable slice iterator.
825 #[stable(feature = "rust1", since = "1.0.0")]
826 pub struct IterMut
<'a
, T
: 'a
> {
829 _marker
: marker
::PhantomData
<&'a
mut T
>,
832 unsafe impl<'a
, T
: Sync
> Sync
for IterMut
<'a
, T
> {}
833 unsafe impl<'a
, T
: Send
> Send
for IterMut
<'a
, T
> {}
835 impl<'a
, T
> IterMut
<'a
, T
> {
836 /// View the underlying data as a subslice of the original data.
838 /// To avoid creating `&mut` references that alias, this is forced
839 /// to consume the iterator. Consider using the `Slice` and
840 /// `SliceMut` implementations for obtaining slices with more
841 /// restricted lifetimes that do not consume the iterator.
842 #[unstable(feature = "core")]
843 pub fn into_slice(self) -> &'a
mut [T
] {
844 make_mut_slice
!(self.ptr
, self.end
)
847 // Helper function for IterMut::nth
848 fn iter_nth(&mut self, n
: usize) -> Option
<&'a
mut T
> {
849 match make_mut_slice
!(self.ptr
, self.end
).get_mut(n
) {
850 Some(elem_ref
) => unsafe {
851 self.ptr
= slice_offset
!(self.ptr
, (n
as isize).wrapping_add(1));
852 Some(slice_ref
!(elem_ref
))
862 iterator
!{struct IterMut -> *mut T, &'a mut T}
864 #[stable(feature = "rust1", since = "1.0.0")]
865 impl<'a
, T
> ExactSizeIterator
for IterMut
<'a
, T
> {}
867 /// An internal abstraction over the splitting iterators, so that
868 /// splitn, splitn_mut etc can be implemented once.
869 trait SplitIter
: DoubleEndedIterator
{
870 /// Mark the underlying iterator as complete, extracting the remaining
871 /// portion of the slice.
872 fn finish(&mut self) -> Option
<Self::Item
>;
875 /// An iterator over subslices separated by elements that match a predicate
877 #[stable(feature = "rust1", since = "1.0.0")]
878 pub struct Split
<'a
, T
:'a
, P
> where P
: FnMut(&T
) -> bool
{
884 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
885 #[stable(feature = "rust1", since = "1.0.0")]
886 impl<'a
, T
, P
> Clone
for Split
<'a
, T
, P
> where P
: Clone
+ FnMut(&T
) -> bool
{
887 fn clone(&self) -> Split
<'a
, T
, P
> {
890 pred
: self.pred
.clone(),
891 finished
: self.finished
,
896 #[stable(feature = "rust1", since = "1.0.0")]
897 impl<'a
, T
, P
> Iterator
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
901 fn next(&mut self) -> Option
<&'a
[T
]> {
902 if self.finished { return None; }
904 match self.v
.iter().position(|x
| (self.pred
)(x
)) {
905 None
=> self.finish(),
907 let ret
= Some(&self.v
[..idx
]);
908 self.v
= &self.v
[idx
+ 1..];
915 fn size_hint(&self) -> (usize, Option
<usize>) {
919 (1, Some(self.v
.len() + 1))
924 #[stable(feature = "rust1", since = "1.0.0")]
925 impl<'a
, T
, P
> DoubleEndedIterator
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
927 fn next_back(&mut self) -> Option
<&'a
[T
]> {
928 if self.finished { return None; }
930 match self.v
.iter().rposition(|x
| (self.pred
)(x
)) {
931 None
=> self.finish(),
933 let ret
= Some(&self.v
[idx
+ 1..]);
934 self.v
= &self.v
[..idx
];
941 impl<'a
, T
, P
> SplitIter
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
943 fn finish(&mut self) -> Option
<&'a
[T
]> {
944 if self.finished { None }
else { self.finished = true; Some(self.v) }
948 /// An iterator over the subslices of the vector which are separated
949 /// by elements that match `pred`.
950 #[stable(feature = "rust1", since = "1.0.0")]
951 pub struct SplitMut
<'a
, T
:'a
, P
> where P
: FnMut(&T
) -> bool
{
957 impl<'a
, T
, P
> SplitIter
for SplitMut
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
959 fn finish(&mut self) -> Option
<&'a
mut [T
]> {
963 self.finished
= true;
964 Some(mem
::replace(&mut self.v
, &mut []))
969 #[stable(feature = "rust1", since = "1.0.0")]
970 impl<'a
, T
, P
> Iterator
for SplitMut
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
971 type Item
= &'a
mut [T
];
974 fn next(&mut self) -> Option
<&'a
mut [T
]> {
975 if self.finished { return None; }
977 let idx_opt
= { // work around borrowck limitations
978 let pred
= &mut self.pred
;
979 self.v
.iter().position(|x
| (*pred
)(x
))
982 None
=> self.finish(),
984 let tmp
= mem
::replace(&mut self.v
, &mut []);
985 let (head
, tail
) = tmp
.split_at_mut(idx
);
986 self.v
= &mut tail
[1..];
993 fn size_hint(&self) -> (usize, Option
<usize>) {
997 // if the predicate doesn't match anything, we yield one slice
998 // if it matches every element, we yield len+1 empty slices.
999 (1, Some(self.v
.len() + 1))
1004 #[stable(feature = "rust1", since = "1.0.0")]
1005 impl<'a
, T
, P
> DoubleEndedIterator
for SplitMut
<'a
, T
, P
> where
1006 P
: FnMut(&T
) -> bool
,
1009 fn next_back(&mut self) -> Option
<&'a
mut [T
]> {
1010 if self.finished { return None; }
1012 let idx_opt
= { // work around borrowck limitations
1013 let pred
= &mut self.pred
;
1014 self.v
.iter().rposition(|x
| (*pred
)(x
))
1017 None
=> self.finish(),
1019 let tmp
= mem
::replace(&mut self.v
, &mut []);
1020 let (head
, tail
) = tmp
.split_at_mut(idx
);
1022 Some(&mut tail
[1..])
1028 /// An private iterator over subslices separated by elements that
1029 /// match a predicate function, splitting at most a fixed number of
1031 struct GenericSplitN
<I
> {
1037 impl<T
, I
: SplitIter
<Item
=T
>> Iterator
for GenericSplitN
<I
> {
1041 fn next(&mut self) -> Option
<T
> {
1044 1 => { self.count -= 1; self.iter.finish() }
1047 if self.invert {self.iter.next_back()}
else {self.iter.next()}
1053 fn size_hint(&self) -> (usize, Option
<usize>) {
1054 let (lower
, upper_opt
) = self.iter
.size_hint();
1055 (lower
, upper_opt
.map(|upper
| cmp
::min(self.count
, upper
)))
1059 /// An iterator over subslices separated by elements that match a predicate
1060 /// function, limited to a given number of splits.
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 pub struct SplitN
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1063 inner
: GenericSplitN
<Split
<'a
, T
, P
>>
1066 /// An iterator over subslices separated by elements that match a
1067 /// predicate function, limited to a given number of splits, starting
1068 /// from the end of the slice.
1069 #[stable(feature = "rust1", since = "1.0.0")]
1070 pub struct RSplitN
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1071 inner
: GenericSplitN
<Split
<'a
, T
, P
>>
1074 /// An iterator over subslices separated by elements that match a predicate
1075 /// function, limited to a given number of splits.
1076 #[stable(feature = "rust1", since = "1.0.0")]
1077 pub struct SplitNMut
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1078 inner
: GenericSplitN
<SplitMut
<'a
, T
, P
>>
1081 /// An iterator over subslices separated by elements that match a
1082 /// predicate function, limited to a given number of splits, starting
1083 /// from the end of the slice.
1084 #[stable(feature = "rust1", since = "1.0.0")]
1085 pub struct RSplitNMut
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1086 inner
: GenericSplitN
<SplitMut
<'a
, T
, P
>>
1089 macro_rules
! forward_iterator
{
1090 ($name
:ident
: $elem
:ident
, $iter_of
:ty
) => {
1091 #[stable(feature = "rust1", since = "1.0.0")]
1092 impl<'a
, $elem
, P
> Iterator
for $name
<'a
, $elem
, P
> where
1093 P
: FnMut(&T
) -> bool
1095 type Item
= $iter_of
;
1098 fn next(&mut self) -> Option
<$iter_of
> {
1103 fn size_hint(&self) -> (usize, Option
<usize>) {
1104 self.inner
.size_hint()
1110 forward_iterator
! { SplitN: T, &'a [T] }
1111 forward_iterator
! { RSplitN: T, &'a [T] }
1112 forward_iterator
! { SplitNMut: T, &'a mut [T] }
1113 forward_iterator
! { RSplitNMut: T, &'a mut [T] }
1115 /// An iterator over overlapping subslices of length `size`.
1116 #[stable(feature = "rust1", since = "1.0.0")]
1117 pub struct Windows
<'a
, T
:'a
> {
1122 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<'a
, T
> Clone
for Windows
<'a
, T
> {
1125 fn clone(&self) -> Windows
<'a
, T
> {
1133 #[stable(feature = "rust1", since = "1.0.0")]
1134 impl<'a
, T
> Iterator
for Windows
<'a
, T
> {
1135 type Item
= &'a
[T
];
1138 fn next(&mut self) -> Option
<&'a
[T
]> {
1139 if self.size
> self.v
.len() {
1142 let ret
= Some(&self.v
[..self.size
]);
1143 self.v
= &self.v
[1..];
1149 fn size_hint(&self) -> (usize, Option
<usize>) {
1150 if self.size
> self.v
.len() {
1153 let size
= self.v
.len() - self.size
+ 1;
1159 #[stable(feature = "rust1", since = "1.0.0")]
1160 impl<'a
, T
> DoubleEndedIterator
for Windows
<'a
, T
> {
1162 fn next_back(&mut self) -> Option
<&'a
[T
]> {
1163 if self.size
> self.v
.len() {
1166 let ret
= Some(&self.v
[self.v
.len()-self.size
..]);
1167 self.v
= &self.v
[..self.v
.len()-1];
1173 #[stable(feature = "rust1", since = "1.0.0")]
1174 impl<'a
, T
> ExactSizeIterator
for Windows
<'a
, T
> {}
1176 #[unstable(feature = "core", reason = "trait is experimental")]
1177 impl<'a
, T
> RandomAccessIterator
for Windows
<'a
, T
> {
1179 fn indexable(&self) -> usize {
1184 fn idx(&mut self, index
: usize) -> Option
<&'a
[T
]> {
1185 if index
+ self.size
> self.v
.len() {
1188 Some(&self.v
[index
.. index
+self.size
])
1193 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1196 /// When the slice len is not evenly divided by the chunk size, the last slice
1197 /// of the iteration will be the remainder.
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 pub struct Chunks
<'a
, T
:'a
> {
1204 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1205 #[stable(feature = "rust1", since = "1.0.0")]
1206 impl<'a
, T
> Clone
for Chunks
<'a
, T
> {
1207 fn clone(&self) -> Chunks
<'a
, T
> {
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<'a
, T
> Iterator
for Chunks
<'a
, T
> {
1217 type Item
= &'a
[T
];
1220 fn next(&mut self) -> Option
<&'a
[T
]> {
1221 if self.v
.is_empty() {
1224 let chunksz
= cmp
::min(self.v
.len(), self.size
);
1225 let (fst
, snd
) = self.v
.split_at(chunksz
);
1232 fn size_hint(&self) -> (usize, Option
<usize>) {
1233 if self.v
.is_empty() {
1236 let n
= self.v
.len() / self.size
;
1237 let rem
= self.v
.len() % self.size
;
1238 let n
= if rem
> 0 { n+1 }
else { n }
;
1244 #[stable(feature = "rust1", since = "1.0.0")]
1245 impl<'a
, T
> DoubleEndedIterator
for Chunks
<'a
, T
> {
1247 fn next_back(&mut self) -> Option
<&'a
[T
]> {
1248 if self.v
.is_empty() {
1251 let remainder
= self.v
.len() % self.size
;
1252 let chunksz
= if remainder
!= 0 { remainder }
else { self.size }
;
1253 let (fst
, snd
) = self.v
.split_at(self.v
.len() - chunksz
);
1260 #[stable(feature = "rust1", since = "1.0.0")]
1261 impl<'a
, T
> ExactSizeIterator
for Chunks
<'a
, T
> {}
1263 #[unstable(feature = "core", reason = "trait is experimental")]
1264 impl<'a
, T
> RandomAccessIterator
for Chunks
<'a
, T
> {
1266 fn indexable(&self) -> usize {
1267 self.v
.len()/self.size
+ if self.v
.len() % self.size
!= 0 { 1 }
else { 0 }
1271 fn idx(&mut self, index
: usize) -> Option
<&'a
[T
]> {
1272 if index
< self.indexable() {
1273 let lo
= index
* self.size
;
1274 let mut hi
= lo
+ self.size
;
1275 if hi
< lo
|| hi
> self.v
.len() { hi = self.v.len(); }
1277 Some(&self.v
[lo
..hi
])
1284 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1285 /// elements at a time). When the slice len is not evenly divided by the chunk
1286 /// size, the last slice of the iteration will be the remainder.
1287 #[stable(feature = "rust1", since = "1.0.0")]
1288 pub struct ChunksMut
<'a
, T
:'a
> {
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 impl<'a
, T
> Iterator
for ChunksMut
<'a
, T
> {
1295 type Item
= &'a
mut [T
];
1298 fn next(&mut self) -> Option
<&'a
mut [T
]> {
1299 if self.v
.is_empty() {
1302 let sz
= cmp
::min(self.v
.len(), self.chunk_size
);
1303 let tmp
= mem
::replace(&mut self.v
, &mut []);
1304 let (head
, tail
) = tmp
.split_at_mut(sz
);
1311 fn size_hint(&self) -> (usize, Option
<usize>) {
1312 if self.v
.is_empty() {
1315 let n
= self.v
.len() / self.chunk_size
;
1316 let rem
= self.v
.len() % self.chunk_size
;
1317 let n
= if rem
> 0 { n + 1 }
else { n }
;
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 impl<'a
, T
> DoubleEndedIterator
for ChunksMut
<'a
, T
> {
1326 fn next_back(&mut self) -> Option
<&'a
mut [T
]> {
1327 if self.v
.is_empty() {
1330 let remainder
= self.v
.len() % self.chunk_size
;
1331 let sz
= if remainder
!= 0 { remainder }
else { self.chunk_size }
;
1332 let tmp
= mem
::replace(&mut self.v
, &mut []);
1333 let tmp_len
= tmp
.len();
1334 let (head
, tail
) = tmp
.split_at_mut(tmp_len
- sz
);
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 impl<'a
, T
> ExactSizeIterator
for ChunksMut
<'a
, T
> {}
1348 /// Converts a pointer to A into a slice of length 1 (without copying).
1349 #[unstable(feature = "core")]
1350 pub fn ref_slice
<'a
, A
>(s
: &'a A
) -> &'a
[A
] {
1352 from_raw_parts(s
, 1)
1356 /// Converts a pointer to A into a slice of length 1 (without copying).
1357 #[unstable(feature = "core")]
1358 pub fn mut_ref_slice
<'a
, A
>(s
: &'a
mut A
) -> &'a
mut [A
] {
1360 from_raw_parts_mut(s
, 1)
1364 /// Forms a slice from a pointer and a length.
1366 /// The `len` argument is the number of **elements**, not the number of bytes.
1368 /// This function is unsafe as there is no guarantee that the given pointer is
1369 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
1370 /// lifetime for the returned slice.
1374 /// The lifetime for the returned slice is inferred from its usage. To
1375 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
1376 /// source lifetime is safe in the context, such as by providing a helper
1377 /// function taking the lifetime of a host value for the slice, or by explicit
1385 /// // manifest a slice out of thin air!
1386 /// let ptr = 0x1234 as *const usize;
1389 /// let slice = slice::from_raw_parts(ptr, amt);
1393 #[stable(feature = "rust1", since = "1.0.0")]
1394 pub unsafe fn from_raw_parts
<'a
, T
>(p
: *const T
, len
: usize) -> &'a
[T
] {
1395 transmute(RawSlice { data: p, len: len }
)
1398 /// Performs the same functionality as `from_raw_parts`, except that a mutable
1399 /// slice is returned.
1401 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
1402 /// as not being able to provide a non-aliasing guarantee of the returned
1405 #[stable(feature = "rust1", since = "1.0.0")]
1406 pub unsafe fn from_raw_parts_mut
<'a
, T
>(p
: *mut T
, len
: usize) -> &'a
mut [T
] {
1407 transmute(RawSlice { data: p, len: len }
)
1414 /// Operations on `[u8]`.
1415 #[unstable(feature = "core", reason = "needs review")]
1418 use slice
::SliceExt
;
1420 /// A trait for operations on mutable `[u8]`s.
1421 pub trait MutableByteVector
{
1422 /// Sets all bytes of the receiver to the given value.
1423 fn set_memory(&mut self, value
: u8);
1426 impl MutableByteVector
for [u8] {
1428 fn set_memory(&mut self, value
: u8) {
1429 unsafe { ptr::write_bytes(self.as_mut_ptr(), value, self.len()) }
;
1433 /// Copies data from `src` to `dst`
1435 /// Panics if the length of `dst` is less than the length of `src`.
1437 pub fn copy_memory(src
: &[u8], dst
: &mut [u8]) {
1438 let len_src
= src
.len();
1439 assert
!(dst
.len() >= len_src
);
1440 // `dst` is unaliasable, so we know statically it doesn't overlap
1443 ptr
::copy_nonoverlapping(src
.as_ptr(),
1453 // Boilerplate traits
1456 #[stable(feature = "rust1", since = "1.0.0")]
1457 impl<A
, B
> PartialEq
<[B
]> for [A
] where A
: PartialEq
<B
> {
1458 fn eq(&self, other
: &[B
]) -> bool
{
1459 self.len() == other
.len() &&
1460 order
::eq(self.iter(), other
.iter())
1462 fn ne(&self, other
: &[B
]) -> bool
{
1463 self.len() != other
.len() ||
1464 order
::ne(self.iter(), other
.iter())
1468 #[stable(feature = "rust1", since = "1.0.0")]
1469 impl<T
: Eq
> Eq
for [T
] {}
1471 #[stable(feature = "rust1", since = "1.0.0")]
1472 impl<T
: Ord
> Ord
for [T
] {
1473 fn cmp(&self, other
: &[T
]) -> Ordering
{
1474 order
::cmp(self.iter(), other
.iter())
1478 #[stable(feature = "rust1", since = "1.0.0")]
1479 impl<T
: PartialOrd
> PartialOrd
for [T
] {
1481 fn partial_cmp(&self, other
: &[T
]) -> Option
<Ordering
> {
1482 order
::partial_cmp(self.iter(), other
.iter())
1485 fn lt(&self, other
: &[T
]) -> bool
{
1486 order
::lt(self.iter(), other
.iter())
1489 fn le(&self, other
: &[T
]) -> bool
{
1490 order
::le(self.iter(), other
.iter())
1493 fn ge(&self, other
: &[T
]) -> bool
{
1494 order
::ge(self.iter(), other
.iter())
1497 fn gt(&self, other
: &[T
]) -> bool
{
1498 order
::gt(self.iter(), other
.iter())
1502 /// Extension methods for slices containing integers.
1503 #[unstable(feature = "core")]
1504 pub trait IntSliceExt
<U
, S
> {
1505 /// Converts the slice to an immutable slice of unsigned integers with the same width.
1506 fn as_unsigned
<'a
>(&'a
self) -> &'a
[U
];
1507 /// Converts the slice to an immutable slice of signed integers with the same width.
1508 fn as_signed
<'a
>(&'a
self) -> &'a
[S
];
1510 /// Converts the slice to a mutable slice of unsigned integers with the same width.
1511 fn as_unsigned_mut
<'a
>(&'a
mut self) -> &'a
mut [U
];
1512 /// Converts the slice to a mutable slice of signed integers with the same width.
1513 fn as_signed_mut
<'a
>(&'a
mut self) -> &'a
mut [S
];
1516 macro_rules
! impl_int_slice
{
1517 ($u
:ty
, $s
:ty
, $t
:ty
) => {
1518 #[unstable(feature = "core")]
1519 impl IntSliceExt
<$u
, $s
> for [$t
] {
1521 fn as_unsigned(&self) -> &[$u
] { unsafe { transmute(self) }
}
1523 fn as_signed(&self) -> &[$s
] { unsafe { transmute(self) }
}
1525 fn as_unsigned_mut(&mut self) -> &mut [$u
] { unsafe { transmute(self) }
}
1527 fn as_signed_mut(&mut self) -> &mut [$s
] { unsafe { transmute(self) }
}
1532 macro_rules
! impl_int_slices
{
1534 impl_int_slice
! { $u, $s, $u }
1535 impl_int_slice
! { $u, $s, $s }
1539 impl_int_slices
! { u8, i8 }
1540 impl_int_slices
! { u16, i16 }
1541 impl_int_slices
! { u32, i32 }
1542 impl_int_slices
! { u64, i64 }
1543 impl_int_slices
! { usize, isize }