src/libcore/slice/rotate.rs

   1 // Copyright 2012-2017 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 use cmp;
  12 use mem::{self, MaybeUninit};
  13 use ptr;
  14
  15 /// Rotation is much faster if it has access to a little bit of memory. This
  16 /// union provides a RawVec-like interface, but to a fixed-size stack buffer.
  17 #[allow(unions_with_drop_fields)]
  18 union RawArray<T> {
  19     /// Ensure this is appropriately aligned for T, and is big
  20     /// enough for two elements even if T is enormous.
  21     typed: [T; 2],
  22     /// For normally-sized types, especially things like u8, having more
  23     /// than 2 in the buffer is necessary for usefulness, so pad it out
  24     /// enough to be helpful, but not so big as to risk overflow.
  25     _extra: [usize; 32],
  26 }
  27
  28 impl<T> RawArray<T> {
  29     fn cap() -> usize {
  30         if mem::size_of::<T>() == 0 {
  31             usize::max_value()
  32         } else {
  33             mem::size_of::<Self>() / mem::size_of::<T>()
  34         }
  35     }
  36 }
  37
  38 /// Rotates the range `[mid-left, mid+right)` such that the element at `mid`
  39 /// becomes the first element.  Equivalently, rotates the range `left`
  40 /// elements to the left or `right` elements to the right.
  41 ///
  42 /// # Safety
  43 ///
  44 /// The specified range must be valid for reading and writing.
  45 ///
  46 /// # Algorithm
  47 ///
  48 /// For longer rotations, swap the left-most `delta = min(left, right)`
  49 /// elements with the right-most `delta` elements.  LLVM vectorizes this,
  50 /// which is profitable as we only reach this step for a "large enough"
  51 /// rotation.  Doing this puts `delta` elements on the larger side into the
  52 /// correct position, leaving a smaller rotate problem.  Demonstration:
  53 ///
  54 /// ```text
  55 /// [ 6 7 8 9 10 11 12 13 . 1 2 3 4 5 ]
  56 /// 1 2 3 4 5 [ 11 12 13 . 6 7 8 9 10 ]
  57 /// 1 2 3 4 5 [ 8 9 10 . 6 7 ] 11 12 13
  58 /// 1 2 3 4 5 6 7 [ 10 . 8 9 ] 11 12 13
  59 /// 1 2 3 4 5 6 7 [ 9 . 8 ] 10 11 12 13
  60 /// 1 2 3 4 5 6 7 8 [ . ] 9 10 11 12 13
  61 /// ```
  62 ///
  63 /// Once the rotation is small enough, copy some elements into a stack
  64 /// buffer, `memmove` the others, and move the ones back from the buffer.
  65 pub unsafe fn ptr_rotate<T>(mut left: usize, mid: *mut T, mut right: usize) {
  66     loop {
  67         let delta = cmp::min(left, right);
  68         if delta <= RawArray::<T>::cap() {
  69             // We will always hit this immediately for ZST.
  70             break;
  71         }
  72
  73         ptr::swap_nonoverlapping(
  74             mid.sub(left),
  75             mid.add(right - delta),
  76             delta);
  77
  78         if left <= right {
  79             right -= delta;
  80         } else {
  81             left -= delta;
  82         }
  83     }
  84
  85     let mut rawarray = MaybeUninit::<RawArray<T>>::uninitialized();
  86     let buf = &mut (*rawarray.as_mut_ptr()).typed as *mut [T; 2] as *mut T;
  87
  88     let dim = mid.sub(left).add(right);
  89     if left <= right {
  90         ptr::copy_nonoverlapping(mid.sub(left), buf, left);
  91         ptr::copy(mid, mid.sub(left), right);
  92         ptr::copy_nonoverlapping(buf, dim, left);
  93     }
  94     else {
  95         ptr::copy_nonoverlapping(mid, buf, right);
  96         ptr::copy(mid.sub(left), dim, left);
  97         ptr::copy_nonoverlapping(buf, mid.sub(left), right);
  98     }
  99 }