]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
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 | //! Slice management and manipulation | |
12 | //! | |
13 | //! For more details `std::slice`. | |
14 | ||
85aaf69f | 15 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
16 | #![doc(primitive = "slice")] |
17 | ||
18 | // How this module is organized. | |
19 | // | |
20 | // The library infrastructure for slices is fairly messy. There's | |
21 | // a lot of stuff defined here. Let's keep it clean. | |
22 | // | |
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. | |
26 | // | |
27 | // The layout of this file is thus: | |
28 | // | |
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. | |
33 | // * Free functions. | |
34 | // * The `raw` and `bytes` submodules. | |
35 | // * Boilerplate trait implementations. | |
36 | ||
37 | use mem::transmute; | |
38 | use clone::Clone; | |
39 | use cmp::{Ordering, PartialEq, PartialOrd, Eq, Ord}; | |
40 | use cmp::Ordering::{Less, Equal, Greater}; | |
41 | use cmp; | |
42 | use default::Default; | |
43 | use iter::*; | |
1a4d82fc | 44 | use ops::{FnMut, self, Index}; |
85aaf69f | 45 | use ops::RangeFull; |
1a4d82fc JJ |
46 | use option::Option; |
47 | use option::Option::{None, Some}; | |
48 | use result::Result; | |
49 | use result::Result::{Ok, Err}; | |
50 | use ptr; | |
51 | use ptr::PtrExt; | |
52 | use mem; | |
53 | use mem::size_of; | |
54 | use marker::{Sized, self}; | |
55 | use raw::Repr; | |
56 | // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module. | |
57 | use raw::Slice as RawSlice; | |
58 | ||
59 | ||
60 | // | |
61 | // Extension traits | |
62 | // | |
63 | ||
64 | /// Extension methods for slices. | |
65 | #[allow(missing_docs)] // docs in libcollections | |
66 | pub trait SliceExt { | |
67 | type Item; | |
68 | ||
85aaf69f | 69 | fn split_at<'a>(&'a self, mid: usize) -> (&'a [Self::Item], &'a [Self::Item]); |
1a4d82fc JJ |
70 | fn iter<'a>(&'a self) -> Iter<'a, Self::Item>; |
71 | fn split<'a, P>(&'a self, pred: P) -> Split<'a, Self::Item, P> | |
72 | where P: FnMut(&Self::Item) -> bool; | |
85aaf69f | 73 | fn splitn<'a, P>(&'a self, n: usize, pred: P) -> SplitN<'a, Self::Item, P> |
1a4d82fc | 74 | where P: FnMut(&Self::Item) -> bool; |
85aaf69f | 75 | fn rsplitn<'a, P>(&'a self, n: usize, pred: P) -> RSplitN<'a, Self::Item, P> |
1a4d82fc | 76 | where P: FnMut(&Self::Item) -> bool; |
85aaf69f SL |
77 | fn windows<'a>(&'a self, size: usize) -> Windows<'a, Self::Item>; |
78 | fn chunks<'a>(&'a self, size: usize) -> Chunks<'a, Self::Item>; | |
79 | fn get<'a>(&'a self, index: usize) -> Option<&'a Self::Item>; | |
1a4d82fc JJ |
80 | fn first<'a>(&'a self) -> Option<&'a Self::Item>; |
81 | fn tail<'a>(&'a self) -> &'a [Self::Item]; | |
82 | fn init<'a>(&'a self) -> &'a [Self::Item]; | |
83 | fn last<'a>(&'a self) -> Option<&'a Self::Item>; | |
85aaf69f | 84 | unsafe fn get_unchecked<'a>(&'a self, index: usize) -> &'a Self::Item; |
1a4d82fc | 85 | fn as_ptr(&self) -> *const Self::Item; |
85aaf69f | 86 | fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> where |
1a4d82fc | 87 | F: FnMut(&Self::Item) -> Ordering; |
85aaf69f | 88 | fn len(&self) -> usize; |
1a4d82fc | 89 | fn is_empty(&self) -> bool { self.len() == 0 } |
85aaf69f | 90 | fn get_mut<'a>(&'a mut self, index: usize) -> Option<&'a mut Self::Item>; |
1a4d82fc | 91 | fn as_mut_slice<'a>(&'a mut self) -> &'a mut [Self::Item]; |
1a4d82fc JJ |
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; | |
85aaf69f | 99 | fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<Self::Item, P> |
1a4d82fc | 100 | where P: FnMut(&Self::Item) -> bool; |
85aaf69f | 101 | fn rsplitn_mut<P>(&mut self, n: usize, pred: P) -> RSplitNMut<Self::Item, P> |
1a4d82fc | 102 | where P: FnMut(&Self::Item) -> bool; |
85aaf69f SL |
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]); | |
1a4d82fc | 106 | fn reverse(&mut self); |
85aaf69f | 107 | unsafe fn get_unchecked_mut<'a>(&'a mut self, index: usize) -> &'a mut Self::Item; |
1a4d82fc JJ |
108 | fn as_mut_ptr(&mut self) -> *mut Self::Item; |
109 | ||
85aaf69f | 110 | fn position_elem(&self, t: &Self::Item) -> Option<usize> where Self::Item: PartialEq; |
1a4d82fc | 111 | |
85aaf69f | 112 | fn rposition_elem(&self, t: &Self::Item) -> Option<usize> where Self::Item: PartialEq; |
1a4d82fc JJ |
113 | |
114 | fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq; | |
115 | ||
116 | fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq; | |
117 | ||
118 | fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq; | |
119 | ||
85aaf69f | 120 | fn binary_search(&self, x: &Self::Item) -> Result<usize, usize> where Self::Item: Ord; |
1a4d82fc JJ |
121 | fn next_permutation(&mut self) -> bool where Self::Item: Ord; |
122 | fn prev_permutation(&mut self) -> bool where Self::Item: Ord; | |
123 | ||
85aaf69f | 124 | fn clone_from_slice(&mut self, &[Self::Item]) -> usize where Self::Item: Clone; |
1a4d82fc JJ |
125 | } |
126 | ||
85aaf69f | 127 | #[unstable(feature = "core")] |
1a4d82fc JJ |
128 | impl<T> SliceExt for [T] { |
129 | type Item = T; | |
130 | ||
131 | #[inline] | |
85aaf69f SL |
132 | fn split_at(&self, mid: usize) -> (&[T], &[T]) { |
133 | (&self[..mid], &self[mid..]) | |
1a4d82fc JJ |
134 | } |
135 | ||
136 | #[inline] | |
137 | fn iter<'a>(&'a self) -> Iter<'a, T> { | |
138 | unsafe { | |
139 | let p = self.as_ptr(); | |
140 | if mem::size_of::<T>() == 0 { | |
141 | Iter {ptr: p, | |
85aaf69f SL |
142 | end: (p as usize + self.len()) as *const T, |
143 | _marker: marker::PhantomData} | |
1a4d82fc JJ |
144 | } else { |
145 | Iter {ptr: p, | |
85aaf69f SL |
146 | end: p.offset(self.len() as isize), |
147 | _marker: marker::PhantomData} | |
1a4d82fc JJ |
148 | } |
149 | } | |
150 | } | |
151 | ||
152 | #[inline] | |
153 | fn split<'a, P>(&'a self, pred: P) -> Split<'a, T, P> where P: FnMut(&T) -> bool { | |
154 | Split { | |
155 | v: self, | |
156 | pred: pred, | |
157 | finished: false | |
158 | } | |
159 | } | |
160 | ||
161 | #[inline] | |
85aaf69f | 162 | fn splitn<'a, P>(&'a self, n: usize, pred: P) -> SplitN<'a, T, P> where |
1a4d82fc JJ |
163 | P: FnMut(&T) -> bool, |
164 | { | |
165 | SplitN { | |
166 | inner: GenericSplitN { | |
167 | iter: self.split(pred), | |
168 | count: n, | |
169 | invert: false | |
170 | } | |
171 | } | |
172 | } | |
173 | ||
174 | #[inline] | |
85aaf69f | 175 | fn rsplitn<'a, P>(&'a self, n: usize, pred: P) -> RSplitN<'a, T, P> where |
1a4d82fc JJ |
176 | P: FnMut(&T) -> bool, |
177 | { | |
178 | RSplitN { | |
179 | inner: GenericSplitN { | |
180 | iter: self.split(pred), | |
181 | count: n, | |
182 | invert: true | |
183 | } | |
184 | } | |
185 | } | |
186 | ||
187 | #[inline] | |
85aaf69f | 188 | fn windows(&self, size: usize) -> Windows<T> { |
1a4d82fc JJ |
189 | assert!(size != 0); |
190 | Windows { v: self, size: size } | |
191 | } | |
192 | ||
193 | #[inline] | |
85aaf69f | 194 | fn chunks(&self, size: usize) -> Chunks<T> { |
1a4d82fc JJ |
195 | assert!(size != 0); |
196 | Chunks { v: self, size: size } | |
197 | } | |
198 | ||
199 | #[inline] | |
85aaf69f | 200 | fn get(&self, index: usize) -> Option<&T> { |
1a4d82fc JJ |
201 | if index < self.len() { Some(&self[index]) } else { None } |
202 | } | |
203 | ||
204 | #[inline] | |
205 | fn first(&self) -> Option<&T> { | |
206 | if self.len() == 0 { None } else { Some(&self[0]) } | |
207 | } | |
208 | ||
209 | #[inline] | |
210 | fn tail(&self) -> &[T] { &self[1..] } | |
211 | ||
212 | #[inline] | |
213 | fn init(&self) -> &[T] { | |
85aaf69f | 214 | &self[..self.len() - 1] |
1a4d82fc JJ |
215 | } |
216 | ||
217 | #[inline] | |
218 | fn last(&self) -> Option<&T> { | |
219 | if self.len() == 0 { None } else { Some(&self[self.len() - 1]) } | |
220 | } | |
221 | ||
222 | #[inline] | |
85aaf69f SL |
223 | unsafe fn get_unchecked(&self, index: usize) -> &T { |
224 | transmute(self.repr().data.offset(index as isize)) | |
1a4d82fc JJ |
225 | } |
226 | ||
227 | #[inline] | |
228 | fn as_ptr(&self) -> *const T { | |
229 | self.repr().data | |
230 | } | |
231 | ||
85aaf69f SL |
232 | #[unstable(feature = "core")] |
233 | fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> where | |
1a4d82fc JJ |
234 | F: FnMut(&T) -> Ordering |
235 | { | |
85aaf69f SL |
236 | let mut base : usize = 0; |
237 | let mut lim : usize = self.len(); | |
1a4d82fc JJ |
238 | |
239 | while lim != 0 { | |
240 | let ix = base + (lim >> 1); | |
241 | match f(&self[ix]) { | |
242 | Equal => return Ok(ix), | |
243 | Less => { | |
244 | base = ix + 1; | |
245 | lim -= 1; | |
246 | } | |
247 | Greater => () | |
248 | } | |
249 | lim >>= 1; | |
250 | } | |
251 | Err(base) | |
252 | } | |
253 | ||
254 | #[inline] | |
85aaf69f | 255 | fn len(&self) -> usize { self.repr().len } |
1a4d82fc JJ |
256 | |
257 | #[inline] | |
85aaf69f | 258 | fn get_mut(&mut self, index: usize) -> Option<&mut T> { |
1a4d82fc JJ |
259 | if index < self.len() { Some(&mut self[index]) } else { None } |
260 | } | |
261 | ||
262 | #[inline] | |
263 | fn as_mut_slice(&mut self) -> &mut [T] { self } | |
264 | ||
1a4d82fc | 265 | #[inline] |
85aaf69f | 266 | fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { |
1a4d82fc JJ |
267 | unsafe { |
268 | let self2: &mut [T] = mem::transmute_copy(&self); | |
269 | ||
270 | (ops::IndexMut::index_mut(self, &ops::RangeTo { end: mid } ), | |
271 | ops::IndexMut::index_mut(self2, &ops::RangeFrom { start: mid } )) | |
272 | } | |
273 | } | |
274 | ||
275 | #[inline] | |
276 | fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> { | |
277 | unsafe { | |
278 | let p = self.as_mut_ptr(); | |
279 | if mem::size_of::<T>() == 0 { | |
280 | IterMut {ptr: p, | |
85aaf69f SL |
281 | end: (p as usize + self.len()) as *mut T, |
282 | _marker: marker::PhantomData} | |
1a4d82fc JJ |
283 | } else { |
284 | IterMut {ptr: p, | |
85aaf69f SL |
285 | end: p.offset(self.len() as isize), |
286 | _marker: marker::PhantomData} | |
1a4d82fc JJ |
287 | } |
288 | } | |
289 | } | |
290 | ||
291 | #[inline] | |
292 | fn last_mut(&mut self) -> Option<&mut T> { | |
293 | let len = self.len(); | |
294 | if len == 0 { return None; } | |
295 | Some(&mut self[len - 1]) | |
296 | } | |
297 | ||
298 | #[inline] | |
299 | fn first_mut(&mut self) -> Option<&mut T> { | |
300 | if self.len() == 0 { None } else { Some(&mut self[0]) } | |
301 | } | |
302 | ||
303 | #[inline] | |
304 | fn tail_mut(&mut self) -> &mut [T] { | |
85aaf69f | 305 | &mut self[1 ..] |
1a4d82fc JJ |
306 | } |
307 | ||
308 | #[inline] | |
309 | fn init_mut(&mut self) -> &mut [T] { | |
310 | let len = self.len(); | |
85aaf69f | 311 | &mut self[.. (len - 1)] |
1a4d82fc JJ |
312 | } |
313 | ||
314 | #[inline] | |
315 | fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool { | |
316 | SplitMut { v: self, pred: pred, finished: false } | |
317 | } | |
318 | ||
319 | #[inline] | |
85aaf69f | 320 | fn splitn_mut<'a, P>(&'a mut self, n: usize, pred: P) -> SplitNMut<'a, T, P> where |
1a4d82fc JJ |
321 | P: FnMut(&T) -> bool |
322 | { | |
323 | SplitNMut { | |
324 | inner: GenericSplitN { | |
325 | iter: self.split_mut(pred), | |
326 | count: n, | |
327 | invert: false | |
328 | } | |
329 | } | |
330 | } | |
331 | ||
332 | #[inline] | |
85aaf69f | 333 | fn rsplitn_mut<'a, P>(&'a mut self, n: usize, pred: P) -> RSplitNMut<'a, T, P> where |
1a4d82fc JJ |
334 | P: FnMut(&T) -> bool, |
335 | { | |
336 | RSplitNMut { | |
337 | inner: GenericSplitN { | |
338 | iter: self.split_mut(pred), | |
339 | count: n, | |
340 | invert: true | |
341 | } | |
342 | } | |
343 | } | |
344 | ||
345 | #[inline] | |
85aaf69f | 346 | fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> { |
1a4d82fc JJ |
347 | assert!(chunk_size > 0); |
348 | ChunksMut { v: self, chunk_size: chunk_size } | |
349 | } | |
350 | ||
85aaf69f | 351 | fn swap(&mut self, a: usize, b: usize) { |
1a4d82fc JJ |
352 | unsafe { |
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]; | |
357 | ptr::swap(pa, pb); | |
358 | } | |
359 | } | |
360 | ||
361 | fn reverse(&mut self) { | |
85aaf69f | 362 | let mut i: usize = 0; |
1a4d82fc JJ |
363 | let ln = self.len(); |
364 | while i < ln / 2 { | |
365 | // Unsafe swap to avoid the bounds check in safe swap. | |
366 | unsafe { | |
367 | let pa: *mut T = self.get_unchecked_mut(i); | |
368 | let pb: *mut T = self.get_unchecked_mut(ln - i - 1); | |
369 | ptr::swap(pa, pb); | |
370 | } | |
371 | i += 1; | |
372 | } | |
373 | } | |
374 | ||
375 | #[inline] | |
85aaf69f SL |
376 | unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T { |
377 | transmute((self.repr().data as *mut T).offset(index as isize)) | |
1a4d82fc JJ |
378 | } |
379 | ||
380 | #[inline] | |
381 | fn as_mut_ptr(&mut self) -> *mut T { | |
382 | self.repr().data as *mut T | |
383 | } | |
384 | ||
385 | #[inline] | |
85aaf69f | 386 | fn position_elem(&self, x: &T) -> Option<usize> where T: PartialEq { |
1a4d82fc JJ |
387 | self.iter().position(|y| *x == *y) |
388 | } | |
389 | ||
390 | #[inline] | |
85aaf69f | 391 | fn rposition_elem(&self, t: &T) -> Option<usize> where T: PartialEq { |
1a4d82fc JJ |
392 | self.iter().rposition(|x| *x == *t) |
393 | } | |
394 | ||
395 | #[inline] | |
396 | fn contains(&self, x: &T) -> bool where T: PartialEq { | |
397 | self.iter().any(|elt| *x == *elt) | |
398 | } | |
399 | ||
400 | #[inline] | |
401 | fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq { | |
402 | let n = needle.len(); | |
85aaf69f | 403 | self.len() >= n && needle == &self[..n] |
1a4d82fc JJ |
404 | } |
405 | ||
406 | #[inline] | |
407 | fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq { | |
408 | let (m, n) = (self.len(), needle.len()); | |
85aaf69f | 409 | m >= n && needle == &self[m-n..] |
1a4d82fc JJ |
410 | } |
411 | ||
85aaf69f SL |
412 | #[unstable(feature = "core")] |
413 | fn binary_search(&self, x: &T) -> Result<usize, usize> where T: Ord { | |
1a4d82fc JJ |
414 | self.binary_search_by(|p| p.cmp(x)) |
415 | } | |
416 | ||
85aaf69f | 417 | #[unstable(feature = "core")] |
1a4d82fc JJ |
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; } | |
421 | ||
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] { | |
425 | i -= 1; | |
426 | } | |
427 | ||
428 | // If that is the entire vector, this is the last-ordered permutation. | |
429 | if i == 0 { | |
430 | return false; | |
431 | } | |
432 | ||
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] { | |
436 | j -= 1; | |
437 | } | |
438 | ||
439 | // Step 3: Swap that element with the pivot | |
440 | self.swap(j, i-1); | |
441 | ||
442 | // Step 4: Reverse the (previously) weakly decreasing part | |
85aaf69f | 443 | self[i..].reverse(); |
1a4d82fc JJ |
444 | |
445 | true | |
446 | } | |
447 | ||
85aaf69f | 448 | #[unstable(feature = "core")] |
1a4d82fc JJ |
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; } | |
452 | ||
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] { | |
456 | i -= 1; | |
457 | } | |
458 | ||
459 | // If that is the entire vector, this is the first-ordered permutation. | |
460 | if i == 0 { | |
461 | return false; | |
462 | } | |
463 | ||
464 | // Step 2: Reverse the weakly increasing part | |
85aaf69f | 465 | self[i..].reverse(); |
1a4d82fc JJ |
466 | |
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] { | |
470 | j -= 1; | |
471 | } | |
472 | ||
473 | // Step 4: Swap that element with the pivot | |
474 | self.swap(i-1, j); | |
475 | ||
476 | true | |
477 | } | |
478 | ||
479 | #[inline] | |
85aaf69f | 480 | fn clone_from_slice(&mut self, src: &[T]) -> usize where T: Clone { |
1a4d82fc | 481 | let min = cmp::min(self.len(), src.len()); |
85aaf69f SL |
482 | let dst = &mut self[.. min]; |
483 | let src = &src[.. min]; | |
484 | for i in 0..min { | |
1a4d82fc JJ |
485 | dst[i].clone_from(&src[i]); |
486 | } | |
487 | min | |
488 | } | |
489 | } | |
490 | ||
85aaf69f SL |
491 | #[stable(feature = "rust1", since = "1.0.0")] |
492 | impl<T> ops::Index<usize> for [T] { | |
1a4d82fc JJ |
493 | type Output = T; |
494 | ||
85aaf69f | 495 | fn index(&self, &index: &usize) -> &T { |
1a4d82fc JJ |
496 | assert!(index < self.len()); |
497 | ||
85aaf69f | 498 | unsafe { mem::transmute(self.repr().data.offset(index as isize)) } |
1a4d82fc JJ |
499 | } |
500 | } | |
501 | ||
85aaf69f SL |
502 | #[stable(feature = "rust1", since = "1.0.0")] |
503 | impl<T> ops::IndexMut<usize> for [T] { | |
504 | fn index_mut(&mut self, &index: &usize) -> &mut T { | |
1a4d82fc JJ |
505 | assert!(index < self.len()); |
506 | ||
85aaf69f | 507 | unsafe { mem::transmute(self.repr().data.offset(index as isize)) } |
1a4d82fc JJ |
508 | } |
509 | } | |
510 | ||
85aaf69f SL |
511 | #[stable(feature = "rust1", since = "1.0.0")] |
512 | impl<T> ops::Index<ops::Range<usize>> for [T] { | |
1a4d82fc JJ |
513 | type Output = [T]; |
514 | #[inline] | |
85aaf69f | 515 | fn index(&self, index: &ops::Range<usize>) -> &[T] { |
1a4d82fc JJ |
516 | assert!(index.start <= index.end); |
517 | assert!(index.end <= self.len()); | |
518 | unsafe { | |
519 | transmute(RawSlice { | |
85aaf69f | 520 | data: self.as_ptr().offset(index.start as isize), |
1a4d82fc JJ |
521 | len: index.end - index.start |
522 | }) | |
523 | } | |
524 | } | |
525 | } | |
85aaf69f SL |
526 | #[stable(feature = "rust1", since = "1.0.0")] |
527 | impl<T> ops::Index<ops::RangeTo<usize>> for [T] { | |
1a4d82fc JJ |
528 | type Output = [T]; |
529 | #[inline] | |
85aaf69f | 530 | fn index(&self, index: &ops::RangeTo<usize>) -> &[T] { |
1a4d82fc JJ |
531 | self.index(&ops::Range{ start: 0, end: index.end }) |
532 | } | |
533 | } | |
85aaf69f SL |
534 | #[stable(feature = "rust1", since = "1.0.0")] |
535 | impl<T> ops::Index<ops::RangeFrom<usize>> for [T] { | |
1a4d82fc JJ |
536 | type Output = [T]; |
537 | #[inline] | |
85aaf69f | 538 | fn index(&self, index: &ops::RangeFrom<usize>) -> &[T] { |
1a4d82fc JJ |
539 | self.index(&ops::Range{ start: index.start, end: self.len() }) |
540 | } | |
541 | } | |
85aaf69f SL |
542 | #[stable(feature = "rust1", since = "1.0.0")] |
543 | impl<T> ops::Index<RangeFull> for [T] { | |
1a4d82fc JJ |
544 | type Output = [T]; |
545 | #[inline] | |
85aaf69f | 546 | fn index(&self, _index: &RangeFull) -> &[T] { |
1a4d82fc JJ |
547 | self |
548 | } | |
549 | } | |
550 | ||
85aaf69f SL |
551 | #[stable(feature = "rust1", since = "1.0.0")] |
552 | impl<T> ops::IndexMut<ops::Range<usize>> for [T] { | |
1a4d82fc | 553 | #[inline] |
85aaf69f | 554 | fn index_mut(&mut self, index: &ops::Range<usize>) -> &mut [T] { |
1a4d82fc JJ |
555 | assert!(index.start <= index.end); |
556 | assert!(index.end <= self.len()); | |
557 | unsafe { | |
558 | transmute(RawSlice { | |
85aaf69f | 559 | data: self.as_ptr().offset(index.start as isize), |
1a4d82fc JJ |
560 | len: index.end - index.start |
561 | }) | |
562 | } | |
563 | } | |
564 | } | |
85aaf69f SL |
565 | #[stable(feature = "rust1", since = "1.0.0")] |
566 | impl<T> ops::IndexMut<ops::RangeTo<usize>> for [T] { | |
1a4d82fc | 567 | #[inline] |
85aaf69f | 568 | fn index_mut(&mut self, index: &ops::RangeTo<usize>) -> &mut [T] { |
1a4d82fc JJ |
569 | self.index_mut(&ops::Range{ start: 0, end: index.end }) |
570 | } | |
571 | } | |
85aaf69f SL |
572 | #[stable(feature = "rust1", since = "1.0.0")] |
573 | impl<T> ops::IndexMut<ops::RangeFrom<usize>> for [T] { | |
1a4d82fc | 574 | #[inline] |
85aaf69f | 575 | fn index_mut(&mut self, index: &ops::RangeFrom<usize>) -> &mut [T] { |
1a4d82fc JJ |
576 | let len = self.len(); |
577 | self.index_mut(&ops::Range{ start: index.start, end: len }) | |
578 | } | |
579 | } | |
85aaf69f SL |
580 | #[stable(feature = "rust1", since = "1.0.0")] |
581 | impl<T> ops::IndexMut<RangeFull> for [T] { | |
1a4d82fc | 582 | #[inline] |
85aaf69f | 583 | fn index_mut(&mut self, _index: &RangeFull) -> &mut [T] { |
1a4d82fc JJ |
584 | self |
585 | } | |
586 | } | |
587 | ||
588 | ||
589 | //////////////////////////////////////////////////////////////////////////////// | |
590 | // Common traits | |
591 | //////////////////////////////////////////////////////////////////////////////// | |
592 | ||
593 | /// Data that is viewable as a slice. | |
85aaf69f SL |
594 | #[unstable(feature = "core", |
595 | reason = "will be replaced by slice syntax")] | |
1a4d82fc JJ |
596 | pub trait AsSlice<T> { |
597 | /// Work with `self` as a slice. | |
598 | fn as_slice<'a>(&'a self) -> &'a [T]; | |
599 | } | |
600 | ||
85aaf69f | 601 | #[unstable(feature = "core", reason = "trait is experimental")] |
1a4d82fc JJ |
602 | impl<T> AsSlice<T> for [T] { |
603 | #[inline(always)] | |
604 | fn as_slice<'a>(&'a self) -> &'a [T] { self } | |
605 | } | |
606 | ||
85aaf69f | 607 | #[unstable(feature = "core", reason = "trait is experimental")] |
1a4d82fc JJ |
608 | impl<'a, T, U: ?Sized + AsSlice<T>> AsSlice<T> for &'a U { |
609 | #[inline(always)] | |
610 | fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) } | |
611 | } | |
612 | ||
85aaf69f | 613 | #[unstable(feature = "core", reason = "trait is experimental")] |
1a4d82fc JJ |
614 | impl<'a, T, U: ?Sized + AsSlice<T>> AsSlice<T> for &'a mut U { |
615 | #[inline(always)] | |
616 | fn as_slice(&self) -> &[T] { AsSlice::as_slice(*self) } | |
617 | } | |
618 | ||
85aaf69f | 619 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 620 | impl<'a, T> Default for &'a [T] { |
85aaf69f | 621 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
622 | fn default() -> &'a [T] { &[] } |
623 | } | |
624 | ||
625 | // | |
626 | // Iterators | |
627 | // | |
628 | ||
85aaf69f SL |
629 | #[stable(feature = "rust1", since = "1.0.0")] |
630 | impl<'a, T> IntoIterator for &'a [T] { | |
631 | type Item = &'a T; | |
632 | type IntoIter = Iter<'a, T>; | |
633 | ||
634 | fn into_iter(self) -> Iter<'a, T> { | |
635 | self.iter() | |
636 | } | |
637 | } | |
638 | ||
639 | #[stable(feature = "rust1", since = "1.0.0")] | |
640 | impl<'a, T> IntoIterator for &'a mut [T] { | |
641 | type Item = &'a mut T; | |
642 | type IntoIter = IterMut<'a, T>; | |
643 | ||
644 | fn into_iter(self) -> IterMut<'a, T> { | |
645 | self.iter_mut() | |
646 | } | |
647 | } | |
648 | ||
1a4d82fc JJ |
649 | // The shared definition of the `Iter` and `IterMut` iterators |
650 | macro_rules! iterator { | |
651 | (struct $name:ident -> $ptr:ty, $elem:ty) => { | |
85aaf69f | 652 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
653 | impl<'a, T> Iterator for $name<'a, T> { |
654 | type Item = $elem; | |
655 | ||
656 | #[inline] | |
657 | fn next(&mut self) -> Option<$elem> { | |
658 | // could be implemented with slices, but this avoids bounds checks | |
659 | unsafe { | |
660 | if self.ptr == self.end { | |
661 | None | |
662 | } else { | |
663 | if mem::size_of::<T>() == 0 { | |
664 | // purposefully don't use 'ptr.offset' because for | |
665 | // vectors with 0-size elements this would return the | |
666 | // same pointer. | |
85aaf69f | 667 | self.ptr = transmute(self.ptr as usize + 1); |
1a4d82fc JJ |
668 | |
669 | // Use a non-null pointer value | |
85aaf69f | 670 | Some(&mut *(1 as *mut _)) |
1a4d82fc JJ |
671 | } else { |
672 | let old = self.ptr; | |
673 | self.ptr = self.ptr.offset(1); | |
674 | ||
675 | Some(transmute(old)) | |
676 | } | |
677 | } | |
678 | } | |
679 | } | |
680 | ||
681 | #[inline] | |
85aaf69f SL |
682 | fn size_hint(&self) -> (usize, Option<usize>) { |
683 | let diff = (self.end as usize) - (self.ptr as usize); | |
1a4d82fc JJ |
684 | let size = mem::size_of::<T>(); |
685 | let exact = diff / (if size == 0 {1} else {size}); | |
686 | (exact, Some(exact)) | |
687 | } | |
688 | } | |
689 | ||
85aaf69f | 690 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
691 | impl<'a, T> DoubleEndedIterator for $name<'a, T> { |
692 | #[inline] | |
693 | fn next_back(&mut self) -> Option<$elem> { | |
694 | // could be implemented with slices, but this avoids bounds checks | |
695 | unsafe { | |
696 | if self.end == self.ptr { | |
697 | None | |
698 | } else { | |
699 | if mem::size_of::<T>() == 0 { | |
700 | // See above for why 'ptr.offset' isn't used | |
85aaf69f | 701 | self.end = transmute(self.end as usize - 1); |
1a4d82fc JJ |
702 | |
703 | // Use a non-null pointer value | |
85aaf69f | 704 | Some(&mut *(1 as *mut _)) |
1a4d82fc JJ |
705 | } else { |
706 | self.end = self.end.offset(-1); | |
707 | ||
708 | Some(transmute(self.end)) | |
709 | } | |
710 | } | |
711 | } | |
712 | } | |
713 | } | |
714 | } | |
715 | } | |
716 | ||
717 | macro_rules! make_slice { | |
718 | ($t: ty => $result: ty: $start: expr, $end: expr) => {{ | |
85aaf69f | 719 | let diff = $end as usize - $start as usize; |
1a4d82fc JJ |
720 | let len = if mem::size_of::<T>() == 0 { |
721 | diff | |
722 | } else { | |
723 | diff / mem::size_of::<$t>() | |
724 | }; | |
725 | unsafe { | |
85aaf69f | 726 | transmute::<_, $result>(RawSlice { data: $start, len: len }) |
1a4d82fc JJ |
727 | } |
728 | }} | |
729 | } | |
730 | ||
731 | /// Immutable slice iterator | |
85aaf69f | 732 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
733 | pub struct Iter<'a, T: 'a> { |
734 | ptr: *const T, | |
735 | end: *const T, | |
85aaf69f | 736 | _marker: marker::PhantomData<&'a T>, |
1a4d82fc JJ |
737 | } |
738 | ||
85aaf69f SL |
739 | #[unstable(feature = "core")] |
740 | impl<'a, T> ops::Index<ops::Range<usize>> for Iter<'a, T> { | |
1a4d82fc JJ |
741 | type Output = [T]; |
742 | #[inline] | |
85aaf69f | 743 | fn index(&self, index: &ops::Range<usize>) -> &[T] { |
1a4d82fc JJ |
744 | self.as_slice().index(index) |
745 | } | |
746 | } | |
747 | ||
85aaf69f SL |
748 | #[unstable(feature = "core")] |
749 | impl<'a, T> ops::Index<ops::RangeTo<usize>> for Iter<'a, T> { | |
1a4d82fc JJ |
750 | type Output = [T]; |
751 | #[inline] | |
85aaf69f | 752 | fn index(&self, index: &ops::RangeTo<usize>) -> &[T] { |
1a4d82fc JJ |
753 | self.as_slice().index(index) |
754 | } | |
755 | } | |
756 | ||
85aaf69f SL |
757 | #[unstable(feature = "core")] |
758 | impl<'a, T> ops::Index<ops::RangeFrom<usize>> for Iter<'a, T> { | |
1a4d82fc JJ |
759 | type Output = [T]; |
760 | #[inline] | |
85aaf69f | 761 | fn index(&self, index: &ops::RangeFrom<usize>) -> &[T] { |
1a4d82fc JJ |
762 | self.as_slice().index(index) |
763 | } | |
764 | } | |
765 | ||
85aaf69f SL |
766 | #[unstable(feature = "core")] |
767 | impl<'a, T> ops::Index<RangeFull> for Iter<'a, T> { | |
1a4d82fc JJ |
768 | type Output = [T]; |
769 | #[inline] | |
85aaf69f | 770 | fn index(&self, _index: &RangeFull) -> &[T] { |
1a4d82fc JJ |
771 | self.as_slice() |
772 | } | |
773 | } | |
774 | ||
775 | impl<'a, T> Iter<'a, T> { | |
776 | /// View the underlying data as a subslice of the original data. | |
777 | /// | |
778 | /// This has the same lifetime as the original slice, and so the | |
779 | /// iterator can continue to be used while this exists. | |
85aaf69f | 780 | #[unstable(feature = "core")] |
1a4d82fc JJ |
781 | pub fn as_slice(&self) -> &'a [T] { |
782 | make_slice!(T => &'a [T]: self.ptr, self.end) | |
783 | } | |
784 | } | |
785 | ||
1a4d82fc JJ |
786 | iterator!{struct Iter -> *const T, &'a T} |
787 | ||
85aaf69f | 788 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
789 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
790 | ||
85aaf69f | 791 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 792 | impl<'a, T> Clone for Iter<'a, T> { |
85aaf69f | 793 | fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } } |
1a4d82fc JJ |
794 | } |
795 | ||
85aaf69f | 796 | #[unstable(feature = "core", reason = "trait is experimental")] |
1a4d82fc JJ |
797 | impl<'a, T> RandomAccessIterator for Iter<'a, T> { |
798 | #[inline] | |
85aaf69f | 799 | fn indexable(&self) -> usize { |
1a4d82fc JJ |
800 | let (exact, _) = self.size_hint(); |
801 | exact | |
802 | } | |
803 | ||
804 | #[inline] | |
85aaf69f | 805 | fn idx(&mut self, index: usize) -> Option<&'a T> { |
1a4d82fc JJ |
806 | unsafe { |
807 | if index < self.indexable() { | |
808 | if mem::size_of::<T>() == 0 { | |
809 | // Use a non-null pointer value | |
85aaf69f | 810 | Some(&mut *(1 as *mut _)) |
1a4d82fc | 811 | } else { |
85aaf69f | 812 | Some(transmute(self.ptr.offset(index as isize))) |
1a4d82fc JJ |
813 | } |
814 | } else { | |
815 | None | |
816 | } | |
817 | } | |
818 | } | |
819 | } | |
820 | ||
821 | /// Mutable slice iterator. | |
85aaf69f | 822 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
823 | pub struct IterMut<'a, T: 'a> { |
824 | ptr: *mut T, | |
825 | end: *mut T, | |
85aaf69f | 826 | _marker: marker::PhantomData<&'a mut T>, |
1a4d82fc JJ |
827 | } |
828 | ||
829 | ||
85aaf69f SL |
830 | #[unstable(feature = "core")] |
831 | impl<'a, T> ops::Index<ops::Range<usize>> for IterMut<'a, T> { | |
1a4d82fc JJ |
832 | type Output = [T]; |
833 | #[inline] | |
85aaf69f SL |
834 | fn index(&self, index: &ops::Range<usize>) -> &[T] { |
835 | self.index(&RangeFull).index(index) | |
1a4d82fc JJ |
836 | } |
837 | } | |
85aaf69f SL |
838 | #[unstable(feature = "core")] |
839 | impl<'a, T> ops::Index<ops::RangeTo<usize>> for IterMut<'a, T> { | |
1a4d82fc JJ |
840 | type Output = [T]; |
841 | #[inline] | |
85aaf69f SL |
842 | fn index(&self, index: &ops::RangeTo<usize>) -> &[T] { |
843 | self.index(&RangeFull).index(index) | |
1a4d82fc JJ |
844 | } |
845 | } | |
85aaf69f SL |
846 | #[unstable(feature = "core")] |
847 | impl<'a, T> ops::Index<ops::RangeFrom<usize>> for IterMut<'a, T> { | |
1a4d82fc JJ |
848 | type Output = [T]; |
849 | #[inline] | |
85aaf69f SL |
850 | fn index(&self, index: &ops::RangeFrom<usize>) -> &[T] { |
851 | self.index(&RangeFull).index(index) | |
1a4d82fc JJ |
852 | } |
853 | } | |
85aaf69f SL |
854 | #[unstable(feature = "core")] |
855 | impl<'a, T> ops::Index<RangeFull> for IterMut<'a, T> { | |
1a4d82fc JJ |
856 | type Output = [T]; |
857 | #[inline] | |
85aaf69f | 858 | fn index(&self, _index: &RangeFull) -> &[T] { |
1a4d82fc JJ |
859 | make_slice!(T => &[T]: self.ptr, self.end) |
860 | } | |
861 | } | |
862 | ||
85aaf69f SL |
863 | #[unstable(feature = "core")] |
864 | impl<'a, T> ops::IndexMut<ops::Range<usize>> for IterMut<'a, T> { | |
1a4d82fc | 865 | #[inline] |
85aaf69f SL |
866 | fn index_mut(&mut self, index: &ops::Range<usize>) -> &mut [T] { |
867 | self.index_mut(&RangeFull).index_mut(index) | |
1a4d82fc JJ |
868 | } |
869 | } | |
85aaf69f SL |
870 | #[unstable(feature = "core")] |
871 | impl<'a, T> ops::IndexMut<ops::RangeTo<usize>> for IterMut<'a, T> { | |
1a4d82fc | 872 | #[inline] |
85aaf69f SL |
873 | fn index_mut(&mut self, index: &ops::RangeTo<usize>) -> &mut [T] { |
874 | self.index_mut(&RangeFull).index_mut(index) | |
1a4d82fc JJ |
875 | } |
876 | } | |
85aaf69f SL |
877 | #[unstable(feature = "core")] |
878 | impl<'a, T> ops::IndexMut<ops::RangeFrom<usize>> for IterMut<'a, T> { | |
1a4d82fc | 879 | #[inline] |
85aaf69f SL |
880 | fn index_mut(&mut self, index: &ops::RangeFrom<usize>) -> &mut [T] { |
881 | self.index_mut(&RangeFull).index_mut(index) | |
1a4d82fc JJ |
882 | } |
883 | } | |
85aaf69f SL |
884 | #[unstable(feature = "core")] |
885 | impl<'a, T> ops::IndexMut<RangeFull> for IterMut<'a, T> { | |
1a4d82fc | 886 | #[inline] |
85aaf69f | 887 | fn index_mut(&mut self, _index: &RangeFull) -> &mut [T] { |
1a4d82fc JJ |
888 | make_slice!(T => &mut [T]: self.ptr, self.end) |
889 | } | |
890 | } | |
891 | ||
892 | ||
893 | impl<'a, T> IterMut<'a, T> { | |
894 | /// View the underlying data as a subslice of the original data. | |
895 | /// | |
896 | /// To avoid creating `&mut` references that alias, this is forced | |
897 | /// to consume the iterator. Consider using the `Slice` and | |
898 | /// `SliceMut` implementations for obtaining slices with more | |
899 | /// restricted lifetimes that do not consume the iterator. | |
85aaf69f | 900 | #[unstable(feature = "core")] |
1a4d82fc JJ |
901 | pub fn into_slice(self) -> &'a mut [T] { |
902 | make_slice!(T => &'a mut [T]: self.ptr, self.end) | |
903 | } | |
904 | } | |
905 | ||
906 | iterator!{struct IterMut -> *mut T, &'a mut T} | |
907 | ||
85aaf69f | 908 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
909 | impl<'a, T> ExactSizeIterator for IterMut<'a, T> {} |
910 | ||
911 | /// An internal abstraction over the splitting iterators, so that | |
912 | /// splitn, splitn_mut etc can be implemented once. | |
913 | trait SplitIter: DoubleEndedIterator { | |
914 | /// Mark the underlying iterator as complete, extracting the remaining | |
915 | /// portion of the slice. | |
916 | fn finish(&mut self) -> Option<Self::Item>; | |
917 | } | |
918 | ||
919 | /// An iterator over subslices separated by elements that match a predicate | |
920 | /// function. | |
85aaf69f | 921 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
922 | pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool { |
923 | v: &'a [T], | |
924 | pred: P, | |
925 | finished: bool | |
926 | } | |
927 | ||
928 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
85aaf69f | 929 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
930 | impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool { |
931 | fn clone(&self) -> Split<'a, T, P> { | |
932 | Split { | |
933 | v: self.v, | |
934 | pred: self.pred.clone(), | |
935 | finished: self.finished, | |
936 | } | |
937 | } | |
938 | } | |
939 | ||
85aaf69f | 940 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
941 | impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool { |
942 | type Item = &'a [T]; | |
943 | ||
944 | #[inline] | |
945 | fn next(&mut self) -> Option<&'a [T]> { | |
946 | if self.finished { return None; } | |
947 | ||
948 | match self.v.iter().position(|x| (self.pred)(x)) { | |
949 | None => self.finish(), | |
950 | Some(idx) => { | |
85aaf69f SL |
951 | let ret = Some(&self.v[..idx]); |
952 | self.v = &self.v[idx + 1..]; | |
1a4d82fc JJ |
953 | ret |
954 | } | |
955 | } | |
956 | } | |
957 | ||
958 | #[inline] | |
85aaf69f | 959 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
960 | if self.finished { |
961 | (0, Some(0)) | |
962 | } else { | |
963 | (1, Some(self.v.len() + 1)) | |
964 | } | |
965 | } | |
966 | } | |
967 | ||
85aaf69f | 968 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
969 | impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool { |
970 | #[inline] | |
971 | fn next_back(&mut self) -> Option<&'a [T]> { | |
972 | if self.finished { return None; } | |
973 | ||
974 | match self.v.iter().rposition(|x| (self.pred)(x)) { | |
975 | None => self.finish(), | |
976 | Some(idx) => { | |
85aaf69f SL |
977 | let ret = Some(&self.v[idx + 1..]); |
978 | self.v = &self.v[..idx]; | |
1a4d82fc JJ |
979 | ret |
980 | } | |
981 | } | |
982 | } | |
983 | } | |
984 | ||
985 | impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool { | |
986 | #[inline] | |
987 | fn finish(&mut self) -> Option<&'a [T]> { | |
988 | if self.finished { None } else { self.finished = true; Some(self.v) } | |
989 | } | |
990 | } | |
991 | ||
992 | /// An iterator over the subslices of the vector which are separated | |
993 | /// by elements that match `pred`. | |
85aaf69f | 994 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
995 | pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool { |
996 | v: &'a mut [T], | |
997 | pred: P, | |
998 | finished: bool | |
999 | } | |
1000 | ||
1001 | impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { | |
1002 | #[inline] | |
1003 | fn finish(&mut self) -> Option<&'a mut [T]> { | |
1004 | if self.finished { | |
1005 | None | |
1006 | } else { | |
1007 | self.finished = true; | |
1008 | Some(mem::replace(&mut self.v, &mut [])) | |
1009 | } | |
1010 | } | |
1011 | } | |
1012 | ||
85aaf69f | 1013 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1014 | impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { |
1015 | type Item = &'a mut [T]; | |
1016 | ||
1017 | #[inline] | |
1018 | fn next(&mut self) -> Option<&'a mut [T]> { | |
1019 | if self.finished { return None; } | |
1020 | ||
1021 | let idx_opt = { // work around borrowck limitations | |
1022 | let pred = &mut self.pred; | |
1023 | self.v.iter().position(|x| (*pred)(x)) | |
1024 | }; | |
1025 | match idx_opt { | |
1026 | None => self.finish(), | |
1027 | Some(idx) => { | |
1028 | let tmp = mem::replace(&mut self.v, &mut []); | |
1029 | let (head, tail) = tmp.split_at_mut(idx); | |
85aaf69f | 1030 | self.v = &mut tail[1..]; |
1a4d82fc JJ |
1031 | Some(head) |
1032 | } | |
1033 | } | |
1034 | } | |
1035 | ||
1036 | #[inline] | |
85aaf69f | 1037 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1038 | if self.finished { |
1039 | (0, Some(0)) | |
1040 | } else { | |
1041 | // if the predicate doesn't match anything, we yield one slice | |
1042 | // if it matches every element, we yield len+1 empty slices. | |
1043 | (1, Some(self.v.len() + 1)) | |
1044 | } | |
1045 | } | |
1046 | } | |
1047 | ||
85aaf69f | 1048 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1049 | impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where |
1050 | P: FnMut(&T) -> bool, | |
1051 | { | |
1052 | #[inline] | |
1053 | fn next_back(&mut self) -> Option<&'a mut [T]> { | |
1054 | if self.finished { return None; } | |
1055 | ||
1056 | let idx_opt = { // work around borrowck limitations | |
1057 | let pred = &mut self.pred; | |
1058 | self.v.iter().rposition(|x| (*pred)(x)) | |
1059 | }; | |
1060 | match idx_opt { | |
1061 | None => self.finish(), | |
1062 | Some(idx) => { | |
1063 | let tmp = mem::replace(&mut self.v, &mut []); | |
1064 | let (head, tail) = tmp.split_at_mut(idx); | |
1065 | self.v = head; | |
85aaf69f | 1066 | Some(&mut tail[1..]) |
1a4d82fc JJ |
1067 | } |
1068 | } | |
1069 | } | |
1070 | } | |
1071 | ||
1072 | /// An private iterator over subslices separated by elements that | |
1073 | /// match a predicate function, splitting at most a fixed number of | |
1074 | /// times. | |
1075 | struct GenericSplitN<I> { | |
1076 | iter: I, | |
85aaf69f | 1077 | count: usize, |
1a4d82fc JJ |
1078 | invert: bool |
1079 | } | |
1080 | ||
1081 | impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> { | |
1082 | type Item = T; | |
1083 | ||
1084 | #[inline] | |
1085 | fn next(&mut self) -> Option<T> { | |
1086 | if self.count == 0 { | |
1087 | self.iter.finish() | |
1088 | } else { | |
1089 | self.count -= 1; | |
1090 | if self.invert { self.iter.next_back() } else { self.iter.next() } | |
1091 | } | |
1092 | } | |
1093 | ||
1094 | #[inline] | |
85aaf69f | 1095 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1096 | let (lower, upper_opt) = self.iter.size_hint(); |
1097 | (lower, upper_opt.map(|upper| cmp::min(self.count + 1, upper))) | |
1098 | } | |
1099 | } | |
1100 | ||
1101 | /// An iterator over subslices separated by elements that match a predicate | |
1102 | /// function, limited to a given number of splits. | |
85aaf69f | 1103 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1104 | pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1105 | inner: GenericSplitN<Split<'a, T, P>> | |
1106 | } | |
1107 | ||
1108 | /// An iterator over subslices separated by elements that match a | |
1109 | /// predicate function, limited to a given number of splits, starting | |
1110 | /// from the end of the slice. | |
85aaf69f | 1111 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1112 | pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1113 | inner: GenericSplitN<Split<'a, T, P>> | |
1114 | } | |
1115 | ||
1116 | /// An iterator over subslices separated by elements that match a predicate | |
1117 | /// function, limited to a given number of splits. | |
85aaf69f | 1118 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1119 | pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1120 | inner: GenericSplitN<SplitMut<'a, T, P>> | |
1121 | } | |
1122 | ||
1123 | /// An iterator over subslices separated by elements that match a | |
1124 | /// predicate function, limited to a given number of splits, starting | |
1125 | /// from the end of the slice. | |
85aaf69f | 1126 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1127 | pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1128 | inner: GenericSplitN<SplitMut<'a, T, P>> | |
1129 | } | |
1130 | ||
1131 | macro_rules! forward_iterator { | |
1132 | ($name:ident: $elem:ident, $iter_of:ty) => { | |
85aaf69f | 1133 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1134 | impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where |
1135 | P: FnMut(&T) -> bool | |
1136 | { | |
1137 | type Item = $iter_of; | |
1138 | ||
1139 | #[inline] | |
1140 | fn next(&mut self) -> Option<$iter_of> { | |
1141 | self.inner.next() | |
1142 | } | |
1143 | ||
1144 | #[inline] | |
85aaf69f | 1145 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1146 | self.inner.size_hint() |
1147 | } | |
1148 | } | |
1149 | } | |
1150 | } | |
1151 | ||
1152 | forward_iterator! { SplitN: T, &'a [T] } | |
1153 | forward_iterator! { RSplitN: T, &'a [T] } | |
1154 | forward_iterator! { SplitNMut: T, &'a mut [T] } | |
1155 | forward_iterator! { RSplitNMut: T, &'a mut [T] } | |
1156 | ||
1157 | /// An iterator over overlapping subslices of length `size`. | |
1158 | #[derive(Clone)] | |
85aaf69f | 1159 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1160 | pub struct Windows<'a, T:'a> { |
1161 | v: &'a [T], | |
85aaf69f | 1162 | size: usize |
1a4d82fc JJ |
1163 | } |
1164 | ||
85aaf69f | 1165 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1166 | impl<'a, T> Iterator for Windows<'a, T> { |
1167 | type Item = &'a [T]; | |
1168 | ||
1169 | #[inline] | |
1170 | fn next(&mut self) -> Option<&'a [T]> { | |
1171 | if self.size > self.v.len() { | |
1172 | None | |
1173 | } else { | |
85aaf69f | 1174 | let ret = Some(&self.v[..self.size]); |
1a4d82fc JJ |
1175 | self.v = &self.v[1..]; |
1176 | ret | |
1177 | } | |
1178 | } | |
1179 | ||
1180 | #[inline] | |
85aaf69f | 1181 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1182 | if self.size > self.v.len() { |
1183 | (0, Some(0)) | |
1184 | } else { | |
85aaf69f SL |
1185 | let size = self.v.len() - self.size + 1; |
1186 | (size, Some(size)) | |
1187 | } | |
1188 | } | |
1189 | } | |
1190 | ||
1191 | #[stable(feature = "rust1", since = "1.0.0")] | |
1192 | impl<'a, T> DoubleEndedIterator for Windows<'a, T> { | |
1193 | #[inline] | |
1194 | fn next_back(&mut self) -> Option<&'a [T]> { | |
1195 | if self.size > self.v.len() { | |
1196 | None | |
1197 | } else { | |
1198 | let ret = Some(&self.v[self.v.len()-self.size..]); | |
1199 | self.v = &self.v[..self.v.len()-1]; | |
1200 | ret | |
1201 | } | |
1202 | } | |
1203 | } | |
1204 | ||
1205 | #[stable(feature = "rust1", since = "1.0.0")] | |
1206 | impl<'a, T> ExactSizeIterator for Windows<'a, T> {} | |
1207 | ||
1208 | #[unstable(feature = "core", reason = "trait is experimental")] | |
1209 | impl<'a, T> RandomAccessIterator for Windows<'a, T> { | |
1210 | #[inline] | |
1211 | fn indexable(&self) -> usize { | |
1212 | self.size_hint().0 | |
1213 | } | |
1214 | ||
1215 | #[inline] | |
1216 | fn idx(&mut self, index: usize) -> Option<&'a [T]> { | |
1217 | if index + self.size > self.v.len() { | |
1218 | None | |
1219 | } else { | |
1220 | Some(&self.v[index .. index+self.size]) | |
1a4d82fc JJ |
1221 | } |
1222 | } | |
1223 | } | |
1224 | ||
1225 | /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a | |
1226 | /// time). | |
1227 | /// | |
1228 | /// When the slice len is not evenly divided by the chunk size, the last slice | |
1229 | /// of the iteration will be the remainder. | |
1230 | #[derive(Clone)] | |
85aaf69f | 1231 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1232 | pub struct Chunks<'a, T:'a> { |
1233 | v: &'a [T], | |
85aaf69f | 1234 | size: usize |
1a4d82fc JJ |
1235 | } |
1236 | ||
85aaf69f | 1237 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1238 | impl<'a, T> Iterator for Chunks<'a, T> { |
1239 | type Item = &'a [T]; | |
1240 | ||
1241 | #[inline] | |
1242 | fn next(&mut self) -> Option<&'a [T]> { | |
1243 | if self.v.len() == 0 { | |
1244 | None | |
1245 | } else { | |
1246 | let chunksz = cmp::min(self.v.len(), self.size); | |
1247 | let (fst, snd) = self.v.split_at(chunksz); | |
1248 | self.v = snd; | |
1249 | Some(fst) | |
1250 | } | |
1251 | } | |
1252 | ||
1253 | #[inline] | |
85aaf69f | 1254 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1255 | if self.v.len() == 0 { |
1256 | (0, Some(0)) | |
1257 | } else { | |
1258 | let n = self.v.len() / self.size; | |
1259 | let rem = self.v.len() % self.size; | |
1260 | let n = if rem > 0 { n+1 } else { n }; | |
1261 | (n, Some(n)) | |
1262 | } | |
1263 | } | |
1264 | } | |
1265 | ||
85aaf69f | 1266 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1267 | impl<'a, T> DoubleEndedIterator for Chunks<'a, T> { |
1268 | #[inline] | |
1269 | fn next_back(&mut self) -> Option<&'a [T]> { | |
1270 | if self.v.len() == 0 { | |
1271 | None | |
1272 | } else { | |
1273 | let remainder = self.v.len() % self.size; | |
1274 | let chunksz = if remainder != 0 { remainder } else { self.size }; | |
1275 | let (fst, snd) = self.v.split_at(self.v.len() - chunksz); | |
1276 | self.v = fst; | |
1277 | Some(snd) | |
1278 | } | |
1279 | } | |
1280 | } | |
1281 | ||
85aaf69f SL |
1282 | #[stable(feature = "rust1", since = "1.0.0")] |
1283 | impl<'a, T> ExactSizeIterator for Chunks<'a, T> {} | |
1284 | ||
1285 | #[unstable(feature = "core", reason = "trait is experimental")] | |
1a4d82fc JJ |
1286 | impl<'a, T> RandomAccessIterator for Chunks<'a, T> { |
1287 | #[inline] | |
85aaf69f | 1288 | fn indexable(&self) -> usize { |
1a4d82fc JJ |
1289 | self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 } |
1290 | } | |
1291 | ||
1292 | #[inline] | |
85aaf69f | 1293 | fn idx(&mut self, index: usize) -> Option<&'a [T]> { |
1a4d82fc JJ |
1294 | if index < self.indexable() { |
1295 | let lo = index * self.size; | |
1296 | let mut hi = lo + self.size; | |
1297 | if hi < lo || hi > self.v.len() { hi = self.v.len(); } | |
1298 | ||
1299 | Some(&self.v[lo..hi]) | |
1300 | } else { | |
1301 | None | |
1302 | } | |
1303 | } | |
1304 | } | |
1305 | ||
1306 | /// An iterator over a slice in (non-overlapping) mutable chunks (`size` | |
1307 | /// elements at a time). When the slice len is not evenly divided by the chunk | |
1308 | /// size, the last slice of the iteration will be the remainder. | |
85aaf69f | 1309 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1310 | pub struct ChunksMut<'a, T:'a> { |
1311 | v: &'a mut [T], | |
85aaf69f | 1312 | chunk_size: usize |
1a4d82fc JJ |
1313 | } |
1314 | ||
85aaf69f | 1315 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1316 | impl<'a, T> Iterator for ChunksMut<'a, T> { |
1317 | type Item = &'a mut [T]; | |
1318 | ||
1319 | #[inline] | |
1320 | fn next(&mut self) -> Option<&'a mut [T]> { | |
1321 | if self.v.len() == 0 { | |
1322 | None | |
1323 | } else { | |
1324 | let sz = cmp::min(self.v.len(), self.chunk_size); | |
1325 | let tmp = mem::replace(&mut self.v, &mut []); | |
1326 | let (head, tail) = tmp.split_at_mut(sz); | |
1327 | self.v = tail; | |
1328 | Some(head) | |
1329 | } | |
1330 | } | |
1331 | ||
1332 | #[inline] | |
85aaf69f | 1333 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1334 | if self.v.len() == 0 { |
1335 | (0, Some(0)) | |
1336 | } else { | |
1337 | let n = self.v.len() / self.chunk_size; | |
1338 | let rem = self.v.len() % self.chunk_size; | |
1339 | let n = if rem > 0 { n + 1 } else { n }; | |
1340 | (n, Some(n)) | |
1341 | } | |
1342 | } | |
1343 | } | |
1344 | ||
85aaf69f | 1345 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1346 | impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> { |
1347 | #[inline] | |
1348 | fn next_back(&mut self) -> Option<&'a mut [T]> { | |
1349 | if self.v.len() == 0 { | |
1350 | None | |
1351 | } else { | |
1352 | let remainder = self.v.len() % self.chunk_size; | |
1353 | let sz = if remainder != 0 { remainder } else { self.chunk_size }; | |
1354 | let tmp = mem::replace(&mut self.v, &mut []); | |
1355 | let tmp_len = tmp.len(); | |
1356 | let (head, tail) = tmp.split_at_mut(tmp_len - sz); | |
1357 | self.v = head; | |
1358 | Some(tail) | |
1359 | } | |
1360 | } | |
1361 | } | |
1362 | ||
85aaf69f SL |
1363 | #[stable(feature = "rust1", since = "1.0.0")] |
1364 | impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {} | |
1a4d82fc JJ |
1365 | |
1366 | // | |
1367 | // Free functions | |
1368 | // | |
1369 | ||
1370 | /// Converts a pointer to A into a slice of length 1 (without copying). | |
85aaf69f | 1371 | #[unstable(feature = "core")] |
1a4d82fc JJ |
1372 | pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] { |
1373 | unsafe { | |
1374 | transmute(RawSlice { data: s, len: 1 }) | |
1375 | } | |
1376 | } | |
1377 | ||
1378 | /// Converts a pointer to A into a slice of length 1 (without copying). | |
85aaf69f | 1379 | #[unstable(feature = "core")] |
1a4d82fc JJ |
1380 | pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] { |
1381 | unsafe { | |
1382 | let ptr: *const A = transmute(s); | |
1383 | transmute(RawSlice { data: ptr, len: 1 }) | |
1384 | } | |
1385 | } | |
1386 | ||
85aaf69f SL |
1387 | /// Forms a slice from a pointer and a length. |
1388 | /// | |
1389 | /// The `len` argument is the number of **elements**, not the number of bytes. | |
1390 | /// | |
1391 | /// This function is unsafe as there is no guarantee that the given pointer is | |
1392 | /// valid for `len` elements, nor whether the lifetime inferred is a suitable | |
1393 | /// lifetime for the returned slice. | |
1394 | /// | |
1395 | /// # Caveat | |
1396 | /// | |
1397 | /// The lifetime for the returned slice is inferred from its usage. To | |
1398 | /// prevent accidental misuse, it's suggested to tie the lifetime to whichever | |
1399 | /// source lifetime is safe in the context, such as by providing a helper | |
1400 | /// function taking the lifetime of a host value for the slice, or by explicit | |
1401 | /// annotation. | |
1402 | /// | |
1403 | /// # Example | |
1404 | /// | |
1405 | /// ```rust | |
1406 | /// use std::slice; | |
1407 | /// | |
1408 | /// // manifest a slice out of thin air! | |
1409 | /// let ptr = 0x1234 as *const usize; | |
1410 | /// let amt = 10; | |
1411 | /// unsafe { | |
1412 | /// let slice = slice::from_raw_parts(ptr, amt); | |
1413 | /// } | |
1414 | /// ``` | |
1415 | #[inline] | |
1416 | #[unstable(feature = "core")] | |
1417 | pub unsafe fn from_raw_parts<'a, T>(p: *const T, len: usize) -> &'a [T] { | |
1418 | transmute(RawSlice { data: p, len: len }) | |
1419 | } | |
1420 | ||
1421 | /// Performs the same functionality as `from_raw_parts`, except that a mutable | |
1422 | /// slice is returned. | |
1423 | /// | |
1424 | /// This function is unsafe for the same reasons as `from_raw_parts`, as well | |
1425 | /// as not being able to provide a non-aliasing guarantee of the returned | |
1426 | /// mutable slice. | |
1427 | #[inline] | |
1428 | #[unstable(feature = "core")] | |
1429 | pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] { | |
1430 | transmute(RawSlice { data: p, len: len }) | |
1431 | } | |
1432 | ||
1a4d82fc JJ |
1433 | /// Forms a slice from a pointer and a length. |
1434 | /// | |
1435 | /// The pointer given is actually a reference to the base of the slice. This | |
1436 | /// reference is used to give a concrete lifetime to tie the returned slice to. | |
1437 | /// Typically this should indicate that the slice is valid for as long as the | |
1438 | /// pointer itself is valid. | |
1439 | /// | |
1440 | /// The `len` argument is the number of **elements**, not the number of bytes. | |
1441 | /// | |
1442 | /// This function is unsafe as there is no guarantee that the given pointer is | |
1443 | /// valid for `len` elements, nor whether the lifetime provided is a suitable | |
1444 | /// lifetime for the returned slice. | |
1445 | /// | |
1446 | /// # Example | |
1447 | /// | |
1448 | /// ```rust | |
1449 | /// use std::slice; | |
1450 | /// | |
1451 | /// // manifest a slice out of thin air! | |
85aaf69f | 1452 | /// let ptr = 0x1234 as *const usize; |
1a4d82fc JJ |
1453 | /// let amt = 10; |
1454 | /// unsafe { | |
1455 | /// let slice = slice::from_raw_buf(&ptr, amt); | |
1456 | /// } | |
1457 | /// ``` | |
1458 | #[inline] | |
85aaf69f SL |
1459 | #[unstable(feature = "core")] |
1460 | #[deprecated(since = "1.0.0", | |
1461 | reason = "use from_raw_parts")] | |
1462 | pub unsafe fn from_raw_buf<'a, T>(p: &'a *const T, len: usize) -> &'a [T] { | |
1a4d82fc JJ |
1463 | transmute(RawSlice { data: *p, len: len }) |
1464 | } | |
1465 | ||
1466 | /// Performs the same functionality as `from_raw_buf`, except that a mutable | |
1467 | /// slice is returned. | |
1468 | /// | |
1469 | /// This function is unsafe for the same reasons as `from_raw_buf`, as well as | |
1470 | /// not being able to provide a non-aliasing guarantee of the returned mutable | |
1471 | /// slice. | |
1472 | #[inline] | |
85aaf69f SL |
1473 | #[unstable(feature = "core")] |
1474 | #[deprecated(since = "1.0.0", | |
1475 | reason = "use from_raw_parts_mut")] | |
1476 | pub unsafe fn from_raw_mut_buf<'a, T>(p: &'a *mut T, len: usize) -> &'a mut [T] { | |
1477 | transmute(RawSlice { data: *p, len: len }) | |
1a4d82fc JJ |
1478 | } |
1479 | ||
1480 | // | |
1481 | // Submodules | |
1482 | // | |
1483 | ||
1484 | /// Operations on `[u8]`. | |
85aaf69f | 1485 | #[unstable(feature = "core", reason = "needs review")] |
1a4d82fc JJ |
1486 | pub mod bytes { |
1487 | use ptr; | |
1488 | use slice::SliceExt; | |
1489 | ||
1490 | /// A trait for operations on mutable `[u8]`s. | |
1491 | pub trait MutableByteVector { | |
1492 | /// Sets all bytes of the receiver to the given value. | |
1493 | fn set_memory(&mut self, value: u8); | |
1494 | } | |
1495 | ||
1496 | impl MutableByteVector for [u8] { | |
1497 | #[inline] | |
1a4d82fc JJ |
1498 | fn set_memory(&mut self, value: u8) { |
1499 | unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) }; | |
1500 | } | |
1501 | } | |
1502 | ||
1503 | /// Copies data from `src` to `dst` | |
1504 | /// | |
1505 | /// Panics if the length of `dst` is less than the length of `src`. | |
1506 | #[inline] | |
1507 | pub fn copy_memory(dst: &mut [u8], src: &[u8]) { | |
1508 | let len_src = src.len(); | |
1509 | assert!(dst.len() >= len_src); | |
1510 | // `dst` is unaliasable, so we know statically it doesn't overlap | |
1511 | // with `src`. | |
1512 | unsafe { | |
1513 | ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(), | |
1514 | src.as_ptr(), | |
1515 | len_src); | |
1516 | } | |
1517 | } | |
1518 | } | |
1519 | ||
1520 | ||
1521 | ||
1522 | // | |
1523 | // Boilerplate traits | |
1524 | // | |
1525 | ||
85aaf69f | 1526 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1527 | impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> { |
1528 | fn eq(&self, other: &[B]) -> bool { | |
1529 | self.len() == other.len() && | |
1530 | order::eq(self.iter(), other.iter()) | |
1531 | } | |
1532 | fn ne(&self, other: &[B]) -> bool { | |
1533 | self.len() != other.len() || | |
1534 | order::ne(self.iter(), other.iter()) | |
1535 | } | |
1536 | } | |
1537 | ||
85aaf69f | 1538 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1539 | impl<T: Eq> Eq for [T] {} |
1540 | ||
85aaf69f | 1541 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1542 | impl<T: Ord> Ord for [T] { |
1543 | fn cmp(&self, other: &[T]) -> Ordering { | |
1544 | order::cmp(self.iter(), other.iter()) | |
1545 | } | |
1546 | } | |
1547 | ||
85aaf69f | 1548 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1549 | impl<T: PartialOrd> PartialOrd for [T] { |
1550 | #[inline] | |
1551 | fn partial_cmp(&self, other: &[T]) -> Option<Ordering> { | |
1552 | order::partial_cmp(self.iter(), other.iter()) | |
1553 | } | |
1554 | #[inline] | |
1555 | fn lt(&self, other: &[T]) -> bool { | |
1556 | order::lt(self.iter(), other.iter()) | |
1557 | } | |
1558 | #[inline] | |
1559 | fn le(&self, other: &[T]) -> bool { | |
1560 | order::le(self.iter(), other.iter()) | |
1561 | } | |
1562 | #[inline] | |
1563 | fn ge(&self, other: &[T]) -> bool { | |
1564 | order::ge(self.iter(), other.iter()) | |
1565 | } | |
1566 | #[inline] | |
1567 | fn gt(&self, other: &[T]) -> bool { | |
1568 | order::gt(self.iter(), other.iter()) | |
1569 | } | |
1570 | } | |
1571 | ||
1572 | /// Extension methods for slices containing integers. | |
85aaf69f | 1573 | #[unstable(feature = "core")] |
1a4d82fc JJ |
1574 | pub trait IntSliceExt<U, S> { |
1575 | /// Converts the slice to an immutable slice of unsigned integers with the same width. | |
1576 | fn as_unsigned<'a>(&'a self) -> &'a [U]; | |
1577 | /// Converts the slice to an immutable slice of signed integers with the same width. | |
1578 | fn as_signed<'a>(&'a self) -> &'a [S]; | |
1579 | ||
1580 | /// Converts the slice to a mutable slice of unsigned integers with the same width. | |
1581 | fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U]; | |
1582 | /// Converts the slice to a mutable slice of signed integers with the same width. | |
1583 | fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S]; | |
1584 | } | |
1585 | ||
1586 | macro_rules! impl_int_slice { | |
1587 | ($u:ty, $s:ty, $t:ty) => { | |
85aaf69f | 1588 | #[unstable(feature = "core")] |
1a4d82fc JJ |
1589 | impl IntSliceExt<$u, $s> for [$t] { |
1590 | #[inline] | |
1591 | fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } } | |
1592 | #[inline] | |
1593 | fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } } | |
1594 | #[inline] | |
1595 | fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } } | |
1596 | #[inline] | |
1597 | fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } } | |
1598 | } | |
1599 | } | |
1600 | } | |
1601 | ||
1602 | macro_rules! impl_int_slices { | |
1603 | ($u:ty, $s:ty) => { | |
1604 | impl_int_slice! { $u, $s, $u } | |
1605 | impl_int_slice! { $u, $s, $s } | |
1606 | } | |
1607 | } | |
1608 | ||
1609 | impl_int_slices! { u8, i8 } | |
1610 | impl_int_slices! { u16, i16 } | |
1611 | impl_int_slices! { u32, i32 } | |
1612 | impl_int_slices! { u64, i64 } | |
85aaf69f | 1613 | impl_int_slices! { usize, isize } |