sized_chunks/sized_chunk/
mod.rs

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/.
4
5//! A fixed capacity smart array.
6//!
7//! See [`Chunk`](struct.Chunk.html)
8
9use 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
31/// A fixed capacity smart array.
32///
33/// An inline array of items with a variable length but a fixed, preallocated
34/// capacity given by the `N` type.
35///
36/// It's 'smart' because it's able to reorganise its contents based on expected
37/// behaviour. If you construct one using `push_back`, it will be laid out like
38/// a `Vec` with space at the end. If you `push_front` it will start filling in
39/// values from the back instead of the front, so that you still get linear time
40/// push as long as you don't reverse direction. If you do, and there's no room
41/// at the end you're pushing to, it'll shift its contents over to the other
42/// side, creating more space to push into. This technique is tuned for
43/// `Chunk`'s expected use case in [im::Vector]: usually, chunks always see
44/// either `push_front` or `push_back`, but not both unless they move around
45/// inside the tree, in which case they're able to reorganise themselves with
46/// reasonable efficiency to suit their new usage patterns.
47///
48/// It maintains a `left` index and a `right` index instead of a simple length
49/// counter in order to accomplish this, much like a ring buffer would, except
50/// that the `Chunk` keeps all its items sequentially in memory so that you can
51/// always get a `&[A]` slice for them, at the price of the occasional
52/// reordering operation. The allocated size of a `Chunk` is thus `usize` * 2 +
53/// `A` * `N`.
54///
55/// This technique also lets us choose to shift the shortest side to account for
56/// the inserted or removed element when performing insert and remove
57/// operations, unlike `Vec` where you always need to shift the right hand side.
58///
59/// Unlike a `Vec`, the `Chunk` has a fixed capacity and cannot grow beyond it.
60/// Being intended for low level use, it expects you to know or test whether
61/// you're pushing to a full array, and has an API more geared towards panics
62/// than returning `Option`s, on the assumption that you know what you're doing.
63/// Of course, if you don't, you can expect it to panic immediately rather than
64/// do something undefined and usually bad.
65///
66/// ## Isn't this just a less efficient ring buffer?
67///
68/// You might be wondering why you would want to use this data structure rather
69/// than a [`RingBuffer`][RingBuffer], which is similar but doesn't need to
70/// shift its content around when it hits the sides of the allocated buffer. The
71/// answer is that `Chunk` can be dereferenced into a slice, while a ring buffer
72/// can not. You'll also save a few cycles on index lookups, as a `Chunk`'s data
73/// is guaranteed to be contiguous in memory, so there's no need to remap logical
74/// indices to a ring buffer's physical layout.
75///
76/// # Examples
77///
78/// ```rust
79/// # use sized_chunks::Chunk;
80/// // Construct a chunk with a 64 item capacity
81/// let mut chunk = Chunk::<i32, 64>::new();
82/// // Fill it with descending numbers
83/// chunk.extend((0..64).rev());
84/// // It derefs to a slice so we can use standard slice methods
85/// chunk.sort();
86/// // It's got all the amenities like `FromIterator` and `Eq`
87/// let expected: Chunk<i32, 64> = (0..64).collect();
88/// assert_eq!(expected, chunk);
89/// ```
90///
91/// [im::Vector]: https://docs.rs/im/latest/im/vector/enum.Vector.html
92/// [RingBuffer]: ../ring_buffer/struct.RingBuffer.html
93pub 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            // Panic safety, move the right index to cover only the really initialized things. This
116            // way we don't try to drop uninitialized, but also don't leak if we panic in the
117            // middle.
118            out.right = index + 1;
119        }
120        out
121    }
122}
123
124impl<A, const N: usize> Chunk<A, N> {
125    /// The maximum number of elements this `Chunk` can contain.
126    pub const CAPACITY: usize = N;
127
128    /// Construct a new empty chunk.
129    pub fn new() -> Self {
130        Self {
131            left: 0,
132            right: 0,
133            data: MaybeUninit::uninit(),
134        }
135    }
136
137    /// Construct a new chunk with one item.
138    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    /// Construct a new chunk with two items.
152    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    /// Construct a new chunk and move every item from `other` into the new
167    /// chunk.
168    ///
169    /// Time: O(n)
170    pub fn drain_from(other: &mut Self) -> Self {
171        let other_len = other.len();
172        Self::from_front(other, other_len)
173    }
174
175    /// Construct a new chunk and populate it by taking `count` items from the
176    /// iterator `iter`.
177    ///
178    /// Panics if the iterator contains less than `count` items.
179    ///
180    /// Time: O(n)
181    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    /// Construct a new chunk and populate it by taking `count` items from the
197    /// front of `other`.
198    ///
199    /// Time: O(n) for the number of items moved
200    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    /// Construct a new chunk and populate it by taking `count` items from the
211    /// back of `other`.
212    ///
213    /// Time: O(n) for the number of items moved
214    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    /// Get the length of the chunk.
225    #[inline]
226    pub fn len(&self) -> usize {
227        self.right - self.left
228    }
229
230    /// Test if the chunk is empty.
231    #[inline]
232    pub fn is_empty(&self) -> bool {
233        self.left == self.right
234    }
235
236    /// Test if the chunk is at capacity.
237    #[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    /// It has no bounds checks
248    #[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    /// Copy the value at an index, discarding ownership of the copied value
254    #[inline]
255    unsafe fn force_read(index: usize, chunk: &mut Self) -> A {
256        chunk.ptr(index).read()
257    }
258
259    /// Write a value at an index without trying to drop what's already there.
260    /// It has no bounds checks.
261    #[inline]
262    unsafe fn force_write(index: usize, value: A, chunk: &mut Self) {
263        chunk.mut_ptr(index).write(value)
264    }
265
266    /// Copy a range within a chunk
267    #[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    /// Write values from iterator into range starting at write_index.
275    ///
276    /// Will overwrite values at the relevant range without dropping even in case the values were
277    /// already initialized (it is expected they are empty). Does not update the left or right
278    /// index.
279    ///
280    /// # Safety
281    ///
282    /// Range checks must already have been performed.
283    ///
284    /// # Panics
285    ///
286    /// If the iterator panics, the chunk becomes conceptually empty and will leak any previous
287    /// elements (even the ones outside the range).
288    #[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        // Panic safety. We make the array conceptually empty, so we never ever drop anything that
294        // is unitialized. We do so because we expect to be called when there's a potential "hole"
295        // in the array that makes the space for the new elements to be written. We return it back
296        // to original when everything goes fine, but leak any elements on panic. This is bad, but
297        // better than dropping non-existing stuff.
298        //
299        // Should we worry about some better panic recovery than this?
300        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        // Oops, we have a hole in here now. That would be bad, give up.
309        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    /// Copy a range between chunks
318    #[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    /// Push an item to the front of the chunk.
332    ///
333    /// Panics if the capacity of the chunk is exceeded.
334    ///
335    /// Time: O(1) if there's room at the front, O(n) otherwise
336    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    /// Push an item to the back of the chunk.
353    ///
354    /// Panics if the capacity of the chunk is exceeded.
355    ///
356    /// Time: O(1) if there's room at the back, O(n) otherwise
357    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    /// Pop an item off the front of the chunk.
374    ///
375    /// Panics if the chunk is empty.
376    ///
377    /// Time: O(1)
378    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    /// Pop an item off the back of the chunk.
389    ///
390    /// Panics if the chunk is empty.
391    ///
392    /// Time: O(1)
393    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    /// Discard all items up to but not including `index`.
403    ///
404    /// Panics if `index` is out of bounds.
405    ///
406    /// Time: O(n) for the number of items dropped
407    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    /// Discard all items from `index` onward.
415    ///
416    /// Panics if `index` is out of bounds.
417    ///
418    /// Time: O(n) for the number of items dropped
419    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    /// Split a chunk into two, the original chunk containing
427    /// everything up to `index` and the returned chunk containing
428    /// everything from `index` onwards.
429    ///
430    /// Panics if `index` is out of bounds.
431    ///
432    /// Time: O(n) for the number of items in the new chunk
433    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    /// Remove all items from `other` and append them to the back of `self`.
450    ///
451    /// Panics if the capacity of the chunk is exceeded.
452    ///
453    /// Time: O(n) for the number of items moved
454    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    /// Remove `count` items from the front of `other` and append them to the
472    /// back of `self`.
473    ///
474    /// Panics if `self` doesn't have `count` items left, or if `other` has
475    /// fewer than `count` items.
476    ///
477    /// Time: O(n) for the number of items moved
478    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    /// Remove `count` items from the back of `other` and append them to the
494    /// front of `self`.
495    ///
496    /// Panics if `self` doesn't have `count` items left, or if `other` has
497    /// fewer than `count` items.
498    ///
499    /// Time: O(n) for the number of items moved
500    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    /// Update the value at index `index`, returning the old value.
516    ///
517    /// Panics if `index` is out of bounds.
518    ///
519    /// Time: O(1)
520    pub fn set(&mut self, index: usize, value: A) -> A {
521        replace(&mut self[index], value)
522    }
523
524    /// Insert a new value at index `index`, shifting all the following values
525    /// to the right.
526    ///
527    /// Panics if the index is out of bounds or the chunk is full.
528    ///
529    /// Time: O(n) for the number of elements shifted
530    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    /// Insert a new value into the chunk in sorted order.
556    ///
557    /// This assumes every element of the chunk is already in sorted order.
558    /// If not, the value will still be inserted but the ordering is not
559    /// guaranteed.
560    ///
561    /// Time: O(log n) to find the insert position, then O(n) for the number
562    /// of elements shifted.
563    ///
564    /// # Examples
565    ///
566    /// ```rust
567    /// # use std::iter::FromIterator;
568    /// # use sized_chunks::Chunk;
569    /// let mut chunk = Chunk::<i32, 64>::from_iter(0..5);
570    /// chunk.insert_ordered(3);
571    /// assert_eq!(&[0, 1, 2, 3, 3, 4], chunk.as_slice());
572    /// ```
573    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    /// Insert multiple values at index `index`, shifting all the following values
587    /// to the right.
588    ///
589    /// Panics if the index is out of bounds or the chunk doesn't have room for
590    /// all the values.
591    ///
592    /// Time: O(m+n) where m is the number of elements inserted and n is the number
593    /// of elements following the insertion index. Calling `insert`
594    /// repeatedly would be O(m*n).
595    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    /// Remove the value at index `index`, shifting all the following values to
642    /// the left.
643    ///
644    /// Returns the removed value.
645    ///
646    /// Panics if the index is out of bounds.
647    ///
648    /// Time: O(n) for the number of items shifted
649    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    /// Construct an iterator that drains values from the front of the chunk.
668    pub fn drain(&mut self) -> Drain<'_, A, N> {
669        Drain { chunk: self }
670    }
671
672    /// Discard the contents of the chunk.
673    ///
674    /// Time: O(n)
675    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    /// Get a reference to the contents of the chunk as a slice.
682    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    /// Get a reference to the contents of the chunk as a mutable slice.
692    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        // The first capacity comparison is to help optimize it out
819        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    /// Append the contents of the iterator to the back of the chunk.
903    ///
904    /// Panics if the chunk exceeds its capacity.
905    ///
906    /// Time: O(n) for the length of the iterator
907    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    /// Append the contents of the iterator to the back of the chunk.
922    ///
923    /// Panics if the chunk exceeds its capacity.
924    ///
925    /// Time: O(n) for the length of the iterator
926    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    /// This is for miri to catch
998    #[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}