]>
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 | |
17 | // How this module is organized. | |
18 | // | |
19 | // The library infrastructure for slices is fairly messy. There's | |
20 | // a lot of stuff defined here. Let's keep it clean. | |
21 | // | |
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. | |
25 | // | |
26 | // The layout of this file is thus: | |
27 | // | |
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. | |
32 | // * Free functions. | |
33 | // * The `raw` and `bytes` submodules. | |
34 | // * Boilerplate trait implementations. | |
35 | ||
1a4d82fc JJ |
36 | use clone::Clone; |
37 | use cmp::{Ordering, PartialEq, PartialOrd, Eq, Ord}; | |
38 | use cmp::Ordering::{Less, Equal, Greater}; | |
39 | use cmp; | |
40 | use default::Default; | |
54a0048b | 41 | use fmt; |
c34b1796 | 42 | use intrinsics::assume; |
1a4d82fc | 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; | |
1a4d82fc | 51 | use mem; |
7453a54e | 52 | use marker::{Copy, Send, Sync, self}; |
1a4d82fc | 53 | |
54a0048b SL |
54 | #[repr(C)] |
55 | struct Repr<T> { | |
56 | pub data: *const T, | |
57 | pub len: usize, | |
58 | } | |
1a4d82fc JJ |
59 | |
60 | // | |
61 | // Extension traits | |
62 | // | |
63 | ||
64 | /// Extension methods for slices. | |
62682a34 | 65 | #[unstable(feature = "core_slice_ext", |
e9174d1e | 66 | reason = "stable interface provided by `impl [T]` in later crates", |
54a0048b | 67 | issue = "32110")] |
92a42be0 | 68 | #[allow(missing_docs)] // documented elsewhere |
1a4d82fc JJ |
69 | pub trait SliceExt { |
70 | type Item; | |
71 | ||
92a42be0 | 72 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 73 | fn split_at(&self, mid: usize) -> (&[Self::Item], &[Self::Item]); |
92a42be0 | 74 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 75 | fn iter(&self) -> Iter<Self::Item>; |
92a42be0 | 76 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 77 | fn split<P>(&self, pred: P) -> Split<Self::Item, P> |
1a4d82fc | 78 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 79 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 80 | fn splitn<P>(&self, n: usize, pred: P) -> SplitN<Self::Item, P> |
1a4d82fc | 81 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 82 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 83 | fn rsplitn<P>(&self, n: usize, pred: P) -> RSplitN<Self::Item, P> |
1a4d82fc | 84 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 85 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 86 | fn windows(&self, size: usize) -> Windows<Self::Item>; |
92a42be0 | 87 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 88 | fn chunks(&self, size: usize) -> Chunks<Self::Item>; |
92a42be0 | 89 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 90 | fn get(&self, index: usize) -> Option<&Self::Item>; |
92a42be0 | 91 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 92 | fn first(&self) -> Option<&Self::Item>; |
92a42be0 | 93 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 94 | fn split_first(&self) -> Option<(&Self::Item, &[Self::Item])>; |
92a42be0 | 95 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 96 | fn split_last(&self) -> Option<(&Self::Item, &[Self::Item])>; |
92a42be0 | 97 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 98 | fn last(&self) -> Option<&Self::Item>; |
92a42be0 | 99 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 100 | unsafe fn get_unchecked(&self, index: usize) -> &Self::Item; |
92a42be0 | 101 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc | 102 | fn as_ptr(&self) -> *const Self::Item; |
92a42be0 SL |
103 | #[stable(feature = "core", since = "1.6.0")] |
104 | fn binary_search(&self, x: &Self::Item) -> Result<usize, usize> | |
105 | where Self::Item: Ord; | |
106 | #[stable(feature = "core", since = "1.6.0")] | |
107 | fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> | |
108 | where F: FnMut(&Self::Item) -> Ordering; | |
109 | #[stable(feature = "core", since = "1.6.0")] | |
85aaf69f | 110 | fn len(&self) -> usize; |
92a42be0 | 111 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc | 112 | fn is_empty(&self) -> bool { self.len() == 0 } |
92a42be0 | 113 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 114 | fn get_mut(&mut self, index: usize) -> Option<&mut Self::Item>; |
92a42be0 | 115 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 116 | fn iter_mut(&mut self) -> IterMut<Self::Item>; |
92a42be0 | 117 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 118 | fn first_mut(&mut self) -> Option<&mut Self::Item>; |
92a42be0 | 119 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 120 | fn split_first_mut(&mut self) -> Option<(&mut Self::Item, &mut [Self::Item])>; |
92a42be0 | 121 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 122 | fn split_last_mut(&mut self) -> Option<(&mut Self::Item, &mut [Self::Item])>; |
92a42be0 | 123 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 124 | fn last_mut(&mut self) -> Option<&mut Self::Item>; |
92a42be0 | 125 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 126 | fn split_mut<P>(&mut self, pred: P) -> SplitMut<Self::Item, P> |
1a4d82fc | 127 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 128 | #[stable(feature = "core", since = "1.6.0")] |
85aaf69f | 129 | fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<Self::Item, P> |
1a4d82fc | 130 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 131 | #[stable(feature = "core", since = "1.6.0")] |
85aaf69f | 132 | fn rsplitn_mut<P>(&mut self, n: usize, pred: P) -> RSplitNMut<Self::Item, P> |
1a4d82fc | 133 | where P: FnMut(&Self::Item) -> bool; |
92a42be0 | 134 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 135 | fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<Self::Item>; |
92a42be0 | 136 | #[stable(feature = "core", since = "1.6.0")] |
85aaf69f | 137 | fn swap(&mut self, a: usize, b: usize); |
92a42be0 | 138 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 139 | fn split_at_mut(&mut self, mid: usize) -> (&mut [Self::Item], &mut [Self::Item]); |
92a42be0 | 140 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc | 141 | fn reverse(&mut self); |
92a42be0 | 142 | #[stable(feature = "core", since = "1.6.0")] |
e9174d1e | 143 | unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Item; |
92a42be0 | 144 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc JJ |
145 | fn as_mut_ptr(&mut self) -> *mut Self::Item; |
146 | ||
92a42be0 | 147 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc JJ |
148 | fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq; |
149 | ||
92a42be0 | 150 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc JJ |
151 | fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq; |
152 | ||
92a42be0 | 153 | #[stable(feature = "core", since = "1.6.0")] |
1a4d82fc JJ |
154 | fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq; |
155 | ||
9cc50fc6 | 156 | #[stable(feature = "clone_from_slice", since = "1.7.0")] |
54a0048b SL |
157 | fn clone_from_slice(&mut self, src: &[Self::Item]) where Self::Item: Clone; |
158 | #[stable(feature = "copy_from_slice", since = "1.9.0")] | |
7453a54e | 159 | fn copy_from_slice(&mut self, src: &[Self::Item]) where Self::Item: Copy; |
1a4d82fc JJ |
160 | } |
161 | ||
62682a34 SL |
162 | // Use macros to be generic over const/mut |
163 | macro_rules! slice_offset { | |
164 | ($ptr:expr, $by:expr) => {{ | |
165 | let ptr = $ptr; | |
166 | if size_from_ptr(ptr) == 0 { | |
167 | ::intrinsics::arith_offset(ptr as *mut i8, $by) as *mut _ | |
168 | } else { | |
169 | ptr.offset($by) | |
170 | } | |
171 | }}; | |
172 | } | |
173 | ||
174 | macro_rules! slice_ref { | |
175 | ($ptr:expr) => {{ | |
176 | let ptr = $ptr; | |
177 | if size_from_ptr(ptr) == 0 { | |
178 | // Use a non-null pointer value | |
179 | &mut *(1 as *mut _) | |
180 | } else { | |
e9174d1e | 181 | mem::transmute(ptr) |
62682a34 SL |
182 | } |
183 | }}; | |
184 | } | |
185 | ||
92a42be0 SL |
186 | #[unstable(feature = "core_slice_ext", |
187 | reason = "stable interface provided by `impl [T]` in later crates", | |
54a0048b | 188 | issue = "32110")] |
1a4d82fc JJ |
189 | impl<T> SliceExt for [T] { |
190 | type Item = T; | |
191 | ||
192 | #[inline] | |
85aaf69f SL |
193 | fn split_at(&self, mid: usize) -> (&[T], &[T]) { |
194 | (&self[..mid], &self[mid..]) | |
1a4d82fc JJ |
195 | } |
196 | ||
197 | #[inline] | |
e9174d1e | 198 | fn iter(&self) -> Iter<T> { |
1a4d82fc | 199 | unsafe { |
62682a34 SL |
200 | let p = if mem::size_of::<T>() == 0 { |
201 | 1 as *const _ | |
1a4d82fc | 202 | } else { |
62682a34 SL |
203 | let p = self.as_ptr(); |
204 | assume(!p.is_null()); | |
205 | p | |
206 | }; | |
207 | ||
208 | Iter { | |
209 | ptr: p, | |
210 | end: slice_offset!(p, self.len() as isize), | |
211 | _marker: marker::PhantomData | |
1a4d82fc JJ |
212 | } |
213 | } | |
214 | } | |
215 | ||
216 | #[inline] | |
e9174d1e | 217 | fn split<P>(&self, pred: P) -> Split<T, P> where P: FnMut(&T) -> bool { |
1a4d82fc JJ |
218 | Split { |
219 | v: self, | |
220 | pred: pred, | |
221 | finished: false | |
222 | } | |
223 | } | |
224 | ||
225 | #[inline] | |
e9174d1e | 226 | fn splitn<P>(&self, n: usize, pred: P) -> SplitN<T, P> where |
1a4d82fc JJ |
227 | P: FnMut(&T) -> bool, |
228 | { | |
229 | SplitN { | |
230 | inner: GenericSplitN { | |
231 | iter: self.split(pred), | |
232 | count: n, | |
233 | invert: false | |
234 | } | |
235 | } | |
236 | } | |
237 | ||
238 | #[inline] | |
e9174d1e | 239 | fn rsplitn<P>(&self, n: usize, pred: P) -> RSplitN<T, P> where |
1a4d82fc JJ |
240 | P: FnMut(&T) -> bool, |
241 | { | |
242 | RSplitN { | |
243 | inner: GenericSplitN { | |
244 | iter: self.split(pred), | |
245 | count: n, | |
246 | invert: true | |
247 | } | |
248 | } | |
249 | } | |
250 | ||
251 | #[inline] | |
85aaf69f | 252 | fn windows(&self, size: usize) -> Windows<T> { |
1a4d82fc JJ |
253 | assert!(size != 0); |
254 | Windows { v: self, size: size } | |
255 | } | |
256 | ||
257 | #[inline] | |
85aaf69f | 258 | fn chunks(&self, size: usize) -> Chunks<T> { |
1a4d82fc JJ |
259 | assert!(size != 0); |
260 | Chunks { v: self, size: size } | |
261 | } | |
262 | ||
263 | #[inline] | |
85aaf69f | 264 | fn get(&self, index: usize) -> Option<&T> { |
1a4d82fc JJ |
265 | if index < self.len() { Some(&self[index]) } else { None } |
266 | } | |
267 | ||
268 | #[inline] | |
269 | fn first(&self) -> Option<&T> { | |
9346a6ac | 270 | if self.is_empty() { None } else { Some(&self[0]) } |
1a4d82fc JJ |
271 | } |
272 | ||
1a4d82fc | 273 | #[inline] |
c1a9b12d SL |
274 | fn split_first(&self) -> Option<(&T, &[T])> { |
275 | if self.is_empty() { None } else { Some((&self[0], &self[1..])) } | |
276 | } | |
277 | ||
c1a9b12d SL |
278 | #[inline] |
279 | fn split_last(&self) -> Option<(&T, &[T])> { | |
280 | let len = self.len(); | |
281 | if len == 0 { None } else { Some((&self[len - 1], &self[..(len - 1)])) } | |
1a4d82fc JJ |
282 | } |
283 | ||
284 | #[inline] | |
285 | fn last(&self) -> Option<&T> { | |
9346a6ac | 286 | if self.is_empty() { None } else { Some(&self[self.len() - 1]) } |
1a4d82fc JJ |
287 | } |
288 | ||
289 | #[inline] | |
85aaf69f | 290 | unsafe fn get_unchecked(&self, index: usize) -> &T { |
54a0048b | 291 | &*(self.as_ptr().offset(index as isize)) |
1a4d82fc JJ |
292 | } |
293 | ||
294 | #[inline] | |
295 | fn as_ptr(&self) -> *const T { | |
54a0048b | 296 | self as *const [T] as *const T |
1a4d82fc JJ |
297 | } |
298 | ||
85aaf69f | 299 | fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> where |
1a4d82fc JJ |
300 | F: FnMut(&T) -> Ordering |
301 | { | |
7453a54e SL |
302 | let mut base = 0usize; |
303 | let mut s = self; | |
1a4d82fc | 304 | |
7453a54e SL |
305 | loop { |
306 | let (head, tail) = s.split_at(s.len() >> 1); | |
307 | if tail.is_empty() { | |
308 | return Err(base) | |
309 | } | |
310 | match f(&tail[0]) { | |
1a4d82fc | 311 | Less => { |
7453a54e SL |
312 | base += head.len() + 1; |
313 | s = &tail[1..]; | |
1a4d82fc | 314 | } |
7453a54e SL |
315 | Greater => s = head, |
316 | Equal => return Ok(base + head.len()), | |
1a4d82fc | 317 | } |
1a4d82fc | 318 | } |
1a4d82fc JJ |
319 | } |
320 | ||
321 | #[inline] | |
54a0048b SL |
322 | fn len(&self) -> usize { |
323 | unsafe { | |
324 | mem::transmute::<&[T], Repr<T>>(self).len | |
325 | } | |
326 | } | |
1a4d82fc JJ |
327 | |
328 | #[inline] | |
85aaf69f | 329 | fn get_mut(&mut self, index: usize) -> Option<&mut T> { |
1a4d82fc JJ |
330 | if index < self.len() { Some(&mut self[index]) } else { None } |
331 | } | |
332 | ||
1a4d82fc | 333 | #[inline] |
85aaf69f | 334 | fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { |
c1a9b12d SL |
335 | let len = self.len(); |
336 | let ptr = self.as_mut_ptr(); | |
e9174d1e | 337 | |
1a4d82fc | 338 | unsafe { |
e9174d1e SL |
339 | assert!(mid <= len); |
340 | ||
c1a9b12d SL |
341 | (from_raw_parts_mut(ptr, mid), |
342 | from_raw_parts_mut(ptr.offset(mid as isize), len - mid)) | |
1a4d82fc JJ |
343 | } |
344 | } | |
345 | ||
346 | #[inline] | |
e9174d1e | 347 | fn iter_mut(&mut self) -> IterMut<T> { |
1a4d82fc | 348 | unsafe { |
62682a34 SL |
349 | let p = if mem::size_of::<T>() == 0 { |
350 | 1 as *mut _ | |
1a4d82fc | 351 | } else { |
62682a34 SL |
352 | let p = self.as_mut_ptr(); |
353 | assume(!p.is_null()); | |
354 | p | |
355 | }; | |
356 | ||
357 | IterMut { | |
358 | ptr: p, | |
359 | end: slice_offset!(p, self.len() as isize), | |
360 | _marker: marker::PhantomData | |
1a4d82fc JJ |
361 | } |
362 | } | |
363 | } | |
364 | ||
365 | #[inline] | |
366 | fn last_mut(&mut self) -> Option<&mut T> { | |
367 | let len = self.len(); | |
368 | if len == 0 { return None; } | |
369 | Some(&mut self[len - 1]) | |
370 | } | |
371 | ||
372 | #[inline] | |
373 | fn first_mut(&mut self) -> Option<&mut T> { | |
9346a6ac | 374 | if self.is_empty() { None } else { Some(&mut self[0]) } |
1a4d82fc JJ |
375 | } |
376 | ||
c1a9b12d SL |
377 | #[inline] |
378 | fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> { | |
379 | if self.is_empty() { None } else { | |
380 | let split = self.split_at_mut(1); | |
381 | Some((&mut split.0[0], split.1)) | |
382 | } | |
1a4d82fc JJ |
383 | } |
384 | ||
c1a9b12d SL |
385 | #[inline] |
386 | fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> { | |
387 | let len = self.len(); | |
388 | if len == 0 { None } else { | |
389 | let split = self.split_at_mut(len - 1); | |
390 | Some((&mut split.1[0], split.0)) | |
391 | } | |
392 | } | |
393 | ||
1a4d82fc | 394 | #[inline] |
e9174d1e | 395 | fn split_mut<P>(&mut self, pred: P) -> SplitMut<T, P> where P: FnMut(&T) -> bool { |
1a4d82fc JJ |
396 | SplitMut { v: self, pred: pred, finished: false } |
397 | } | |
398 | ||
399 | #[inline] | |
e9174d1e | 400 | fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<T, P> where |
1a4d82fc JJ |
401 | P: FnMut(&T) -> bool |
402 | { | |
403 | SplitNMut { | |
404 | inner: GenericSplitN { | |
405 | iter: self.split_mut(pred), | |
406 | count: n, | |
407 | invert: false | |
408 | } | |
409 | } | |
410 | } | |
411 | ||
412 | #[inline] | |
e9174d1e | 413 | fn rsplitn_mut<P>(&mut self, n: usize, pred: P) -> RSplitNMut<T, P> where |
1a4d82fc JJ |
414 | P: FnMut(&T) -> bool, |
415 | { | |
416 | RSplitNMut { | |
417 | inner: GenericSplitN { | |
418 | iter: self.split_mut(pred), | |
419 | count: n, | |
420 | invert: true | |
421 | } | |
422 | } | |
423 | } | |
424 | ||
425 | #[inline] | |
85aaf69f | 426 | fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> { |
1a4d82fc JJ |
427 | assert!(chunk_size > 0); |
428 | ChunksMut { v: self, chunk_size: chunk_size } | |
429 | } | |
430 | ||
c34b1796 | 431 | #[inline] |
85aaf69f | 432 | fn swap(&mut self, a: usize, b: usize) { |
1a4d82fc JJ |
433 | unsafe { |
434 | // Can't take two mutable loans from one vector, so instead just cast | |
435 | // them to their raw pointers to do the swap | |
436 | let pa: *mut T = &mut self[a]; | |
437 | let pb: *mut T = &mut self[b]; | |
438 | ptr::swap(pa, pb); | |
439 | } | |
440 | } | |
441 | ||
442 | fn reverse(&mut self) { | |
85aaf69f | 443 | let mut i: usize = 0; |
1a4d82fc JJ |
444 | let ln = self.len(); |
445 | while i < ln / 2 { | |
446 | // Unsafe swap to avoid the bounds check in safe swap. | |
447 | unsafe { | |
448 | let pa: *mut T = self.get_unchecked_mut(i); | |
449 | let pb: *mut T = self.get_unchecked_mut(ln - i - 1); | |
450 | ptr::swap(pa, pb); | |
451 | } | |
452 | i += 1; | |
453 | } | |
454 | } | |
455 | ||
456 | #[inline] | |
85aaf69f | 457 | unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T { |
54a0048b | 458 | &mut *self.as_mut_ptr().offset(index as isize) |
1a4d82fc JJ |
459 | } |
460 | ||
461 | #[inline] | |
462 | fn as_mut_ptr(&mut self) -> *mut T { | |
54a0048b | 463 | self as *mut [T] as *mut T |
1a4d82fc JJ |
464 | } |
465 | ||
1a4d82fc JJ |
466 | #[inline] |
467 | fn contains(&self, x: &T) -> bool where T: PartialEq { | |
468 | self.iter().any(|elt| *x == *elt) | |
469 | } | |
470 | ||
471 | #[inline] | |
472 | fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq { | |
473 | let n = needle.len(); | |
85aaf69f | 474 | self.len() >= n && needle == &self[..n] |
1a4d82fc JJ |
475 | } |
476 | ||
477 | #[inline] | |
478 | fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq { | |
479 | let (m, n) = (self.len(), needle.len()); | |
85aaf69f | 480 | m >= n && needle == &self[m-n..] |
1a4d82fc JJ |
481 | } |
482 | ||
85aaf69f | 483 | fn binary_search(&self, x: &T) -> Result<usize, usize> where T: Ord { |
1a4d82fc JJ |
484 | self.binary_search_by(|p| p.cmp(x)) |
485 | } | |
486 | ||
1a4d82fc | 487 | #[inline] |
9cc50fc6 SL |
488 | fn clone_from_slice(&mut self, src: &[T]) where T: Clone { |
489 | assert!(self.len() == src.len(), | |
490 | "destination and source slices have different lengths"); | |
491 | // NOTE: We need to explicitly slice them to the same length | |
492 | // for bounds checking to be elided, and the optimizer will | |
493 | // generate memcpy for simple cases (for example T = u8). | |
494 | let len = self.len(); | |
495 | let src = &src[..len]; | |
496 | for i in 0..len { | |
497 | self[i].clone_from(&src[i]); | |
1a4d82fc | 498 | } |
1a4d82fc | 499 | } |
7453a54e SL |
500 | |
501 | #[inline] | |
502 | fn copy_from_slice(&mut self, src: &[T]) where T: Copy { | |
503 | assert!(self.len() == src.len(), | |
504 | "destination and source slices have different lengths"); | |
505 | unsafe { | |
506 | ptr::copy_nonoverlapping( | |
507 | src.as_ptr(), self.as_mut_ptr(), self.len()); | |
508 | } | |
509 | } | |
1a4d82fc JJ |
510 | } |
511 | ||
85aaf69f SL |
512 | #[stable(feature = "rust1", since = "1.0.0")] |
513 | impl<T> ops::Index<usize> for [T] { | |
1a4d82fc JJ |
514 | type Output = T; |
515 | ||
c34b1796 | 516 | fn index(&self, index: usize) -> &T { |
1a4d82fc | 517 | assert!(index < self.len()); |
e9174d1e | 518 | unsafe { self.get_unchecked(index) } |
1a4d82fc JJ |
519 | } |
520 | } | |
521 | ||
85aaf69f SL |
522 | #[stable(feature = "rust1", since = "1.0.0")] |
523 | impl<T> ops::IndexMut<usize> for [T] { | |
c34b1796 AL |
524 | #[inline] |
525 | fn index_mut(&mut self, index: usize) -> &mut T { | |
1a4d82fc | 526 | assert!(index < self.len()); |
e9174d1e | 527 | unsafe { self.get_unchecked_mut(index) } |
1a4d82fc JJ |
528 | } |
529 | } | |
530 | ||
92a42be0 SL |
531 | #[inline(never)] |
532 | #[cold] | |
533 | fn slice_index_len_fail(index: usize, len: usize) -> ! { | |
534 | panic!("index {} out of range for slice of length {}", index, len); | |
535 | } | |
536 | ||
537 | #[inline(never)] | |
538 | #[cold] | |
539 | fn slice_index_order_fail(index: usize, end: usize) -> ! { | |
540 | panic!("slice index starts at {} but ends at {}", index, end); | |
541 | } | |
542 | ||
54a0048b SL |
543 | // FIXME implement indexing with inclusive ranges |
544 | ||
545 | /// Implements slicing with syntax `&self[begin .. end]`. | |
546 | /// | |
547 | /// Returns a slice of self for the index range [`begin`..`end`). | |
548 | /// | |
549 | /// This operation is `O(1)`. | |
550 | /// | |
551 | /// # Panics | |
552 | /// | |
553 | /// Requires that `begin <= end` and `end <= self.len()`, | |
554 | /// otherwise slicing will panic. | |
85aaf69f SL |
555 | #[stable(feature = "rust1", since = "1.0.0")] |
556 | impl<T> ops::Index<ops::Range<usize>> for [T] { | |
1a4d82fc | 557 | type Output = [T]; |
c34b1796 | 558 | |
1a4d82fc | 559 | #[inline] |
c34b1796 | 560 | fn index(&self, index: ops::Range<usize>) -> &[T] { |
92a42be0 SL |
561 | if index.start > index.end { |
562 | slice_index_order_fail(index.start, index.end); | |
563 | } else if index.end > self.len() { | |
564 | slice_index_len_fail(index.end, self.len()); | |
565 | } | |
1a4d82fc | 566 | unsafe { |
c34b1796 AL |
567 | from_raw_parts ( |
568 | self.as_ptr().offset(index.start as isize), | |
569 | index.end - index.start | |
570 | ) | |
1a4d82fc JJ |
571 | } |
572 | } | |
573 | } | |
54a0048b SL |
574 | |
575 | /// Implements slicing with syntax `&self[.. end]`. | |
576 | /// | |
577 | /// Returns a slice of self from the beginning until but not including | |
578 | /// the index `end`. | |
579 | /// | |
580 | /// Equivalent to `&self[0 .. end]` | |
85aaf69f SL |
581 | #[stable(feature = "rust1", since = "1.0.0")] |
582 | impl<T> ops::Index<ops::RangeTo<usize>> for [T] { | |
1a4d82fc | 583 | type Output = [T]; |
c34b1796 | 584 | |
1a4d82fc | 585 | #[inline] |
c34b1796 | 586 | fn index(&self, index: ops::RangeTo<usize>) -> &[T] { |
54a0048b | 587 | self.index(0 .. index.end) |
1a4d82fc JJ |
588 | } |
589 | } | |
54a0048b SL |
590 | |
591 | /// Implements slicing with syntax `&self[begin ..]`. | |
592 | /// | |
593 | /// Returns a slice of self from and including the index `begin` until the end. | |
594 | /// | |
595 | /// Equivalent to `&self[begin .. self.len()]` | |
85aaf69f SL |
596 | #[stable(feature = "rust1", since = "1.0.0")] |
597 | impl<T> ops::Index<ops::RangeFrom<usize>> for [T] { | |
1a4d82fc | 598 | type Output = [T]; |
c34b1796 | 599 | |
1a4d82fc | 600 | #[inline] |
c34b1796 | 601 | fn index(&self, index: ops::RangeFrom<usize>) -> &[T] { |
54a0048b | 602 | self.index(index.start .. self.len()) |
1a4d82fc JJ |
603 | } |
604 | } | |
54a0048b SL |
605 | |
606 | /// Implements slicing with syntax `&self[..]`. | |
607 | /// | |
608 | /// Returns a slice of the whole slice. This operation can not panic. | |
609 | /// | |
610 | /// Equivalent to `&self[0 .. self.len()]` | |
85aaf69f SL |
611 | #[stable(feature = "rust1", since = "1.0.0")] |
612 | impl<T> ops::Index<RangeFull> for [T] { | |
1a4d82fc | 613 | type Output = [T]; |
c34b1796 | 614 | |
1a4d82fc | 615 | #[inline] |
c34b1796 | 616 | fn index(&self, _index: RangeFull) -> &[T] { |
1a4d82fc JJ |
617 | self |
618 | } | |
619 | } | |
620 | ||
54a0048b SL |
621 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] |
622 | impl<T> ops::Index<ops::RangeInclusive<usize>> for [T] { | |
623 | type Output = [T]; | |
624 | ||
625 | #[inline] | |
626 | fn index(&self, index: ops::RangeInclusive<usize>) -> &[T] { | |
627 | match index { | |
628 | ops::RangeInclusive::Empty { .. } => &[], | |
629 | ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => | |
630 | panic!("attempted to index slice up to maximum usize"), | |
631 | ops::RangeInclusive::NonEmpty { start, end } => | |
632 | self.index(start .. end+1) | |
633 | } | |
634 | } | |
635 | } | |
636 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] | |
637 | impl<T> ops::Index<ops::RangeToInclusive<usize>> for [T] { | |
638 | type Output = [T]; | |
639 | ||
640 | #[inline] | |
641 | fn index(&self, index: ops::RangeToInclusive<usize>) -> &[T] { | |
642 | self.index(0...index.end) | |
643 | } | |
644 | } | |
645 | ||
646 | /// Implements mutable slicing with syntax `&mut self[begin .. end]`. | |
647 | /// | |
648 | /// Returns a slice of self for the index range [`begin`..`end`). | |
649 | /// | |
650 | /// This operation is `O(1)`. | |
651 | /// | |
652 | /// # Panics | |
653 | /// | |
654 | /// Requires that `begin <= end` and `end <= self.len()`, | |
655 | /// otherwise slicing will panic. | |
85aaf69f SL |
656 | #[stable(feature = "rust1", since = "1.0.0")] |
657 | impl<T> ops::IndexMut<ops::Range<usize>> for [T] { | |
1a4d82fc | 658 | #[inline] |
c34b1796 | 659 | fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] { |
92a42be0 SL |
660 | if index.start > index.end { |
661 | slice_index_order_fail(index.start, index.end); | |
662 | } else if index.end > self.len() { | |
663 | slice_index_len_fail(index.end, self.len()); | |
664 | } | |
1a4d82fc | 665 | unsafe { |
c34b1796 AL |
666 | from_raw_parts_mut( |
667 | self.as_mut_ptr().offset(index.start as isize), | |
668 | index.end - index.start | |
669 | ) | |
1a4d82fc JJ |
670 | } |
671 | } | |
672 | } | |
54a0048b SL |
673 | |
674 | /// Implements mutable slicing with syntax `&mut self[.. end]`. | |
675 | /// | |
676 | /// Returns a slice of self from the beginning until but not including | |
677 | /// the index `end`. | |
678 | /// | |
679 | /// Equivalent to `&mut self[0 .. end]` | |
85aaf69f SL |
680 | #[stable(feature = "rust1", since = "1.0.0")] |
681 | impl<T> ops::IndexMut<ops::RangeTo<usize>> for [T] { | |
1a4d82fc | 682 | #[inline] |
c34b1796 | 683 | fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] { |
54a0048b | 684 | self.index_mut(0 .. index.end) |
1a4d82fc JJ |
685 | } |
686 | } | |
54a0048b SL |
687 | |
688 | /// Implements mutable slicing with syntax `&mut self[begin ..]`. | |
689 | /// | |
690 | /// Returns a slice of self from and including the index `begin` until the end. | |
691 | /// | |
692 | /// Equivalent to `&mut self[begin .. self.len()]` | |
85aaf69f SL |
693 | #[stable(feature = "rust1", since = "1.0.0")] |
694 | impl<T> ops::IndexMut<ops::RangeFrom<usize>> for [T] { | |
1a4d82fc | 695 | #[inline] |
c34b1796 | 696 | fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] { |
1a4d82fc | 697 | let len = self.len(); |
54a0048b | 698 | self.index_mut(index.start .. len) |
1a4d82fc JJ |
699 | } |
700 | } | |
54a0048b SL |
701 | |
702 | /// Implements mutable slicing with syntax `&mut self[..]`. | |
703 | /// | |
704 | /// Returns a slice of the whole slice. This operation can not panic. | |
705 | /// | |
706 | /// Equivalent to `&mut self[0 .. self.len()]` | |
85aaf69f SL |
707 | #[stable(feature = "rust1", since = "1.0.0")] |
708 | impl<T> ops::IndexMut<RangeFull> for [T] { | |
1a4d82fc | 709 | #[inline] |
c34b1796 | 710 | fn index_mut(&mut self, _index: RangeFull) -> &mut [T] { |
1a4d82fc JJ |
711 | self |
712 | } | |
713 | } | |
714 | ||
54a0048b SL |
715 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] |
716 | impl<T> ops::IndexMut<ops::RangeInclusive<usize>> for [T] { | |
717 | #[inline] | |
718 | fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut [T] { | |
719 | match index { | |
720 | ops::RangeInclusive::Empty { .. } => &mut [], | |
721 | ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => | |
722 | panic!("attempted to index slice up to maximum usize"), | |
723 | ops::RangeInclusive::NonEmpty { start, end } => | |
724 | self.index_mut(start .. end+1) | |
725 | } | |
726 | } | |
727 | } | |
728 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] | |
729 | impl<T> ops::IndexMut<ops::RangeToInclusive<usize>> for [T] { | |
730 | #[inline] | |
731 | fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut [T] { | |
732 | self.index_mut(0...index.end) | |
733 | } | |
734 | } | |
1a4d82fc JJ |
735 | |
736 | //////////////////////////////////////////////////////////////////////////////// | |
737 | // Common traits | |
738 | //////////////////////////////////////////////////////////////////////////////// | |
739 | ||
85aaf69f | 740 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 741 | impl<'a, T> Default for &'a [T] { |
1a4d82fc JJ |
742 | fn default() -> &'a [T] { &[] } |
743 | } | |
744 | ||
b039eaaf SL |
745 | #[stable(feature = "mut_slice_default", since = "1.5.0")] |
746 | impl<'a, T> Default for &'a mut [T] { | |
747 | fn default() -> &'a mut [T] { &mut [] } | |
748 | } | |
749 | ||
1a4d82fc JJ |
750 | // |
751 | // Iterators | |
752 | // | |
753 | ||
85aaf69f SL |
754 | #[stable(feature = "rust1", since = "1.0.0")] |
755 | impl<'a, T> IntoIterator for &'a [T] { | |
756 | type Item = &'a T; | |
757 | type IntoIter = Iter<'a, T>; | |
758 | ||
759 | fn into_iter(self) -> Iter<'a, T> { | |
760 | self.iter() | |
761 | } | |
762 | } | |
763 | ||
764 | #[stable(feature = "rust1", since = "1.0.0")] | |
765 | impl<'a, T> IntoIterator for &'a mut [T] { | |
766 | type Item = &'a mut T; | |
767 | type IntoIter = IterMut<'a, T>; | |
768 | ||
769 | fn into_iter(self) -> IterMut<'a, T> { | |
770 | self.iter_mut() | |
771 | } | |
772 | } | |
773 | ||
d9579d0f AL |
774 | #[inline(always)] |
775 | fn size_from_ptr<T>(_: *const T) -> usize { | |
776 | mem::size_of::<T>() | |
777 | } | |
778 | ||
1a4d82fc JJ |
779 | // The shared definition of the `Iter` and `IterMut` iterators |
780 | macro_rules! iterator { | |
781 | (struct $name:ident -> $ptr:ty, $elem:ty) => { | |
85aaf69f | 782 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
783 | impl<'a, T> Iterator for $name<'a, T> { |
784 | type Item = $elem; | |
785 | ||
786 | #[inline] | |
787 | fn next(&mut self) -> Option<$elem> { | |
788 | // could be implemented with slices, but this avoids bounds checks | |
789 | unsafe { | |
d9579d0f AL |
790 | if mem::size_of::<T>() != 0 { |
791 | assume(!self.ptr.is_null()); | |
792 | assume(!self.end.is_null()); | |
793 | } | |
1a4d82fc JJ |
794 | if self.ptr == self.end { |
795 | None | |
796 | } else { | |
d9579d0f AL |
797 | let old = self.ptr; |
798 | self.ptr = slice_offset!(self.ptr, 1); | |
799 | Some(slice_ref!(old)) | |
1a4d82fc JJ |
800 | } |
801 | } | |
802 | } | |
803 | ||
804 | #[inline] | |
85aaf69f | 805 | fn size_hint(&self) -> (usize, Option<usize>) { |
d9579d0f | 806 | let diff = (self.end as usize).wrapping_sub(self.ptr as usize); |
1a4d82fc JJ |
807 | let size = mem::size_of::<T>(); |
808 | let exact = diff / (if size == 0 {1} else {size}); | |
809 | (exact, Some(exact)) | |
810 | } | |
d9579d0f AL |
811 | |
812 | #[inline] | |
813 | fn count(self) -> usize { | |
814 | self.size_hint().0 | |
815 | } | |
816 | ||
817 | #[inline] | |
818 | fn nth(&mut self, n: usize) -> Option<$elem> { | |
819 | // Call helper method. Can't put the definition here because mut versus const. | |
820 | self.iter_nth(n) | |
821 | } | |
822 | ||
823 | #[inline] | |
824 | fn last(mut self) -> Option<$elem> { | |
825 | self.next_back() | |
826 | } | |
1a4d82fc JJ |
827 | } |
828 | ||
85aaf69f | 829 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
830 | impl<'a, T> DoubleEndedIterator for $name<'a, T> { |
831 | #[inline] | |
832 | fn next_back(&mut self) -> Option<$elem> { | |
833 | // could be implemented with slices, but this avoids bounds checks | |
834 | unsafe { | |
d9579d0f AL |
835 | if mem::size_of::<T>() != 0 { |
836 | assume(!self.ptr.is_null()); | |
837 | assume(!self.end.is_null()); | |
838 | } | |
1a4d82fc JJ |
839 | if self.end == self.ptr { |
840 | None | |
841 | } else { | |
d9579d0f AL |
842 | self.end = slice_offset!(self.end, -1); |
843 | Some(slice_ref!(self.end)) | |
1a4d82fc JJ |
844 | } |
845 | } | |
846 | } | |
847 | } | |
848 | } | |
849 | } | |
850 | ||
851 | macro_rules! make_slice { | |
d9579d0f AL |
852 | ($start: expr, $end: expr) => {{ |
853 | let start = $start; | |
854 | let diff = ($end as usize).wrapping_sub(start as usize); | |
855 | if size_from_ptr(start) == 0 { | |
856 | // use a non-null pointer value | |
857 | unsafe { from_raw_parts(1 as *const _, diff) } | |
1a4d82fc | 858 | } else { |
d9579d0f AL |
859 | let len = diff / size_from_ptr(start); |
860 | unsafe { from_raw_parts(start, len) } | |
c34b1796 AL |
861 | } |
862 | }} | |
863 | } | |
864 | ||
865 | macro_rules! make_mut_slice { | |
d9579d0f AL |
866 | ($start: expr, $end: expr) => {{ |
867 | let start = $start; | |
868 | let diff = ($end as usize).wrapping_sub(start as usize); | |
869 | if size_from_ptr(start) == 0 { | |
870 | // use a non-null pointer value | |
871 | unsafe { from_raw_parts_mut(1 as *mut _, diff) } | |
c34b1796 | 872 | } else { |
d9579d0f AL |
873 | let len = diff / size_from_ptr(start); |
874 | unsafe { from_raw_parts_mut(start, len) } | |
1a4d82fc JJ |
875 | } |
876 | }} | |
877 | } | |
878 | ||
879 | /// Immutable slice iterator | |
85aaf69f | 880 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
881 | pub struct Iter<'a, T: 'a> { |
882 | ptr: *const T, | |
883 | end: *const T, | |
85aaf69f | 884 | _marker: marker::PhantomData<&'a T>, |
1a4d82fc JJ |
885 | } |
886 | ||
54a0048b SL |
887 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
888 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> { | |
889 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
890 | f.debug_tuple("Iter") | |
891 | .field(&self.as_slice()) | |
892 | .finish() | |
893 | } | |
894 | } | |
895 | ||
92a42be0 | 896 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 897 | unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {} |
92a42be0 | 898 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
899 | unsafe impl<'a, T: Sync> Send for Iter<'a, T> {} |
900 | ||
1a4d82fc JJ |
901 | impl<'a, T> Iter<'a, T> { |
902 | /// View the underlying data as a subslice of the original data. | |
903 | /// | |
904 | /// This has the same lifetime as the original slice, and so the | |
905 | /// iterator can continue to be used while this exists. | |
e9174d1e | 906 | #[stable(feature = "iter_to_slice", since = "1.4.0")] |
1a4d82fc | 907 | pub fn as_slice(&self) -> &'a [T] { |
d9579d0f AL |
908 | make_slice!(self.ptr, self.end) |
909 | } | |
910 | ||
911 | // Helper function for Iter::nth | |
912 | fn iter_nth(&mut self, n: usize) -> Option<&'a T> { | |
913 | match self.as_slice().get(n) { | |
914 | Some(elem_ref) => unsafe { | |
915 | self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1)); | |
62682a34 | 916 | Some(elem_ref) |
d9579d0f AL |
917 | }, |
918 | None => { | |
919 | self.ptr = self.end; | |
920 | None | |
921 | } | |
922 | } | |
1a4d82fc JJ |
923 | } |
924 | } | |
925 | ||
1a4d82fc JJ |
926 | iterator!{struct Iter -> *const T, &'a T} |
927 | ||
85aaf69f | 928 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
929 | impl<'a, T> ExactSizeIterator for Iter<'a, T> {} |
930 | ||
85aaf69f | 931 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 932 | impl<'a, T> Clone for Iter<'a, T> { |
85aaf69f | 933 | fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } } |
1a4d82fc JJ |
934 | } |
935 | ||
1a4d82fc | 936 | /// Mutable slice iterator. |
85aaf69f | 937 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
938 | pub struct IterMut<'a, T: 'a> { |
939 | ptr: *mut T, | |
940 | end: *mut T, | |
85aaf69f | 941 | _marker: marker::PhantomData<&'a mut T>, |
1a4d82fc JJ |
942 | } |
943 | ||
54a0048b SL |
944 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
945 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> { | |
946 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
947 | f.debug_tuple("IterMut") | |
948 | .field(&make_slice!(self.ptr, self.end)) | |
949 | .finish() | |
950 | } | |
951 | } | |
952 | ||
92a42be0 | 953 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 954 | unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {} |
92a42be0 | 955 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 956 | unsafe impl<'a, T: Send> Send for IterMut<'a, T> {} |
1a4d82fc | 957 | |
1a4d82fc JJ |
958 | impl<'a, T> IterMut<'a, T> { |
959 | /// View the underlying data as a subslice of the original data. | |
960 | /// | |
961 | /// To avoid creating `&mut` references that alias, this is forced | |
962 | /// to consume the iterator. Consider using the `Slice` and | |
963 | /// `SliceMut` implementations for obtaining slices with more | |
964 | /// restricted lifetimes that do not consume the iterator. | |
e9174d1e | 965 | #[stable(feature = "iter_to_slice", since = "1.4.0")] |
1a4d82fc | 966 | pub fn into_slice(self) -> &'a mut [T] { |
d9579d0f AL |
967 | make_mut_slice!(self.ptr, self.end) |
968 | } | |
969 | ||
970 | // Helper function for IterMut::nth | |
971 | fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> { | |
972 | match make_mut_slice!(self.ptr, self.end).get_mut(n) { | |
973 | Some(elem_ref) => unsafe { | |
974 | self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1)); | |
62682a34 | 975 | Some(elem_ref) |
d9579d0f AL |
976 | }, |
977 | None => { | |
978 | self.ptr = self.end; | |
979 | None | |
980 | } | |
981 | } | |
1a4d82fc JJ |
982 | } |
983 | } | |
984 | ||
985 | iterator!{struct IterMut -> *mut T, &'a mut T} | |
986 | ||
85aaf69f | 987 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
988 | impl<'a, T> ExactSizeIterator for IterMut<'a, T> {} |
989 | ||
990 | /// An internal abstraction over the splitting iterators, so that | |
991 | /// splitn, splitn_mut etc can be implemented once. | |
54a0048b | 992 | #[doc(hidden)] |
1a4d82fc JJ |
993 | trait SplitIter: DoubleEndedIterator { |
994 | /// Mark the underlying iterator as complete, extracting the remaining | |
995 | /// portion of the slice. | |
996 | fn finish(&mut self) -> Option<Self::Item>; | |
997 | } | |
998 | ||
999 | /// An iterator over subslices separated by elements that match a predicate | |
1000 | /// function. | |
85aaf69f | 1001 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1002 | pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool { |
1003 | v: &'a [T], | |
1004 | pred: P, | |
1005 | finished: bool | |
1006 | } | |
1007 | ||
54a0048b SL |
1008 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1009 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for Split<'a, T, P> where P: FnMut(&T) -> bool { | |
1010 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1011 | f.debug_struct("Split") | |
1012 | .field("v", &self.v) | |
1013 | .field("finished", &self.finished) | |
1014 | .finish() | |
1015 | } | |
1016 | } | |
1017 | ||
1a4d82fc | 1018 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` |
85aaf69f | 1019 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1020 | impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool { |
1021 | fn clone(&self) -> Split<'a, T, P> { | |
1022 | Split { | |
1023 | v: self.v, | |
1024 | pred: self.pred.clone(), | |
1025 | finished: self.finished, | |
1026 | } | |
1027 | } | |
1028 | } | |
1029 | ||
85aaf69f | 1030 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1031 | impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool { |
1032 | type Item = &'a [T]; | |
1033 | ||
1034 | #[inline] | |
1035 | fn next(&mut self) -> Option<&'a [T]> { | |
1036 | if self.finished { return None; } | |
1037 | ||
1038 | match self.v.iter().position(|x| (self.pred)(x)) { | |
1039 | None => self.finish(), | |
1040 | Some(idx) => { | |
85aaf69f SL |
1041 | let ret = Some(&self.v[..idx]); |
1042 | self.v = &self.v[idx + 1..]; | |
1a4d82fc JJ |
1043 | ret |
1044 | } | |
1045 | } | |
1046 | } | |
1047 | ||
1048 | #[inline] | |
85aaf69f | 1049 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1050 | if self.finished { |
1051 | (0, Some(0)) | |
1052 | } else { | |
1053 | (1, Some(self.v.len() + 1)) | |
1054 | } | |
1055 | } | |
1056 | } | |
1057 | ||
85aaf69f | 1058 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1059 | impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool { |
1060 | #[inline] | |
1061 | fn next_back(&mut self) -> Option<&'a [T]> { | |
1062 | if self.finished { return None; } | |
1063 | ||
1064 | match self.v.iter().rposition(|x| (self.pred)(x)) { | |
1065 | None => self.finish(), | |
1066 | Some(idx) => { | |
85aaf69f SL |
1067 | let ret = Some(&self.v[idx + 1..]); |
1068 | self.v = &self.v[..idx]; | |
1a4d82fc JJ |
1069 | ret |
1070 | } | |
1071 | } | |
1072 | } | |
1073 | } | |
1074 | ||
1075 | impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool { | |
1076 | #[inline] | |
1077 | fn finish(&mut self) -> Option<&'a [T]> { | |
1078 | if self.finished { None } else { self.finished = true; Some(self.v) } | |
1079 | } | |
1080 | } | |
1081 | ||
1082 | /// An iterator over the subslices of the vector which are separated | |
1083 | /// by elements that match `pred`. | |
85aaf69f | 1084 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1085 | pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool { |
1086 | v: &'a mut [T], | |
1087 | pred: P, | |
1088 | finished: bool | |
1089 | } | |
1090 | ||
54a0048b SL |
1091 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1092 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { | |
1093 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1094 | f.debug_struct("SplitMut") | |
1095 | .field("v", &self.v) | |
1096 | .field("finished", &self.finished) | |
1097 | .finish() | |
1098 | } | |
1099 | } | |
1100 | ||
1a4d82fc JJ |
1101 | impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { |
1102 | #[inline] | |
1103 | fn finish(&mut self) -> Option<&'a mut [T]> { | |
1104 | if self.finished { | |
1105 | None | |
1106 | } else { | |
1107 | self.finished = true; | |
1108 | Some(mem::replace(&mut self.v, &mut [])) | |
1109 | } | |
1110 | } | |
1111 | } | |
1112 | ||
85aaf69f | 1113 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1114 | impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool { |
1115 | type Item = &'a mut [T]; | |
1116 | ||
1117 | #[inline] | |
1118 | fn next(&mut self) -> Option<&'a mut [T]> { | |
1119 | if self.finished { return None; } | |
1120 | ||
1121 | let idx_opt = { // work around borrowck limitations | |
1122 | let pred = &mut self.pred; | |
1123 | self.v.iter().position(|x| (*pred)(x)) | |
1124 | }; | |
1125 | match idx_opt { | |
1126 | None => self.finish(), | |
1127 | Some(idx) => { | |
1128 | let tmp = mem::replace(&mut self.v, &mut []); | |
1129 | let (head, tail) = tmp.split_at_mut(idx); | |
85aaf69f | 1130 | self.v = &mut tail[1..]; |
1a4d82fc JJ |
1131 | Some(head) |
1132 | } | |
1133 | } | |
1134 | } | |
1135 | ||
1136 | #[inline] | |
85aaf69f | 1137 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1138 | if self.finished { |
1139 | (0, Some(0)) | |
1140 | } else { | |
1141 | // if the predicate doesn't match anything, we yield one slice | |
1142 | // if it matches every element, we yield len+1 empty slices. | |
1143 | (1, Some(self.v.len() + 1)) | |
1144 | } | |
1145 | } | |
1146 | } | |
1147 | ||
85aaf69f | 1148 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1149 | impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where |
1150 | P: FnMut(&T) -> bool, | |
1151 | { | |
1152 | #[inline] | |
1153 | fn next_back(&mut self) -> Option<&'a mut [T]> { | |
1154 | if self.finished { return None; } | |
1155 | ||
1156 | let idx_opt = { // work around borrowck limitations | |
1157 | let pred = &mut self.pred; | |
1158 | self.v.iter().rposition(|x| (*pred)(x)) | |
1159 | }; | |
1160 | match idx_opt { | |
1161 | None => self.finish(), | |
1162 | Some(idx) => { | |
1163 | let tmp = mem::replace(&mut self.v, &mut []); | |
1164 | let (head, tail) = tmp.split_at_mut(idx); | |
1165 | self.v = head; | |
85aaf69f | 1166 | Some(&mut tail[1..]) |
1a4d82fc JJ |
1167 | } |
1168 | } | |
1169 | } | |
1170 | } | |
1171 | ||
1172 | /// An private iterator over subslices separated by elements that | |
1173 | /// match a predicate function, splitting at most a fixed number of | |
1174 | /// times. | |
54a0048b | 1175 | #[derive(Debug)] |
1a4d82fc JJ |
1176 | struct GenericSplitN<I> { |
1177 | iter: I, | |
85aaf69f | 1178 | count: usize, |
1a4d82fc JJ |
1179 | invert: bool |
1180 | } | |
1181 | ||
1182 | impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> { | |
1183 | type Item = T; | |
1184 | ||
1185 | #[inline] | |
1186 | fn next(&mut self) -> Option<T> { | |
c34b1796 AL |
1187 | match self.count { |
1188 | 0 => None, | |
1189 | 1 => { self.count -= 1; self.iter.finish() } | |
1190 | _ => { | |
1191 | self.count -= 1; | |
1192 | if self.invert {self.iter.next_back()} else {self.iter.next()} | |
1193 | } | |
1a4d82fc JJ |
1194 | } |
1195 | } | |
1196 | ||
1197 | #[inline] | |
85aaf69f | 1198 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc | 1199 | let (lower, upper_opt) = self.iter.size_hint(); |
c34b1796 | 1200 | (lower, upper_opt.map(|upper| cmp::min(self.count, upper))) |
1a4d82fc JJ |
1201 | } |
1202 | } | |
1203 | ||
1204 | /// An iterator over subslices separated by elements that match a predicate | |
1205 | /// function, limited to a given number of splits. | |
85aaf69f | 1206 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1207 | pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1208 | inner: GenericSplitN<Split<'a, T, P>> | |
1209 | } | |
1210 | ||
54a0048b SL |
1211 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1212 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitN<'a, T, P> where P: FnMut(&T) -> bool { | |
1213 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1214 | f.debug_struct("SplitN") | |
1215 | .field("inner", &self.inner) | |
1216 | .finish() | |
1217 | } | |
1218 | } | |
1219 | ||
1a4d82fc JJ |
1220 | /// An iterator over subslices separated by elements that match a |
1221 | /// predicate function, limited to a given number of splits, starting | |
1222 | /// from the end of the slice. | |
85aaf69f | 1223 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1224 | pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1225 | inner: GenericSplitN<Split<'a, T, P>> | |
1226 | } | |
1227 | ||
54a0048b SL |
1228 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1229 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitN<'a, T, P> where P: FnMut(&T) -> bool { | |
1230 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1231 | f.debug_struct("RSplitN") | |
1232 | .field("inner", &self.inner) | |
1233 | .finish() | |
1234 | } | |
1235 | } | |
1236 | ||
1a4d82fc JJ |
1237 | /// An iterator over subslices separated by elements that match a predicate |
1238 | /// function, limited to a given number of splits. | |
85aaf69f | 1239 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1240 | pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1241 | inner: GenericSplitN<SplitMut<'a, T, P>> | |
1242 | } | |
1243 | ||
54a0048b SL |
1244 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1245 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitNMut<'a, T, P> where P: FnMut(&T) -> bool { | |
1246 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1247 | f.debug_struct("SplitNMut") | |
1248 | .field("inner", &self.inner) | |
1249 | .finish() | |
1250 | } | |
1251 | } | |
1252 | ||
1a4d82fc JJ |
1253 | /// An iterator over subslices separated by elements that match a |
1254 | /// predicate function, limited to a given number of splits, starting | |
1255 | /// from the end of the slice. | |
85aaf69f | 1256 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1257 | pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool { |
1258 | inner: GenericSplitN<SplitMut<'a, T, P>> | |
1259 | } | |
1260 | ||
54a0048b SL |
1261 | #[stable(feature = "core_impl_debug", since = "1.9.0")] |
1262 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitNMut<'a, T, P> where P: FnMut(&T) -> bool { | |
1263 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
1264 | f.debug_struct("RSplitNMut") | |
1265 | .field("inner", &self.inner) | |
1266 | .finish() | |
1267 | } | |
1268 | } | |
1269 | ||
1a4d82fc JJ |
1270 | macro_rules! forward_iterator { |
1271 | ($name:ident: $elem:ident, $iter_of:ty) => { | |
85aaf69f | 1272 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1273 | impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where |
1274 | P: FnMut(&T) -> bool | |
1275 | { | |
1276 | type Item = $iter_of; | |
1277 | ||
1278 | #[inline] | |
1279 | fn next(&mut self) -> Option<$iter_of> { | |
1280 | self.inner.next() | |
1281 | } | |
1282 | ||
1283 | #[inline] | |
85aaf69f | 1284 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1285 | self.inner.size_hint() |
1286 | } | |
1287 | } | |
1288 | } | |
1289 | } | |
1290 | ||
1291 | forward_iterator! { SplitN: T, &'a [T] } | |
1292 | forward_iterator! { RSplitN: T, &'a [T] } | |
1293 | forward_iterator! { SplitNMut: T, &'a mut [T] } | |
1294 | forward_iterator! { RSplitNMut: T, &'a mut [T] } | |
1295 | ||
1296 | /// An iterator over overlapping subslices of length `size`. | |
54a0048b | 1297 | #[derive(Debug)] |
85aaf69f | 1298 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1299 | pub struct Windows<'a, T:'a> { |
1300 | v: &'a [T], | |
85aaf69f | 1301 | size: usize |
1a4d82fc JJ |
1302 | } |
1303 | ||
c34b1796 AL |
1304 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` |
1305 | #[stable(feature = "rust1", since = "1.0.0")] | |
1306 | impl<'a, T> Clone for Windows<'a, T> { | |
1307 | fn clone(&self) -> Windows<'a, T> { | |
1308 | Windows { | |
1309 | v: self.v, | |
1310 | size: self.size, | |
1311 | } | |
1312 | } | |
1313 | } | |
1314 | ||
85aaf69f | 1315 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1316 | impl<'a, T> Iterator for Windows<'a, T> { |
1317 | type Item = &'a [T]; | |
1318 | ||
1319 | #[inline] | |
1320 | fn next(&mut self) -> Option<&'a [T]> { | |
1321 | if self.size > self.v.len() { | |
1322 | None | |
1323 | } else { | |
85aaf69f | 1324 | let ret = Some(&self.v[..self.size]); |
1a4d82fc JJ |
1325 | self.v = &self.v[1..]; |
1326 | ret | |
1327 | } | |
1328 | } | |
1329 | ||
1330 | #[inline] | |
85aaf69f | 1331 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1332 | if self.size > self.v.len() { |
1333 | (0, Some(0)) | |
1334 | } else { | |
85aaf69f SL |
1335 | let size = self.v.len() - self.size + 1; |
1336 | (size, Some(size)) | |
1337 | } | |
1338 | } | |
e9174d1e SL |
1339 | |
1340 | #[inline] | |
1341 | fn count(self) -> usize { | |
1342 | self.size_hint().0 | |
1343 | } | |
1344 | ||
1345 | #[inline] | |
1346 | fn nth(&mut self, n: usize) -> Option<Self::Item> { | |
1347 | let (end, overflow) = self.size.overflowing_add(n); | |
1348 | if end > self.v.len() || overflow { | |
1349 | self.v = &[]; | |
1350 | None | |
1351 | } else { | |
1352 | let nth = &self.v[n..end]; | |
1353 | self.v = &self.v[n+1..]; | |
1354 | Some(nth) | |
1355 | } | |
1356 | } | |
1357 | ||
1358 | #[inline] | |
1359 | fn last(self) -> Option<Self::Item> { | |
1360 | if self.size > self.v.len() { | |
1361 | None | |
1362 | } else { | |
1363 | let start = self.v.len() - self.size; | |
1364 | Some(&self.v[start..]) | |
1365 | } | |
1366 | } | |
85aaf69f SL |
1367 | } |
1368 | ||
1369 | #[stable(feature = "rust1", since = "1.0.0")] | |
1370 | impl<'a, T> DoubleEndedIterator for Windows<'a, T> { | |
1371 | #[inline] | |
1372 | fn next_back(&mut self) -> Option<&'a [T]> { | |
1373 | if self.size > self.v.len() { | |
1374 | None | |
1375 | } else { | |
1376 | let ret = Some(&self.v[self.v.len()-self.size..]); | |
1377 | self.v = &self.v[..self.v.len()-1]; | |
1378 | ret | |
1379 | } | |
1380 | } | |
1381 | } | |
1382 | ||
1383 | #[stable(feature = "rust1", since = "1.0.0")] | |
1384 | impl<'a, T> ExactSizeIterator for Windows<'a, T> {} | |
1385 | ||
1a4d82fc JJ |
1386 | /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a |
1387 | /// time). | |
1388 | /// | |
1389 | /// When the slice len is not evenly divided by the chunk size, the last slice | |
1390 | /// of the iteration will be the remainder. | |
54a0048b | 1391 | #[derive(Debug)] |
85aaf69f | 1392 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1393 | pub struct Chunks<'a, T:'a> { |
1394 | v: &'a [T], | |
85aaf69f | 1395 | size: usize |
1a4d82fc JJ |
1396 | } |
1397 | ||
c34b1796 AL |
1398 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` |
1399 | #[stable(feature = "rust1", since = "1.0.0")] | |
1400 | impl<'a, T> Clone for Chunks<'a, T> { | |
1401 | fn clone(&self) -> Chunks<'a, T> { | |
1402 | Chunks { | |
1403 | v: self.v, | |
1404 | size: self.size, | |
1405 | } | |
1406 | } | |
1407 | } | |
1408 | ||
85aaf69f | 1409 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1410 | impl<'a, T> Iterator for Chunks<'a, T> { |
1411 | type Item = &'a [T]; | |
1412 | ||
1413 | #[inline] | |
1414 | fn next(&mut self) -> Option<&'a [T]> { | |
9346a6ac | 1415 | if self.v.is_empty() { |
1a4d82fc JJ |
1416 | None |
1417 | } else { | |
1418 | let chunksz = cmp::min(self.v.len(), self.size); | |
1419 | let (fst, snd) = self.v.split_at(chunksz); | |
1420 | self.v = snd; | |
1421 | Some(fst) | |
1422 | } | |
1423 | } | |
1424 | ||
1425 | #[inline] | |
85aaf69f | 1426 | fn size_hint(&self) -> (usize, Option<usize>) { |
9346a6ac | 1427 | if self.v.is_empty() { |
1a4d82fc JJ |
1428 | (0, Some(0)) |
1429 | } else { | |
1430 | let n = self.v.len() / self.size; | |
1431 | let rem = self.v.len() % self.size; | |
1432 | let n = if rem > 0 { n+1 } else { n }; | |
1433 | (n, Some(n)) | |
1434 | } | |
1435 | } | |
e9174d1e SL |
1436 | |
1437 | #[inline] | |
1438 | fn count(self) -> usize { | |
1439 | self.size_hint().0 | |
1440 | } | |
1441 | ||
1442 | #[inline] | |
1443 | fn nth(&mut self, n: usize) -> Option<Self::Item> { | |
1444 | let (start, overflow) = n.overflowing_mul(self.size); | |
1445 | if start >= self.v.len() || overflow { | |
1446 | self.v = &[]; | |
1447 | None | |
1448 | } else { | |
1449 | let end = match start.checked_add(self.size) { | |
1450 | Some(sum) => cmp::min(self.v.len(), sum), | |
1451 | None => self.v.len(), | |
1452 | }; | |
1453 | let nth = &self.v[start..end]; | |
1454 | self.v = &self.v[end..]; | |
1455 | Some(nth) | |
1456 | } | |
1457 | } | |
1458 | ||
1459 | #[inline] | |
1460 | fn last(self) -> Option<Self::Item> { | |
1461 | if self.v.is_empty() { | |
1462 | None | |
1463 | } else { | |
1464 | let start = (self.v.len() - 1) / self.size * self.size; | |
1465 | Some(&self.v[start..]) | |
1466 | } | |
1467 | } | |
1a4d82fc JJ |
1468 | } |
1469 | ||
85aaf69f | 1470 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1471 | impl<'a, T> DoubleEndedIterator for Chunks<'a, T> { |
1472 | #[inline] | |
1473 | fn next_back(&mut self) -> Option<&'a [T]> { | |
9346a6ac | 1474 | if self.v.is_empty() { |
1a4d82fc JJ |
1475 | None |
1476 | } else { | |
1477 | let remainder = self.v.len() % self.size; | |
1478 | let chunksz = if remainder != 0 { remainder } else { self.size }; | |
1479 | let (fst, snd) = self.v.split_at(self.v.len() - chunksz); | |
1480 | self.v = fst; | |
1481 | Some(snd) | |
1482 | } | |
1483 | } | |
1484 | } | |
1485 | ||
85aaf69f SL |
1486 | #[stable(feature = "rust1", since = "1.0.0")] |
1487 | impl<'a, T> ExactSizeIterator for Chunks<'a, T> {} | |
1488 | ||
1a4d82fc JJ |
1489 | /// An iterator over a slice in (non-overlapping) mutable chunks (`size` |
1490 | /// elements at a time). When the slice len is not evenly divided by the chunk | |
1491 | /// size, the last slice of the iteration will be the remainder. | |
54a0048b | 1492 | #[derive(Debug)] |
85aaf69f | 1493 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1494 | pub struct ChunksMut<'a, T:'a> { |
1495 | v: &'a mut [T], | |
85aaf69f | 1496 | chunk_size: usize |
1a4d82fc JJ |
1497 | } |
1498 | ||
85aaf69f | 1499 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1500 | impl<'a, T> Iterator for ChunksMut<'a, T> { |
1501 | type Item = &'a mut [T]; | |
1502 | ||
1503 | #[inline] | |
1504 | fn next(&mut self) -> Option<&'a mut [T]> { | |
9346a6ac | 1505 | if self.v.is_empty() { |
1a4d82fc JJ |
1506 | None |
1507 | } else { | |
1508 | let sz = cmp::min(self.v.len(), self.chunk_size); | |
1509 | let tmp = mem::replace(&mut self.v, &mut []); | |
1510 | let (head, tail) = tmp.split_at_mut(sz); | |
1511 | self.v = tail; | |
1512 | Some(head) | |
1513 | } | |
1514 | } | |
1515 | ||
1516 | #[inline] | |
85aaf69f | 1517 | fn size_hint(&self) -> (usize, Option<usize>) { |
9346a6ac | 1518 | if self.v.is_empty() { |
1a4d82fc JJ |
1519 | (0, Some(0)) |
1520 | } else { | |
1521 | let n = self.v.len() / self.chunk_size; | |
1522 | let rem = self.v.len() % self.chunk_size; | |
1523 | let n = if rem > 0 { n + 1 } else { n }; | |
1524 | (n, Some(n)) | |
1525 | } | |
1526 | } | |
e9174d1e SL |
1527 | |
1528 | #[inline] | |
1529 | fn count(self) -> usize { | |
1530 | self.size_hint().0 | |
1531 | } | |
1532 | ||
1533 | #[inline] | |
1534 | fn nth(&mut self, n: usize) -> Option<&'a mut [T]> { | |
1535 | let (start, overflow) = n.overflowing_mul(self.chunk_size); | |
1536 | if start >= self.v.len() || overflow { | |
1537 | self.v = &mut []; | |
1538 | None | |
1539 | } else { | |
1540 | let end = match start.checked_add(self.chunk_size) { | |
1541 | Some(sum) => cmp::min(self.v.len(), sum), | |
1542 | None => self.v.len(), | |
1543 | }; | |
1544 | let tmp = mem::replace(&mut self.v, &mut []); | |
1545 | let (head, tail) = tmp.split_at_mut(end); | |
1546 | let (_, nth) = head.split_at_mut(start); | |
1547 | self.v = tail; | |
1548 | Some(nth) | |
1549 | } | |
1550 | } | |
1551 | ||
1552 | #[inline] | |
1553 | fn last(self) -> Option<Self::Item> { | |
1554 | if self.v.is_empty() { | |
1555 | None | |
1556 | } else { | |
1557 | let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size; | |
1558 | Some(&mut self.v[start..]) | |
1559 | } | |
1560 | } | |
1a4d82fc JJ |
1561 | } |
1562 | ||
85aaf69f | 1563 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1564 | impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> { |
1565 | #[inline] | |
1566 | fn next_back(&mut self) -> Option<&'a mut [T]> { | |
9346a6ac | 1567 | if self.v.is_empty() { |
1a4d82fc JJ |
1568 | None |
1569 | } else { | |
1570 | let remainder = self.v.len() % self.chunk_size; | |
1571 | let sz = if remainder != 0 { remainder } else { self.chunk_size }; | |
1572 | let tmp = mem::replace(&mut self.v, &mut []); | |
1573 | let tmp_len = tmp.len(); | |
1574 | let (head, tail) = tmp.split_at_mut(tmp_len - sz); | |
1575 | self.v = head; | |
1576 | Some(tail) | |
1577 | } | |
1578 | } | |
1579 | } | |
1580 | ||
85aaf69f SL |
1581 | #[stable(feature = "rust1", since = "1.0.0")] |
1582 | impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {} | |
1a4d82fc JJ |
1583 | |
1584 | // | |
1585 | // Free functions | |
1586 | // | |
1587 | ||
85aaf69f SL |
1588 | /// Forms a slice from a pointer and a length. |
1589 | /// | |
1590 | /// The `len` argument is the number of **elements**, not the number of bytes. | |
1591 | /// | |
b039eaaf | 1592 | /// # Safety |
c1a9b12d | 1593 | /// |
85aaf69f SL |
1594 | /// This function is unsafe as there is no guarantee that the given pointer is |
1595 | /// valid for `len` elements, nor whether the lifetime inferred is a suitable | |
1596 | /// lifetime for the returned slice. | |
1597 | /// | |
c1a9b12d SL |
1598 | /// `p` must be non-null, even for zero-length slices. |
1599 | /// | |
85aaf69f SL |
1600 | /// # Caveat |
1601 | /// | |
1602 | /// The lifetime for the returned slice is inferred from its usage. To | |
1603 | /// prevent accidental misuse, it's suggested to tie the lifetime to whichever | |
1604 | /// source lifetime is safe in the context, such as by providing a helper | |
1605 | /// function taking the lifetime of a host value for the slice, or by explicit | |
1606 | /// annotation. | |
1607 | /// | |
c34b1796 | 1608 | /// # Examples |
85aaf69f | 1609 | /// |
c34b1796 | 1610 | /// ``` |
85aaf69f SL |
1611 | /// use std::slice; |
1612 | /// | |
1613 | /// // manifest a slice out of thin air! | |
1614 | /// let ptr = 0x1234 as *const usize; | |
1615 | /// let amt = 10; | |
1616 | /// unsafe { | |
1617 | /// let slice = slice::from_raw_parts(ptr, amt); | |
1618 | /// } | |
1619 | /// ``` | |
1620 | #[inline] | |
c34b1796 | 1621 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f | 1622 | pub unsafe fn from_raw_parts<'a, T>(p: *const T, len: usize) -> &'a [T] { |
54a0048b | 1623 | mem::transmute(Repr { data: p, len: len }) |
85aaf69f SL |
1624 | } |
1625 | ||
1626 | /// Performs the same functionality as `from_raw_parts`, except that a mutable | |
1627 | /// slice is returned. | |
1628 | /// | |
1629 | /// This function is unsafe for the same reasons as `from_raw_parts`, as well | |
1630 | /// as not being able to provide a non-aliasing guarantee of the returned | |
1631 | /// mutable slice. | |
1632 | #[inline] | |
c34b1796 | 1633 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f | 1634 | pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] { |
54a0048b | 1635 | mem::transmute(Repr { data: p, len: len }) |
85aaf69f SL |
1636 | } |
1637 | ||
1a4d82fc | 1638 | // |
54a0048b | 1639 | // Comparison traits |
1a4d82fc JJ |
1640 | // |
1641 | ||
54a0048b SL |
1642 | extern { |
1643 | /// Call implementation provided memcmp | |
1644 | /// | |
1645 | /// Interprets the data as u8. | |
1646 | /// | |
1647 | /// Return 0 for equal, < 0 for less than and > 0 for greater | |
1648 | /// than. | |
1649 | // FIXME(#32610): Return type should be c_int | |
1650 | fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32; | |
1651 | } | |
1a4d82fc | 1652 | |
54a0048b SL |
1653 | #[stable(feature = "rust1", since = "1.0.0")] |
1654 | impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> { | |
1655 | fn eq(&self, other: &[B]) -> bool { | |
1656 | SlicePartialEq::equal(self, other) | |
1a4d82fc JJ |
1657 | } |
1658 | ||
54a0048b SL |
1659 | fn ne(&self, other: &[B]) -> bool { |
1660 | SlicePartialEq::not_equal(self, other) | |
1a4d82fc | 1661 | } |
54a0048b | 1662 | } |
1a4d82fc | 1663 | |
54a0048b SL |
1664 | #[stable(feature = "rust1", since = "1.0.0")] |
1665 | impl<T: Eq> Eq for [T] {} | |
1666 | ||
1667 | #[stable(feature = "rust1", since = "1.0.0")] | |
1668 | impl<T: Ord> Ord for [T] { | |
1669 | fn cmp(&self, other: &[T]) -> Ordering { | |
1670 | SliceOrd::compare(self, other) | |
1a4d82fc JJ |
1671 | } |
1672 | } | |
1673 | ||
54a0048b SL |
1674 | #[stable(feature = "rust1", since = "1.0.0")] |
1675 | impl<T: PartialOrd> PartialOrd for [T] { | |
1676 | fn partial_cmp(&self, other: &[T]) -> Option<Ordering> { | |
1677 | SlicePartialOrd::partial_compare(self, other) | |
1678 | } | |
1679 | } | |
1a4d82fc | 1680 | |
54a0048b SL |
1681 | #[doc(hidden)] |
1682 | // intermediate trait for specialization of slice's PartialEq | |
1683 | trait SlicePartialEq<B> { | |
1684 | fn equal(&self, other: &[B]) -> bool; | |
1685 | fn not_equal(&self, other: &[B]) -> bool; | |
1686 | } | |
1a4d82fc | 1687 | |
54a0048b SL |
1688 | // Generic slice equality |
1689 | impl<A, B> SlicePartialEq<B> for [A] | |
1690 | where A: PartialEq<B> | |
1691 | { | |
1692 | default fn equal(&self, other: &[B]) -> bool { | |
c1a9b12d SL |
1693 | if self.len() != other.len() { |
1694 | return false; | |
1695 | } | |
1696 | ||
1697 | for i in 0..self.len() { | |
1698 | if !self[i].eq(&other[i]) { | |
1699 | return false; | |
1700 | } | |
1701 | } | |
1702 | ||
1703 | true | |
1a4d82fc | 1704 | } |
54a0048b SL |
1705 | |
1706 | default fn not_equal(&self, other: &[B]) -> bool { | |
c1a9b12d SL |
1707 | if self.len() != other.len() { |
1708 | return true; | |
1709 | } | |
1710 | ||
1711 | for i in 0..self.len() { | |
1712 | if self[i].ne(&other[i]) { | |
1713 | return true; | |
1714 | } | |
1715 | } | |
1716 | ||
1717 | false | |
1a4d82fc JJ |
1718 | } |
1719 | } | |
1720 | ||
54a0048b SL |
1721 | // Use memcmp for bytewise equality when the types allow |
1722 | impl<A> SlicePartialEq<A> for [A] | |
1723 | where A: PartialEq<A> + BytewiseEquality | |
1724 | { | |
1725 | fn equal(&self, other: &[A]) -> bool { | |
1726 | if self.len() != other.len() { | |
1727 | return false; | |
1728 | } | |
1729 | unsafe { | |
1730 | let size = mem::size_of_val(self); | |
1731 | memcmp(self.as_ptr() as *const u8, | |
1732 | other.as_ptr() as *const u8, size) == 0 | |
1733 | } | |
1734 | } | |
1a4d82fc | 1735 | |
54a0048b SL |
1736 | fn not_equal(&self, other: &[A]) -> bool { |
1737 | !self.equal(other) | |
1738 | } | |
1739 | } | |
1740 | ||
1741 | #[doc(hidden)] | |
1742 | // intermediate trait for specialization of slice's PartialOrd | |
1743 | trait SlicePartialOrd<B> { | |
1744 | fn partial_compare(&self, other: &[B]) -> Option<Ordering>; | |
1745 | } | |
1746 | ||
1747 | impl<A> SlicePartialOrd<A> for [A] | |
1748 | where A: PartialOrd | |
1749 | { | |
1750 | default fn partial_compare(&self, other: &[A]) -> Option<Ordering> { | |
b039eaaf SL |
1751 | let l = cmp::min(self.len(), other.len()); |
1752 | ||
1753 | // Slice to the loop iteration range to enable bound check | |
1754 | // elimination in the compiler | |
1755 | let lhs = &self[..l]; | |
1756 | let rhs = &other[..l]; | |
1757 | ||
1758 | for i in 0..l { | |
54a0048b SL |
1759 | match lhs[i].partial_cmp(&rhs[i]) { |
1760 | Some(Ordering::Equal) => (), | |
b039eaaf SL |
1761 | non_eq => return non_eq, |
1762 | } | |
1763 | } | |
1764 | ||
54a0048b | 1765 | self.len().partial_cmp(&other.len()) |
1a4d82fc JJ |
1766 | } |
1767 | } | |
1768 | ||
54a0048b SL |
1769 | impl SlicePartialOrd<u8> for [u8] { |
1770 | #[inline] | |
1771 | fn partial_compare(&self, other: &[u8]) -> Option<Ordering> { | |
1772 | Some(SliceOrd::compare(self, other)) | |
1773 | } | |
1774 | } | |
1775 | ||
1776 | #[doc(hidden)] | |
1777 | // intermediate trait for specialization of slice's Ord | |
1778 | trait SliceOrd<B> { | |
1779 | fn compare(&self, other: &[B]) -> Ordering; | |
1780 | } | |
1781 | ||
1782 | impl<A> SliceOrd<A> for [A] | |
1783 | where A: Ord | |
1784 | { | |
1785 | default fn compare(&self, other: &[A]) -> Ordering { | |
b039eaaf SL |
1786 | let l = cmp::min(self.len(), other.len()); |
1787 | ||
1788 | // Slice to the loop iteration range to enable bound check | |
1789 | // elimination in the compiler | |
1790 | let lhs = &self[..l]; | |
1791 | let rhs = &other[..l]; | |
1792 | ||
1793 | for i in 0..l { | |
54a0048b SL |
1794 | match lhs[i].cmp(&rhs[i]) { |
1795 | Ordering::Equal => (), | |
b039eaaf SL |
1796 | non_eq => return non_eq, |
1797 | } | |
1798 | } | |
1799 | ||
54a0048b SL |
1800 | self.len().cmp(&other.len()) |
1801 | } | |
1802 | } | |
1803 | ||
1804 | // memcmp compares a sequence of unsigned bytes lexicographically. | |
1805 | // this matches the order we want for [u8], but no others (not even [i8]). | |
1806 | impl SliceOrd<u8> for [u8] { | |
1807 | #[inline] | |
1808 | fn compare(&self, other: &[u8]) -> Ordering { | |
1809 | let order = unsafe { | |
1810 | memcmp(self.as_ptr(), other.as_ptr(), | |
1811 | cmp::min(self.len(), other.len())) | |
1812 | }; | |
1813 | if order == 0 { | |
1814 | self.len().cmp(&other.len()) | |
1815 | } else if order < 0 { | |
1816 | Less | |
1817 | } else { | |
1818 | Greater | |
1819 | } | |
1820 | } | |
1821 | } | |
1822 | ||
1823 | #[doc(hidden)] | |
1824 | /// Trait implemented for types that can be compared for equality using | |
1825 | /// their bytewise representation | |
1826 | trait BytewiseEquality { } | |
1827 | ||
1828 | macro_rules! impl_marker_for { | |
1829 | ($traitname:ident, $($ty:ty)*) => { | |
1830 | $( | |
1831 | impl $traitname for $ty { } | |
1832 | )* | |
1a4d82fc JJ |
1833 | } |
1834 | } | |
54a0048b SL |
1835 | |
1836 | impl_marker_for!(BytewiseEquality, | |
1837 | u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool); | |
1838 |