andylokandy/arraydeque

A circular buffer with fixed capacity (Rust).

arraydeque's Issues

Function `insert` is missing from the `Wrapping` behaviour

I couldn't find any reason for this to be the case in the documentation or the issue tracker, so I'm guessing it got missed? If there is a reason that insert is missing for the Wrapping behaviour, it would be good to add it to the docs.

#![feature] may not be used on the stable release channel

ArrayDeque used to compile but suddenly I'm stuck with this error. Does anyone know where it came from ?

error[E0554]: `#![feature]` may not be used on the stable release channel
  --> /home/sisyphe/.cargo/registry/src/github.com-1ecc6299db9ec823/arraydeque-0.4.5/src/lib.rs:57:32
   |
57 | #![cfg_attr(has_union_feature, feature(untagged_unions))]
   |                

Array trait is private

So I'm using this to implement an optimization of the LRUCache in Servo servo/servo#17054, but I need a small change making mod array and use array::Array both public, so I can guarantee the trait being held.

I can submit the pull request needed for it.

Mininum rust version

Hi. I notice you're testing against Rust 1.15.0 as a minimum supported version. If this is for compatibility with Firefox, I wanted to let you know that we bumped that minimum to 1.17.0 today, so if you'd prefer to use more recent language features, that's an option.

Copy trait?

I'd like to be able to derive Copy. For example:

#[derive(Clone, Copy)]
struct Foo {
    ring: ArrayDeque<u16, 16>
}

Did I overlook an easy way to do this? If not, is this possible with the current design? If so, would you be open to a PR adding this functionality?

Thanks for making this library!

Overwriting API variants

Hi Andy,

I found arraydeque while looking for a stack-allocated fixed-size circular buffer that is compatible with no_std.

It seems to match 90% of my (DSP-related) needs, but seems to lack support for overwriting existing elements rather than dropping a given insert.

I'd rather not implement my own circular buffer from scratch, so I chose to –for now– just extend its existing API through a trait:

trait WrapAround {
    type Item;

    fn wrapping_push_back(&mut self, item: Self::Item) -> Option<Self::Item>;
    fn wrapping_push_front(&mut self, item: Self::Item) -> Option<Self::Item>;
}

impl<T> WrapAround for ArrayDeque<T> where T: Array {
    type Item = T::Item;

    fn wrapping_push_back(&mut self, item: Self::Item) -> Option<Self::Item> {
        let existing = if self.len() == self.capacity() {
            self.pop_front()
        } else {
            None
        };
        self.push_back(item);
        existing
    }

    fn wrapping_push_front(&mut self, item: Self::Item) -> Option<Self::Item> {
        let existing = if self.len() == self.capacity() {
            self.pop_back()
        } else {
            None
        };
        self.push_front(item);
        existing
    }
}

I'm certainly not the only one with these particular needs (especially with Rust reaching for a wide use in embedded/DSP). And there are a bunch of other methods on ArrayDeque<T> that would make sense to provide "wrapping" variants for.

So, should I:

1. Create my own MIT-licensed crate under a different name by copying your code but changing its logic from "drop if full" to "overwrite if full"?
2. Make a PR for arraydeque adding wrapping_-variants (or whatever prefix seems most appropriate) to all methods that would make sense?
3. Make a PR for arraydeque adding a overwriting: bool field to ArrayDeque<T> (along with setter & getter), which would then change the behavior of the existing API?
4. Make a PR for arraydeque adding a Wrapping<T> wrapper for ArrayDeque<T>, which would then change the behavior of the wrapped deque's API?

?

1. would cause needless duplication.
2. would clutter the API.
3. would make the API depend on the state of self.overwriting.
4. would probably be the cleanest approach?

Unneeded `T: Clone` bound on `Iter<'a, T>`

The auto derive Clone add a unneeded bound on T.

I can do the fixing PR if you want.

Infinite (looping) iterator?

AFAICS. the only iterators are single-pass. Having a loop-forever iterator would be neat.

Use const generics instead of `generic-array`

Now that Rust supports const generics, ArrayDeque should take the capacity as a type parameter rather than an array type. This prevents the deque from using smaller index types, but that isn't a big drawback in practice. ArrayVec is already using const generics, and their array index is set to u32.

Access raw single backing slice?

In circumstances where a user knows they are not going to pop_back/front passed a particular item, but may otherwise be doing various pushes and pops, it would be nice to be able to hold on to an index/iterator that would keep working as long as the specific item being referred to hasn't been removed. The most straightforward way to do this is to give the user the index of an item in the array and an interface for accessing it (where the index is used directly on the raw array backing the container, without taking into account the current location of head or tail).

You can kind of get this effect now by calling as_slices or as_mut_slices right when the container is created and only using the first slice, but this relies on knowledge of implementation details for the initial container (e.g. since the buffer is circular in principle there is no reason that tail couldn't start at N/2). Is there a better way?

Bad use of `mem::uninitialized` in constructor

Spawned from rust-lang/rust#58684

The following test is likely to fail in the current code base, at least for many versions of rustc.

    #[test]
    fn test_option_encoding() {
        let tester: ArrayDeque<[Box<()>; 100], Wrapping> = ArrayDeque::new();
        assert!(Some(tester).is_some());
    }

The reason it will fail is because ArrayDeque::new() is using mem::uninitialized to create the array itself, which is discouraged because the resulting value will tend to yield undefined behavior unless the type is valid for all possible bit patterns. (And an easy example of a type that is not valid for all possible bit patterns is Box<T>, since it must be non-null.)

The test above is demonstrating how violating this rule can break invariants like Some(E).is_some() for any E.

• One potential fix for this has been pointed out by oli: Use an untagged union instead of mem::uninitialized.
• Another potential fix would be to use MaybeUninit instead of ManuallyDrop, as pointed out by nagisa.

Neither of these fixes is available in stable Rust today, though. (untagged unions only support Copy data if you're on stable.)

Expose `set_len`?

I'm writing some embedded code using this crate to buffer USB data. To read data, I have to call a read_packet(&mut [u8]) method, but accessing an ArrayDeque's backing array directly then setting the length is currently impossible.

I could create an array, read into it, then extend, but I'd prefer to use the deque rather than allocating memory for every packet:

let mut usb = ...;
let mut buf = ArrayDeque::<_, 128>::default();

const PKT_SIZE: usize = 64;
assert!(buf.capacity() - buf.len() >= PKT_SIZE);

let mut packet = [0; PKT_SIZE];
let read_count = usb.read_packet(&mut packet)?;
buf.extend_back(packet[..read_count].iter().copied());

If I know a whole packet can fit at the deque's tail, say it's empty and contiguous, I should be able to read into the buffer like this safely:

buf.linearize();
assert!(buf.is_empty());

unsafe {
    let slice = MaybeUninit::slice_assume_init_mut(buf.as_uninit_slice_mut());
    let read_count = usb.read_packet(&mut slice[..PKT_SIZE])?;
    // set_len?
}

But now how do I "grow" the deque to inform it of the new elements? Exposing set_len as is (unsafe) would help in this use case