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.
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.
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)]
19 /// Ensure this is appropriately aligned for T, and is big
20 /// enough for two elements even if T is enormous.
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.
30 unsafe { mem::uninitialized() }
32 fn ptr(&self) -> *mut T
{
33 unsafe { &self.typed as *const T as *mut T }
36 if mem
::size_of
::<T
>() == 0 {
39 mem
::size_of
::<Self>() / mem
::size_of
::<T
>()
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.
50 /// The specified range must be valid for reading and writing.
51 /// The type `T` must have non-zero size.
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:
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
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) {
74 let delta
= cmp
::min(left
, right
);
75 if delta
<= RawArray
::<T
>::cap() {
79 ptr
::swap_nonoverlapping(
80 mid
.offset(-(left
as isize)),
81 mid
.offset((right
-delta
) as isize),
91 let rawarray
= RawArray
::new();
92 let buf
= rawarray
.ptr();
94 let dim
= mid
.offset(-(left
as isize)).offset(right
as isize);
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
);
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
);