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;
  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 new() -> Self {
  30         unsafe { mem::uninitialized() }
  31     }
  32     fn ptr(&self) -> *mut T {
  33         unsafe { &self.typed as *const T as *mut T }
  34     }
  35     fn cap() -> usize {
  36         if mem::size_of::<T>() == 0 {
  37             usize::max_value()
  38         } else {
  39             mem::size_of::<Self>() / mem::size_of::<T>()
  40         }
  41     }
  42 }
  43
  44 /// Rotates the range `[mid-left, mid+right)` such that the element at `mid`
  45 /// becomes the first element.  Equivalently, rotates the range `left`
  46 /// elements to the left or `right` elements to the right.
  47 ///
  48 /// # Safety
  49 ///
  50 /// The specified range must be valid for reading and writing.
  51 /// The type `T` must have non-zero size.
  52 ///
  53 /// # Algorithm
  54 ///
  55 /// For longer rotations, swap the left-most `delta = min(left, right)`
  56 /// elements with the right-most `delta` elements.  LLVM vectorizes this,
  57 /// which is profitable as we only reach this step for a "large enough"
  58 /// rotation.  Doing this puts `delta` elements on the larger side into the
  59 /// correct position, leaving a smaller rotate problem.  Demonstration:
  60 ///
  61 /// ```text
  62 /// [ 6 7 8 9 10 11 12 13 . 1 2 3 4 5 ]
  63 /// 1 2 3 4 5 [ 11 12 13 . 6 7 8 9 10 ]
  64 /// 1 2 3 4 5 [ 8 9 10 . 6 7 ] 11 12 13
  65 /// 1 2 3 4 5 6 7 [ 10 . 8 9 ] 11 12 13
  66 /// 1 2 3 4 5 6 7 [ 9 . 8 ] 10 11 12 13
  67 /// 1 2 3 4 5 6 7 8 [ . ] 9 10 11 12 13
  68 /// ```
  69 ///
  70 /// Once the rotation is small enough, copy some elements into a stack
  71 /// buffer, `memmove` the others, and move the ones back from the buffer.
  72 pub unsafe fn ptr_rotate<T>(mut left: usize, mid: *mut T, mut right: usize) {
  73     loop {
  74         let delta = cmp::min(left, right);
  75         if delta <= RawArray::<T>::cap() {
  76             break;
  77         }
  78
  79         ptr_swap_n(
  80             mid.offset(-(left as isize)),
  81             mid.offset((right-delta) as isize),
  82             delta);
  83
  84         if left <= right {
  85             right -= delta;
  86         } else {
  87             left -= delta;
  88         }
  89     }
  90
  91     let rawarray = RawArray::new();
  92     let buf = rawarray.ptr();
  93
  94     let dim = mid.offset(-(left as isize)).offset(right as isize);
  95     if left <= right {
  96         ptr::copy_nonoverlapping(mid.offset(-(left as isize)), buf, left);
  97         ptr::copy(mid, mid.offset(-(left as isize)), right);
  98         ptr::copy_nonoverlapping(buf, dim, left);
  99     }
 100     else {
 101         ptr::copy_nonoverlapping(mid, buf, right);
 102         ptr::copy(mid.offset(-(left as isize)), dim, left);
 103         ptr::copy_nonoverlapping(buf, mid.offset(-(left as isize)), right);
 104     }
 105 }
 106
 107 unsafe fn ptr_swap_u8(a: *mut u8, b: *mut u8, n: usize) {
 108     for i in 0..n {
 109         ptr::swap(a.offset(i as isize), b.offset(i as isize));
 110     }
 111 }
 112 unsafe fn ptr_swap_u16(a: *mut u16, b: *mut u16, n: usize) {
 113     for i in 0..n {
 114         ptr::swap(a.offset(i as isize), b.offset(i as isize));
 115     }
 116 }
 117 unsafe fn ptr_swap_u32(a: *mut u32, b: *mut u32, n: usize) {
 118     for i in 0..n {
 119         ptr::swap(a.offset(i as isize), b.offset(i as isize));
 120     }
 121 }
 122 unsafe fn ptr_swap_u64(a: *mut u64, b: *mut u64, n: usize) {
 123     for i in 0..n {
 124         ptr::swap(a.offset(i as isize), b.offset(i as isize));
 125     }
 126 }
 127
 128 unsafe fn ptr_swap_n<T>(a: *mut T, b: *mut T, n: usize) {
 129     // Doing this as a generic is 16% & 40% slower in two of the `String`
 130     // benchmarks, as (based on the block names) LLVM doesn't vectorize it.
 131     // Since this is just operating on raw memory, dispatch to a version
 132     // with appropriate alignment.  Helps with code size as well, by
 133     // avoiding monomorphizing different unrolled loops for `i32`,
 134     // `u32`, `f32`, `[u32; 1]`, etc.
 135     let size_of_t = mem::size_of::<T>();
 136     let align_of_t = mem::align_of::<T>();
 137
 138     let a64 = mem::align_of::<u64>();
 139     if a64 == 8 && align_of_t % a64 == 0 {
 140         return ptr_swap_u64(a as *mut u64, b as *mut u64, n * (size_of_t / 8));
 141     }
 142
 143     let a32 = mem::align_of::<u32>();
 144     if a32 == 4 && align_of_t % a32 == 0 {
 145         return ptr_swap_u32(a as *mut u32, b as *mut u32, n * (size_of_t / 4));
 146     }
 147
 148     let a16 = mem::align_of::<u16>();
 149     if a16 == 2 && align_of_t % a16 == 0 {
 150         return ptr_swap_u16(a as *mut u16, b as *mut u16, n * (size_of_t / 2));
 151     }
 152
 153     ptr_swap_u8(a as *mut u8, b as *mut u8, n * size_of_t);
 154 }