1 // ignore-tidy-undocumented-unsafe
4 use crate::mem
::{self, MaybeUninit}
;
7 /// Rotates the range `[mid-left, mid+right)` such that the element at `mid` becomes the first
8 /// element. Equivalently, rotates the range `left` elements to the left or `right` elements to the
13 /// The specified range must be valid for reading and writing.
17 /// Algorithm 1 is used for small values of `left + right` or for large `T`. The elements are moved
18 /// into their final positions one at a time starting at `mid - left` and advancing by `right` steps
19 /// modulo `left + right`, such that only one temporary is needed. Eventually, we arrive back at
20 /// `mid - left`. However, if `gcd(left + right, right)` is not 1, the above steps skipped over
21 /// elements. For example:
23 /// left = 10, right = 6
24 /// the `^` indicates an element in its final place
25 /// 6 7 8 9 10 11 12 13 14 15 . 0 1 2 3 4 5
26 /// after using one step of the above algorithm (The X will be overwritten at the end of the round,
27 /// and 12 is stored in a temporary):
28 /// X 7 8 9 10 11 6 13 14 15 . 0 1 2 3 4 5
30 /// after using another step (now 2 is in the temporary):
31 /// X 7 8 9 10 11 6 13 14 15 . 0 1 12 3 4 5
33 /// after the third step (the steps wrap around, and 8 is in the temporary):
34 /// X 7 2 9 10 11 6 13 14 15 . 0 1 12 3 4 5
36 /// after 7 more steps, the round ends with the temporary 0 getting put in the X:
37 /// 0 7 2 9 4 11 6 13 8 15 . 10 1 12 3 14 5
40 /// Fortunately, the number of skipped over elements between finalized elements is always equal, so
41 /// we can just offset our starting position and do more rounds (the total number of rounds is the
42 /// `gcd(left + right, right)` value). The end result is that all elements are finalized once and
45 /// Algorithm 2 is used if `left + right` is large but `min(left, right)` is small enough to
46 /// fit onto a stack buffer. The `min(left, right)` elements are copied onto the buffer, `memmove`
47 /// is applied to the others, and the ones on the buffer are moved back into the hole on the
48 /// opposite side of where they originated.
50 /// Algorithms that can be vectorized outperform the above once `left + right` becomes large enough.
51 /// Algorithm 1 can be vectorized by chunking and performing many rounds at once, but there are too
52 /// few rounds on average until `left + right` is enormous, and the worst case of a single
53 /// round is always there. Instead, algorithm 3 utilizes repeated swapping of
54 /// `min(left, right)` elements until a smaller rotate problem is left.
57 /// left = 11, right = 4
58 /// [4 5 6 7 8 9 10 11 12 13 14 . 0 1 2 3]
59 /// ^ ^ ^ ^ ^ ^ ^ ^ swapping the right most elements with elements to the left
60 /// [4 5 6 7 8 9 10 . 0 1 2 3] 11 12 13 14
61 /// ^ ^ ^ ^ ^ ^ ^ ^ swapping these
62 /// [4 5 6 . 0 1 2 3] 7 8 9 10 11 12 13 14
63 /// we cannot swap any more, but a smaller rotation problem is left to solve
65 /// when `left < right` the swapping happens from the left instead.
66 pub unsafe fn ptr_rotate
<T
>(mut left
: usize, mut mid
: *mut T
, mut right
: usize) {
67 type BufType
= [usize; 32];
68 if mem
::size_of
::<T
>() == 0 {
72 // N.B. the below algorithms can fail if these cases are not checked
73 if (right
== 0) || (left
== 0) {
76 if (left
+ right
< 24) || (mem
::size_of
::<T
>() > mem
::size_of
::<[usize; 4]>()) {
78 // Microbenchmarks indicate that the average performance for random shifts is better all
79 // the way until about `left + right == 32`, but the worst case performance breaks even
80 // around 16. 24 was chosen as middle ground. If the size of `T` is larger than 4
81 // `usize`s, this algorithm also outperforms other algorithms.
82 let x
= unsafe { mid.sub(left) }
;
83 // beginning of first round
84 let mut tmp
: T
= unsafe { x.read() }
;
86 // `gcd` can be found before hand by calculating `gcd(left + right, right)`,
87 // but it is faster to do one loop which calculates the gcd as a side effect, then
88 // doing the rest of the chunk
90 // benchmarks reveal that it is faster to swap temporaries all the way through instead
91 // of reading one temporary once, copying backwards, and then writing that temporary at
92 // the very end. This is possibly due to the fact that swapping or replacing temporaries
93 // uses only one memory address in the loop instead of needing to manage two.
95 tmp
= unsafe { x.add(i).replace(tmp) }
;
96 // instead of incrementing `i` and then checking if it is outside the bounds, we
97 // check if `i` will go outside the bounds on the next increment. This prevents
98 // any wrapping of pointers or `usize`.
102 // end of first round
103 unsafe { x.write(tmp) }
;
106 // this conditional must be here if `left + right >= 15`
114 // finish the chunk with more rounds
115 for start
in 1..gcd
{
116 tmp
= unsafe { x.add(start).read() }
;
119 tmp
= unsafe { x.add(i).replace(tmp) }
;
123 unsafe { x.add(start).write(tmp) }
;
132 // `T` is not a zero-sized type, so it's okay to divide by its size.
133 } else if cmp
::min(left
, right
) <= mem
::size_of
::<BufType
>() / mem
::size_of
::<T
>() {
135 // The `[T; 0]` here is to ensure this is appropriately aligned for T
136 let mut rawarray
= MaybeUninit
::<(BufType
, [T
; 0])>::uninit();
137 let buf
= rawarray
.as_mut_ptr() as *mut T
;
138 let dim
= unsafe { mid.sub(left).add(right) }
;
141 ptr
::copy_nonoverlapping(mid
.sub(left
), buf
, left
);
142 ptr
::copy(mid
, mid
.sub(left
), right
);
143 ptr
::copy_nonoverlapping(buf
, dim
, left
);
147 ptr
::copy_nonoverlapping(mid
, buf
, right
);
148 ptr
::copy(mid
.sub(left
), dim
, left
);
149 ptr
::copy_nonoverlapping(buf
, mid
.sub(left
), right
);
153 } else if left
>= right
{
155 // There is an alternate way of swapping that involves finding where the last swap
156 // of this algorithm would be, and swapping using that last chunk instead of swapping
157 // adjacent chunks like this algorithm is doing, but this way is still faster.
160 ptr
::swap_nonoverlapping(mid
.sub(right
), mid
, right
);
161 mid
= mid
.sub(right
);
169 // Algorithm 3, `left < right`
172 ptr
::swap_nonoverlapping(mid
.sub(left
), mid
, left
);