pub fn make_contiguous(&mut
self
)
-
> &mut [T] {
if
self
.is_contiguous() {
let tail
=
self
.tail;
let head
=
self
.head;
return
unsafe { &mut
self
.buffer_as_mut_slice()[tail..head] };
}
let buf
=
self
.buf.ptr();
let cap
=
self
.cap();
let
len
=
self
.
len
();
let free
=
self
.tail
-
self
.head;
let tail_len
=
cap
-
self
.tail;
if
free >
=
tail_len {
/
/
there
is
enough free space to copy the tail
in
one go,
/
/
this means that we first shift the head backwards,
and
then
/
/
copy the tail to the correct position.
/
/
/
/
from
: DEFGH....ABC
/
/
to: ABCDEFGH....
unsafe {
ptr::copy(buf, buf.add(tail_len),
self
.head);
/
/
...DEFGH.ABC
ptr::copy_nonoverlapping(buf.add(
self
.tail), buf, tail_len);
/
/
ABCDEFGH....
self
.tail
=
0
;
self
.head
=
len
;
}
}
else
if
free >
=
self
.head {
/
/
there
is
enough free space to copy the head
in
one go,
/
/
this means that we first shift the tail forwards,
and
then
/
/
copy the head to the correct position.
/
/
/
/
from
: FGH....ABCDE
/
/
to: ...ABCDEFGH.
unsafe {
ptr::copy(buf.add(
self
.tail), buf.add(
self
.head), tail_len);
/
/
FGHABCDE....
ptr::copy_nonoverlapping(buf, buf.add(
self
.head
+
tail_len),
self
.head);
/
/
...ABCDEFGH.
self
.tail
=
self
.head;
self
.head
=
self
.tail
+
len
;
}
}
else
{
/
/
free
is
smaller than both head
and
tail,
/
/
this means we have to slowly
"swap"
the tail
and
the head.
/
/
/
/
from
: EFGHI...ABCD
or
HIJK.ABCDEFG
/
/
to: ABCDEFGHI...
or
ABCDEFGHIJK.
let mut left_edge: usize
=
0
;
let mut right_edge: usize
=
self
.tail;
unsafe {
/
/
The general problem looks like this
/
/
GHIJKLM...ABCDEF
-
before
any
swaps
/
/
ABCDEFM...GHIJKL
-
after
1
pass
of swaps
/
/
ABCDEFGHIJM...KL
-
swap until the left edge reaches the temp store
/
/
-
then restart the algorithm with a new (smaller) store
/
/
Sometimes the temp store
is
reached when the right edge
is
at the end
/
/
of the
buffer
-
this means we've hit the right order with fewer swaps!
/
/
E.g
/
/
EF..ABCD
/
/
ABCDEF..
-
after four only swaps we've finished
while
left_edge <
len
&& right_edge !
=
cap {
let mut right_offset
=
0
;
for
i
in
left_edge..right_edge {
right_offset
=
(i
-
left_edge)
%
(cap
-
right_edge);
let src: isize
=
(right_edge
+
right_offset) as isize;
ptr::swap(buf.add(i), buf.offset(src));
}
let n_ops
=
right_edge
-
left_edge;
left_edge
+
=
n_ops;
right_edge
+
=
right_offset
+
1
;
}
self
.tail
=
0
;
self
.head
=
len
;
}
}
let tail
=
self
.tail;
let head
=
self
.head;
unsafe { &mut
self
.buffer_as_mut_slice()[tail..head] }
}