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")]
17 // How this module is organized.
19 // The library infrastructure for slices is fairly messy. There's
20 // a lot of stuff defined here. Let's keep it clean.
22 // Since slices don't support inherent methods; all operations
23 // on them are defined on traits, which are then reexported from
24 // the prelude for convenience. So there are a lot of traits here.
26 // The layout of this file is thus:
28 // * Slice-specific 'extension' traits and their implementations. This
29 // is where most of the slice API resides.
30 // * Implementations of a few common traits with important slice ops.
31 // * Definitions of a bunch of iterators.
33 // * The `raw` and `bytes` submodules.
34 // * Boilerplate trait implementations.
37 use cmp
::{Ordering, PartialEq, PartialOrd, Eq, Ord}
;
38 use cmp
::Ordering
::{Less, Equal, Greater}
;
41 use intrinsics
::assume
;
43 use ops
::{FnMut, self, Index}
;
46 use option
::Option
::{None, Some}
;
48 use result
::Result
::{Ok, Err}
;
52 use marker
::{Send, Sync, self}
;
53 use num
::wrapping
::OverflowingOps
;
55 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
56 use raw
::Slice
as RawSlice
;
63 /// Extension methods for slices.
64 #[allow(missing_docs)] // docs in libcollections
66 #[unstable(feature = "core_slice_ext",
67 reason
= "stable interface provided by `impl [T]` in later crates",
72 fn split_at(&self, mid
: usize) -> (&[Self::Item
], &[Self::Item
]);
73 fn iter(&self) -> Iter
<Self::Item
>;
74 fn split
<P
>(&self, pred
: P
) -> Split
<Self::Item
, P
>
75 where P
: FnMut(&Self::Item
) -> bool
;
76 fn splitn
<P
>(&self, n
: usize, pred
: P
) -> SplitN
<Self::Item
, P
>
77 where P
: FnMut(&Self::Item
) -> bool
;
78 fn rsplitn
<P
>(&self, n
: usize, pred
: P
) -> RSplitN
<Self::Item
, P
>
79 where P
: FnMut(&Self::Item
) -> bool
;
80 fn windows(&self, size
: usize) -> Windows
<Self::Item
>;
81 fn chunks(&self, size
: usize) -> Chunks
<Self::Item
>;
82 fn get(&self, index
: usize) -> Option
<&Self::Item
>;
83 fn first(&self) -> Option
<&Self::Item
>;
84 fn tail(&self) -> &[Self::Item
];
85 fn init(&self) -> &[Self::Item
];
86 fn split_first(&self) -> Option
<(&Self::Item
, &[Self::Item
])>;
87 fn split_last(&self) -> Option
<(&Self::Item
, &[Self::Item
])>;
88 fn last(&self) -> Option
<&Self::Item
>;
89 unsafe fn get_unchecked(&self, index
: usize) -> &Self::Item
;
90 fn as_ptr(&self) -> *const Self::Item
;
91 fn binary_search_by
<F
>(&self, f
: F
) -> Result
<usize, usize> where
92 F
: FnMut(&Self::Item
) -> Ordering
;
93 fn len(&self) -> usize;
94 fn is_empty(&self) -> bool { self.len() == 0 }
95 fn get_mut(&mut self, index
: usize) -> Option
<&mut Self::Item
>;
96 fn iter_mut(&mut self) -> IterMut
<Self::Item
>;
97 fn first_mut(&mut self) -> Option
<&mut Self::Item
>;
98 fn tail_mut(&mut self) -> &mut [Self::Item
];
99 fn init_mut(&mut self) -> &mut [Self::Item
];
100 fn split_first_mut(&mut self) -> Option
<(&mut Self::Item
, &mut [Self::Item
])>;
101 fn split_last_mut(&mut self) -> Option
<(&mut Self::Item
, &mut [Self::Item
])>;
102 fn last_mut(&mut self) -> Option
<&mut Self::Item
>;
103 fn split_mut
<P
>(&mut self, pred
: P
) -> SplitMut
<Self::Item
, P
>
104 where P
: FnMut(&Self::Item
) -> bool
;
105 fn splitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> SplitNMut
<Self::Item
, P
>
106 where P
: FnMut(&Self::Item
) -> bool
;
107 fn rsplitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> RSplitNMut
<Self::Item
, P
>
108 where P
: FnMut(&Self::Item
) -> bool
;
109 fn chunks_mut(&mut self, chunk_size
: usize) -> ChunksMut
<Self::Item
>;
110 fn swap(&mut self, a
: usize, b
: usize);
111 fn split_at_mut(&mut self, mid
: usize) -> (&mut [Self::Item
], &mut [Self::Item
]);
112 fn reverse(&mut self);
113 unsafe fn get_unchecked_mut(&mut self, index
: usize) -> &mut Self::Item
;
114 fn as_mut_ptr(&mut self) -> *mut Self::Item
;
116 fn position_elem(&self, t
: &Self::Item
) -> Option
<usize> where Self::Item
: PartialEq
;
118 fn rposition_elem(&self, t
: &Self::Item
) -> Option
<usize> where Self::Item
: PartialEq
;
120 fn contains(&self, x
: &Self::Item
) -> bool
where Self::Item
: PartialEq
;
122 fn starts_with(&self, needle
: &[Self::Item
]) -> bool
where Self::Item
: PartialEq
;
124 fn ends_with(&self, needle
: &[Self::Item
]) -> bool
where Self::Item
: PartialEq
;
126 fn binary_search(&self, x
: &Self::Item
) -> Result
<usize, usize> where Self::Item
: Ord
;
127 fn next_permutation(&mut self) -> bool
where Self::Item
: Ord
;
128 fn prev_permutation(&mut self) -> bool
where Self::Item
: Ord
;
130 fn clone_from_slice(&mut self, &[Self::Item
]) -> usize where Self::Item
: Clone
;
133 // Use macros to be generic over const/mut
134 macro_rules
! slice_offset
{
135 ($ptr
:expr
, $by
:expr
) => {{
137 if size_from_ptr(ptr
) == 0 {
138 ::intrinsics
::arith_offset(ptr
as *mut i8, $by
) as *mut _
145 macro_rules
! slice_ref
{
148 if size_from_ptr(ptr
) == 0 {
149 // Use a non-null pointer value
157 impl<T
> SliceExt
for [T
] {
161 fn split_at(&self, mid
: usize) -> (&[T
], &[T
]) {
162 (&self[..mid
], &self[mid
..])
166 fn iter(&self) -> Iter
<T
> {
168 let p
= if mem
::size_of
::<T
>() == 0 {
171 let p
= self.as_ptr();
172 assume(!p
.is_null());
178 end
: slice_offset
!(p
, self.len() as isize),
179 _marker
: marker
::PhantomData
185 fn split
<P
>(&self, pred
: P
) -> Split
<T
, P
> where P
: FnMut(&T
) -> bool
{
194 fn splitn
<P
>(&self, n
: usize, pred
: P
) -> SplitN
<T
, P
> where
195 P
: FnMut(&T
) -> bool
,
198 inner
: GenericSplitN
{
199 iter
: self.split(pred
),
207 fn rsplitn
<P
>(&self, n
: usize, pred
: P
) -> RSplitN
<T
, P
> where
208 P
: FnMut(&T
) -> bool
,
211 inner
: GenericSplitN
{
212 iter
: self.split(pred
),
220 fn windows(&self, size
: usize) -> Windows
<T
> {
222 Windows { v: self, size: size }
226 fn chunks(&self, size
: usize) -> Chunks
<T
> {
228 Chunks { v: self, size: size }
232 fn get(&self, index
: usize) -> Option
<&T
> {
233 if index
< self.len() { Some(&self[index]) }
else { None }
237 fn first(&self) -> Option
<&T
> {
238 if self.is_empty() { None }
else { Some(&self[0]) }
242 fn tail(&self) -> &[T
] { &self[1..] }
245 fn split_first(&self) -> Option
<(&T
, &[T
])> {
246 if self.is_empty() { None }
else { Some((&self[0], &self[1..])) }
250 fn init(&self) -> &[T
] { &self[..self.len() - 1] }
253 fn split_last(&self) -> Option
<(&T
, &[T
])> {
254 let len
= self.len();
255 if len
== 0 { None }
else { Some((&self[len - 1], &self[..(len - 1)])) }
259 fn last(&self) -> Option
<&T
> {
260 if self.is_empty() { None }
else { Some(&self[self.len() - 1]) }
264 unsafe fn get_unchecked(&self, index
: usize) -> &T
{
265 &*(self.repr().data
.offset(index
as isize))
269 fn as_ptr(&self) -> *const T
{
273 fn binary_search_by
<F
>(&self, mut f
: F
) -> Result
<usize, usize> where
274 F
: FnMut(&T
) -> Ordering
276 let mut base
: usize = 0;
277 let mut lim
: usize = self.len();
280 let ix
= base
+ (lim
>> 1);
282 Equal
=> return Ok(ix
),
295 fn len(&self) -> usize { self.repr().len }
298 fn get_mut(&mut self, index
: usize) -> Option
<&mut T
> {
299 if index
< self.len() { Some(&mut self[index]) }
else { None }
303 fn split_at_mut(&mut self, mid
: usize) -> (&mut [T
], &mut [T
]) {
304 let len
= self.len();
305 let ptr
= self.as_mut_ptr();
310 (from_raw_parts_mut(ptr
, mid
),
311 from_raw_parts_mut(ptr
.offset(mid
as isize), len
- mid
))
316 fn iter_mut(&mut self) -> IterMut
<T
> {
318 let p
= if mem
::size_of
::<T
>() == 0 {
321 let p
= self.as_mut_ptr();
322 assume(!p
.is_null());
328 end
: slice_offset
!(p
, self.len() as isize),
329 _marker
: marker
::PhantomData
335 fn last_mut(&mut self) -> Option
<&mut T
> {
336 let len
= self.len();
337 if len
== 0 { return None; }
338 Some(&mut self[len
- 1])
342 fn first_mut(&mut self) -> Option
<&mut T
> {
343 if self.is_empty() { None }
else { Some(&mut self[0]) }
347 fn tail_mut(&mut self) -> &mut [T
] { &mut self[1 ..] }
350 fn split_first_mut(&mut self) -> Option
<(&mut T
, &mut [T
])> {
351 if self.is_empty() { None }
else {
352 let split
= self.split_at_mut(1);
353 Some((&mut split
.0[0], split
.1))
358 fn init_mut(&mut self) -> &mut [T
] {
359 let len
= self.len();
360 &mut self[.. (len
- 1)]
364 fn split_last_mut(&mut self) -> Option
<(&mut T
, &mut [T
])> {
365 let len
= self.len();
366 if len
== 0 { None }
else {
367 let split
= self.split_at_mut(len
- 1);
368 Some((&mut split
.1[0], split
.0))
373 fn split_mut
<P
>(&mut self, pred
: P
) -> SplitMut
<T
, P
> where P
: FnMut(&T
) -> bool
{
374 SplitMut { v: self, pred: pred, finished: false }
378 fn splitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> SplitNMut
<T
, P
> where
382 inner
: GenericSplitN
{
383 iter
: self.split_mut(pred
),
391 fn rsplitn_mut
<P
>(&mut self, n
: usize, pred
: P
) -> RSplitNMut
<T
, P
> where
392 P
: FnMut(&T
) -> bool
,
395 inner
: GenericSplitN
{
396 iter
: self.split_mut(pred
),
404 fn chunks_mut(&mut self, chunk_size
: usize) -> ChunksMut
<T
> {
405 assert
!(chunk_size
> 0);
406 ChunksMut { v: self, chunk_size: chunk_size }
410 fn swap(&mut self, a
: usize, b
: usize) {
412 // Can't take two mutable loans from one vector, so instead just cast
413 // them to their raw pointers to do the swap
414 let pa
: *mut T
= &mut self[a
];
415 let pb
: *mut T
= &mut self[b
];
420 fn reverse(&mut self) {
421 let mut i
: usize = 0;
424 // Unsafe swap to avoid the bounds check in safe swap.
426 let pa
: *mut T
= self.get_unchecked_mut(i
);
427 let pb
: *mut T
= self.get_unchecked_mut(ln
- i
- 1);
435 unsafe fn get_unchecked_mut(&mut self, index
: usize) -> &mut T
{
436 &mut *(self.repr().data
as *mut T
).offset(index
as isize)
440 fn as_mut_ptr(&mut self) -> *mut T
{
441 self.repr().data
as *mut T
445 fn position_elem(&self, x
: &T
) -> Option
<usize> where T
: PartialEq
{
446 self.iter().position(|y
| *x
== *y
)
450 fn rposition_elem(&self, t
: &T
) -> Option
<usize> where T
: PartialEq
{
451 self.iter().rposition(|x
| *x
== *t
)
455 fn contains(&self, x
: &T
) -> bool
where T
: PartialEq
{
456 self.iter().any(|elt
| *x
== *elt
)
460 fn starts_with(&self, needle
: &[T
]) -> bool
where T
: PartialEq
{
461 let n
= needle
.len();
462 self.len() >= n
&& needle
== &self[..n
]
466 fn ends_with(&self, needle
: &[T
]) -> bool
where T
: PartialEq
{
467 let (m
, n
) = (self.len(), needle
.len());
468 m
>= n
&& needle
== &self[m
-n
..]
471 fn binary_search(&self, x
: &T
) -> Result
<usize, usize> where T
: Ord
{
472 self.binary_search_by(|p
| p
.cmp(x
))
475 fn next_permutation(&mut self) -> bool
where T
: Ord
{
476 // These cases only have 1 permutation each, so we can't do anything.
477 if self.len() < 2 { return false; }
479 // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
480 let mut i
= self.len() - 1;
481 while i
> 0 && self[i
-1] >= self[i
] {
485 // If that is the entire vector, this is the last-ordered permutation.
490 // Step 2: Find the rightmost element larger than the pivot (i-1)
491 let mut j
= self.len() - 1;
492 while j
>= i
&& self[j
] <= self[i
-1] {
496 // Step 3: Swap that element with the pivot
499 // Step 4: Reverse the (previously) weakly decreasing part
505 fn prev_permutation(&mut self) -> bool
where T
: Ord
{
506 // These cases only have 1 permutation each, so we can't do anything.
507 if self.len() < 2 { return false; }
509 // Step 1: Identify the longest, rightmost weakly increasing part of the vector
510 let mut i
= self.len() - 1;
511 while i
> 0 && self[i
-1] <= self[i
] {
515 // If that is the entire vector, this is the first-ordered permutation.
520 // Step 2: Reverse the weakly increasing part
523 // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
524 let mut j
= self.len() - 1;
525 while j
>= i
&& self[j
-1] < self[i
-1] {
529 // Step 4: Swap that element with the pivot
536 fn clone_from_slice(&mut self, src
: &[T
]) -> usize where T
: Clone
{
537 let min
= cmp
::min(self.len(), src
.len());
538 let dst
= &mut self[.. min
];
539 let src
= &src
[.. min
];
541 dst
[i
].clone_from(&src
[i
]);
547 #[stable(feature = "rust1", since = "1.0.0")]
548 impl<T
> ops
::Index
<usize> for [T
] {
551 fn index(&self, index
: usize) -> &T
{
552 assert
!(index
< self.len());
553 unsafe { self.get_unchecked(index) }
557 #[stable(feature = "rust1", since = "1.0.0")]
558 impl<T
> ops
::IndexMut
<usize> for [T
] {
560 fn index_mut(&mut self, index
: usize) -> &mut T
{
561 assert
!(index
< self.len());
562 unsafe { self.get_unchecked_mut(index) }
566 #[stable(feature = "rust1", since = "1.0.0")]
567 impl<T
> ops
::Index
<ops
::Range
<usize>> for [T
] {
571 fn index(&self, index
: ops
::Range
<usize>) -> &[T
] {
572 assert
!(index
.start
<= index
.end
);
573 assert
!(index
.end
<= self.len());
576 self.as_ptr().offset(index
.start
as isize),
577 index
.end
- index
.start
582 #[stable(feature = "rust1", since = "1.0.0")]
583 impl<T
> ops
::Index
<ops
::RangeTo
<usize>> for [T
] {
587 fn index(&self, index
: ops
::RangeTo
<usize>) -> &[T
] {
588 self.index(ops
::Range{ start: 0, end: index.end }
)
591 #[stable(feature = "rust1", since = "1.0.0")]
592 impl<T
> ops
::Index
<ops
::RangeFrom
<usize>> for [T
] {
596 fn index(&self, index
: ops
::RangeFrom
<usize>) -> &[T
] {
597 self.index(ops
::Range{ start: index.start, end: self.len() }
)
600 #[stable(feature = "rust1", since = "1.0.0")]
601 impl<T
> ops
::Index
<RangeFull
> for [T
] {
605 fn index(&self, _index
: RangeFull
) -> &[T
] {
610 #[stable(feature = "rust1", since = "1.0.0")]
611 impl<T
> ops
::IndexMut
<ops
::Range
<usize>> for [T
] {
613 fn index_mut(&mut self, index
: ops
::Range
<usize>) -> &mut [T
] {
614 assert
!(index
.start
<= index
.end
);
615 assert
!(index
.end
<= self.len());
618 self.as_mut_ptr().offset(index
.start
as isize),
619 index
.end
- index
.start
624 #[stable(feature = "rust1", since = "1.0.0")]
625 impl<T
> ops
::IndexMut
<ops
::RangeTo
<usize>> for [T
] {
627 fn index_mut(&mut self, index
: ops
::RangeTo
<usize>) -> &mut [T
] {
628 self.index_mut(ops
::Range{ start: 0, end: index.end }
)
631 #[stable(feature = "rust1", since = "1.0.0")]
632 impl<T
> ops
::IndexMut
<ops
::RangeFrom
<usize>> for [T
] {
634 fn index_mut(&mut self, index
: ops
::RangeFrom
<usize>) -> &mut [T
] {
635 let len
= self.len();
636 self.index_mut(ops
::Range{ start: index.start, end: len }
)
639 #[stable(feature = "rust1", since = "1.0.0")]
640 impl<T
> ops
::IndexMut
<RangeFull
> for [T
] {
642 fn index_mut(&mut self, _index
: RangeFull
) -> &mut [T
] {
648 ////////////////////////////////////////////////////////////////////////////////
650 ////////////////////////////////////////////////////////////////////////////////
652 #[stable(feature = "rust1", since = "1.0.0")]
653 impl<'a
, T
> Default
for &'a
[T
] {
654 #[stable(feature = "rust1", since = "1.0.0")]
655 fn default() -> &'a
[T
] { &[] }
658 #[stable(feature = "mut_slice_default", since = "1.5.0")]
659 impl<'a
, T
> Default
for &'a
mut [T
] {
660 fn default() -> &'a
mut [T
] { &mut [] }
667 #[stable(feature = "rust1", since = "1.0.0")]
668 impl<'a
, T
> IntoIterator
for &'a
[T
] {
670 type IntoIter
= Iter
<'a
, T
>;
672 fn into_iter(self) -> Iter
<'a
, T
> {
677 #[stable(feature = "rust1", since = "1.0.0")]
678 impl<'a
, T
> IntoIterator
for &'a
mut [T
] {
679 type Item
= &'a
mut T
;
680 type IntoIter
= IterMut
<'a
, T
>;
682 fn into_iter(self) -> IterMut
<'a
, T
> {
688 fn size_from_ptr
<T
>(_
: *const T
) -> usize {
692 // The shared definition of the `Iter` and `IterMut` iterators
693 macro_rules
! iterator
{
694 (struct $name
:ident
-> $ptr
:ty
, $elem
:ty
) => {
695 #[stable(feature = "rust1", since = "1.0.0")]
696 impl<'a
, T
> Iterator
for $name
<'a
, T
> {
700 fn next(&mut self) -> Option
<$elem
> {
701 // could be implemented with slices, but this avoids bounds checks
703 if mem
::size_of
::<T
>() != 0 {
704 assume(!self.ptr
.is_null());
705 assume(!self.end
.is_null());
707 if self.ptr
== self.end
{
711 self.ptr
= slice_offset
!(self.ptr
, 1);
712 Some(slice_ref
!(old
))
718 fn size_hint(&self) -> (usize, Option
<usize>) {
719 let diff
= (self.end
as usize).wrapping_sub(self.ptr
as usize);
720 let size
= mem
::size_of
::<T
>();
721 let exact
= diff
/ (if size
== 0 {1}
else {size}
);
726 fn count(self) -> usize {
731 fn nth(&mut self, n
: usize) -> Option
<$elem
> {
732 // Call helper method. Can't put the definition here because mut versus const.
737 fn last(mut self) -> Option
<$elem
> {
742 #[stable(feature = "rust1", since = "1.0.0")]
743 impl<'a
, T
> DoubleEndedIterator
for $name
<'a
, T
> {
745 fn next_back(&mut self) -> Option
<$elem
> {
746 // could be implemented with slices, but this avoids bounds checks
748 if mem
::size_of
::<T
>() != 0 {
749 assume(!self.ptr
.is_null());
750 assume(!self.end
.is_null());
752 if self.end
== self.ptr
{
755 self.end
= slice_offset
!(self.end
, -1);
756 Some(slice_ref
!(self.end
))
764 macro_rules
! make_slice
{
765 ($start
: expr
, $end
: expr
) => {{
767 let diff
= ($end
as usize).wrapping_sub(start
as usize);
768 if size_from_ptr(start
) == 0 {
769 // use a non-null pointer value
770 unsafe { from_raw_parts(1 as *const _, diff) }
772 let len
= diff
/ size_from_ptr(start
);
773 unsafe { from_raw_parts(start, len) }
778 macro_rules
! make_mut_slice
{
779 ($start
: expr
, $end
: expr
) => {{
781 let diff
= ($end
as usize).wrapping_sub(start
as usize);
782 if size_from_ptr(start
) == 0 {
783 // use a non-null pointer value
784 unsafe { from_raw_parts_mut(1 as *mut _, diff) }
786 let len
= diff
/ size_from_ptr(start
);
787 unsafe { from_raw_parts_mut(start, len) }
792 /// Immutable slice iterator
793 #[stable(feature = "rust1", since = "1.0.0")]
794 pub struct Iter
<'a
, T
: 'a
> {
797 _marker
: marker
::PhantomData
<&'a T
>,
800 unsafe impl<'a
, T
: Sync
> Sync
for Iter
<'a
, T
> {}
801 unsafe impl<'a
, T
: Sync
> Send
for Iter
<'a
, T
> {}
803 impl<'a
, T
> Iter
<'a
, T
> {
804 /// View the underlying data as a subslice of the original data.
806 /// This has the same lifetime as the original slice, and so the
807 /// iterator can continue to be used while this exists.
808 #[stable(feature = "iter_to_slice", since = "1.4.0")]
809 pub fn as_slice(&self) -> &'a
[T
] {
810 make_slice
!(self.ptr
, self.end
)
813 // Helper function for Iter::nth
814 fn iter_nth(&mut self, n
: usize) -> Option
<&'a T
> {
815 match self.as_slice().get(n
) {
816 Some(elem_ref
) => unsafe {
817 self.ptr
= slice_offset
!(self.ptr
, (n
as isize).wrapping_add(1));
828 iterator
!{struct Iter -> *const T, &'a T}
830 #[stable(feature = "rust1", since = "1.0.0")]
831 impl<'a
, T
> ExactSizeIterator
for Iter
<'a
, T
> {}
833 #[stable(feature = "rust1", since = "1.0.0")]
834 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
835 fn clone(&self) -> Iter
<'a
, T
> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
}
838 /// Mutable slice iterator.
839 #[stable(feature = "rust1", since = "1.0.0")]
840 pub struct IterMut
<'a
, T
: 'a
> {
843 _marker
: marker
::PhantomData
<&'a
mut T
>,
846 unsafe impl<'a
, T
: Sync
> Sync
for IterMut
<'a
, T
> {}
847 unsafe impl<'a
, T
: Send
> Send
for IterMut
<'a
, T
> {}
849 impl<'a
, T
> IterMut
<'a
, T
> {
850 /// View the underlying data as a subslice of the original data.
852 /// To avoid creating `&mut` references that alias, this is forced
853 /// to consume the iterator. Consider using the `Slice` and
854 /// `SliceMut` implementations for obtaining slices with more
855 /// restricted lifetimes that do not consume the iterator.
856 #[stable(feature = "iter_to_slice", since = "1.4.0")]
857 pub fn into_slice(self) -> &'a
mut [T
] {
858 make_mut_slice
!(self.ptr
, self.end
)
861 // Helper function for IterMut::nth
862 fn iter_nth(&mut self, n
: usize) -> Option
<&'a
mut T
> {
863 match make_mut_slice
!(self.ptr
, self.end
).get_mut(n
) {
864 Some(elem_ref
) => unsafe {
865 self.ptr
= slice_offset
!(self.ptr
, (n
as isize).wrapping_add(1));
876 iterator
!{struct IterMut -> *mut T, &'a mut T}
878 #[stable(feature = "rust1", since = "1.0.0")]
879 impl<'a
, T
> ExactSizeIterator
for IterMut
<'a
, T
> {}
881 /// An internal abstraction over the splitting iterators, so that
882 /// splitn, splitn_mut etc can be implemented once.
883 trait SplitIter
: DoubleEndedIterator
{
884 /// Mark the underlying iterator as complete, extracting the remaining
885 /// portion of the slice.
886 fn finish(&mut self) -> Option
<Self::Item
>;
889 /// An iterator over subslices separated by elements that match a predicate
891 #[stable(feature = "rust1", since = "1.0.0")]
892 pub struct Split
<'a
, T
:'a
, P
> where P
: FnMut(&T
) -> bool
{
898 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
899 #[stable(feature = "rust1", since = "1.0.0")]
900 impl<'a
, T
, P
> Clone
for Split
<'a
, T
, P
> where P
: Clone
+ FnMut(&T
) -> bool
{
901 fn clone(&self) -> Split
<'a
, T
, P
> {
904 pred
: self.pred
.clone(),
905 finished
: self.finished
,
910 #[stable(feature = "rust1", since = "1.0.0")]
911 impl<'a
, T
, P
> Iterator
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
915 fn next(&mut self) -> Option
<&'a
[T
]> {
916 if self.finished { return None; }
918 match self.v
.iter().position(|x
| (self.pred
)(x
)) {
919 None
=> self.finish(),
921 let ret
= Some(&self.v
[..idx
]);
922 self.v
= &self.v
[idx
+ 1..];
929 fn size_hint(&self) -> (usize, Option
<usize>) {
933 (1, Some(self.v
.len() + 1))
938 #[stable(feature = "rust1", since = "1.0.0")]
939 impl<'a
, T
, P
> DoubleEndedIterator
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
941 fn next_back(&mut self) -> Option
<&'a
[T
]> {
942 if self.finished { return None; }
944 match self.v
.iter().rposition(|x
| (self.pred
)(x
)) {
945 None
=> self.finish(),
947 let ret
= Some(&self.v
[idx
+ 1..]);
948 self.v
= &self.v
[..idx
];
955 impl<'a
, T
, P
> SplitIter
for Split
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
957 fn finish(&mut self) -> Option
<&'a
[T
]> {
958 if self.finished { None }
else { self.finished = true; Some(self.v) }
962 /// An iterator over the subslices of the vector which are separated
963 /// by elements that match `pred`.
964 #[stable(feature = "rust1", since = "1.0.0")]
965 pub struct SplitMut
<'a
, T
:'a
, P
> where P
: FnMut(&T
) -> bool
{
971 impl<'a
, T
, P
> SplitIter
for SplitMut
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
973 fn finish(&mut self) -> Option
<&'a
mut [T
]> {
977 self.finished
= true;
978 Some(mem
::replace(&mut self.v
, &mut []))
983 #[stable(feature = "rust1", since = "1.0.0")]
984 impl<'a
, T
, P
> Iterator
for SplitMut
<'a
, T
, P
> where P
: FnMut(&T
) -> bool
{
985 type Item
= &'a
mut [T
];
988 fn next(&mut self) -> Option
<&'a
mut [T
]> {
989 if self.finished { return None; }
991 let idx_opt
= { // work around borrowck limitations
992 let pred
= &mut self.pred
;
993 self.v
.iter().position(|x
| (*pred
)(x
))
996 None
=> self.finish(),
998 let tmp
= mem
::replace(&mut self.v
, &mut []);
999 let (head
, tail
) = tmp
.split_at_mut(idx
);
1000 self.v
= &mut tail
[1..];
1007 fn size_hint(&self) -> (usize, Option
<usize>) {
1011 // if the predicate doesn't match anything, we yield one slice
1012 // if it matches every element, we yield len+1 empty slices.
1013 (1, Some(self.v
.len() + 1))
1018 #[stable(feature = "rust1", since = "1.0.0")]
1019 impl<'a
, T
, P
> DoubleEndedIterator
for SplitMut
<'a
, T
, P
> where
1020 P
: FnMut(&T
) -> bool
,
1023 fn next_back(&mut self) -> Option
<&'a
mut [T
]> {
1024 if self.finished { return None; }
1026 let idx_opt
= { // work around borrowck limitations
1027 let pred
= &mut self.pred
;
1028 self.v
.iter().rposition(|x
| (*pred
)(x
))
1031 None
=> self.finish(),
1033 let tmp
= mem
::replace(&mut self.v
, &mut []);
1034 let (head
, tail
) = tmp
.split_at_mut(idx
);
1036 Some(&mut tail
[1..])
1042 /// An private iterator over subslices separated by elements that
1043 /// match a predicate function, splitting at most a fixed number of
1045 struct GenericSplitN
<I
> {
1051 impl<T
, I
: SplitIter
<Item
=T
>> Iterator
for GenericSplitN
<I
> {
1055 fn next(&mut self) -> Option
<T
> {
1058 1 => { self.count -= 1; self.iter.finish() }
1061 if self.invert {self.iter.next_back()}
else {self.iter.next()}
1067 fn size_hint(&self) -> (usize, Option
<usize>) {
1068 let (lower
, upper_opt
) = self.iter
.size_hint();
1069 (lower
, upper_opt
.map(|upper
| cmp
::min(self.count
, upper
)))
1073 /// An iterator over subslices separated by elements that match a predicate
1074 /// function, limited to a given number of splits.
1075 #[stable(feature = "rust1", since = "1.0.0")]
1076 pub struct SplitN
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1077 inner
: GenericSplitN
<Split
<'a
, T
, P
>>
1080 /// An iterator over subslices separated by elements that match a
1081 /// predicate function, limited to a given number of splits, starting
1082 /// from the end of the slice.
1083 #[stable(feature = "rust1", since = "1.0.0")]
1084 pub struct RSplitN
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1085 inner
: GenericSplitN
<Split
<'a
, T
, P
>>
1088 /// An iterator over subslices separated by elements that match a predicate
1089 /// function, limited to a given number of splits.
1090 #[stable(feature = "rust1", since = "1.0.0")]
1091 pub struct SplitNMut
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1092 inner
: GenericSplitN
<SplitMut
<'a
, T
, P
>>
1095 /// An iterator over subslices separated by elements that match a
1096 /// predicate function, limited to a given number of splits, starting
1097 /// from the end of the slice.
1098 #[stable(feature = "rust1", since = "1.0.0")]
1099 pub struct RSplitNMut
<'a
, T
: 'a
, P
> where P
: FnMut(&T
) -> bool
{
1100 inner
: GenericSplitN
<SplitMut
<'a
, T
, P
>>
1103 macro_rules
! forward_iterator
{
1104 ($name
:ident
: $elem
:ident
, $iter_of
:ty
) => {
1105 #[stable(feature = "rust1", since = "1.0.0")]
1106 impl<'a
, $elem
, P
> Iterator
for $name
<'a
, $elem
, P
> where
1107 P
: FnMut(&T
) -> bool
1109 type Item
= $iter_of
;
1112 fn next(&mut self) -> Option
<$iter_of
> {
1117 fn size_hint(&self) -> (usize, Option
<usize>) {
1118 self.inner
.size_hint()
1124 forward_iterator
! { SplitN: T, &'a [T] }
1125 forward_iterator
! { RSplitN: T, &'a [T] }
1126 forward_iterator
! { SplitNMut: T, &'a mut [T] }
1127 forward_iterator
! { RSplitNMut: T, &'a mut [T] }
1129 /// An iterator over overlapping subslices of length `size`.
1130 #[stable(feature = "rust1", since = "1.0.0")]
1131 pub struct Windows
<'a
, T
:'a
> {
1136 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1137 #[stable(feature = "rust1", since = "1.0.0")]
1138 impl<'a
, T
> Clone
for Windows
<'a
, T
> {
1139 fn clone(&self) -> Windows
<'a
, T
> {
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 impl<'a
, T
> Iterator
for Windows
<'a
, T
> {
1149 type Item
= &'a
[T
];
1152 fn next(&mut self) -> Option
<&'a
[T
]> {
1153 if self.size
> self.v
.len() {
1156 let ret
= Some(&self.v
[..self.size
]);
1157 self.v
= &self.v
[1..];
1163 fn size_hint(&self) -> (usize, Option
<usize>) {
1164 if self.size
> self.v
.len() {
1167 let size
= self.v
.len() - self.size
+ 1;
1173 fn count(self) -> usize {
1178 fn nth(&mut self, n
: usize) -> Option
<Self::Item
> {
1179 let (end
, overflow
) = self.size
.overflowing_add(n
);
1180 if end
> self.v
.len() || overflow
{
1184 let nth
= &self.v
[n
..end
];
1185 self.v
= &self.v
[n
+1..];
1191 fn last(self) -> Option
<Self::Item
> {
1192 if self.size
> self.v
.len() {
1195 let start
= self.v
.len() - self.size
;
1196 Some(&self.v
[start
..])
1201 #[stable(feature = "rust1", since = "1.0.0")]
1202 impl<'a
, T
> DoubleEndedIterator
for Windows
<'a
, T
> {
1204 fn next_back(&mut self) -> Option
<&'a
[T
]> {
1205 if self.size
> self.v
.len() {
1208 let ret
= Some(&self.v
[self.v
.len()-self.size
..]);
1209 self.v
= &self.v
[..self.v
.len()-1];
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<'a
, T
> ExactSizeIterator
for Windows
<'a
, T
> {}
1218 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1221 /// When the slice len is not evenly divided by the chunk size, the last slice
1222 /// of the iteration will be the remainder.
1223 #[stable(feature = "rust1", since = "1.0.0")]
1224 pub struct Chunks
<'a
, T
:'a
> {
1229 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 impl<'a
, T
> Clone
for Chunks
<'a
, T
> {
1232 fn clone(&self) -> Chunks
<'a
, T
> {
1240 #[stable(feature = "rust1", since = "1.0.0")]
1241 impl<'a
, T
> Iterator
for Chunks
<'a
, T
> {
1242 type Item
= &'a
[T
];
1245 fn next(&mut self) -> Option
<&'a
[T
]> {
1246 if self.v
.is_empty() {
1249 let chunksz
= cmp
::min(self.v
.len(), self.size
);
1250 let (fst
, snd
) = self.v
.split_at(chunksz
);
1257 fn size_hint(&self) -> (usize, Option
<usize>) {
1258 if self.v
.is_empty() {
1261 let n
= self.v
.len() / self.size
;
1262 let rem
= self.v
.len() % self.size
;
1263 let n
= if rem
> 0 { n+1 }
else { n }
;
1269 fn count(self) -> usize {
1274 fn nth(&mut self, n
: usize) -> Option
<Self::Item
> {
1275 let (start
, overflow
) = n
.overflowing_mul(self.size
);
1276 if start
>= self.v
.len() || overflow
{
1280 let end
= match start
.checked_add(self.size
) {
1281 Some(sum
) => cmp
::min(self.v
.len(), sum
),
1282 None
=> self.v
.len(),
1284 let nth
= &self.v
[start
..end
];
1285 self.v
= &self.v
[end
..];
1291 fn last(self) -> Option
<Self::Item
> {
1292 if self.v
.is_empty() {
1295 let start
= (self.v
.len() - 1) / self.size
* self.size
;
1296 Some(&self.v
[start
..])
1301 #[stable(feature = "rust1", since = "1.0.0")]
1302 impl<'a
, T
> DoubleEndedIterator
for Chunks
<'a
, T
> {
1304 fn next_back(&mut self) -> Option
<&'a
[T
]> {
1305 if self.v
.is_empty() {
1308 let remainder
= self.v
.len() % self.size
;
1309 let chunksz
= if remainder
!= 0 { remainder }
else { self.size }
;
1310 let (fst
, snd
) = self.v
.split_at(self.v
.len() - chunksz
);
1317 #[stable(feature = "rust1", since = "1.0.0")]
1318 impl<'a
, T
> ExactSizeIterator
for Chunks
<'a
, T
> {}
1320 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1321 /// elements at a time). When the slice len is not evenly divided by the chunk
1322 /// size, the last slice of the iteration will be the remainder.
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 pub struct ChunksMut
<'a
, T
:'a
> {
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 impl<'a
, T
> Iterator
for ChunksMut
<'a
, T
> {
1331 type Item
= &'a
mut [T
];
1334 fn next(&mut self) -> Option
<&'a
mut [T
]> {
1335 if self.v
.is_empty() {
1338 let sz
= cmp
::min(self.v
.len(), self.chunk_size
);
1339 let tmp
= mem
::replace(&mut self.v
, &mut []);
1340 let (head
, tail
) = tmp
.split_at_mut(sz
);
1347 fn size_hint(&self) -> (usize, Option
<usize>) {
1348 if self.v
.is_empty() {
1351 let n
= self.v
.len() / self.chunk_size
;
1352 let rem
= self.v
.len() % self.chunk_size
;
1353 let n
= if rem
> 0 { n + 1 }
else { n }
;
1359 fn count(self) -> usize {
1364 fn nth(&mut self, n
: usize) -> Option
<&'a
mut [T
]> {
1365 let (start
, overflow
) = n
.overflowing_mul(self.chunk_size
);
1366 if start
>= self.v
.len() || overflow
{
1370 let end
= match start
.checked_add(self.chunk_size
) {
1371 Some(sum
) => cmp
::min(self.v
.len(), sum
),
1372 None
=> self.v
.len(),
1374 let tmp
= mem
::replace(&mut self.v
, &mut []);
1375 let (head
, tail
) = tmp
.split_at_mut(end
);
1376 let (_
, nth
) = head
.split_at_mut(start
);
1383 fn last(self) -> Option
<Self::Item
> {
1384 if self.v
.is_empty() {
1387 let start
= (self.v
.len() - 1) / self.chunk_size
* self.chunk_size
;
1388 Some(&mut self.v
[start
..])
1393 #[stable(feature = "rust1", since = "1.0.0")]
1394 impl<'a
, T
> DoubleEndedIterator
for ChunksMut
<'a
, T
> {
1396 fn next_back(&mut self) -> Option
<&'a
mut [T
]> {
1397 if self.v
.is_empty() {
1400 let remainder
= self.v
.len() % self.chunk_size
;
1401 let sz
= if remainder
!= 0 { remainder }
else { self.chunk_size }
;
1402 let tmp
= mem
::replace(&mut self.v
, &mut []);
1403 let tmp_len
= tmp
.len();
1404 let (head
, tail
) = tmp
.split_at_mut(tmp_len
- sz
);
1411 #[stable(feature = "rust1", since = "1.0.0")]
1412 impl<'a
, T
> ExactSizeIterator
for ChunksMut
<'a
, T
> {}
1418 /// Converts a reference to A into a slice of length 1 (without copying).
1419 #[unstable(feature = "ref_slice", issue = "27774")]
1420 #[deprecated(since = "1.5.0", reason = "unclear whether belongs in libstd")]
1421 pub fn ref_slice
<A
>(s
: &A
) -> &[A
] {
1423 from_raw_parts(s
, 1)
1427 /// Converts a reference to A into a slice of length 1 (without copying).
1428 #[unstable(feature = "ref_slice", issue = "27774")]
1429 #[deprecated(since = "1.5.0", reason = "unclear whether belongs in libstd")]
1430 pub fn mut_ref_slice
<A
>(s
: &mut A
) -> &mut [A
] {
1432 from_raw_parts_mut(s
, 1)
1436 /// Forms a slice from a pointer and a length.
1438 /// The `len` argument is the number of **elements**, not the number of bytes.
1442 /// This function is unsafe as there is no guarantee that the given pointer is
1443 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
1444 /// lifetime for the returned slice.
1446 /// `p` must be non-null, even for zero-length slices.
1450 /// The lifetime for the returned slice is inferred from its usage. To
1451 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
1452 /// source lifetime is safe in the context, such as by providing a helper
1453 /// function taking the lifetime of a host value for the slice, or by explicit
1461 /// // manifest a slice out of thin air!
1462 /// let ptr = 0x1234 as *const usize;
1465 /// let slice = slice::from_raw_parts(ptr, amt);
1469 #[stable(feature = "rust1", since = "1.0.0")]
1470 pub unsafe fn from_raw_parts
<'a
, T
>(p
: *const T
, len
: usize) -> &'a
[T
] {
1471 mem
::transmute(RawSlice { data: p, len: len }
)
1474 /// Performs the same functionality as `from_raw_parts`, except that a mutable
1475 /// slice is returned.
1477 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
1478 /// as not being able to provide a non-aliasing guarantee of the returned
1481 #[stable(feature = "rust1", since = "1.0.0")]
1482 pub unsafe fn from_raw_parts_mut
<'a
, T
>(p
: *mut T
, len
: usize) -> &'a
mut [T
] {
1483 mem
::transmute(RawSlice { data: p, len: len }
)
1490 /// Operations on `[u8]`.
1491 #[unstable(feature = "slice_bytes", reason = "needs review",
1495 use slice
::SliceExt
;
1497 /// A trait for operations on mutable `[u8]`s.
1498 pub trait MutableByteVector
{
1499 /// Sets all bytes of the receiver to the given value.
1500 fn set_memory(&mut self, value
: u8);
1503 impl MutableByteVector
for [u8] {
1505 fn set_memory(&mut self, value
: u8) {
1506 unsafe { ptr::write_bytes(self.as_mut_ptr(), value, self.len()) }
;
1510 /// Copies data from `src` to `dst`
1512 /// Panics if the length of `dst` is less than the length of `src`.
1514 pub fn copy_memory(src
: &[u8], dst
: &mut [u8]) {
1515 let len_src
= src
.len();
1516 assert
!(dst
.len() >= len_src
);
1517 // `dst` is unaliasable, so we know statically it doesn't overlap
1520 ptr
::copy_nonoverlapping(src
.as_ptr(),
1530 // Boilerplate traits
1533 #[stable(feature = "rust1", since = "1.0.0")]
1534 impl<A
, B
> PartialEq
<[B
]> for [A
] where A
: PartialEq
<B
> {
1535 fn eq(&self, other
: &[B
]) -> bool
{
1536 if self.len() != other
.len() {
1540 for i
in 0..self.len() {
1541 if !self[i
].eq(&other
[i
]) {
1548 fn ne(&self, other
: &[B
]) -> bool
{
1549 if self.len() != other
.len() {
1553 for i
in 0..self.len() {
1554 if self[i
].ne(&other
[i
]) {
1563 #[stable(feature = "rust1", since = "1.0.0")]
1564 impl<T
: Eq
> Eq
for [T
] {}
1566 #[stable(feature = "rust1", since = "1.0.0")]
1567 impl<T
: Ord
> Ord
for [T
] {
1568 fn cmp(&self, other
: &[T
]) -> Ordering
{
1569 let l
= cmp
::min(self.len(), other
.len());
1571 // Slice to the loop iteration range to enable bound check
1572 // elimination in the compiler
1573 let lhs
= &self[..l
];
1574 let rhs
= &other
[..l
];
1577 match lhs
[i
].cmp(&rhs
[i
]) {
1578 Ordering
::Equal
=> (),
1579 non_eq
=> return non_eq
,
1583 self.len().cmp(&other
.len())
1587 #[stable(feature = "rust1", since = "1.0.0")]
1588 impl<T
: PartialOrd
> PartialOrd
for [T
] {
1589 fn partial_cmp(&self, other
: &[T
]) -> Option
<Ordering
> {
1590 let l
= cmp
::min(self.len(), other
.len());
1592 // Slice to the loop iteration range to enable bound check
1593 // elimination in the compiler
1594 let lhs
= &self[..l
];
1595 let rhs
= &other
[..l
];
1598 match lhs
[i
].partial_cmp(&rhs
[i
]) {
1599 Some(Ordering
::Equal
) => (),
1600 non_eq
=> return non_eq
,
1604 self.len().partial_cmp(&other
.len())