1use crate::inline_array::InlineArray;
10use core::borrow::{Borrow, BorrowMut};
11use core::cmp::Ordering;
12use core::fmt::{Debug, Error, Formatter};
13use core::hash::{Hash, Hasher};
14use core::iter::FromIterator;
15use core::mem::{replace, MaybeUninit};
16use core::ops::{Deref, DerefMut, Index, IndexMut};
17use core::ptr;
18use core::slice::{
19 from_raw_parts, from_raw_parts_mut, Iter as SliceIter, IterMut as SliceIterMut, SliceIndex,
20};
21
22#[cfg(feature = "std")]
23use std::io;
24
25mod iter;
26pub use self::iter::{Drain, Iter};
27
28#[cfg(feature = "refpool")]
29mod refpool;
30
31pub struct Chunk<A, const N: usize> {
94 left: usize,
95 right: usize,
96 data: MaybeUninit<[A; N]>,
97}
98
99impl<A, const N: usize> Drop for Chunk<A, N> {
100 fn drop(&mut self) {
101 unsafe { ptr::drop_in_place(self.as_mut_slice()) }
102 }
103}
104
105impl<A, const N: usize> Clone for Chunk<A, N>
106where
107 A: Clone,
108{
109 fn clone(&self) -> Self {
110 let mut out = Self::new();
111 out.left = self.left;
112 out.right = self.left;
113 for index in self.left..self.right {
114 unsafe { Chunk::force_write(index, (*self.ptr(index)).clone(), &mut out) }
115 out.right = index + 1;
119 }
120 out
121 }
122}
123
124impl<A, const N: usize> Chunk<A, N> {
125 pub const CAPACITY: usize = N;
127
128 pub fn new() -> Self {
130 Self {
131 left: 0,
132 right: 0,
133 data: MaybeUninit::uninit(),
134 }
135 }
136
137 pub fn unit(value: A) -> Self {
139 assert!(Self::CAPACITY >= 1);
140 let mut chunk = Self {
141 left: 0,
142 right: 1,
143 data: MaybeUninit::uninit(),
144 };
145 unsafe {
146 Chunk::force_write(0, value, &mut chunk);
147 }
148 chunk
149 }
150
151 pub fn pair(left: A, right: A) -> Self {
153 assert!(Self::CAPACITY >= 2);
154 let mut chunk = Self {
155 left: 0,
156 right: 2,
157 data: MaybeUninit::uninit(),
158 };
159 unsafe {
160 Chunk::force_write(0, left, &mut chunk);
161 Chunk::force_write(1, right, &mut chunk);
162 }
163 chunk
164 }
165
166 pub fn drain_from(other: &mut Self) -> Self {
171 let other_len = other.len();
172 Self::from_front(other, other_len)
173 }
174
175 pub fn collect_from<I>(iter: &mut I, mut count: usize) -> Self
182 where
183 I: Iterator<Item = A>,
184 {
185 let mut chunk = Self::new();
186 while count > 0 {
187 count -= 1;
188 chunk.push_back(
189 iter.next()
190 .expect("Chunk::collect_from: underfull iterator"),
191 );
192 }
193 chunk
194 }
195
196 pub fn from_front(other: &mut Self, count: usize) -> Self {
201 let other_len = other.len();
202 debug_assert!(count <= other_len);
203 let mut chunk = Self::new();
204 unsafe { Chunk::force_copy_to(other.left, 0, count, other, &mut chunk) };
205 chunk.right = count;
206 other.left += count;
207 chunk
208 }
209
210 pub fn from_back(other: &mut Self, count: usize) -> Self {
215 let other_len = other.len();
216 debug_assert!(count <= other_len);
217 let mut chunk = Self::new();
218 unsafe { Chunk::force_copy_to(other.right - count, 0, count, other, &mut chunk) };
219 chunk.right = count;
220 other.right -= count;
221 chunk
222 }
223
224 #[inline]
226 pub fn len(&self) -> usize {
227 self.right - self.left
228 }
229
230 #[inline]
232 pub fn is_empty(&self) -> bool {
233 self.left == self.right
234 }
235
236 #[inline]
238 pub fn is_full(&self) -> bool {
239 self.left == 0 && self.right == Self::CAPACITY
240 }
241
242 #[inline]
243 unsafe fn ptr(&self, index: usize) -> *const A {
244 (&self.data as *const _ as *const A).add(index)
245 }
246
247 #[inline]
249 unsafe fn mut_ptr(&mut self, index: usize) -> *mut A {
250 (&mut self.data as *mut _ as *mut A).add(index)
251 }
252
253 #[inline]
255 unsafe fn force_read(index: usize, chunk: &mut Self) -> A {
256 chunk.ptr(index).read()
257 }
258
259 #[inline]
262 unsafe fn force_write(index: usize, value: A, chunk: &mut Self) {
263 chunk.mut_ptr(index).write(value)
264 }
265
266 #[inline]
268 unsafe fn force_copy(from: usize, to: usize, count: usize, chunk: &mut Self) {
269 if count > 0 {
270 ptr::copy(chunk.ptr(from), chunk.mut_ptr(to), count)
271 }
272 }
273
274 #[inline]
289 unsafe fn write_from_iter<I>(mut write_index: usize, iter: I, chunk: &mut Self)
290 where
291 I: ExactSizeIterator<Item = A>,
292 {
293 let left = replace(&mut chunk.left, 0);
301 let right = replace(&mut chunk.right, 0);
302 let len = iter.len();
303 let expected_end = write_index + len;
304 for value in iter.take(len) {
305 Chunk::force_write(write_index, value, chunk);
306 write_index += 1;
307 }
308 assert_eq!(
310 expected_end, write_index,
311 "ExactSizeIterator yielded fewer values than advertised",
312 );
313 chunk.left = left;
314 chunk.right = right;
315 }
316
317 #[inline]
319 unsafe fn force_copy_to(
320 from: usize,
321 to: usize,
322 count: usize,
323 chunk: &mut Self,
324 other: &mut Self,
325 ) {
326 if count > 0 {
327 ptr::copy_nonoverlapping(chunk.ptr(from), other.mut_ptr(to), count)
328 }
329 }
330
331 pub fn push_front(&mut self, value: A) {
337 if self.is_full() {
338 panic!("Chunk::push_front: can't push to full chunk");
339 }
340 if self.is_empty() {
341 self.left = N;
342 self.right = N;
343 } else if self.left == 0 {
344 self.left = N - self.right;
345 unsafe { Chunk::force_copy(0, self.left, self.right, self) };
346 self.right = N;
347 }
348 self.left -= 1;
349 unsafe { Chunk::force_write(self.left, value, self) }
350 }
351
352 pub fn push_back(&mut self, value: A) {
358 if self.is_full() {
359 panic!("Chunk::push_back: can't push to full chunk");
360 }
361 if self.is_empty() {
362 self.left = 0;
363 self.right = 0;
364 } else if self.right == N {
365 unsafe { Chunk::force_copy(self.left, 0, self.len(), self) };
366 self.right = N - self.left;
367 self.left = 0;
368 }
369 unsafe { Chunk::force_write(self.right, value, self) }
370 self.right += 1;
371 }
372
373 pub fn pop_front(&mut self) -> A {
379 if self.is_empty() {
380 panic!("Chunk::pop_front: can't pop from empty chunk");
381 } else {
382 let value = unsafe { Chunk::force_read(self.left, self) };
383 self.left += 1;
384 value
385 }
386 }
387
388 pub fn pop_back(&mut self) -> A {
394 if self.is_empty() {
395 panic!("Chunk::pop_back: can't pop from empty chunk");
396 } else {
397 self.right -= 1;
398 unsafe { Chunk::force_read(self.right, self) }
399 }
400 }
401
402 pub fn drop_left(&mut self, index: usize) {
408 if index > 0 {
409 unsafe { ptr::drop_in_place(&mut self[..index]) }
410 self.left += index;
411 }
412 }
413
414 pub fn drop_right(&mut self, index: usize) {
420 if index != self.len() {
421 unsafe { ptr::drop_in_place(&mut self[index..]) }
422 self.right = self.left + index;
423 }
424 }
425
426 pub fn split_off(&mut self, index: usize) -> Self {
434 if index > self.len() {
435 panic!("Chunk::split_off: index out of bounds");
436 }
437 if index == self.len() {
438 return Self::new();
439 }
440 let mut right_chunk = Self::new();
441 let start = self.left + index;
442 let len = self.right - start;
443 unsafe { Chunk::force_copy_to(start, 0, len, self, &mut right_chunk) };
444 right_chunk.right = len;
445 self.right = start;
446 right_chunk
447 }
448
449 pub fn append(&mut self, other: &mut Self) {
455 let self_len = self.len();
456 let other_len = other.len();
457 if self_len + other_len > N {
458 panic!("Chunk::append: chunk size overflow");
459 }
460 if self.right + other_len > N {
461 unsafe { Chunk::force_copy(self.left, 0, self_len, self) };
462 self.right -= self.left;
463 self.left = 0;
464 }
465 unsafe { Chunk::force_copy_to(other.left, self.right, other_len, other, self) };
466 self.right += other_len;
467 other.left = 0;
468 other.right = 0;
469 }
470
471 pub fn drain_from_front(&mut self, other: &mut Self, count: usize) {
479 let self_len = self.len();
480 let other_len = other.len();
481 assert!(self_len + count <= N);
482 assert!(other_len >= count);
483 if self.right + count > N {
484 unsafe { Chunk::force_copy(self.left, 0, self_len, self) };
485 self.right -= self.left;
486 self.left = 0;
487 }
488 unsafe { Chunk::force_copy_to(other.left, self.right, count, other, self) };
489 self.right += count;
490 other.left += count;
491 }
492
493 pub fn drain_from_back(&mut self, other: &mut Self, count: usize) {
501 let self_len = self.len();
502 let other_len = other.len();
503 assert!(self_len + count <= N);
504 assert!(other_len >= count);
505 if self.left < count {
506 unsafe { Chunk::force_copy(self.left, N - self_len, self_len, self) };
507 self.left = N - self_len;
508 self.right = N;
509 }
510 unsafe { Chunk::force_copy_to(other.right - count, self.left - count, count, other, self) };
511 self.left -= count;
512 other.right -= count;
513 }
514
515 pub fn set(&mut self, index: usize, value: A) -> A {
521 replace(&mut self[index], value)
522 }
523
524 pub fn insert(&mut self, index: usize, value: A) {
531 if self.is_full() {
532 panic!("Chunk::insert: chunk is full");
533 }
534 if index > self.len() {
535 panic!("Chunk::insert: index out of bounds");
536 }
537 let real_index = index + self.left;
538 let left_size = index;
539 let right_size = self.right - real_index;
540 if self.right == N || (self.left > 0 && left_size < right_size) {
541 unsafe {
542 Chunk::force_copy(self.left, self.left - 1, left_size, self);
543 Chunk::force_write(real_index - 1, value, self);
544 }
545 self.left -= 1;
546 } else {
547 unsafe {
548 Chunk::force_copy(real_index, real_index + 1, right_size, self);
549 Chunk::force_write(real_index, value, self);
550 }
551 self.right += 1;
552 }
553 }
554
555 pub fn insert_ordered(&mut self, value: A)
574 where
575 A: Ord,
576 {
577 if self.is_full() {
578 panic!("Chunk::insert: chunk is full");
579 }
580 match self.binary_search(&value) {
581 Ok(index) => self.insert(index, value),
582 Err(index) => self.insert(index, value),
583 }
584 }
585
586 pub fn insert_from<Iterable, I>(&mut self, index: usize, iter: Iterable)
596 where
597 Iterable: IntoIterator<Item = A, IntoIter = I>,
598 I: ExactSizeIterator<Item = A>,
599 {
600 let iter = iter.into_iter();
601 let insert_size = iter.len();
602 if self.len() + insert_size > Self::CAPACITY {
603 panic!(
604 "Chunk::insert_from: chunk cannot fit {} elements",
605 insert_size
606 );
607 }
608 if index > self.len() {
609 panic!("Chunk::insert_from: index out of bounds");
610 }
611 let real_index = index + self.left;
612 let left_size = index;
613 let right_size = self.right - real_index;
614 if self.right == N || (self.left >= insert_size && left_size < right_size) {
615 unsafe {
616 Chunk::force_copy(self.left, self.left - insert_size, left_size, self);
617 let write_index = real_index - insert_size;
618 Chunk::write_from_iter(write_index, iter, self);
619 }
620 self.left -= insert_size;
621 } else if self.left == 0 || (self.right + insert_size <= Self::CAPACITY) {
622 unsafe {
623 Chunk::force_copy(real_index, real_index + insert_size, right_size, self);
624 let write_index = real_index;
625 Chunk::write_from_iter(write_index, iter, self);
626 }
627 self.right += insert_size;
628 } else {
629 unsafe {
630 Chunk::force_copy(self.left, 0, left_size, self);
631 Chunk::force_copy(real_index, left_size + insert_size, right_size, self);
632 let write_index = left_size;
633 Chunk::write_from_iter(write_index, iter, self);
634 }
635 self.right -= self.left;
636 self.right += insert_size;
637 self.left = 0;
638 }
639 }
640
641 pub fn remove(&mut self, index: usize) -> A {
650 if index >= self.len() {
651 panic!("Chunk::remove: index out of bounds");
652 }
653 let real_index = index + self.left;
654 let value = unsafe { Chunk::force_read(real_index, self) };
655 let left_size = index;
656 let right_size = self.right - real_index - 1;
657 if left_size < right_size {
658 unsafe { Chunk::force_copy(self.left, self.left + 1, left_size, self) };
659 self.left += 1;
660 } else {
661 unsafe { Chunk::force_copy(real_index + 1, real_index, right_size, self) };
662 self.right -= 1;
663 }
664 value
665 }
666
667 pub fn drain(&mut self) -> Drain<'_, A, N> {
669 Drain { chunk: self }
670 }
671
672 pub fn clear(&mut self) {
676 unsafe { ptr::drop_in_place(self.as_mut_slice()) }
677 self.left = 0;
678 self.right = 0;
679 }
680
681 pub fn as_slice(&self) -> &[A] {
683 unsafe {
684 from_raw_parts(
685 (&self.data as *const MaybeUninit<[A; N]> as *const A).add(self.left),
686 self.len(),
687 )
688 }
689 }
690
691 pub fn as_mut_slice(&mut self) -> &mut [A] {
693 unsafe {
694 from_raw_parts_mut(
695 (&mut self.data as *mut MaybeUninit<[A; N]> as *mut A).add(self.left),
696 self.len(),
697 )
698 }
699 }
700}
701
702impl<A, const N: usize> Default for Chunk<A, N> {
703 fn default() -> Self {
704 Self::new()
705 }
706}
707
708impl<A, I, const N: usize> Index<I> for Chunk<A, N>
709where
710 I: SliceIndex<[A]>,
711{
712 type Output = I::Output;
713 fn index(&self, index: I) -> &Self::Output {
714 self.as_slice().index(index)
715 }
716}
717
718impl<A, I, const N: usize> IndexMut<I> for Chunk<A, N>
719where
720 I: SliceIndex<[A]>,
721{
722 fn index_mut(&mut self, index: I) -> &mut Self::Output {
723 self.as_mut_slice().index_mut(index)
724 }
725}
726
727impl<A, const N: usize> Debug for Chunk<A, N>
728where
729 A: Debug,
730{
731 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
732 f.write_str("Chunk")?;
733 f.debug_list().entries(self.iter()).finish()
734 }
735}
736
737impl<A, const N: usize> Hash for Chunk<A, N>
738where
739 A: Hash,
740{
741 fn hash<H>(&self, hasher: &mut H)
742 where
743 H: Hasher,
744 {
745 for item in self {
746 item.hash(hasher)
747 }
748 }
749}
750
751impl<A, Slice, const N: usize> PartialEq<Slice> for Chunk<A, N>
752where
753 Slice: Borrow<[A]>,
754 A: PartialEq,
755{
756 fn eq(&self, other: &Slice) -> bool {
757 self.as_slice() == other.borrow()
758 }
759}
760
761impl<A, const N: usize> Eq for Chunk<A, N> where A: Eq {}
762
763impl<A, const N: usize> PartialOrd for Chunk<A, N>
764where
765 A: PartialOrd,
766{
767 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
768 self.iter().partial_cmp(other.iter())
769 }
770}
771
772impl<A, const N: usize> Ord for Chunk<A, N>
773where
774 A: Ord,
775{
776 fn cmp(&self, other: &Self) -> Ordering {
777 self.iter().cmp(other.iter())
778 }
779}
780
781#[cfg(feature = "std")]
782impl<const N: usize> io::Write for Chunk<u8, N> {
783 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
784 let old_len = self.len();
785 self.extend(buf.iter().cloned().take(N - old_len));
786 Ok(self.len() - old_len)
787 }
788
789 fn flush(&mut self) -> io::Result<()> {
790 Ok(())
791 }
792}
793
794#[cfg(feature = "std")]
795impl<const N: usize> std::io::Read for Chunk<u8, N> {
796 fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
797 let read_size = buf.len().min(self.len());
798 if read_size == 0 {
799 Ok(0)
800 } else {
801 for p in buf.iter_mut().take(read_size) {
802 *p = self.pop_front();
803 }
804 Ok(read_size)
805 }
806 }
807}
808
809impl<A, T, const N: usize> From<InlineArray<A, T>> for Chunk<A, N> {
810 #[inline]
811 fn from(mut array: InlineArray<A, T>) -> Self {
812 Self::from(&mut array)
813 }
814}
815
816impl<'a, A, T, const N: usize> From<&'a mut InlineArray<A, T>> for Chunk<A, N> {
817 fn from(array: &mut InlineArray<A, T>) -> Self {
818 assert!(
820 InlineArray::<A, T>::CAPACITY <= Self::CAPACITY || array.len() <= Self::CAPACITY,
821 "CAPACITY too small"
822 );
823 let mut out = Self::new();
824 out.left = 0;
825 out.right = array.len();
826 unsafe {
827 ptr::copy_nonoverlapping(array.data(), out.mut_ptr(0), out.right);
828 *array.len_mut() = 0;
829 }
830 out
831 }
832}
833
834impl<A, const N: usize> Borrow<[A]> for Chunk<A, N> {
835 fn borrow(&self) -> &[A] {
836 self.as_slice()
837 }
838}
839
840impl<A, const N: usize> BorrowMut<[A]> for Chunk<A, N> {
841 fn borrow_mut(&mut self) -> &mut [A] {
842 self.as_mut_slice()
843 }
844}
845
846impl<A, const N: usize> AsRef<[A]> for Chunk<A, N> {
847 fn as_ref(&self) -> &[A] {
848 self.as_slice()
849 }
850}
851
852impl<A, const N: usize> AsMut<[A]> for Chunk<A, N> {
853 fn as_mut(&mut self) -> &mut [A] {
854 self.as_mut_slice()
855 }
856}
857
858impl<A, const N: usize> Deref for Chunk<A, N> {
859 type Target = [A];
860
861 fn deref(&self) -> &Self::Target {
862 self.as_slice()
863 }
864}
865
866impl<A, const N: usize> DerefMut for Chunk<A, N> {
867 fn deref_mut(&mut self) -> &mut Self::Target {
868 self.as_mut_slice()
869 }
870}
871
872impl<A, const N: usize> FromIterator<A> for Chunk<A, N> {
873 fn from_iter<I>(it: I) -> Self
874 where
875 I: IntoIterator<Item = A>,
876 {
877 let mut chunk = Self::new();
878 for item in it {
879 chunk.push_back(item);
880 }
881 chunk
882 }
883}
884
885impl<'a, A, const N: usize> IntoIterator for &'a Chunk<A, N> {
886 type Item = &'a A;
887 type IntoIter = SliceIter<'a, A>;
888 fn into_iter(self) -> Self::IntoIter {
889 self.iter()
890 }
891}
892
893impl<'a, A, const N: usize> IntoIterator for &'a mut Chunk<A, N> {
894 type Item = &'a mut A;
895 type IntoIter = SliceIterMut<'a, A>;
896 fn into_iter(self) -> Self::IntoIter {
897 self.iter_mut()
898 }
899}
900
901impl<A, const N: usize> Extend<A> for Chunk<A, N> {
902 fn extend<I>(&mut self, it: I)
908 where
909 I: IntoIterator<Item = A>,
910 {
911 for item in it {
912 self.push_back(item);
913 }
914 }
915}
916
917impl<'a, A, const N: usize> Extend<&'a A> for Chunk<A, N>
918where
919 A: 'a + Copy,
920{
921 fn extend<I>(&mut self, it: I)
927 where
928 I: IntoIterator<Item = &'a A>,
929 {
930 for item in it {
931 self.push_back(*item);
932 }
933 }
934}
935
936impl<A, const N: usize> IntoIterator for Chunk<A, N> {
937 type Item = A;
938 type IntoIter = Iter<A, N>;
939
940 fn into_iter(self) -> Self::IntoIter {
941 Iter { chunk: self }
942 }
943}
944
945#[cfg(test)]
946#[rustfmt::skip]
947mod test {
948 use super::*;
949
950 #[test]
951 #[should_panic(expected = "Chunk::push_back: can't push to full chunk")]
952 fn issue_11_testcase1d() {
953 let mut chunk = Chunk::<usize, 2>::pair(123, 456);
954 chunk.push_back(789);
955 }
956
957 #[test]
958 #[should_panic(expected = "CAPACITY too small")]
959 fn issue_11_testcase2a() {
960 let mut from = InlineArray::<u8, [u8; 256]>::new();
961 from.push(1);
962
963 let _ = Chunk::<u8, 0>::from(from);
964 }
965
966 #[test]
967 fn issue_11_testcase2b() {
968 let mut from = InlineArray::<u8, [u8; 256]>::new();
969 from.push(1);
970
971 let _ = Chunk::<u8, 1>::from(from);
972 }
973
974 struct DropDetector(u32);
975
976 impl DropDetector {
977 fn new(num: u32) -> Self {
978 DropDetector(num)
979 }
980 }
981
982 impl Drop for DropDetector {
983 fn drop(&mut self) {
984 assert!(self.0 == 42 || self.0 == 43);
985 }
986 }
987
988 impl Clone for DropDetector {
989 fn clone(&self) -> Self {
990 if self.0 == 42 {
991 panic!("panic on clone")
992 }
993 DropDetector::new(self.0)
994 }
995 }
996
997 #[test]
999 fn issue_11_testcase3a() {
1000 let mut chunk = Chunk::<DropDetector, 3>::new();
1001 chunk.push_back(DropDetector::new(42));
1002 chunk.push_back(DropDetector::new(42));
1003 chunk.push_back(DropDetector::new(43));
1004 let _ = chunk.pop_front();
1005
1006 let _ = std::panic::catch_unwind(|| {
1007 let _ = chunk.clone();
1008 });
1009 }
1010
1011 struct PanickingIterator {
1012 current: u32,
1013 panic_at: u32,
1014 len: usize,
1015 }
1016
1017 impl Iterator for PanickingIterator {
1018 type Item = DropDetector;
1019
1020 fn next(&mut self) -> Option<Self::Item> {
1021 let num = self.current;
1022
1023 if num == self.panic_at {
1024 panic!("panicking index")
1025 }
1026
1027 self.current += 1;
1028 Some(DropDetector::new(num))
1029 }
1030
1031 fn size_hint(&self) -> (usize, Option<usize>) {
1032 (self.len, Some(self.len))
1033 }
1034 }
1035
1036 impl ExactSizeIterator for PanickingIterator {}
1037
1038 #[test]
1039 fn issue_11_testcase3b() {
1040 let _ = std::panic::catch_unwind(|| {
1041 let mut chunk = Chunk::<DropDetector, 5>::new();
1042 chunk.push_back(DropDetector::new(1));
1043 chunk.push_back(DropDetector::new(2));
1044 chunk.push_back(DropDetector::new(3));
1045
1046 chunk.insert_from(
1047 1,
1048 PanickingIterator {
1049 current: 1,
1050 panic_at: 1,
1051 len: 1,
1052 },
1053 );
1054 });
1055 }
1056
1057 struct FakeSizeIterator { reported: usize, actual: usize }
1058 impl Iterator for FakeSizeIterator {
1059 type Item = u8;
1060 fn next(&mut self) -> Option<Self::Item> {
1061 if self.actual == 0 {
1062 None
1063 } else {
1064 self.actual -= 1;
1065 Some(1)
1066 }
1067 }
1068
1069 fn size_hint(&self) -> (usize, Option<usize>) {
1070 (self.reported, Some(self.reported))
1071 }
1072 }
1073
1074 impl ExactSizeIterator for FakeSizeIterator {
1075 fn len(&self) -> usize {
1076 self.reported
1077 }
1078 }
1079
1080 #[test]
1081 fn iterator_too_long() {
1082 let mut chunk = Chunk::<u8, 5>::new();
1083 chunk.push_back(0);
1084 chunk.push_back(1);
1085 chunk.push_back(2);
1086 chunk.insert_from(1, FakeSizeIterator { reported: 1, actual: 10 });
1087
1088 let mut chunk = Chunk::<u8, 5>::new();
1089 chunk.push_back(1);
1090 chunk.insert_from(0, FakeSizeIterator { reported: 1, actual: 10 });
1091
1092 let mut chunk = Chunk::<u8, 5>::new();
1093 chunk.insert_from(0, FakeSizeIterator { reported: 1, actual: 10 });
1094 }
1095
1096 #[test]
1097 #[should_panic(expected = "ExactSizeIterator yielded fewer values than advertised")]
1098 fn iterator_too_short1() {
1099 let mut chunk = Chunk::<u8, 5>::new();
1100 chunk.push_back(0);
1101 chunk.push_back(1);
1102 chunk.push_back(2);
1103 chunk.insert_from(1, FakeSizeIterator { reported: 2, actual: 0 });
1104 }
1105
1106 #[test]
1107 #[should_panic(expected = "ExactSizeIterator yielded fewer values than advertised")]
1108 fn iterator_too_short2() {
1109 let mut chunk = Chunk::<u8, 5>::new();
1110 chunk.push_back(1);
1111 chunk.insert_from(1, FakeSizeIterator { reported: 4, actual: 2 });
1112 }
1113
1114 #[test]
1115 fn is_full() {
1116 let mut chunk = Chunk::<_, 64>::new();
1117 for i in 0..64 {
1118 assert_eq!(false, chunk.is_full());
1119 chunk.push_back(i);
1120 }
1121 assert_eq!(true, chunk.is_full());
1122 }
1123
1124 #[test]
1125 fn push_back_front() {
1126 let mut chunk = Chunk::<_, 64>::new();
1127 for i in 12..20 {
1128 chunk.push_back(i);
1129 }
1130 assert_eq!(8, chunk.len());
1131 for i in (0..12).rev() {
1132 chunk.push_front(i);
1133 }
1134 assert_eq!(20, chunk.len());
1135 for i in 20..32 {
1136 chunk.push_back(i);
1137 }
1138 assert_eq!(32, chunk.len());
1139 let right: Vec<i32> = chunk.into_iter().collect();
1140 let left: Vec<i32> = (0..32).collect();
1141 assert_eq!(left, right);
1142 }
1143
1144 #[test]
1145 fn push_and_pop() {
1146 let mut chunk = Chunk::<_, 64>::new();
1147 for i in 0..64 {
1148 chunk.push_back(i);
1149 }
1150 for i in 0..64 {
1151 assert_eq!(i, chunk.pop_front());
1152 }
1153 for i in 0..64 {
1154 chunk.push_front(i);
1155 }
1156 for i in 0..64 {
1157 assert_eq!(i, chunk.pop_back());
1158 }
1159 }
1160
1161 #[test]
1162 fn drop_left() {
1163 let mut chunk = Chunk::<_, 64>::new();
1164 for i in 0..6 {
1165 chunk.push_back(i);
1166 }
1167 chunk.drop_left(3);
1168 let vec: Vec<i32> = chunk.into_iter().collect();
1169 assert_eq!(vec![3, 4, 5], vec);
1170 }
1171
1172 #[test]
1173 fn drop_right() {
1174 let mut chunk = Chunk::<_, 64>::new();
1175 for i in 0..6 {
1176 chunk.push_back(i);
1177 }
1178 chunk.drop_right(3);
1179 let vec: Vec<i32> = chunk.into_iter().collect();
1180 assert_eq!(vec![0, 1, 2], vec);
1181 }
1182
1183 #[test]
1184 fn split_off() {
1185 let mut left = Chunk::<_, 64>::new();
1186 for i in 0..6 {
1187 left.push_back(i);
1188 }
1189 let right = left.split_off(3);
1190 let left_vec: Vec<i32> = left.into_iter().collect();
1191 let right_vec: Vec<i32> = right.into_iter().collect();
1192 assert_eq!(vec![0, 1, 2], left_vec);
1193 assert_eq!(vec![3, 4, 5], right_vec);
1194 }
1195
1196 #[test]
1197 fn append() {
1198 let mut left = Chunk::<_, 64>::new();
1199 for i in 0..32 {
1200 left.push_back(i);
1201 }
1202 let mut right = Chunk::<_, 64>::new();
1203 for i in (32..64).rev() {
1204 right.push_front(i);
1205 }
1206 left.append(&mut right);
1207 let out_vec: Vec<i32> = left.into_iter().collect();
1208 let should_vec: Vec<i32> = (0..64).collect();
1209 assert_eq!(should_vec, out_vec);
1210 }
1211
1212 #[test]
1213 fn ref_iter() {
1214 let mut chunk = Chunk::<_, 64>::new();
1215 for i in 0..64 {
1216 chunk.push_back(i);
1217 }
1218 let out_vec: Vec<&i32> = chunk.iter().collect();
1219 let should_vec_p: Vec<i32> = (0..64).collect();
1220 let should_vec: Vec<&i32> = should_vec_p.iter().collect();
1221 assert_eq!(should_vec, out_vec);
1222 }
1223
1224 #[test]
1225 fn mut_ref_iter() {
1226 let mut chunk = Chunk::<_, 64>::new();
1227 for i in 0..64 {
1228 chunk.push_back(i);
1229 }
1230 let out_vec: Vec<&mut i32> = chunk.iter_mut().collect();
1231 let mut should_vec_p: Vec<i32> = (0..64).collect();
1232 let should_vec: Vec<&mut i32> = should_vec_p.iter_mut().collect();
1233 assert_eq!(should_vec, out_vec);
1234 }
1235
1236 #[test]
1237 fn consuming_iter() {
1238 let mut chunk = Chunk::<_, 64>::new();
1239 for i in 0..64 {
1240 chunk.push_back(i);
1241 }
1242 let out_vec: Vec<i32> = chunk.into_iter().collect();
1243 let should_vec: Vec<i32> = (0..64).collect();
1244 assert_eq!(should_vec, out_vec);
1245 }
1246
1247 #[test]
1248 fn insert_middle() {
1249 let mut chunk = Chunk::<_, 64>::new();
1250 for i in 0..32 {
1251 chunk.push_back(i);
1252 }
1253 for i in 33..64 {
1254 chunk.push_back(i);
1255 }
1256 chunk.insert(32, 32);
1257 let out_vec: Vec<i32> = chunk.into_iter().collect();
1258 let should_vec: Vec<i32> = (0..64).collect();
1259 assert_eq!(should_vec, out_vec);
1260 }
1261
1262 #[test]
1263 fn insert_back() {
1264 let mut chunk = Chunk::<_, 64>::new();
1265 for i in 0..63 {
1266 chunk.push_back(i);
1267 }
1268 chunk.insert(63, 63);
1269 let out_vec: Vec<i32> = chunk.into_iter().collect();
1270 let should_vec: Vec<i32> = (0..64).collect();
1271 assert_eq!(should_vec, out_vec);
1272 }
1273
1274 #[test]
1275 fn insert_front() {
1276 let mut chunk = Chunk::<_, 64>::new();
1277 for i in 1..64 {
1278 chunk.push_front(64 - i);
1279 }
1280 chunk.insert(0, 0);
1281 let out_vec: Vec<i32> = chunk.into_iter().collect();
1282 let should_vec: Vec<i32> = (0..64).collect();
1283 assert_eq!(should_vec, out_vec);
1284 }
1285
1286 #[test]
1287 fn remove_value() {
1288 let mut chunk = Chunk::<_, 64>::new();
1289 for i in 0..64 {
1290 chunk.push_back(i);
1291 }
1292 chunk.remove(32);
1293 let out_vec: Vec<i32> = chunk.into_iter().collect();
1294 let should_vec: Vec<i32> = (0..32).chain(33..64).collect();
1295 assert_eq!(should_vec, out_vec);
1296 }
1297
1298 use crate::tests::DropTest;
1299 use std::sync::atomic::{AtomicUsize, Ordering};
1300
1301 #[test]
1302 fn dropping() {
1303 let counter = AtomicUsize::new(0);
1304 {
1305 let mut chunk: Chunk<DropTest<'_>, 64> = Chunk::new();
1306 for _i in 0..20 {
1307 chunk.push_back(DropTest::new(&counter))
1308 }
1309 for _i in 0..20 {
1310 chunk.push_front(DropTest::new(&counter))
1311 }
1312 assert_eq!(40, counter.load(Ordering::Relaxed));
1313 for _i in 0..10 {
1314 chunk.pop_back();
1315 }
1316 assert_eq!(30, counter.load(Ordering::Relaxed));
1317 }
1318 assert_eq!(0, counter.load(Ordering::Relaxed));
1319 }
1320
1321 #[test]
1322 #[should_panic(expected = "assertion failed: Self::CAPACITY >= 1")]
1323 fn unit_on_empty() {
1324 Chunk::<usize, 0>::unit(1);
1325 }
1326
1327 #[test]
1328 #[should_panic(expected = "assertion failed: Self::CAPACITY >= 2")]
1329 fn pair_on_empty() {
1330 Chunk::<usize, 0>::pair(1, 2);
1331 }
1332}