mod sort;
#[repr(C)]
-struct Repr<T> {
- pub data: *const T,
- pub len: usize,
+union Repr<'a, T: 'a> {
+ rust: &'a [T],
+ rust_mut: &'a mut [T],
+ raw: FatPtr<T>,
+}
+
+#[repr(C)]
+struct FatPtr<T> {
+ data: *const T,
+ len: usize,
}
//
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
#[inline]
- pub fn len(&self) -> usize {
+ #[rustc_const_unstable(feature = "const_slice_len")]
+ pub const fn len(&self) -> usize {
unsafe {
- mem::transmute::<&[T], Repr<T>>(self).len
+ Repr { rust: self }.raw.len
}
}
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
#[inline]
- pub fn is_empty(&self) -> bool {
+ #[rustc_const_unstable(feature = "const_slice_len")]
+ pub const fn is_empty(&self) -> bool {
self.len() == 0
}
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
#[inline]
- pub fn as_ptr(&self) -> *const T {
+ #[rustc_const_unstable(feature = "const_slice_as_ptr")]
+ pub const fn as_ptr(&self) -> *const T {
self as *const [T] as *const T
}
self.as_mut_ptr(), other.as_mut_ptr(), self.len());
}
}
+
+ /// Function to calculate lenghts of the middle and trailing slice for `align_to{,_mut}`.
+ #[cfg(not(stage0))]
+ fn align_to_offsets<U>(&self) -> (usize, usize) {
+ // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
+ // lowest number of `T`s. And how many `T`s we need for each such "multiple".
+ //
+ // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
+ // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
+ // place of every 3 Ts in the `rest` slice. A bit more complicated.
+ //
+ // Formula to calculate this is:
+ //
+ // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
+ // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
+ //
+ // Expanded and simplified:
+ //
+ // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
+ // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
+ //
+ // Luckily since all this is constant-evaluated... performance here matters not!
+ #[inline]
+ fn gcd(a: usize, b: usize) -> usize {
+ // iterative stein’s algorithm
+ // We should still make this `const fn` (and revert to recursive algorithm if we do)
+ // because relying on llvm to consteval all this is… well, it makes me
+ let (ctz_a, mut ctz_b) = unsafe {
+ if a == 0 { return b; }
+ if b == 0 { return a; }
+ (::intrinsics::cttz_nonzero(a), ::intrinsics::cttz_nonzero(b))
+ };
+ let k = ctz_a.min(ctz_b);
+ let mut a = a >> ctz_a;
+ let mut b = b;
+ loop {
+ // remove all factors of 2 from b
+ b >>= ctz_b;
+ if a > b {
+ ::mem::swap(&mut a, &mut b);
+ }
+ b = b - a;
+ unsafe {
+ if b == 0 {
+ break;
+ }
+ ctz_b = ::intrinsics::cttz_nonzero(b);
+ }
+ }
+ return a << k;
+ }
+ let gcd: usize = gcd(::mem::size_of::<T>(), ::mem::size_of::<U>());
+ let ts: usize = ::mem::size_of::<U>() / gcd;
+ let us: usize = ::mem::size_of::<T>() / gcd;
+
+ // Armed with this knowledge, we can find how many `U`s we can fit!
+ let us_len = self.len() / ts * us;
+ // And how many `T`s will be in the trailing slice!
+ let ts_len = self.len() % ts;
+ return (us_len, ts_len);
+ }
+
+ /// Transmute the slice to a slice of another type, ensuring aligment of the types is
+ /// maintained.
+ ///
+ /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
+ /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
+ /// possible for a given type and input slice.
+ ///
+ /// This method has no purpose when either input element `T` or output element `U` are
+ /// zero-sized and will return the original slice without splitting anything.
+ ///
+ /// # Unsafety
+ ///
+ /// This method is essentially a `transmute` with respect to the elements in the returned
+ /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// # #![feature(slice_align_to)]
+ /// unsafe {
+ /// let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
+ /// let (prefix, shorts, suffix) = bytes.align_to::<u16>();
+ /// // less_efficient_algorithm_for_bytes(prefix);
+ /// // more_efficient_algorithm_for_aligned_shorts(shorts);
+ /// // less_efficient_algorithm_for_bytes(suffix);
+ /// }
+ /// ```
+ #[unstable(feature = "slice_align_to", issue = "44488")]
+ #[cfg(not(stage0))]
+ pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
+ // Note that most of this function will be constant-evaluated,
+ if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
+ // handle ZSTs specially, which is – don't handle them at all.
+ return (self, &[], &[]);
+ }
+
+ // First, find at what point do we split between the first and 2nd slice. Easy with
+ // ptr.align_offset.
+ let ptr = self.as_ptr();
+ let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
+ if offset > self.len() {
+ return (self, &[], &[]);
+ } else {
+ let (left, rest) = self.split_at(offset);
+ let (us_len, ts_len) = rest.align_to_offsets::<U>();
+ return (left,
+ from_raw_parts(rest.as_ptr() as *const U, us_len),
+ from_raw_parts(rest.as_ptr().offset((rest.len() - ts_len) as isize), ts_len))
+ }
+ }
+
+ /// Transmute the slice to a slice of another type, ensuring aligment of the types is
+ /// maintained.
+ ///
+ /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
+ /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
+ /// possible for a given type and input slice.
+ ///
+ /// This method has no purpose when either input element `T` or output element `U` are
+ /// zero-sized and will return the original slice without splitting anything.
+ ///
+ /// # Unsafety
+ ///
+ /// This method is essentially a `transmute` with respect to the elements in the returned
+ /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// # #![feature(slice_align_to)]
+ /// unsafe {
+ /// let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
+ /// let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
+ /// // less_efficient_algorithm_for_bytes(prefix);
+ /// // more_efficient_algorithm_for_aligned_shorts(shorts);
+ /// // less_efficient_algorithm_for_bytes(suffix);
+ /// }
+ /// ```
+ #[unstable(feature = "slice_align_to", issue = "44488")]
+ #[cfg(not(stage0))]
+ pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
+ // Note that most of this function will be constant-evaluated,
+ if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
+ // handle ZSTs specially, which is – don't handle them at all.
+ return (self, &mut [], &mut []);
+ }
+
+ // First, find at what point do we split between the first and 2nd slice. Easy with
+ // ptr.align_offset.
+ let ptr = self.as_ptr();
+ let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
+ if offset > self.len() {
+ return (self, &mut [], &mut []);
+ } else {
+ let (left, rest) = self.split_at_mut(offset);
+ let (us_len, ts_len) = rest.align_to_offsets::<U>();
+ let mut_ptr = rest.as_mut_ptr();
+ return (left,
+ from_raw_parts_mut(mut_ptr as *mut U, us_len),
+ from_raw_parts_mut(mut_ptr.offset((rest.len() - ts_len) as isize), ts_len))
+ }
+ }
}
#[lang = "slice_u8"]
panic!("attempted to index slice up to maximum usize");
}
+mod private_slice_index {
+ use super::ops;
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ pub trait Sealed {}
+
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for usize {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::Range<usize> {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::RangeTo<usize> {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::RangeFrom<usize> {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::RangeFull {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::RangeInclusive<usize> {}
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
+ impl Sealed for ops::RangeToInclusive<usize> {}
+}
+
/// A helper trait used for indexing operations.
-#[unstable(feature = "slice_get_slice", issue = "35729")]
+#[stable(feature = "slice_get_slice", since = "1.28.0")]
#[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
-pub trait SliceIndex<T: ?Sized> {
+pub trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
/// The output type returned by methods.
+ #[stable(feature = "slice_get_slice", since = "1.28.0")]
type Output: ?Sized;
/// Returns a shared reference to the output at this location, if in
/// bounds.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
fn get(self, slice: &T) -> Option<&Self::Output>;
/// Returns a mutable reference to the output at this location, if in
/// bounds.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
/// Returns a shared reference to the output at this location, without
/// performing any bounds checking.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
/// Returns a mutable reference to the output at this location, without
/// performing any bounds checking.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
/// Returns a shared reference to the output at this location, panicking
/// if out of bounds.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
fn index(self, slice: &T) -> &Self::Output;
/// Returns a mutable reference to the output at this location, panicking
/// if out of bounds.
+ #[unstable(feature = "slice_index_methods", issue = "0")]
fn index_mut(self, slice: &mut T) -> &mut Self::Output;
}
accum
}
}
+
+ #[stable(feature = "fused", since = "1.26.0")]
+ impl<'a, T> FusedIterator for $name<'a, T> {}
+
+ #[unstable(feature = "trusted_len", issue = "37572")]
+ unsafe impl<'a, T> TrustedLen for $name<'a, T> {}
}
}
}
}
-#[stable(feature = "fused", since = "1.26.0")]
-impl<'a, T> FusedIterator for Iter<'a, T> {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<'a, T> TrustedLen for Iter<'a, T> {}
-
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> Clone for Iter<'a, T> {
fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
/// View the underlying data as a subslice of the original data.
///
/// To avoid creating `&mut` references that alias, this is forced
- /// to consume the iterator. Consider using the `Slice` and
- /// `SliceMut` implementations for obtaining slices with more
- /// restricted lifetimes that do not consume the iterator.
+ /// to consume the iterator.
///
/// # Examples
///
}
}
-#[stable(feature = "fused", since = "1.26.0")]
-impl<'a, T> FusedIterator for IterMut<'a, T> {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<'a, T> TrustedLen for IterMut<'a, T> {}
-
-
// Return the number of elements of `T` from `start` to `end`.
// Return the arithmetic difference if `T` is zero size.
#[inline(always)]
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<'a, T> TrustedLen for Windows<'a, T> {}
+
#[stable(feature = "fused", since = "1.26.0")]
impl<'a, T> FusedIterator for Windows<'a, T> {}
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<'a, T> TrustedLen for Chunks<'a, T> {}
+
#[stable(feature = "fused", since = "1.26.0")]
impl<'a, T> FusedIterator for Chunks<'a, T> {}
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<'a, T> TrustedLen for ChunksMut<'a, T> {}
+
#[stable(feature = "fused", since = "1.26.0")]
impl<'a, T> FusedIterator for ChunksMut<'a, T> {}
}
}
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<'a, T> TrustedLen for ExactChunks<'a, T> {}
+
#[unstable(feature = "exact_chunks", issue = "47115")]
impl<'a, T> FusedIterator for ExactChunks<'a, T> {}
}
}
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<'a, T> TrustedLen for ExactChunksMut<'a, T> {}
+
#[unstable(feature = "exact_chunks", issue = "47115")]
impl<'a, T> FusedIterator for ExactChunksMut<'a, T> {}
/// valid for `len` elements, nor whether the lifetime inferred is a suitable
/// lifetime for the returned slice.
///
-/// `p` must be non-null, even for zero-length slices, because non-zero bits
-/// are required to distinguish between a zero-length slice within `Some()`
-/// from `None`. `p` can be a bogus non-dereferencable pointer, such as `0x1`,
-/// for zero-length slices, though.
+/// `p` must be non-null and aligned, even for zero-length slices, as is
+/// required for all references. However, for zero-length slices, `p` can be
+/// a bogus non-dereferencable pointer such as [`NonNull::dangling()`].
///
/// # Caveat
///
/// let slice = slice::from_raw_parts(ptr, amt);
/// }
/// ```
+///
+/// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
-pub unsafe fn from_raw_parts<'a, T>(p: *const T, len: usize) -> &'a [T] {
- mem::transmute(Repr { data: p, len: len })
+pub unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] {
+ Repr { raw: FatPtr { data, len } }.rust
}
/// Performs the same functionality as `from_raw_parts`, except that a mutable
///
/// This function is unsafe for the same reasons as `from_raw_parts`, as well
/// as not being able to provide a non-aliasing guarantee of the returned
-/// mutable slice. `p` must be non-null even for zero-length slices as with
+/// mutable slice. `p` must be non-null and aligned even for zero-length slices as with
/// `from_raw_parts`.
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
-pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] {
- mem::transmute(Repr { data: p, len: len })
+pub unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] {
+ Repr { raw: FatPtr { data, len} }.rust_mut
}
/// Converts a reference to T into a slice of length 1 (without copying).
-#[unstable(feature = "from_ref", issue = "45703")]
+#[stable(feature = "from_ref", since = "1.28.0")]
pub fn from_ref<T>(s: &T) -> &[T] {
unsafe {
from_raw_parts(s, 1)
}
/// Converts a reference to T into a slice of length 1 (without copying).
-#[unstable(feature = "from_ref", issue = "45703")]
-pub fn from_ref_mut<T>(s: &mut T) -> &mut [T] {
+#[stable(feature = "from_ref", since = "1.28.0")]
+pub fn from_mut<T>(s: &mut T) -> &mut [T] {
unsafe {
from_raw_parts_mut(s, 1)
}
projects / rust.git / blobdiff