src/libcore/slice/rotate.rs

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