1 // This Source Code Form is subject to the terms of the Mozilla Public
2 // License, v. 2.0. If a copy of the MPL was not distributed with this
3 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 //! A fixed capacity smart array.
7 //! See [`Chunk`](struct.Chunk.html)
9 use std
::borrow
::{Borrow, BorrowMut}
;
10 use std
::cmp
::Ordering
;
11 use std
::fmt
::{Debug, Error, Formatter}
;
12 use std
::hash
::{Hash, Hasher}
;
14 use std
::iter
::{FromIterator, FusedIterator}
;
15 use std
::mem
::{self, replace, ManuallyDrop}
;
16 use std
::ops
::{Deref, DerefMut, Index, IndexMut}
;
19 from_raw_parts
, from_raw_parts_mut
, Iter
as SliceIter
, IterMut
as SliceIterMut
, SliceIndex
,
24 use nodes
::types
::ChunkLength
;
26 /// A fixed capacity smart array.
28 /// An inline array of items with a variable length but a fixed, preallocated
29 /// capacity given by the `N` type, which must be an [`Unsigned`][Unsigned] type
32 /// It's 'smart' because it's able to reorganise its contents based on expected
33 /// behaviour. If you construct one using `push_back`, it will be laid out like
34 /// a `Vec` with space at the end. If you `push_front` it will start filling in
35 /// values from the back instead of the front, so that you still get linear time
36 /// push as long as you don't reverse direction. If you do, and there's no room
37 /// at the end you're pushing to, it'll shift its contents over to the other
38 /// side, creating more space to push into. This technique is tuned for
39 /// `Chunk`'s expected use case: usually, chunks always see either `push_front`
40 /// or `push_back`, but not both unless they move around inside the tree, in
41 /// which case they're able to reorganise themselves with reasonable efficiency
42 /// to suit their new usage patterns.
44 /// It maintains a `left` index and a `right` index instead of a simple length
45 /// counter in order to accomplish this, much like a ring buffer would, except
46 /// that the `Chunk` keeps all its items sequentially in memory so that you can
47 /// always get a `&[A]` slice for them, at the price of the occasional
48 /// reordering operation.
50 /// This technique also lets us choose to shift the shortest side to account for
51 /// the inserted or removed element when performing insert and remove
52 /// operations, unlike `Vec` where you always need to shift the right hand side.
54 /// Unlike a `Vec`, the `Chunk` has a fixed capacity and cannot grow beyond it.
55 /// Being intended for low level use, it expects you to know or test whether
56 /// you're pushing to a full array, and has an API more geared towards panics
57 /// than returning `Option`s, on the assumption that you know what you're doing.
62 /// # #[macro_use] extern crate im_rc as im;
63 /// # extern crate typenum;
64 /// # use im::chunk::Chunk;
65 /// # use typenum::U64;
67 /// // Construct a chunk with a 64 item capacity
68 /// let mut chunk = Chunk::<i32, U64>::new();
69 /// // Fill it with descending numbers
70 /// chunk.extend((0..64).rev());
71 /// // It derefs to a slice so we can use standard slice methods
73 /// // It's got all the amenities like `FromIterator` and `Eq`
74 /// let expected: Chunk<i32, U64> = (0..64).collect();
75 /// assert_eq!(expected, chunk);
79 /// [Unsigned]: https://docs.rs/typenum/1.10.0/typenum/marker_traits/trait.Unsigned.html
80 pub struct Chunk
<A
, N
= U64
>
86 data
: ManuallyDrop
<N
::SizedType
>,
89 impl<A
, N
> Drop
for Chunk
<A
, N
>
94 if mem
::needs_drop
::<A
>() {
95 for i
in self.left
..self.right
{
96 unsafe { Chunk::force_drop(i, self) }
102 impl<A
, N
> Clone
for Chunk
<A
, N
>
107 fn clone(&self) -> Self {
108 let mut out
= Self::new();
109 out
.left
= self.left
;
110 out
.right
= self.right
;
111 for index
in self.left
..self.right
{
112 unsafe { Chunk::force_write(index, self.values()[index].clone(), &mut out) }
118 impl<A
, N
> Chunk
<A
, N
>
122 /// Construct a new empty chunk.
123 pub fn new() -> Self {
126 chunk
= mem
::uninitialized();
127 ptr
::write(&mut chunk
.left
, 0);
128 ptr
::write(&mut chunk
.right
, 0);
133 /// Construct a new chunk with one item.
134 pub fn unit(value
: A
) -> Self {
137 chunk
= mem
::uninitialized();
138 ptr
::write(&mut chunk
.left
, 0);
139 ptr
::write(&mut chunk
.right
, 1);
140 Chunk
::force_write(0, value
, &mut chunk
);
145 /// Construct a new chunk with two items.
146 pub fn pair(left
: A
, right
: A
) -> Self {
149 chunk
= mem
::uninitialized();
150 ptr
::write(&mut chunk
.left
, 0);
151 ptr
::write(&mut chunk
.right
, 2);
152 Chunk
::force_write(0, left
, &mut chunk
);
153 Chunk
::force_write(1, right
, &mut chunk
);
158 /// Construct a new chunk and move every item from `other` into the new
162 pub fn drain_from(other
: &mut Self) -> Self {
163 let other_len
= other
.len();
164 Self::from_front(other
, other_len
)
167 /// Construct a new chunk and populate it by taking `count` items from the
170 /// Panics if the iterator contains less than `count` items.
173 pub fn collect_from
<I
>(iter
: &mut I
, mut count
: usize) -> Self
175 I
: Iterator
<Item
= A
>,
177 let mut chunk
= Self::new();
182 .expect("Chunk::collect_from: underfull iterator"),
188 /// Construct a new chunk and populate it by taking `count` items from the
189 /// front of `other`.
191 /// Time: O(n) for the number of items moved
192 pub fn from_front(other
: &mut Self, count
: usize) -> Self {
193 let other_len
= other
.len();
194 debug_assert
!(count
<= other_len
);
195 let mut chunk
= Self::new();
196 unsafe { Chunk::force_copy_to(other.left, 0, count, other, &mut chunk) }
;
202 /// Construct a new chunk and populate it by taking `count` items from the
205 /// Time: O(n) for the number of items moved
206 pub fn from_back(other
: &mut Self, count
: usize) -> Self {
207 let other_len
= other
.len();
208 debug_assert
!(count
<= other_len
);
209 let mut chunk
= Self::new();
210 unsafe { Chunk::force_copy_to(other.right - count, 0, count, other, &mut chunk) }
;
212 other
.right
-= count
;
216 /// Get the length of the chunk.
218 pub fn len(&self) -> usize {
219 self.right
- self.left
222 /// Test if the chunk is empty.
224 pub fn is_empty(&self) -> bool
{
225 self.left
== self.right
228 /// Test if the chunk is at capacity.
230 pub fn is_full(&self) -> bool
{
231 self.left
== 0 && self.right
== N
::USIZE
235 fn values(&self) -> &[A
] {
238 &self.data
as *const ManuallyDrop
<N
::SizedType
> as *const A
,
245 fn values_mut(&mut self) -> &mut [A
] {
248 &mut self.data
as *mut ManuallyDrop
<N
::SizedType
> as *mut A
,
254 /// Copy the value at an index, discarding ownership of the copied value
256 unsafe fn force_read(index
: usize, chunk
: &mut Self) -> A
{
257 ptr
::read(&chunk
.values()[index
])
260 /// Write a value at an index without trying to drop what's already there
262 unsafe fn force_write(index
: usize, value
: A
, chunk
: &mut Self) {
263 ptr
::write(&mut chunk
.values_mut()[index
], value
)
266 /// Drop the value at an index
268 unsafe fn force_drop(index
: usize, chunk
: &mut Self) {
269 ptr
::drop_in_place(&mut chunk
.values_mut()[index
])
272 /// Copy a range within a chunk
274 unsafe fn force_copy(from
: usize, to
: usize, count
: usize, chunk
: &mut Self) {
276 ptr
::copy(&chunk
.values()[from
], &mut chunk
.values_mut()[to
], count
)
280 /// Copy a range between chunks
282 unsafe fn force_copy_to(
290 ptr
::copy_nonoverlapping(&chunk
.values()[from
], &mut other
.values_mut()[to
], count
)
294 /// Push an item to the front of the chunk.
296 /// Panics if the capacity of the chunk is exceeded.
298 /// Time: O(1) if there's room at the front, O(n) otherwise
299 pub fn push_front(&mut self, value
: A
) {
301 panic
!("Chunk::push_front: can't push to full chunk");
304 self.left
= N
::USIZE
;
305 self.right
= N
::USIZE
;
306 } else if self.left
== 0 {
307 self.left
= N
::USIZE
- self.right
;
308 unsafe { Chunk::force_copy(0, self.left, self.right, self) }
;
309 self.right
= N
::USIZE
;
312 unsafe { Chunk::force_write(self.left, value, self) }
315 /// Push an item to the back of the chunk.
317 /// Panics if the capacity of the chunk is exceeded.
319 /// Time: O(1) if there's room at the back, O(n) otherwise
320 pub fn push_back(&mut self, value
: A
) {
322 panic
!("Chunk::push_back: can't push to full chunk");
327 } else if self.right
== N
::USIZE
{
328 unsafe { Chunk::force_copy(self.left, 0, self.len(), self) }
;
329 self.right
= N
::USIZE
- self.left
;
332 unsafe { Chunk::force_write(self.right, value, self) }
336 /// Pop an item off the front of the chunk.
338 /// Panics if the chunk is empty.
341 pub fn pop_front(&mut self) -> A
{
343 panic
!("Chunk::pop_front: can't pop from empty chunk");
345 let value
= unsafe { Chunk::force_read(self.left, self) }
;
351 /// Pop an item off the back of the chunk.
353 /// Panics if the chunk is empty.
356 pub fn pop_back(&mut self) -> A
{
358 panic
!("Chunk::pop_back: can't pop from empty chunk");
361 unsafe { Chunk::force_read(self.right, self) }
365 /// Discard all items up to but not including `index`.
367 /// Panics if `index` is out of bounds.
369 /// Time: O(n) for the number of items dropped
370 pub fn drop_left(&mut self, index
: usize) {
372 if index
> self.len() {
373 panic
!("Chunk::drop_left: index out of bounds");
375 let start
= self.left
;
376 for i
in start
..(start
+ index
) {
377 unsafe { Chunk::force_drop(i, self) }
383 /// Discard all items from `index` onward.
385 /// Panics if `index` is out of bounds.
387 /// Time: O(n) for the number of items dropped
388 pub fn drop_right(&mut self, index
: usize) {
389 if index
> self.len() {
390 panic
!("Chunk::drop_right: index out of bounds");
392 if index
== self.len() {
395 let start
= self.left
+ index
;
396 for i
in start
..self.right
{
397 unsafe { Chunk::force_drop(i, self) }
402 /// Split a chunk into two, the original chunk containing
403 /// everything up to `index` and the returned chunk containing
404 /// everything from `index` onwards.
406 /// Panics if `index` is out of bounds.
408 /// Time: O(n) for the number of items in the new chunk
409 pub fn split_off(&mut self, index
: usize) -> Self {
410 if index
> self.len() {
411 panic
!("Chunk::split: index out of bounds");
413 if index
== self.len() {
416 let mut right_chunk
= Self::new();
417 let start
= self.left
+ index
;
418 let len
= self.right
- start
;
419 unsafe { Chunk::force_copy_to(start, 0, len, self, &mut right_chunk) }
;
420 right_chunk
.right
= len
;
425 /// Remove all items from `other` and append them to the back of `self`.
427 /// Panics if the capacity of the chunk is exceeded.
429 /// Time: O(n) for the number of items moved
430 pub fn append(&mut self, other
: &mut Self) {
431 let self_len
= self.len();
432 let other_len
= other
.len();
433 if self_len
+ other_len
> N
::USIZE
{
434 panic
!("Chunk::append: chunk size overflow");
436 if self.right
+ other_len
> N
::USIZE
{
437 unsafe { Chunk::force_copy(self.left, 0, self_len, self) }
;
438 self.right
-= self.left
;
441 unsafe { Chunk::force_copy_to(other.left, self.right, other_len, other, self) }
;
442 self.right
+= other_len
;
447 /// Remove `count` items from the front of `other` and append them to the
450 /// Panics if `self` doesn't have `count` items left, or if `other` has
451 /// fewer than `count` items.
453 /// Time: O(n) for the number of items moved
454 pub fn drain_from_front(&mut self, other
: &mut Self, count
: usize) {
455 let self_len
= self.len();
456 let other_len
= other
.len();
457 debug_assert
!(self_len
+ count
<= N
::USIZE
);
458 debug_assert
!(other_len
>= count
);
459 if self.right
+ count
> N
::USIZE
{
460 unsafe { Chunk::force_copy(self.left, 0, self_len, self) }
;
461 self.right
-= self.left
;
464 unsafe { Chunk::force_copy_to(other.left, self.right, count, other, self) }
;
469 /// Remove `count` items from the back of `other` and append them to the
472 /// Panics if `self` doesn't have `count` items left, or if `other` has
473 /// fewer than `count` items.
475 /// Time: O(n) for the number of items moved
476 pub fn drain_from_back(&mut self, other
: &mut Self, count
: usize) {
477 let self_len
= self.len();
478 let other_len
= other
.len();
479 debug_assert
!(self_len
+ count
<= N
::USIZE
);
480 debug_assert
!(other_len
>= count
);
481 if self.left
< count
{
482 self.left
= N
::USIZE
- self.right
;
483 unsafe { Chunk::force_copy(0, self.left, self.right, self) }
;
484 self.right
= N
::USIZE
;
486 unsafe { Chunk::force_copy_to(other.right - count, self.left - count, count, other, self) }
;
488 other
.right
-= count
;
491 /// Update the value at index `index`, returning the old value.
493 /// Panics if `index` is out of bounds.
496 pub fn set(&mut self, index
: usize, value
: A
) -> A
{
497 replace(&mut self[index
], value
)
500 /// Insert a new value at index `index`, shifting all the following values
503 /// Panics if the index is out of bounds.
505 /// Time: O(n) for the number of items shifted
506 pub fn insert(&mut self, index
: usize, value
: A
) {
508 panic
!("Chunk::insert: chunk is full");
510 if index
> self.len() {
511 panic
!("Chunk::insert: index out of bounds");
513 let real_index
= index
+ self.left
;
514 let left_size
= index
;
515 let right_size
= self.right
- real_index
;
516 if self.right
== N
::USIZE
|| (self.left
> 0 && left_size
< right_size
) {
518 Chunk
::force_copy(self.left
, self.left
- 1, left_size
, self);
519 Chunk
::force_write(real_index
- 1, value
, self);
524 Chunk
::force_copy(real_index
, real_index
+ 1, right_size
, self);
525 Chunk
::force_write(real_index
, value
, self);
531 /// Remove the value at index `index`, shifting all the following values to
534 /// Returns the removed value.
536 /// Panics if the index is out of bounds.
538 /// Time: O(n) for the number of items shifted
539 pub fn remove(&mut self, index
: usize) -> A
{
540 if index
>= self.len() {
541 panic
!("Chunk::remove: index out of bounds");
543 let real_index
= index
+ self.left
;
544 let value
= unsafe { Chunk::force_read(real_index, self) }
;
545 let left_size
= index
;
546 let right_size
= self.right
- real_index
- 1;
547 if left_size
< right_size
{
548 unsafe { Chunk::force_copy(self.left, self.left + 1, left_size, self) }
;
551 unsafe { Chunk::force_copy(real_index + 1, real_index, right_size, self) }
;
557 /// Construct an iterator that drains values from the front of the chunk.
558 pub fn drain(&mut self) -> Drain
<'_
, A
, N
> {
559 Drain { chunk: self }
562 /// Discard the contents of the chunk.
565 pub fn clear(&mut self) {
571 /// Get a reference to the contents of the chunk as a slice.
572 pub fn as_slice(&self) -> &[A
] {
575 (&self.data
as *const ManuallyDrop
<N
::SizedType
> as *const A
).add(self.left
),
581 /// Get a reference to the contents of the chunk as a mutable slice.
582 pub fn as_mut_slice(&mut self) -> &mut [A
] {
585 (&mut self.data
as *mut ManuallyDrop
<N
::SizedType
> as *mut A
).add(self.left
),
592 impl<A
, N
> Default
for Chunk
<A
, N
>
596 fn default() -> Self {
601 impl<A
, N
, I
> Index
<I
> for Chunk
<A
, N
>
606 type Output
= I
::Output
;
607 fn index(&self, index
: I
) -> &Self::Output
{
608 self.as_slice().index(index
)
612 impl<A
, N
, I
> IndexMut
<I
> for Chunk
<A
, N
>
617 fn index_mut(&mut self, index
: I
) -> &mut Self::Output
{
618 self.as_mut_slice().index_mut(index
)
622 impl<A
, N
> Debug
for Chunk
<A
, N
>
627 fn fmt(&self, f
: &mut Formatter
) -> Result
<(), Error
> {
628 f
.write_str("Chunk")?
;
629 f
.debug_list().entries(self.iter()).finish()
633 impl<A
, N
> Hash
for Chunk
<A
, N
>
638 fn hash
<H
>(&self, hasher
: &mut H
)
648 impl<A
, N
> PartialEq
for Chunk
<A
, N
>
653 fn eq(&self, other
: &Self) -> bool
{
654 self.len() == other
.len() && self.iter().eq(other
.iter())
658 impl<A
, N
> Eq
for Chunk
<A
, N
>
665 impl<A
, N
> PartialOrd
for Chunk
<A
, N
>
670 fn partial_cmp(&self, other
: &Self) -> Option
<Ordering
> {
671 self.iter().partial_cmp(other
.iter())
675 impl<A
, N
> Ord
for Chunk
<A
, N
>
680 fn cmp(&self, other
: &Self) -> Ordering
{
681 self.iter().cmp(other
.iter())
685 impl<N
> io
::Write
for Chunk
<u8, N
>
689 fn write(&mut self, buf
: &[u8]) -> io
::Result
<usize> {
690 let old_len
= self.len();
691 self.extend(buf
.iter().cloned().take(N
::USIZE
- old_len
));
692 Ok(self.len() - old_len
)
695 fn flush(&mut self) -> io
::Result
<()> {
700 impl<A
, N
> Borrow
<[A
]> for Chunk
<A
, N
>
704 fn borrow(&self) -> &[A
] {
709 impl<A
, N
> BorrowMut
<[A
]> for Chunk
<A
, N
>
713 fn borrow_mut(&mut self) -> &mut [A
] {
718 impl<A
, N
> AsRef
<[A
]> for Chunk
<A
, N
>
722 fn as_ref(&self) -> &[A
] {
727 impl<A
, N
> AsMut
<[A
]> for Chunk
<A
, N
>
731 fn as_mut(&mut self) -> &mut [A
] {
736 impl<A
, N
> Deref
for Chunk
<A
, N
>
742 fn deref(&self) -> &Self::Target
{
747 impl<A
, N
> DerefMut
for Chunk
<A
, N
>
751 fn deref_mut(&mut self) -> &mut Self::Target
{
756 impl<A
, N
> FromIterator
<A
> for Chunk
<A
, N
>
760 fn from_iter
<I
>(it
: I
) -> Self
762 I
: IntoIterator
<Item
= A
>,
764 let mut chunk
= Self::new();
766 chunk
.push_back(item
);
772 impl<'a
, A
, N
> IntoIterator
for &'a Chunk
<A
, N
>
777 type IntoIter
= SliceIter
<'a
, A
>;
778 fn into_iter(self) -> Self::IntoIter
{
783 impl<'a
, A
, N
> IntoIterator
for &'a
mut Chunk
<A
, N
>
787 type Item
= &'a
mut A
;
788 type IntoIter
= SliceIterMut
<'a
, A
>;
789 fn into_iter(self) -> Self::IntoIter
{
794 impl<A
, N
> Extend
<A
> for Chunk
<A
, N
>
798 /// Append the contents of the iterator to the back of the chunk.
800 /// Panics if the chunk exceeds its capacity.
802 /// Time: O(n) for the length of the iterator
803 fn extend
<I
>(&mut self, it
: I
)
805 I
: IntoIterator
<Item
= A
>,
808 self.push_back(item
);
813 impl<'a
, A
, N
> Extend
<&'a A
> for Chunk
<A
, N
>
818 /// Append the contents of the iterator to the back of the chunk.
820 /// Panics if the chunk exceeds its capacity.
822 /// Time: O(n) for the length of the iterator
823 fn extend
<I
>(&mut self, it
: I
)
825 I
: IntoIterator
<Item
= &'a A
>,
828 self.push_back(*item
);
833 pub struct Iter
<A
, N
>
840 impl<A
, N
> Iterator
for Iter
<A
, N
>
845 fn next(&mut self) -> Option
<Self::Item
> {
846 if self.chunk
.is_empty() {
849 Some(self.chunk
.pop_front())
853 fn size_hint(&self) -> (usize, Option
<usize>) {
854 (self.chunk
.len(), Some(self.chunk
.len()))
858 impl<A
, N
> DoubleEndedIterator
for Iter
<A
, N
>
862 fn next_back(&mut self) -> Option
<Self::Item
> {
863 if self.chunk
.is_empty() {
866 Some(self.chunk
.pop_back())
871 impl<A
, N
> ExactSizeIterator
for Iter
<A
, N
> where N
: ChunkLength
<A
> {}
873 impl<A
, N
> FusedIterator
for Iter
<A
, N
> where N
: ChunkLength
<A
> {}
875 impl<A
, N
> IntoIterator
for Chunk
<A
, N
>
880 type IntoIter
= Iter
<A
, N
>;
882 fn into_iter(self) -> Self::IntoIter
{
887 pub struct Drain
<'a
, A
, N
>
890 N
: ChunkLength
<A
> + 'a
,
892 chunk
: &'a
mut Chunk
<A
, N
>,
895 impl<'a
, A
, N
> Iterator
for Drain
<'a
, A
, N
>
898 N
: ChunkLength
<A
> + 'a
,
902 fn next(&mut self) -> Option
<Self::Item
> {
903 if self.chunk
.is_empty() {
906 Some(self.chunk
.pop_front())
910 fn size_hint(&self) -> (usize, Option
<usize>) {
911 (self.chunk
.len(), Some(self.chunk
.len()))
915 impl<'a
, A
, N
> ExactSizeIterator
for Drain
<'a
, A
, N
>
918 N
: ChunkLength
<A
> + 'a
,
922 impl<'a
, A
, N
> FusedIterator
for Drain
<'a
, A
, N
>
925 N
: ChunkLength
<A
> + 'a
,
935 let mut chunk
= Chunk
::<_
, U64
>::new();
937 assert_eq
!(false, chunk
.is_full());
940 assert_eq
!(true, chunk
.is_full());
944 fn push_back_front() {
945 let mut chunk
= Chunk
::<_
, U64
>::new();
949 assert_eq
!(8, chunk
.len());
950 for i
in (0..12).rev() {
953 assert_eq
!(20, chunk
.len());
957 assert_eq
!(32, chunk
.len());
958 let right
: Vec
<i32> = chunk
.into_iter().collect();
959 let left
: Vec
<i32> = (0..32).collect();
960 assert_eq
!(left
, right
);
965 let mut chunk
= Chunk
::<_
, U64
>::new();
970 assert_eq
!(i
, chunk
.pop_front());
976 assert_eq
!(i
, chunk
.pop_back());
982 let mut chunk
= Chunk
::<_
, U64
>::new();
987 let vec
: Vec
<i32> = chunk
.into_iter().collect();
988 assert_eq
!(vec
![3, 4, 5], vec
);
993 let mut chunk
= Chunk
::<_
, U64
>::new();
998 let vec
: Vec
<i32> = chunk
.into_iter().collect();
999 assert_eq
!(vec
![0, 1, 2], vec
);
1004 let mut left
= Chunk
::<_
, U64
>::new();
1008 let right
= left
.split_off(3);
1009 let left_vec
: Vec
<i32> = left
.into_iter().collect();
1010 let right_vec
: Vec
<i32> = right
.into_iter().collect();
1011 assert_eq
!(vec
![0, 1, 2], left_vec
);
1012 assert_eq
!(vec
![3, 4, 5], right_vec
);
1017 let mut left
= Chunk
::<_
, U64
>::new();
1021 let mut right
= Chunk
::<_
, U64
>::new();
1022 for i
in (32..64).rev() {
1023 right
.push_front(i
);
1025 left
.append(&mut right
);
1026 let out_vec
: Vec
<i32> = left
.into_iter().collect();
1027 let should_vec
: Vec
<i32> = (0..64).collect();
1028 assert_eq
!(should_vec
, out_vec
);
1033 let mut chunk
= Chunk
::<_
, U64
>::new();
1037 let out_vec
: Vec
<&i32> = chunk
.iter().collect();
1038 let should_vec_p
: Vec
<i32> = (0..64).collect();
1039 let should_vec
: Vec
<&i32> = should_vec_p
.iter().collect();
1040 assert_eq
!(should_vec
, out_vec
);
1045 let mut chunk
= Chunk
::<_
, U64
>::new();
1049 let out_vec
: Vec
<&mut i32> = chunk
.iter_mut().collect();
1050 let mut should_vec_p
: Vec
<i32> = (0..64).collect();
1051 let should_vec
: Vec
<&mut i32> = should_vec_p
.iter_mut().collect();
1052 assert_eq
!(should_vec
, out_vec
);
1056 fn consuming_iter() {
1057 let mut chunk
= Chunk
::<_
, U64
>::new();
1061 let out_vec
: Vec
<i32> = chunk
.into_iter().collect();
1062 let should_vec
: Vec
<i32> = (0..64).collect();
1063 assert_eq
!(should_vec
, out_vec
);
1067 fn insert_middle() {
1068 let mut chunk
= Chunk
::<_
, U64
>::new();
1075 chunk
.insert(32, 32);
1076 let out_vec
: Vec
<i32> = chunk
.into_iter().collect();
1077 let should_vec
: Vec
<i32> = (0..64).collect();
1078 assert_eq
!(should_vec
, out_vec
);
1083 let mut chunk
= Chunk
::<_
, U64
>::new();
1087 chunk
.insert(63, 63);
1088 let out_vec
: Vec
<i32> = chunk
.into_iter().collect();
1089 let should_vec
: Vec
<i32> = (0..64).collect();
1090 assert_eq
!(should_vec
, out_vec
);
1095 let mut chunk
= Chunk
::<_
, U64
>::new();
1097 chunk
.push_front(64 - i
);
1100 let out_vec
: Vec
<i32> = chunk
.into_iter().collect();
1101 let should_vec
: Vec
<i32> = (0..64).collect();
1102 assert_eq
!(should_vec
, out_vec
);
1107 let mut chunk
= Chunk
::<_
, U64
>::new();
1112 let out_vec
: Vec
<i32> = chunk
.into_iter().collect();
1113 let should_vec
: Vec
<i32> = (0..32).chain(33..64).collect();
1114 assert_eq
!(should_vec
, out_vec
);
1117 use std
::sync
::atomic
::{AtomicUsize, Ordering}
;
1119 struct DropTest
<'a
> {
1120 counter
: &'a AtomicUsize
,
1123 impl<'a
> DropTest
<'a
> {
1124 fn new(counter
: &'a AtomicUsize
) -> Self {
1125 counter
.fetch_add(1, Ordering
::Relaxed
);
1126 DropTest { counter }
1130 impl<'a
> Drop
for DropTest
<'a
> {
1131 fn drop(&mut self) {
1132 self.counter
.fetch_sub(1, Ordering
::Relaxed
);
1138 let counter
= AtomicUsize
::new(0);
1140 let mut chunk
: Chunk
<DropTest
> = Chunk
::new();
1142 chunk
.push_back(DropTest
::new(&counter
))
1145 chunk
.push_front(DropTest
::new(&counter
))
1147 assert_eq
!(40, counter
.load(Ordering
::Relaxed
));
1151 assert_eq
!(30, counter
.load(Ordering
::Relaxed
));
1153 assert_eq
!(0, counter
.load(Ordering
::Relaxed
));