src/libcore/slice.rs

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