sized_chunks/sized_chunk/
mod.rs

Help
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
25use typenum::U64;
26
27use crate::types::ChunkLength;
28
29mod iter;
30pub use self::iter::{Drain, Iter};
31
32#[cfg(feature = "refpool")]
33mod refpool;
34
35/// A fixed capacity smart array.
36///
37/// An inline array of items with a variable length but a fixed, preallocated
38/// capacity given by the `N` type, which must be an [`Unsigned`][Unsigned] type
39/// level numeral.
40///
41/// It's 'smart' because it's able to reorganise its contents based on expected
42/// behaviour. If you construct one using `push_back`, it will be laid out like
43/// a `Vec` with space at the end. If you `push_front` it will start filling in
44/// values from the back instead of the front, so that you still get linear time
45/// push as long as you don't reverse direction. If you do, and there's no room
46/// at the end you're pushing to, it'll shift its contents over to the other
47/// side, creating more space to push into. This technique is tuned for
48/// `Chunk`'s expected use case in [im::Vector]: usually, chunks always see
49/// either `push_front` or `push_back`, but not both unless they move around
50/// inside the tree, in which case they're able to reorganise themselves with
51/// reasonable efficiency to suit their new usage patterns.
52///
53/// It maintains a `left` index and a `right` index instead of a simple length
54/// counter in order to accomplish this, much like a ring buffer would, except
55/// that the `Chunk` keeps all its items sequentially in memory so that you can
56/// always get a `&[A]` slice for them, at the price of the occasional
57/// reordering operation. The allocated size of a `Chunk` is thus `usize` * 2 +
58/// `A` * `N`.
59///
60/// This technique also lets us choose to shift the shortest side to account for
61/// the inserted or removed element when performing insert and remove
62/// operations, unlike `Vec` where you always need to shift the right hand side.
63///
64/// Unlike a `Vec`, the `Chunk` has a fixed capacity and cannot grow beyond it.
65/// Being intended for low level use, it expects you to know or test whether
66/// you're pushing to a full array, and has an API more geared towards panics
67/// than returning `Option`s, on the assumption that you know what you're doing.
68/// Of course, if you don't, you can expect it to panic immediately rather than
69/// do something undefined and usually bad.
70///
71/// ## Isn't this just a less efficient ring buffer?
72///
73/// You might be wondering why you would want to use this data structure rather
74/// than a [`RingBuffer`][RingBuffer], which is similar but doesn't need to
75/// shift its content around when it hits the sides of the allocated buffer. The
76/// answer is that `Chunk` can be dereferenced into a slice, while a ring buffer
77/// can not. You'll also save a few cycles on index lookups, as a `Chunk`'s data
78/// is guaranteed to be contiguous in memory, so there's no need to remap logical
79/// indices to a ring buffer's physical layout.
80///
81/// # Examples
82///
83/// ```rust
84/// # #[macro_use] extern crate sized_chunks;
85/// # extern crate typenum;
86/// # use sized_chunks::Chunk;
87/// # use typenum::U64;
88/// // Construct a chunk with a 64 item capacity
89/// let mut chunk = Chunk::<i32, U64>::new();
90/// // Fill it with descending numbers
91/// chunk.extend((0..64).rev());
92/// // It derefs to a slice so we can use standard slice methods
93/// chunk.sort();
94/// // It's got all the amenities like `FromIterator` and `Eq`
95/// let expected: Chunk<i32, U64> = (0..64).collect();
96/// assert_eq!(expected, chunk);
97/// ```
98///
99/// [Unsigned]: https://docs.rs/typenum/1.10.0/typenum/marker_traits/trait.Unsigned.html
100/// [im::Vector]: https://docs.rs/im/latest/im/vector/enum.Vector.html
101/// [RingBuffer]: ../ring_buffer/struct.RingBuffer.html
102pub struct Chunk<A, N = U64>
103where
104    N: ChunkLength<A>,
105{
106    left: usize,
107    right: usize,
108    data: MaybeUninit<N::SizedType>,
109}
110
111impl<A, N> Drop for Chunk<A, N>
112where
113    N: ChunkLength<A>,
114{
115    fn drop(&mut self) {
116        unsafe { ptr::drop_in_place(self.as_mut_slice()) }
117    }
118}
119
120impl<A, N> Clone for Chunk<A, N>
121where
122    A: Clone,
123    N: ChunkLength<A>,
124{
125    fn clone(&self) -> Self {
126        let mut out = Self::new();
127        out.left = self.left;
128        out.right = self.left;
129        for index in self.left..self.right {
130            unsafe { Chunk::force_write(index, (*self.ptr(index)).clone(), &mut out) }
131            // Panic safety, move the right index to cover only the really initialized things. This
132            // way we don't try to drop uninitialized, but also don't leak if we panic in the
133            // middle.
134            out.right = index + 1;
135        }
136        out
137    }
138}
139
140impl<A, N> Chunk<A, N>
141where
142    N: ChunkLength<A>,
143{
144    /// The maximum number of elements this `Chunk` can contain.
145    pub const CAPACITY: usize = N::USIZE;
146
147    /// Construct a new empty chunk.
148    pub fn new() -> Self {
149        Self {
150            left: 0,
151            right: 0,
152            data: MaybeUninit::uninit(),
153        }
154    }
155
156    /// Construct a new chunk with one item.
157    pub fn unit(value: A) -> Self {
158        assert!(Self::CAPACITY >= 1);
159        let mut chunk = Self {
160            left: 0,
161            right: 1,
162            data: MaybeUninit::uninit(),
163        };
164        unsafe {
165            Chunk::force_write(0, value, &mut chunk);
166        }
167        chunk
168    }
169
170    /// Construct a new chunk with two items.
171    pub fn pair(left: A, right: A) -> Self {
172        assert!(Self::CAPACITY >= 2);
173        let mut chunk = Self {
174            left: 0,
175            right: 2,
176            data: MaybeUninit::uninit(),
177        };
178        unsafe {
179            Chunk::force_write(0, left, &mut chunk);
180            Chunk::force_write(1, right, &mut chunk);
181        }
182        chunk
183    }
184
185    /// Construct a new chunk and move every item from `other` into the new
186    /// chunk.
187    ///
188    /// Time: O(n)
189    pub fn drain_from(other: &mut Self) -> Self {
190        let other_len = other.len();
191        Self::from_front(other, other_len)
192    }
193
194    /// Construct a new chunk and populate it by taking `count` items from the
195    /// iterator `iter`.
196    ///
197    /// Panics if the iterator contains less than `count` items.
198    ///
199    /// Time: O(n)
200    pub fn collect_from<I>(iter: &mut I, mut count: usize) -> Self
201    where
202        I: Iterator<Item = A>,
203    {
204        let mut chunk = Self::new();
205        while count > 0 {
206            count -= 1;
207            chunk.push_back(
208                iter.next()
209                    .expect("Chunk::collect_from: underfull iterator"),
210            );
211        }
212        chunk
213    }
214
215    /// Construct a new chunk and populate it by taking `count` items from the
216    /// front of `other`.
217    ///
218    /// Time: O(n) for the number of items moved
219    pub fn from_front(other: &mut Self, count: usize) -> Self {
220        let other_len = other.len();
221        debug_assert!(count <= other_len);
222        let mut chunk = Self::new();
223        unsafe { Chunk::force_copy_to(other.left, 0, count, other, &mut chunk) };
224        chunk.right = count;
225        other.left += count;
226        chunk
227    }
228
229    /// Construct a new chunk and populate it by taking `count` items from the
230    /// back of `other`.
231    ///
232    /// Time: O(n) for the number of items moved
233    pub fn from_back(other: &mut Self, count: usize) -> Self {
234        let other_len = other.len();
235        debug_assert!(count <= other_len);
236        let mut chunk = Self::new();
237        unsafe { Chunk::force_copy_to(other.right - count, 0, count, other, &mut chunk) };
238        chunk.right = count;
239        other.right -= count;
240        chunk
241    }
242
243    /// Get the length of the chunk.
244    #[inline]
245    pub fn len(&self) -> usize {
246        self.right - self.left
247    }
248
249    /// Test if the chunk is empty.
250    #[inline]
251    pub fn is_empty(&self) -> bool {
252        self.left == self.right
253    }
254
255    /// Test if the chunk is at capacity.
256    #[inline]
257    pub fn is_full(&self) -> bool {
258        self.left == 0 && self.right == Self::CAPACITY
259    }
260
261    #[inline]
262    unsafe fn ptr(&self, index: usize) -> *const A {
263        (&self.data as *const _ as *const A).add(index)
264    }
265
266    /// It has no bounds checks
267    #[inline]
268    unsafe fn mut_ptr(&mut self, index: usize) -> *mut A {
269        (&mut self.data as *mut _ as *mut A).add(index)
270    }
271
272    /// Copy the value at an index, discarding ownership of the copied value
273    #[inline]
274    unsafe fn force_read(index: usize, chunk: &mut Self) -> A {
275        chunk.ptr(index).read()
276    }
277
278    /// Write a value at an index without trying to drop what's already there.
279    /// It has no bounds checks.
280    #[inline]
281    unsafe fn force_write(index: usize, value: A, chunk: &mut Self) {
282        chunk.mut_ptr(index).write(value)
283    }
284
285    /// Copy a range within a chunk
286    #[inline]
287    unsafe fn force_copy(from: usize, to: usize, count: usize, chunk: &mut Self) {
288        if count > 0 {
289            ptr::copy(chunk.ptr(from), chunk.mut_ptr(to), count)
290        }
291    }
292
293    /// Write values from iterator into range starting at write_index.
294    ///
295    /// Will overwrite values at the relevant range without dropping even in case the values were
296    /// already initialized (it is expected they are empty). Does not update the left or right
297    /// index.
298    ///
299    /// # Safety
300    ///
301    /// Range checks must already have been performed.
302    ///
303    /// # Panics
304    ///
305    /// If the iterator panics, the chunk becomes conceptually empty and will leak any previous
306    /// elements (even the ones outside the range).
307    #[inline]
308    unsafe fn write_from_iter<I>(mut write_index: usize, iter: I, chunk: &mut Self)
309    where
310        I: ExactSizeIterator<Item = A>,
311    {
312        // Panic safety. We make the array conceptually empty, so we never ever drop anything that
313        // is unitialized. We do so because we expect to be called when there's a potential "hole"
314        // in the array that makes the space for the new elements to be written. We return it back
315        // to original when everything goes fine, but leak any elements on panic. This is bad, but
316        // better than dropping non-existing stuff.
317        //
318        // Should we worry about some better panic recovery than this?
319        let left = replace(&mut chunk.left, 0);
320        let right = replace(&mut chunk.right, 0);
321        let len = iter.len();
322        let expected_end = write_index + len;
323        for value in iter.take(len) {
324            Chunk::force_write(write_index, value, chunk);
325            write_index += 1;
326        }
327        // Oops, we have a hole in here now. That would be bad, give up.
328        assert_eq!(
329            expected_end, write_index,
330            "ExactSizeIterator yielded fewer values than advertised",
331        );
332        chunk.left = left;
333        chunk.right = right;
334    }
335
336    /// Copy a range between chunks
337    #[inline]
338    unsafe fn force_copy_to(
339        from: usize,
340        to: usize,
341        count: usize,
342        chunk: &mut Self,
343        other: &mut Self,
344    ) {
345        if count > 0 {
346            ptr::copy_nonoverlapping(chunk.ptr(from), other.mut_ptr(to), count)
347        }
348    }
349
350    /// Push an item to the front of the chunk.
351    ///
352    /// Panics if the capacity of the chunk is exceeded.
353    ///
354    /// Time: O(1) if there's room at the front, O(n) otherwise
355    pub fn push_front(&mut self, value: A) {
356        if self.is_full() {
357            panic!("Chunk::push_front: can't push to full chunk");
358        }
359        if self.is_empty() {
360            self.left = N::USIZE;
361            self.right = N::USIZE;
362        } else if self.left == 0 {
363            self.left = N::USIZE - self.right;
364            unsafe { Chunk::force_copy(0, self.left, self.right, self) };
365            self.right = N::USIZE;
366        }
367        self.left -= 1;
368        unsafe { Chunk::force_write(self.left, value, self) }
369    }
370
371    /// Push an item to the back of the chunk.
372    ///
373    /// Panics if the capacity of the chunk is exceeded.
374    ///
375    /// Time: O(1) if there's room at the back, O(n) otherwise
376    pub fn push_back(&mut self, value: A) {
377        if self.is_full() {
378            panic!("Chunk::push_back: can't push to full chunk");
379        }
380        if self.is_empty() {
381            self.left = 0;
382            self.right = 0;
383        } else if self.right == N::USIZE {
384            unsafe { Chunk::force_copy(self.left, 0, self.len(), self) };
385            self.right = N::USIZE - self.left;
386            self.left = 0;
387        }
388        unsafe { Chunk::force_write(self.right, value, self) }
389        self.right += 1;
390    }
391
392    /// Pop an item off the front of the chunk.
393    ///
394    /// Panics if the chunk is empty.
395    ///
396    /// Time: O(1)
397    pub fn pop_front(&mut self) -> A {
398        if self.is_empty() {
399            panic!("Chunk::pop_front: can't pop from empty chunk");
400        } else {
401            let value = unsafe { Chunk::force_read(self.left, self) };
402            self.left += 1;
403            value
404        }
405    }
406
407    /// Pop an item off the back of the chunk.
408    ///
409    /// Panics if the chunk is empty.
410    ///
411    /// Time: O(1)
412    pub fn pop_back(&mut self) -> A {
413        if self.is_empty() {
414            panic!("Chunk::pop_back: can't pop from empty chunk");
415        } else {
416            self.right -= 1;
417            unsafe { Chunk::force_read(self.right, self) }
418        }
419    }
420
421    /// Discard all items up to but not including `index`.
422    ///
423    /// Panics if `index` is out of bounds.
424    ///
425    /// Time: O(n) for the number of items dropped
426    pub fn drop_left(&mut self, index: usize) {
427        if index > 0 {
428            unsafe { ptr::drop_in_place(&mut self[..index]) }
429            self.left += index;
430        }
431    }
432
433    /// Discard all items from `index` onward.
434    ///
435    /// Panics if `index` is out of bounds.
436    ///
437    /// Time: O(n) for the number of items dropped
438    pub fn drop_right(&mut self, index: usize) {
439        if index != self.len() {
440            unsafe { ptr::drop_in_place(&mut self[index..]) }
441            self.right = self.left + index;
442        }
443    }
444
445    /// Split a chunk into two, the original chunk containing
446    /// everything up to `index` and the returned chunk containing
447    /// everything from `index` onwards.
448    ///
449    /// Panics if `index` is out of bounds.
450    ///
451    /// Time: O(n) for the number of items in the new chunk
452    pub fn split_off(&mut self, index: usize) -> Self {
453        if index > self.len() {
454            panic!("Chunk::split_off: index out of bounds");
455        }
456        if index == self.len() {
457            return Self::new();
458        }
459        let mut right_chunk = Self::new();
460        let start = self.left + index;
461        let len = self.right - start;
462        unsafe { Chunk::force_copy_to(start, 0, len, self, &mut right_chunk) };
463        right_chunk.right = len;
464        self.right = start;
465        right_chunk
466    }
467
468    /// Remove all items from `other` and append them to the back of `self`.
469    ///
470    /// Panics if the capacity of the chunk is exceeded.
471    ///
472    /// Time: O(n) for the number of items moved
473    pub fn append(&mut self, other: &mut Self) {
474        let self_len = self.len();
475        let other_len = other.len();
476        if self_len + other_len > N::USIZE {
477            panic!("Chunk::append: chunk size overflow");
478        }
479        if self.right + other_len > N::USIZE {
480            unsafe { Chunk::force_copy(self.left, 0, self_len, self) };
481            self.right -= self.left;
482            self.left = 0;
483        }
484        unsafe { Chunk::force_copy_to(other.left, self.right, other_len, other, self) };
485        self.right += other_len;
486        other.left = 0;
487        other.right = 0;
488    }
489
490    /// Remove `count` items from the front of `other` and append them to the
491    /// back of `self`.
492    ///
493    /// Panics if `self` doesn't have `count` items left, or if `other` has
494    /// fewer than `count` items.
495    ///
496    /// Time: O(n) for the number of items moved
497    pub fn drain_from_front(&mut self, other: &mut Self, count: usize) {
498        let self_len = self.len();
499        let other_len = other.len();
500        assert!(self_len + count <= N::USIZE);
501        assert!(other_len >= count);
502        if self.right + count > N::USIZE {
503            unsafe { Chunk::force_copy(self.left, 0, self_len, self) };
504            self.right -= self.left;
505            self.left = 0;
506        }
507        unsafe { Chunk::force_copy_to(other.left, self.right, count, other, self) };
508        self.right += count;
509        other.left += count;
510    }
511
512    /// Remove `count` items from the back of `other` and append them to the
513    /// front of `self`.
514    ///
515    /// Panics if `self` doesn't have `count` items left, or if `other` has
516    /// fewer than `count` items.
517    ///
518    /// Time: O(n) for the number of items moved
519    pub fn drain_from_back(&mut self, other: &mut Self, count: usize) {
520        let self_len = self.len();
521        let other_len = other.len();
522        assert!(self_len + count <= N::USIZE);
523        assert!(other_len >= count);
524        if self.left < count {
525            unsafe { Chunk::force_copy(self.left, N::USIZE - self_len, self_len, self) };
526            self.left = N::USIZE - self_len;
527            self.right = N::USIZE;
528        }
529        unsafe { Chunk::force_copy_to(other.right - count, self.left - count, count, other, self) };
530        self.left -= count;
531        other.right -= count;
532    }
533
534    /// Update the value at index `index`, returning the old value.
535    ///
536    /// Panics if `index` is out of bounds.
537    ///
538    /// Time: O(1)
539    pub fn set(&mut self, index: usize, value: A) -> A {
540        replace(&mut self[index], value)
541    }
542
543    /// Insert a new value at index `index`, shifting all the following values
544    /// to the right.
545    ///
546    /// Panics if the index is out of bounds or the chunk is full.
547    ///
548    /// Time: O(n) for the number of elements shifted
549    pub fn insert(&mut self, index: usize, value: A) {
550        if self.is_full() {
551            panic!("Chunk::insert: chunk is full");
552        }
553        if index > self.len() {
554            panic!("Chunk::insert: index out of bounds");
555        }
556        let real_index = index + self.left;
557        let left_size = index;
558        let right_size = self.right - real_index;
559        if self.right == N::USIZE || (self.left > 0 && left_size < right_size) {
560            unsafe {
561                Chunk::force_copy(self.left, self.left - 1, left_size, self);
562                Chunk::force_write(real_index - 1, value, self);
563            }
564            self.left -= 1;
565        } else {
566            unsafe {
567                Chunk::force_copy(real_index, real_index + 1, right_size, self);
568                Chunk::force_write(real_index, value, self);
569            }
570            self.right += 1;
571        }
572    }
573
574    /// Insert a new value into the chunk in sorted order.
575    ///
576    /// This assumes every element of the chunk is already in sorted order.
577    /// If not, the value will still be inserted but the ordering is not
578    /// guaranteed.
579    ///
580    /// Time: O(log n) to find the insert position, then O(n) for the number
581    /// of elements shifted.
582    ///
583    /// # Examples
584    ///
585    /// ```rust
586    /// # use std::iter::FromIterator;
587    /// # use sized_chunks::Chunk;
588    /// # use typenum::U64;
589    /// let mut chunk = Chunk::<i32, U64>::from_iter(0..5);
590    /// chunk.insert_ordered(3);
591    /// assert_eq!(&[0, 1, 2, 3, 3, 4], chunk.as_slice());
592    /// ```
593    pub fn insert_ordered(&mut self, value: A)
594    where
595        A: Ord,
596    {
597        if self.is_full() {
598            panic!("Chunk::insert: chunk is full");
599        }
600        match self.binary_search(&value) {
601            Ok(index) => self.insert(index, value),
602            Err(index) => self.insert(index, value),
603        }
604    }
605
606    /// Insert multiple values at index `index`, shifting all the following values
607    /// to the right.
608    ///
609    /// Panics if the index is out of bounds or the chunk doesn't have room for
610    /// all the values.
611    ///
612    /// Time: O(m+n) where m is the number of elements inserted and n is the number
613    /// of elements following the insertion index. Calling `insert`
614    /// repeatedly would be O(m*n).
615    pub fn insert_from<Iterable, I>(&mut self, index: usize, iter: Iterable)
616    where
617        Iterable: IntoIterator<Item = A, IntoIter = I>,
618        I: ExactSizeIterator<Item = A>,
619    {
620        let iter = iter.into_iter();
621        let insert_size = iter.len();
622        if self.len() + insert_size > Self::CAPACITY {
623            panic!(
624                "Chunk::insert_from: chunk cannot fit {} elements",
625                insert_size
626            );
627        }
628        if index > self.len() {
629            panic!("Chunk::insert_from: index out of bounds");
630        }
631        let real_index = index + self.left;
632        let left_size = index;
633        let right_size = self.right - real_index;
634        if self.right == N::USIZE || (self.left >= insert_size && left_size < right_size) {
635            unsafe {
636                Chunk::force_copy(self.left, self.left - insert_size, left_size, self);
637                let write_index = real_index - insert_size;
638                Chunk::write_from_iter(write_index, iter, self);
639            }
640            self.left -= insert_size;
641        } else if self.left == 0 || (self.right + insert_size <= Self::CAPACITY) {
642            unsafe {
643                Chunk::force_copy(real_index, real_index + insert_size, right_size, self);
644                let write_index = real_index;
645                Chunk::write_from_iter(write_index, iter, self);
646            }
647            self.right += insert_size;
648        } else {
649            unsafe {
650                Chunk::force_copy(self.left, 0, left_size, self);
651                Chunk::force_copy(real_index, left_size + insert_size, right_size, self);
652                let write_index = left_size;
653                Chunk::write_from_iter(write_index, iter, self);
654            }
655            self.right -= self.left;
656            self.right += insert_size;
657            self.left = 0;
658        }
659    }
660
661    /// Remove the value at index `index`, shifting all the following values to
662    /// the left.
663    ///
664    /// Returns the removed value.
665    ///
666    /// Panics if the index is out of bounds.
667    ///
668    /// Time: O(n) for the number of items shifted
669    pub fn remove(&mut self, index: usize) -> A {
670        if index >= self.len() {
671            panic!("Chunk::remove: index out of bounds");
672        }
673        let real_index = index + self.left;
674        let value = unsafe { Chunk::force_read(real_index, self) };
675        let left_size = index;
676        let right_size = self.right - real_index - 1;
677        if left_size < right_size {
678            unsafe { Chunk::force_copy(self.left, self.left + 1, left_size, self) };
679            self.left += 1;
680        } else {
681            unsafe { Chunk::force_copy(real_index + 1, real_index, right_size, self) };
682            self.right -= 1;
683        }
684        value
685    }
686
687    /// Construct an iterator that drains values from the front of the chunk.
688    pub fn drain(&mut self) -> Drain<'_, A, N> {
689        Drain { chunk: self }
690    }
691
692    /// Discard the contents of the chunk.
693    ///
694    /// Time: O(n)
695    pub fn clear(&mut self) {
696        unsafe { ptr::drop_in_place(self.as_mut_slice()) }
697        self.left = 0;
698        self.right = 0;
699    }
700
701    /// Get a reference to the contents of the chunk as a slice.
702    pub fn as_slice(&self) -> &[A] {
703        unsafe {
704            from_raw_parts(
705                (&self.data as *const MaybeUninit<N::SizedType> as *const A).add(self.left),
706                self.len(),
707            )
708        }
709    }
710
711    /// Get a reference to the contents of the chunk as a mutable slice.
712    pub fn as_mut_slice(&mut self) -> &mut [A] {
713        unsafe {
714            from_raw_parts_mut(
715                (&mut self.data as *mut MaybeUninit<N::SizedType> as *mut A).add(self.left),
716                self.len(),
717            )
718        }
719    }
720}
721
722impl<A, N> Default for Chunk<A, N>
723where
724    N: ChunkLength<A>,
725{
726    fn default() -> Self {
727        Self::new()
728    }
729}
730
731impl<A, N, I> Index<I> for Chunk<A, N>
732where
733    I: SliceIndex<[A]>,
734    N: ChunkLength<A>,
735{
736    type Output = I::Output;
737    fn index(&self, index: I) -> &Self::Output {
738        self.as_slice().index(index)
739    }
740}
741
742impl<A, N, I> IndexMut<I> for Chunk<A, N>
743where
744    I: SliceIndex<[A]>,
745    N: ChunkLength<A>,
746{
747    fn index_mut(&mut self, index: I) -> &mut Self::Output {
748        self.as_mut_slice().index_mut(index)
749    }
750}
751
752impl<A, N> Debug for Chunk<A, N>
753where
754    A: Debug,
755    N: ChunkLength<A>,
756{
757    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
758        f.write_str("Chunk")?;
759        f.debug_list().entries(self.iter()).finish()
760    }
761}
762
763impl<A, N> Hash for Chunk<A, N>
764where
765    A: Hash,
766    N: ChunkLength<A>,
767{
768    fn hash<H>(&self, hasher: &mut H)
769    where
770        H: Hasher,
771    {
772        for item in self {
773            item.hash(hasher)
774        }
775    }
776}
777
778impl<A, N, Slice> PartialEq<Slice> for Chunk<A, N>
779where
780    Slice: Borrow<[A]>,
781    A: PartialEq,
782    N: ChunkLength<A>,
783{
784    fn eq(&self, other: &Slice) -> bool {
785        self.as_slice() == other.borrow()
786    }
787}
788
789impl<A, N> Eq for Chunk<A, N>
790where
791    A: Eq,
792    N: ChunkLength<A>,
793{
794}
795
796impl<A, N> PartialOrd for Chunk<A, N>
797where
798    A: PartialOrd,
799    N: ChunkLength<A>,
800{
801    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
802        self.iter().partial_cmp(other.iter())
803    }
804}
805
806impl<A, N> Ord for Chunk<A, N>
807where
808    A: Ord,
809    N: ChunkLength<A>,
810{
811    fn cmp(&self, other: &Self) -> Ordering {
812        self.iter().cmp(other.iter())
813    }
814}
815
816#[cfg(feature = "std")]
817impl<N> io::Write for Chunk<u8, N>
818where
819    N: ChunkLength<u8>,
820{
821    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
822        let old_len = self.len();
823        self.extend(buf.iter().cloned().take(N::USIZE - old_len));
824        Ok(self.len() - old_len)
825    }
826
827    fn flush(&mut self) -> io::Result<()> {
828        Ok(())
829    }
830}
831
832#[cfg(feature = "std")]
833impl<N: ChunkLength<u8>> std::io::Read for Chunk<u8, N> {
834    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
835        let read_size = buf.len().min(self.len());
836        if read_size == 0 {
837            Ok(0)
838        } else {
839            for p in buf.iter_mut().take(read_size) {
840                *p = self.pop_front();
841            }
842            Ok(read_size)
843        }
844    }
845}
846
847impl<A, N, T> From<InlineArray<A, T>> for Chunk<A, N>
848where
849    N: ChunkLength<A>,
850{
851    #[inline]
852    fn from(mut array: InlineArray<A, T>) -> Self {
853        Self::from(&mut array)
854    }
855}
856
857impl<'a, A, N, T> From<&'a mut InlineArray<A, T>> for Chunk<A, N>
858where
859    N: ChunkLength<A>,
860{
861    fn from(array: &mut InlineArray<A, T>) -> Self {
862        // The first capacity comparison is to help optimize it out
863        assert!(
864            InlineArray::<A, T>::CAPACITY <= Self::CAPACITY || array.len() <= Self::CAPACITY,
865            "CAPACITY too small"
866        );
867        let mut out = Self::new();
868        out.left = 0;
869        out.right = array.len();
870        unsafe {
871            ptr::copy_nonoverlapping(array.data(), out.mut_ptr(0), out.right);
872            *array.len_mut() = 0;
873        }
874        out
875    }
876}
877
878impl<A, N> Borrow<[A]> for Chunk<A, N>
879where
880    N: ChunkLength<A>,
881{
882    fn borrow(&self) -> &[A] {
883        self.as_slice()
884    }
885}
886
887impl<A, N> BorrowMut<[A]> for Chunk<A, N>
888where
889    N: ChunkLength<A>,
890{
891    fn borrow_mut(&mut self) -> &mut [A] {
892        self.as_mut_slice()
893    }
894}
895
896impl<A, N> AsRef<[A]> for Chunk<A, N>
897where
898    N: ChunkLength<A>,
899{
900    fn as_ref(&self) -> &[A] {
901        self.as_slice()
902    }
903}
904
905impl<A, N> AsMut<[A]> for Chunk<A, N>
906where
907    N: ChunkLength<A>,
908{
909    fn as_mut(&mut self) -> &mut [A] {
910        self.as_mut_slice()
911    }
912}
913
914impl<A, N> Deref for Chunk<A, N>
915where
916    N: ChunkLength<A>,
917{
918    type Target = [A];
919
920    fn deref(&self) -> &Self::Target {
921        self.as_slice()
922    }
923}
924
925impl<A, N> DerefMut for Chunk<A, N>
926where
927    N: ChunkLength<A>,
928{
929    fn deref_mut(&mut self) -> &mut Self::Target {
930        self.as_mut_slice()
931    }
932}
933
934impl<A, N> FromIterator<A> for Chunk<A, N>
935where
936    N: ChunkLength<A>,
937{
938    fn from_iter<I>(it: I) -> Self
939    where
940        I: IntoIterator<Item = A>,
941    {
942        let mut chunk = Self::new();
943        for item in it {
944            chunk.push_back(item);
945        }
946        chunk
947    }
948}
949
950impl<'a, A, N> IntoIterator for &'a Chunk<A, N>
951where
952    N: ChunkLength<A>,
953{
954    type Item = &'a A;
955    type IntoIter = SliceIter<'a, A>;
956    fn into_iter(self) -> Self::IntoIter {
957        self.iter()
958    }
959}
960
961impl<'a, A, N> IntoIterator for &'a mut Chunk<A, N>
962where
963    N: ChunkLength<A>,
964{
965    type Item = &'a mut A;
966    type IntoIter = SliceIterMut<'a, A>;
967    fn into_iter(self) -> Self::IntoIter {
968        self.iter_mut()
969    }
970}
971
972impl<A, N> Extend<A> for Chunk<A, N>
973where
974    N: ChunkLength<A>,
975{
976    /// Append the contents of the iterator to the back of the chunk.
977    ///
978    /// Panics if the chunk exceeds its capacity.
979    ///
980    /// Time: O(n) for the length of the iterator
981    fn extend<I>(&mut self, it: I)
982    where
983        I: IntoIterator<Item = A>,
984    {
985        for item in it {
986            self.push_back(item);
987        }
988    }
989}
990
991impl<'a, A, N> Extend<&'a A> for Chunk<A, N>
992where
993    A: 'a + Copy,
994    N: ChunkLength<A>,
995{
996    /// Append the contents of the iterator to the back of the chunk.
997    ///
998    /// Panics if the chunk exceeds its capacity.
999    ///
1000    /// Time: O(n) for the length of the iterator
1001    fn extend<I>(&mut self, it: I)
1002    where
1003        I: IntoIterator<Item = &'a A>,
1004    {
1005        for item in it {
1006            self.push_back(*item);
1007        }
1008    }
1009}
1010
1011impl<A, N> IntoIterator for Chunk<A, N>
1012where
1013    N: ChunkLength<A>,
1014{
1015    type Item = A;
1016    type IntoIter = Iter<A, N>;
1017
1018    fn into_iter(self) -> Self::IntoIter {
1019        Iter { chunk: self }
1020    }
1021}
1022
1023#[cfg(test)]
1024#[rustfmt::skip]
1025mod test {
1026    use super::*;
1027    use typenum::{U0, U1, U2, U3, U5};
1028
1029    #[test]
1030    #[should_panic(expected = "Chunk::push_back: can't push to full chunk")]
1031    fn issue_11_testcase1d() {
1032        let mut chunk = Chunk::<usize, U2>::pair(123, 456);
1033        chunk.push_back(789);
1034    }
1035
1036    #[test]
1037    #[should_panic(expected = "CAPACITY too small")]
1038    fn issue_11_testcase2a() {
1039        let mut from = InlineArray::<u8, [u8; 256]>::new();
1040        from.push(1);
1041
1042        let _ = Chunk::<u8, U0>::from(from);
1043    }
1044
1045    #[test]
1046    fn issue_11_testcase2b() {
1047        let mut from = InlineArray::<u8, [u8; 256]>::new();
1048        from.push(1);
1049
1050        let _ = Chunk::<u8, U1>::from(from);
1051    }
1052
1053    struct DropDetector(u32);
1054
1055    impl DropDetector {
1056        fn new(num: u32) -> Self {
1057            DropDetector(num)
1058        }
1059    }
1060
1061    impl Drop for DropDetector {
1062        fn drop(&mut self) {
1063            assert!(self.0 == 42 || self.0 == 43);
1064        }
1065    }
1066
1067    impl Clone for DropDetector {
1068        fn clone(&self) -> Self {
1069            if self.0 == 42 {
1070                panic!("panic on clone")
1071            }
1072            DropDetector::new(self.0)
1073        }
1074    }
1075
1076    /// This is for miri to catch
1077    #[test]
1078    fn issue_11_testcase3a() {
1079        let mut chunk = Chunk::<DropDetector, U3>::new();
1080        chunk.push_back(DropDetector::new(42));
1081        chunk.push_back(DropDetector::new(42));
1082        chunk.push_back(DropDetector::new(43));
1083        let _ = chunk.pop_front();
1084
1085        let _ = std::panic::catch_unwind(|| {
1086            let _ = chunk.clone();
1087        });
1088    }
1089
1090    struct PanickingIterator {
1091        current: u32,
1092        panic_at: u32,
1093        len: usize,
1094    }
1095
1096    impl Iterator for PanickingIterator {
1097        type Item = DropDetector;
1098
1099        fn next(&mut self) -> Option<Self::Item> {
1100            let num = self.current;
1101
1102            if num == self.panic_at {
1103                panic!("panicking index")
1104            }
1105
1106            self.current += 1;
1107            Some(DropDetector::new(num))
1108        }
1109
1110        fn size_hint(&self) -> (usize, Option<usize>) {
1111            (self.len, Some(self.len))
1112        }
1113    }
1114
1115    impl ExactSizeIterator for PanickingIterator {}
1116
1117    #[test]
1118    fn issue_11_testcase3b() {
1119        let _ = std::panic::catch_unwind(|| {
1120            let mut chunk = Chunk::<DropDetector, U5>::new();
1121            chunk.push_back(DropDetector::new(1));
1122            chunk.push_back(DropDetector::new(2));
1123            chunk.push_back(DropDetector::new(3));
1124
1125            chunk.insert_from(
1126                1,
1127                PanickingIterator {
1128                    current: 1,
1129                    panic_at: 1,
1130                    len: 1,
1131                },
1132            );
1133        });
1134    }
1135
1136    struct FakeSizeIterator { reported: usize, actual: usize }
1137    impl Iterator for FakeSizeIterator {
1138        type Item = u8;
1139        fn next(&mut self) -> Option<Self::Item> {
1140            if self.actual == 0 {
1141                None
1142            } else {
1143                self.actual -= 1;
1144                Some(1)
1145            }
1146        }
1147
1148        fn size_hint(&self) -> (usize, Option<usize>) {
1149            (self.reported, Some(self.reported))
1150        }
1151    }
1152
1153    impl ExactSizeIterator for FakeSizeIterator {
1154        fn len(&self) -> usize {
1155            self.reported
1156        }
1157    }
1158
1159    #[test]
1160    fn iterator_too_long() {
1161        let mut chunk = Chunk::<u8, U5>::new();
1162        chunk.push_back(0);
1163        chunk.push_back(1);
1164        chunk.push_back(2);
1165        chunk.insert_from(1, FakeSizeIterator { reported: 1, actual: 10 });
1166
1167        let mut chunk = Chunk::<u8, U5>::new();
1168        chunk.push_back(1);
1169        chunk.insert_from(0, FakeSizeIterator { reported: 1, actual: 10 });
1170
1171        let mut chunk = Chunk::<u8, U5>::new();
1172        chunk.insert_from(0, FakeSizeIterator { reported: 1, actual: 10 });
1173    }
1174
1175    #[test]
1176    #[should_panic(expected = "ExactSizeIterator yielded fewer values than advertised")]
1177    fn iterator_too_short1() {
1178        let mut chunk = Chunk::<u8, U5>::new();
1179        chunk.push_back(0);
1180        chunk.push_back(1);
1181        chunk.push_back(2);
1182        chunk.insert_from(1, FakeSizeIterator { reported: 2, actual: 0 });
1183    }
1184
1185    #[test]
1186    #[should_panic(expected = "ExactSizeIterator yielded fewer values than advertised")]
1187    fn iterator_too_short2() {
1188        let mut chunk = Chunk::<u8, U5>::new();
1189        chunk.push_back(1);
1190        chunk.insert_from(1, FakeSizeIterator { reported: 4, actual: 2 });
1191    }
1192
1193    #[test]
1194    fn is_full() {
1195        let mut chunk = Chunk::<_, U64>::new();
1196        for i in 0..64 {
1197            assert_eq!(false, chunk.is_full());
1198            chunk.push_back(i);
1199        }
1200        assert_eq!(true, chunk.is_full());
1201    }
1202
1203    #[test]
1204    fn push_back_front() {
1205        let mut chunk = Chunk::<_, U64>::new();
1206        for i in 12..20 {
1207            chunk.push_back(i);
1208        }
1209        assert_eq!(8, chunk.len());
1210        for i in (0..12).rev() {
1211            chunk.push_front(i);
1212        }
1213        assert_eq!(20, chunk.len());
1214        for i in 20..32 {
1215            chunk.push_back(i);
1216        }
1217        assert_eq!(32, chunk.len());
1218        let right: Vec<i32> = chunk.into_iter().collect();
1219        let left: Vec<i32> = (0..32).collect();
1220        assert_eq!(left, right);
1221    }
1222
1223    #[test]
1224    fn push_and_pop() {
1225        let mut chunk = Chunk::<_, U64>::new();
1226        for i in 0..64 {
1227            chunk.push_back(i);
1228        }
1229        for i in 0..64 {
1230            assert_eq!(i, chunk.pop_front());
1231        }
1232        for i in 0..64 {
1233            chunk.push_front(i);
1234        }
1235        for i in 0..64 {
1236            assert_eq!(i, chunk.pop_back());
1237        }
1238    }
1239
1240    #[test]
1241    fn drop_left() {
1242        let mut chunk = Chunk::<_, U64>::new();
1243        for i in 0..6 {
1244            chunk.push_back(i);
1245        }
1246        chunk.drop_left(3);
1247        let vec: Vec<i32> = chunk.into_iter().collect();
1248        assert_eq!(vec![3, 4, 5], vec);
1249    }
1250
1251    #[test]
1252    fn drop_right() {
1253        let mut chunk = Chunk::<_, U64>::new();
1254        for i in 0..6 {
1255            chunk.push_back(i);
1256        }
1257        chunk.drop_right(3);
1258        let vec: Vec<i32> = chunk.into_iter().collect();
1259        assert_eq!(vec![0, 1, 2], vec);
1260    }
1261
1262    #[test]
1263    fn split_off() {
1264        let mut left = Chunk::<_, U64>::new();
1265        for i in 0..6 {
1266            left.push_back(i);
1267        }
1268        let right = left.split_off(3);
1269        let left_vec: Vec<i32> = left.into_iter().collect();
1270        let right_vec: Vec<i32> = right.into_iter().collect();
1271        assert_eq!(vec![0, 1, 2], left_vec);
1272        assert_eq!(vec![3, 4, 5], right_vec);
1273    }
1274
1275    #[test]
1276    fn append() {
1277        let mut left = Chunk::<_, U64>::new();
1278        for i in 0..32 {
1279            left.push_back(i);
1280        }
1281        let mut right = Chunk::<_, U64>::new();
1282        for i in (32..64).rev() {
1283            right.push_front(i);
1284        }
1285        left.append(&mut right);
1286        let out_vec: Vec<i32> = left.into_iter().collect();
1287        let should_vec: Vec<i32> = (0..64).collect();
1288        assert_eq!(should_vec, out_vec);
1289    }
1290
1291    #[test]
1292    fn ref_iter() {
1293        let mut chunk = Chunk::<_, U64>::new();
1294        for i in 0..64 {
1295            chunk.push_back(i);
1296        }
1297        let out_vec: Vec<&i32> = chunk.iter().collect();
1298        let should_vec_p: Vec<i32> = (0..64).collect();
1299        let should_vec: Vec<&i32> = should_vec_p.iter().collect();
1300        assert_eq!(should_vec, out_vec);
1301    }
1302
1303    #[test]
1304    fn mut_ref_iter() {
1305        let mut chunk = Chunk::<_, U64>::new();
1306        for i in 0..64 {
1307            chunk.push_back(i);
1308        }
1309        let out_vec: Vec<&mut i32> = chunk.iter_mut().collect();
1310        let mut should_vec_p: Vec<i32> = (0..64).collect();
1311        let should_vec: Vec<&mut i32> = should_vec_p.iter_mut().collect();
1312        assert_eq!(should_vec, out_vec);
1313    }
1314
1315    #[test]
1316    fn consuming_iter() {
1317        let mut chunk = Chunk::<_, U64>::new();
1318        for i in 0..64 {
1319            chunk.push_back(i);
1320        }
1321        let out_vec: Vec<i32> = chunk.into_iter().collect();
1322        let should_vec: Vec<i32> = (0..64).collect();
1323        assert_eq!(should_vec, out_vec);
1324    }
1325
1326    #[test]
1327    fn insert_middle() {
1328        let mut chunk = Chunk::<_, U64>::new();
1329        for i in 0..32 {
1330            chunk.push_back(i);
1331        }
1332        for i in 33..64 {
1333            chunk.push_back(i);
1334        }
1335        chunk.insert(32, 32);
1336        let out_vec: Vec<i32> = chunk.into_iter().collect();
1337        let should_vec: Vec<i32> = (0..64).collect();
1338        assert_eq!(should_vec, out_vec);
1339    }
1340
1341    #[test]
1342    fn insert_back() {
1343        let mut chunk = Chunk::<_, U64>::new();
1344        for i in 0..63 {
1345            chunk.push_back(i);
1346        }
1347        chunk.insert(63, 63);
1348        let out_vec: Vec<i32> = chunk.into_iter().collect();
1349        let should_vec: Vec<i32> = (0..64).collect();
1350        assert_eq!(should_vec, out_vec);
1351    }
1352
1353    #[test]
1354    fn insert_front() {
1355        let mut chunk = Chunk::<_, U64>::new();
1356        for i in 1..64 {
1357            chunk.push_front(64 - i);
1358        }
1359        chunk.insert(0, 0);
1360        let out_vec: Vec<i32> = chunk.into_iter().collect();
1361        let should_vec: Vec<i32> = (0..64).collect();
1362        assert_eq!(should_vec, out_vec);
1363    }
1364
1365    #[test]
1366    fn remove_value() {
1367        let mut chunk = Chunk::<_, U64>::new();
1368        for i in 0..64 {
1369            chunk.push_back(i);
1370        }
1371        chunk.remove(32);
1372        let out_vec: Vec<i32> = chunk.into_iter().collect();
1373        let should_vec: Vec<i32> = (0..32).chain(33..64).collect();
1374        assert_eq!(should_vec, out_vec);
1375    }
1376
1377    use crate::tests::DropTest;
1378    use std::sync::atomic::{AtomicUsize, Ordering};
1379
1380    #[test]
1381    fn dropping() {
1382        let counter = AtomicUsize::new(0);
1383        {
1384            let mut chunk: Chunk<DropTest<'_>> = Chunk::new();
1385            for _i in 0..20 {
1386                chunk.push_back(DropTest::new(&counter))
1387            }
1388            for _i in 0..20 {
1389                chunk.push_front(DropTest::new(&counter))
1390            }
1391            assert_eq!(40, counter.load(Ordering::Relaxed));
1392            for _i in 0..10 {
1393                chunk.pop_back();
1394            }
1395            assert_eq!(30, counter.load(Ordering::Relaxed));
1396        }
1397        assert_eq!(0, counter.load(Ordering::Relaxed));
1398    }
1399
1400    #[test]
1401    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 1")]
1402    fn unit_on_empty() {
1403        Chunk::<usize, U0>::unit(1);
1404    }
1405
1406    #[test]
1407    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 2")]
1408    fn pair_on_empty() {
1409        Chunk::<usize, U0>::pair(1, 2);
1410    }
1411}
sized_chunks/sized_chunk/mod.rs

sized_chunks/sized_chunk/
mod.rs
