#Announcing ArrayDeque
https://crates.io/crates/arraydeque/
A ring buffer with a fixed capacity
ArrayDeque brings full functionality of Deque in std to stack-only-world. It's especially suit for microcontroller and hardware driver to buffer IO flow, at the same time, without involving heap.
Example
let mut vector: ArrayDeque<[usize; 8]> = ArrayDeque::new();
assert!(vector.capacity() == 7);
assert!(vector.len() == 0);
vector.push_back(1);
vector.push_back(2);
assert!(vector.len() == 2);
assert_eq!(vector.pop_front(), Some(1));
assert_eq!(vector.pop_front(), Some(2));
assert_eq!(vector.pop_front(), None);
Another example showing more functionality
let mut vector: ArrayDeque<[_; 8]> = ArrayDeque::new();
let mut vector2: ArrayDeque<[_; 8]> = ArrayDeque::new();
vector.extend(0..5);
vector2.extend(5..7);
assert_eq!(format!("{:?}", vector), "[0, 1, 2, 3, 4]");
assert_eq!(format!("{:?}", vector2), "[5, 6]");
vector.append(&mut vector2);
assert_eq!(format!("{:?}", vector), "[0, 1, 2, 3, 4, 5, 6]");
assert_eq!(format!("{:?}", vector2), "[]");
Looking forward to your advice.
3 Likes
Cool. What would you say are the main advantages / disadvantages to cbuf?
Cbuf is also a ring buffer for microcontrollers
Edit: I guess for starters it follows the same api and naming convention!
1 Like
Thank you for linking the issue.
I don't know the issue, since I am not in servo's thread. They seems to be talking about a re-creation of ArrayDeque, so I will suggest them.
1 Like
There are two major advantages of ArrayDeque:
-
ArrayDeque takes over ownership of an array, since cbuf takes a reference, which makes ArrayDeque's methods more ergonomic.
-
API design: cbuf doesn't support IntoIterator, drain() and something else, and importantly you can't be aware of overflow becausethe method put() on CBufControl doesn't return the failed value and instead does not thing when it is full.
Disadvantage:
-
cbuf provide full capacity from the array while ArrayDeque's capacity is always array.len() - 1. This is a performance tradeoff, and I choose to lose one cell of storage in order to reduce complexity on operations.
I started the works on this crate on October, 2016 when there have been loads of ring buffer, including cbuf on crate.io, but I was disappointed with all of them, and their problems included lack of documentation, insufficient testing , lack of functionalities and lack of maintenance.
2 Likes
It's not just for small CPUs 
In Ada 2012 they have added the "bounded containers":
http://www.ada-auth.org/standards/12rat/html/Rat12-8-2.html
A.C.Bounded_Vectors
A.C.Bounded_Doubly_Linked_Lists
A.C.Bounded_Hashed_Maps
A.C.Bounded_Ordered_Maps
A.C.Bounded_Hashed_Sets
A.C.Bounded_Ordered_Sets
It's nice to have a complete suit of stack-allocated collections in Rust. It's also nice to have heap-backed collections when the amount of data grows too much (SmallVec, SmallString, small-number optimized BigInts, and so on).
2 Likes
I've been looking for something like this for my gcode crate for a buffered reader. I especially like how a push will give you back your element if it fails and how it takes a lot of inspiration from bluss/arrayvec.
Just out of curiosity, why is ArrayDeque's capacity one less than the underlying array? The Wikipedia article you link to doesn't seem to explain why, or maybe I just missed it when skimming the article.
1 Like
If it's implemented as a ring buffer, as I understand, then it's probably a way to resolve the circular ambiguity.
The simplest way to implement a ring buffer is to have an array, one index representing the first data item in the array, and one index representing the last data item in the array. So, something like this:
struct RingBuffer<T> {
data: [T; CAPACITY],
start: usize,
end: usize,
}
If, like Rust, we use right-exclusive ranges, we consider the ring buffer to be empty when start = end. In FIFO operation, to push an element, we store it at data[end] and increment end (modulo CAPACITY), and to pop an element, we read from data[start] and increment start (modulo CAPACITY). Add error handling (e.g. empty/full buffer) and a way to insert and read data in both directions, and you get a decent implementation.
But in this implementation, there is no way to distinguish between a full and an empty buffer. In both cases, one will have start = end. There are many ways to resolve this ambiguity, but the simplest by far is to never completely fill the buffer, and only use CAPACITY-1 elements.
Hope this helps.
5 Likes
You can add my SmallBox to your menu.
2 Likes
