fixed_vec_deque/lib.rs
1//! [<img alt="github" src="https://img.shields.io/badge/github-udoprog/fixed--vec--deque-8da0cb?style=for-the-badge&logo=github" height="20">](https://github.com/udoprog/fixed-vec-deque)
2//! [<img alt="crates.io" src="https://img.shields.io/crates/v/fixed-vec-deque.svg?style=for-the-badge&color=fc8d62&logo=rust" height="20">](https://crates.io/crates/fixed-vec-deque)
3//! [<img alt="docs.rs" src="https://img.shields.io/badge/docs.rs-fixed--vec--deque-66c2a5?style=for-the-badge&logoColor=white&logo=data:image/svg+xml;base64,PHN2ZyByb2xlPSJpbWciIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgdmlld0JveD0iMCAwIDUxMiA1MTIiPjxwYXRoIGZpbGw9IiNmNWY1ZjUiIGQ9Ik00ODguNiAyNTAuMkwzOTIgMjE0VjEwNS41YzAtMTUtOS4zLTI4LjQtMjMuNC0zMy43bC0xMDAtMzcuNWMtOC4xLTMuMS0xNy4xLTMuMS0yNS4zIDBsLTEwMCAzNy41Yy0xNC4xIDUuMy0yMy40IDE4LjctMjMuNCAzMy43VjIxNGwtOTYuNiAzNi4yQzkuMyAyNTUuNSAwIDI2OC45IDAgMjgzLjlWMzk0YzAgMTMuNiA3LjcgMjYuMSAxOS45IDMyLjJsMTAwIDUwYzEwLjEgNS4xIDIyLjEgNS4xIDMyLjIgMGwxMDMuOS01MiAxMDMuOSA1MmMxMC4xIDUuMSAyMi4xIDUuMSAzMi4yIDBsMTAwLTUwYzEyLjItNi4xIDE5LjktMTguNiAxOS45LTMyLjJWMjgzLjljMC0xNS05LjMtMjguNC0yMy40LTMzLjd6TTM1OCAyMTQuOGwtODUgMzEuOXYtNjguMmw4NS0zN3Y3My4zek0xNTQgMTA0LjFsMTAyLTM4LjIgMTAyIDM4LjJ2LjZsLTEwMiA0MS40LTEwMi00MS40di0uNnptODQgMjkxLjFsLTg1IDQyLjV2LTc5LjFsODUtMzguOHY3NS40em0wLTExMmwtMTAyIDQxLjQtMTAyLTQxLjR2LS42bDEwMi0zOC4yIDEwMiAzOC4ydi42em0yNDAgMTEybC04NSA0Mi41di03OS4xbDg1LTM4Ljh2NzUuNHptMC0xMTJsLTEwMiA0MS40LTEwMi00MS40di0uNmwxMDItMzguMiAxMDIgMzguMnYuNnoiPjwvcGF0aD48L3N2Zz4K" height="20">](https://docs.rs/fixed-vec-deque)
4//!
5//! A double-ended queue implemented with a fixed ring buffer.
6//!
7//! This queue has `O(1)` amortized inserts and removals from both ends of the
8//! container. It also has `O(1)` indexing like a vector. The contained elements
9//! are not required to be copyable, and the queue will be sendable if the
10//! contained type is sendable.
11//!
12//! The size of the `FixedVecDeque` must be completely specified at construction
13//! time, like this:
14//!
15//! ```rust
16//! # extern crate fixed_vec_deque;
17//! use fixed_vec_deque::FixedVecDeque;
18//!
19//! let _ = FixedVecDeque::<[Foo; 4]>::new();
20//!
21//! #[derive(Default)]
22//! struct Foo;
23//! ```
24//!
25//! Modifications can only happen _in-place_, this means that items stored in
26//! the queue must always implement `Default`.
27//!
28//! [`push_back`] and [`push_front`] don't take an argument, instead they return
29//! a mutable reference so that the newly inserted element is mutated in-place:
30//!
31//! ```rust
32//! # extern crate fixed_vec_deque;
33//! use fixed_vec_deque::FixedVecDeque;
34//!
35//! let mut buf = FixedVecDeque::<[Foo; 4]>::new();
36//! buf.push_back().data = 42;
37//!
38//! #[derive(Default)]
39//! struct Foo {
40//! data: u32,
41//! }
42//! ```
43//!
44//! On a similar note, [`pop_front`] and [`pop_back`] returns references instead of moving the
45//! elements.
46//!
47//! A consequence of this is that this structure _never_ modifies the data it contains, even if it
48//! has been _popped_.
49//!
50//! <br>
51//!
52//! ## Missing APIs
53//!
54//! [Some APIs are missing](https://github.com/udoprog/fixed-vec-deque/issues/2).
55//! If you want to help out, leave a comment in the issue!
56//!
57//! <br>
58//!
59//! ## When should I use `FixedVecDeque`?
60//!
61//! Generally when the following holds:
62//!
63//! * You have a maximum number of elements that you need to store for a short period of time.
64//! * You only need to modify part of the element from the default when pushed.
65//!
66//! A conventional collection require you to write a "complete" element every time it is added to
67//! it.
68//! With `FixedVecDeque` we can instead modify the existing elements in place, and keep track of
69//! how many such logical "additions" we have done.
70//! For example:
71//!
72//! ```rust
73//! # extern crate fixed_vec_deque;
74//! use fixed_vec_deque::FixedVecDeque;
75//! use std::collections::VecDeque;
76//!
77//! pub struct BigStruct {
78//! fields: [u64; 100],
79//! }
80//!
81//! impl Default for BigStruct {
82//! fn default() -> Self {
83//! BigStruct {
84//! fields: [0u64; 100],
85//! }
86//! }
87//! }
88//!
89//! let mut deq = FixedVecDeque::<[BigStruct; 0x10]>::new();
90//!
91//! for i in 0..100 {
92//! deq.push_back().fields[i] = i as u64;
93//!
94//! let mut count = 0;
95//!
96//! for big in &deq {
97//! count += 1;
98//! assert_eq!(big.fields[i], i as u64);
99//! }
100//!
101//! assert_eq!(count, 1);
102//! deq.clear();
103//! }
104//!
105//! deq.clear();
106//!
107//! // Note: modifications are still stored in the ring buffer and will be visible the next time we
108//! // push to it unless we cleared it.
109//! for i in 0..100 {
110//! assert_eq!(deq.push_back().fields[i], i as u64);
111//! deq.clear();
112//! }
113//! ```
114//!
115//! [`push_back`]: https://docs.rs/fixed-vec-deque/latest/fixed_vec_deque/struct.FixedVecDeque.html#method.push_back
116//! [`push_front`]: https://docs.rs/fixed-vec-deque/latest/fixed_vec_deque/struct.FixedVecDeque.html#method.push_front
117//! [`pop_back`]: https://docs.rs/fixed-vec-deque/latest/fixed_vec_deque/struct.FixedVecDeque.html#method.pop_back
118//! [`pop_front`]: https://docs.rs/fixed-vec-deque/latest/fixed_vec_deque/struct.FixedVecDeque.html#method.pop_front
119
120#![cfg_attr(nightly, feature(test))]
121
122/// Code extensively based on Rust stdlib:
123/// https://github.com/rust-lang/rust/blob/e8aef7cae14bc7a56859408c90253e9bcc07fcff/src/liballoc/collections/vec_deque.rs
124/// And rust-smallvec:
125/// https://github.com/servo/rust-smallvec
126use std::cmp;
127use std::fmt;
128use std::hash;
129use std::iter::{repeat, FromIterator};
130use std::marker;
131use std::mem;
132use std::ops::{Index, IndexMut};
133use std::ptr;
134use std::slice;
135
136/// A double-ended queue implemented with a fixed buffer.
137pub struct FixedVecDeque<T>
138where
139 T: Array,
140{
141 // where we are currently writing.
142 head: usize,
143 // how many valid elements we have in the queue.
144 len: usize,
145 // underlying array.
146 data: T,
147}
148
149impl<T> Clone for FixedVecDeque<T>
150where
151 T: Array,
152 T::Item: Clone,
153{
154 fn clone(&self) -> Self {
155 let data = unsafe {
156 let mut data: mem::MaybeUninit<T> = mem::MaybeUninit::uninit();
157 slice::from_raw_parts_mut((*data.as_mut_ptr()).ptr_mut(), T::size())
158 .clone_from_slice(self.buffer_as_slice());
159 data.assume_init()
160 };
161
162 FixedVecDeque {
163 head: self.head,
164 len: self.len,
165 data,
166 }
167 }
168}
169
170impl<T> FixedVecDeque<T>
171where
172 T: Array,
173 T::Item: Default,
174{
175 /// Construct a new fixed ring buffer, pre-allocating all elements through [`Default`].
176 ///
177 /// ## Examples
178 ///
179 /// ```rust
180 /// use fixed_vec_deque::FixedVecDeque;
181 ///
182 /// let mut deq = FixedVecDeque::<[u32; 16]>::new();
183 /// assert_eq!(deq, []);
184 /// *deq.push_back() = 1;
185 /// assert_eq!(deq, [1]);
186 /// ```
187 pub fn new() -> Self {
188 FixedVecDeque {
189 head: 0,
190 len: 0,
191 data: Self::data_from_default(),
192 }
193 }
194
195 /// Initialize stored data using `Default::default()`
196 fn data_from_default() -> T {
197 unsafe {
198 let mut data: mem::MaybeUninit<T> = mem::MaybeUninit::uninit();
199 let m = (*data.as_mut_ptr()).ptr_mut();
200
201 for o in 0..T::size() {
202 ptr::write(m.add(o), T::Item::default());
203 }
204
205 data.assume_init()
206 }
207 }
208}
209
210impl<T> FixedVecDeque<T>
211where
212 T: Array,
213{
214 /// Returns `true` if the `FixedVecDeque` is empty.
215 ///
216 /// # Examples
217 ///
218 /// ```
219 /// # extern crate fixed_vec_deque;
220 /// use fixed_vec_deque::FixedVecDeque;
221 ///
222 /// let mut v = FixedVecDeque::<[u32; 1]>::new();
223 /// assert!(v.is_empty());
224 /// *v.push_front() = 1;
225 /// assert!(!v.is_empty());
226 /// ```
227 pub fn is_empty(&self) -> bool {
228 self.len == 0
229 }
230
231 /// Returns `true` if the `FixedVecDeque` is full.
232 ///
233 /// Writing to a queue that is full will overwrite existing elements.
234 ///
235 /// # Examples
236 ///
237 /// ```
238 /// # extern crate fixed_vec_deque;
239 /// use fixed_vec_deque::FixedVecDeque;
240 ///
241 /// let mut v = FixedVecDeque::<[u32; 1]>::new();
242 /// assert!(!v.is_full());
243 /// *v.push_front() = 1;
244 /// assert!(v.is_full());
245 /// ```
246 pub fn is_full(&self) -> bool {
247 self.len == T::size()
248 }
249
250 /// Returns the number of elements in the `FixedVecDeque`.
251 ///
252 /// # Examples
253 ///
254 /// ```
255 /// # extern crate fixed_vec_deque;
256 /// use fixed_vec_deque::FixedVecDeque;
257 ///
258 /// let mut v = FixedVecDeque::<[u32; 2]>::new();
259 /// assert_eq!(v.len(), 0);
260 /// *v.push_back() = 1;
261 /// assert_eq!(v.len(), 1);
262 /// *v.push_back() = 1;
263 /// assert_eq!(v.len(), 2);
264 /// ```
265 pub fn len(&self) -> usize {
266 self.len
267 }
268
269 /// Returns the number of elements the `FixedVecDeque` can hold.
270 ///
271 /// # Examples
272 ///
273 /// ```
274 /// use fixed_vec_deque::FixedVecDeque;
275 ///
276 /// let buf = FixedVecDeque::<[u32; 16]>::new();
277 /// assert_eq!(buf.capacity(), 16);
278 /// ```
279 #[inline]
280 pub fn capacity(&self) -> usize {
281 T::size()
282 }
283
284 /// Shortens the `FixedVecDeque`, causing excess elements to be unused.
285 ///
286 /// If `len` is greater than the `FixedVecDeque`'s current length, this has no
287 /// effect.
288 ///
289 /// # Examples
290 ///
291 /// ```
292 /// use fixed_vec_deque::FixedVecDeque;
293 ///
294 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
295 /// *buf.push_back() = 5;
296 /// *buf.push_back() = 10;
297 /// *buf.push_back() = 15;
298 /// assert_eq!(buf, [5, 10, 15]);
299 /// buf.truncate(1);
300 /// assert_eq!(buf, [5]);
301 /// ```
302 pub fn truncate(&mut self, len: usize) {
303 if len < self.len {
304 self.head = T::wrap_sub(self.head, self.len - len);
305 self.len = len;
306 }
307 }
308
309 /// Provides a reference to the front element, or `None` if the `FixedVecDeque` is
310 /// empty.
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// use fixed_vec_deque::FixedVecDeque;
316 ///
317 /// let mut d = FixedVecDeque::<[u32; 2]>::new();
318 /// assert_eq!(d.front(), None);
319 ///
320 /// *d.push_back() = 1;
321 /// *d.push_back() = 2;
322 /// assert_eq!(d.front(), Some(&1));
323 /// ```
324 pub fn front(&self) -> Option<&T::Item> {
325 if self.is_empty() {
326 return None;
327 }
328
329 let front = self.tail();
330 Some(unsafe { self.buffer(front) })
331 }
332
333 /// Provides a mutable reference to the front element, or `None` if the `FixedVecDeque` is
334 /// empty.
335 ///
336 /// # Examples
337 ///
338 /// ```
339 /// use fixed_vec_deque::FixedVecDeque;
340 ///
341 /// let mut d = FixedVecDeque::<[u32; 2]>::new();
342 ///
343 /// assert_eq!(d.front_mut(), None);
344 ///
345 /// *d.push_back() = 1;
346 /// *d.push_back() = 2;
347 ///
348 /// match d.front_mut() {
349 /// Some(x) => *x = 9,
350 /// None => (),
351 /// }
352 ///
353 /// assert_eq!(d.front(), Some(&9));
354 /// assert_eq!(d.back(), Some(&2));
355 /// ```
356 pub fn front_mut(&mut self) -> Option<&mut T::Item> {
357 if self.is_empty() {
358 return None;
359 }
360
361 let front = self.tail();
362 Some(unsafe { self.buffer_mut(front) })
363 }
364
365 /// Provides a reference to the back element, or `None` if the `FixedVecDeque` is
366 /// empty.
367 ///
368 /// # Examples
369 ///
370 /// ```
371 /// use fixed_vec_deque::FixedVecDeque;
372 ///
373 /// let mut d = FixedVecDeque::<[u32; 2]>::new();
374 ///
375 /// assert_eq!(d.back(), None);
376 ///
377 /// *d.push_back() = 1;
378 /// *d.push_back() = 2;
379 /// assert_eq!(d.back(), Some(&2));
380 /// ```
381 pub fn back(&self) -> Option<&T::Item> {
382 if self.is_empty() {
383 return None;
384 }
385
386 let back = T::wrap_sub(self.head, 1);
387 Some(unsafe { self.buffer(back) })
388 }
389
390 /// Provides a mutable reference to the back element, or `None` if the
391 /// `FixedVecDeque` is empty.
392 ///
393 /// # Examples
394 ///
395 /// ```
396 /// use fixed_vec_deque::FixedVecDeque;
397 ///
398 /// let mut d = FixedVecDeque::<[u32; 2]>::new();
399 ///
400 /// assert_eq!(d.back(), None);
401 ///
402 /// *d.push_back() = 1;
403 /// *d.push_back() = 2;
404 ///
405 /// match d.back_mut() {
406 /// Some(x) => *x = 9,
407 /// None => (),
408 /// }
409 /// assert_eq!(d.back(), Some(&9));
410 /// ```
411 pub fn back_mut(&mut self) -> Option<&mut T::Item> {
412 if self.is_empty() {
413 return None;
414 }
415
416 let back = T::wrap_sub(self.head, 1);
417 Some(unsafe { self.buffer_mut(back) })
418 }
419
420 /// Prepends an element to the `FixedVecDeque`.
421 ///
422 /// # Panics
423 ///
424 /// Calling this function will panic if the circular buffer is zero-sized.
425 ///
426 /// # Examples
427 ///
428 /// ```
429 /// use fixed_vec_deque::FixedVecDeque;
430 ///
431 /// let mut d = FixedVecDeque::<[u32; 3]>::new();
432 ///
433 /// assert_eq!(d.front(), None);
434 /// assert_eq!(d.back(), None);
435 ///
436 /// *d.push_front() = 1;
437 /// assert_eq!(d.front(), Some(&1));
438 /// assert_eq!(d.back(), Some(&1));
439 ///
440 /// *d.push_front() = 2;
441 /// assert_eq!(d.front(), Some(&2));
442 /// assert_eq!(d.back(), Some(&1));
443 ///
444 /// *d.push_front() = 3;
445 /// assert_eq!(d.front(), Some(&3));
446 /// assert_eq!(d.back(), Some(&1));
447 ///
448 /// *d.push_front() = 4;
449 /// assert_eq!(d.front(), Some(&4));
450 /// assert_eq!(d.back(), Some(&2));
451 /// ```
452 pub fn push_front(&mut self) -> &mut T::Item {
453 assert!(T::size() > 0, "Cannot add to an empty deque");
454
455 // overwriting existing elements.
456 if self.len == T::size() {
457 self.head = T::wrap_sub(self.head, 1);
458 let front = self.head;
459 return unsafe { self.buffer_mut(front) };
460 }
461
462 self.len += 1;
463 let front = self.tail();
464 unsafe { self.buffer_mut(front) }
465 }
466
467 /// Removes the first element and returns it, or `None` if the `FixedVecDeque` is
468 /// empty.
469 ///
470 /// # Examples
471 ///
472 /// ```
473 /// use fixed_vec_deque::FixedVecDeque;
474 ///
475 /// let mut d = FixedVecDeque::<[u32; 2]>::new();
476 /// *d.push_back() = 1;
477 /// *d.push_back() = 2;
478 ///
479 /// assert_eq!(d.pop_front(), Some(&mut 1));
480 /// assert_eq!(d.pop_front(), Some(&mut 2));
481 /// assert_eq!(d.pop_front(), None);
482 /// ```
483 pub fn pop_front(&mut self) -> Option<&mut T::Item> {
484 if self.is_empty() {
485 return None;
486 }
487
488 let tail = self.tail();
489 self.len -= 1;
490 unsafe { Some(self.buffer_mut(tail)) }
491 }
492
493 /// Appends an element to the back of the `FixedVecDeque` by returning a mutable reference that
494 /// can be modified to it.
495 ///
496 /// Note: this might potentially remove elements from the head, unless they have been read.
497 ///
498 /// # Panics
499 ///
500 /// Calling this function will panic if the circular buffer is zero-sized.
501 ///
502 /// # Examples
503 ///
504 /// ```
505 /// use fixed_vec_deque::FixedVecDeque;
506 ///
507 /// let mut buf = FixedVecDeque::<[u32; 2]>::new();
508 /// assert_eq!(buf.back(), None);
509 /// assert_eq!(buf.front(), None);
510 ///
511 /// *buf.push_back() = 1;
512 ///
513 /// assert_eq!(buf.front(), Some(&1));
514 /// assert_eq!(buf.back(), Some(&1));
515 ///
516 /// *buf.push_back() = 2;
517 ///
518 /// assert_eq!(buf.front(), Some(&1));
519 /// assert_eq!(buf.back(), Some(&2));
520 ///
521 /// *buf.push_back() = 3;
522 ///
523 /// assert_eq!(buf.front(), Some(&2));
524 /// assert_eq!(buf.back(), Some(&3));
525 /// ```
526 ///
527 /// ```
528 /// use fixed_vec_deque::FixedVecDeque;
529 ///
530 /// let mut buf = FixedVecDeque::<[u32; 1]>::new();
531 /// assert_eq!(buf.back(), None);
532 /// assert_eq!(buf.front(), None);
533 ///
534 /// *buf.push_back() = 1;
535 ///
536 /// assert_eq!(buf.front(), Some(&1));
537 /// assert_eq!(buf.back(), Some(&1));
538 ///
539 /// *buf.push_back() = 2;
540 ///
541 /// assert_eq!(buf.front(), Some(&2));
542 /// assert_eq!(buf.back(), Some(&2));
543 ///
544 /// buf.pop_back();
545 ///
546 /// assert!(buf.is_empty());
547 /// assert_eq!(buf.back(), None);
548 /// assert_eq!(buf.front(), None);
549 /// ```
550 pub fn push_back(&mut self) -> &mut T::Item {
551 assert!(T::size() > 0, "Cannot add to an empty deque");
552
553 let head = self.head;
554 self.head = T::wrap_add(self.head, 1);
555
556 if self.len < T::size() {
557 self.len += 1;
558 }
559
560 unsafe { self.buffer_mut(head) }
561 }
562
563 /// Removes the last element from the `FixedVecDeque` and returns a reference to it, or `None`
564 /// if it is empty.
565 ///
566 /// # Examples
567 ///
568 /// ```
569 /// use fixed_vec_deque::FixedVecDeque;
570 ///
571 /// let mut buf = FixedVecDeque::<[u32; 2]>::new();
572 /// assert_eq!(buf.pop_back(), None);
573 /// *buf.push_back() = 1;
574 /// *buf.push_back() = 3;
575 /// assert_eq!(buf.pop_back(), Some(&mut 3));
576 /// ```
577 pub fn pop_back(&mut self) -> Option<&mut T::Item> {
578 if self.is_empty() {
579 return None;
580 }
581
582 self.head = T::wrap_sub(self.head, 1);
583 self.len -= 1;
584 let head = self.head;
585 unsafe { Some(self.buffer_mut(head)) }
586 }
587
588 /// Removes an element from anywhere in the `FixedVecDeque` and returns a mutable reference to
589 /// it, replacing it with the last element.
590 ///
591 /// This does not preserve ordering, but is O(1).
592 ///
593 /// Returns `None` if `index` is out of bounds.
594 ///
595 /// Element at index 0 is the front of the queue.
596 ///
597 /// # Examples
598 ///
599 /// ```
600 /// use fixed_vec_deque::FixedVecDeque;
601 ///
602 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
603 /// assert_eq!(buf.swap_remove_back(0), None);
604 /// *buf.push_back() = 1;
605 /// *buf.push_back() = 2;
606 /// *buf.push_back() = 3;
607 /// assert_eq!(buf, [1, 2, 3]);
608 ///
609 /// assert_eq!(buf.swap_remove_back(0), Some(&mut 1));
610 /// assert_eq!(buf, [3, 2]);
611 /// ```
612 pub fn swap_remove_back(&mut self, index: usize) -> Option<&mut T::Item> {
613 let length = self.len();
614 if length > 0 && index < length - 1 {
615 self.swap(index, length - 1);
616 } else if index >= length {
617 return None;
618 }
619 self.pop_back()
620 }
621
622 /// Removes an element from anywhere in the `FixedVecDeque` and returns a reference to it,
623 /// replacing it with the first element.
624 ///
625 /// This does not preserve ordering, but is O(1).
626 ///
627 /// Returns `None` if `index` is out of bounds.
628 ///
629 /// Element at index 0 is the front of the queue.
630 ///
631 /// # Examples
632 ///
633 /// ```
634 /// use fixed_vec_deque::FixedVecDeque;
635 ///
636 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
637 /// assert_eq!(buf.swap_remove_front(0), None);
638 /// *buf.push_back() = 1;
639 /// *buf.push_back() = 2;
640 /// *buf.push_back() = 3;
641 /// assert_eq!(buf, [1, 2, 3]);
642 ///
643 /// assert_eq!(buf.swap_remove_front(2), Some(&mut 3));
644 /// assert_eq!(buf, [2, 1]);
645 /// ```
646 pub fn swap_remove_front(&mut self, index: usize) -> Option<&mut T::Item> {
647 let length = self.len();
648 if length > 0 && index < length && index != 0 {
649 self.swap(index, 0);
650 } else if index >= length {
651 return None;
652 }
653 self.pop_front()
654 }
655
656 /// Removes and returns the element at `index` from the `VecDeque`.
657 /// Whichever end is closer to the removal point will be moved to make
658 /// room, and all the affected elements will be moved to new positions.
659 /// Returns `None` if `index` is out of bounds.
660 ///
661 /// Element at index 0 is the front of the queue.
662 ///
663 /// # Examples
664 ///
665 /// ```
666 /// use fixed_vec_deque::FixedVecDeque;
667 ///
668 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
669 /// *buf.push_back() = 1;
670 /// *buf.push_back() = 2;
671 /// *buf.push_back() = 3;
672 /// assert_eq!(buf, [1, 2, 3]);
673 ///
674 /// assert_eq!(buf.remove(1), Some(&mut 2));
675 /// assert_eq!(buf, [1, 3]);
676 /// ```
677 pub fn remove(&mut self, index: usize) -> Option<&mut T::Item>
678 where
679 T::Item: fmt::Debug,
680 {
681 // if empty, nothing to do.
682 if T::size() == 0 || index >= self.len {
683 return None;
684 }
685
686 // There are three main cases:
687 // Elements are contiguous
688 // Elements are discontiguous and the removal is in the tail section
689 // Elements are discontiguous and the removal is in the head section
690 // - special case when elements are technically contiguous,
691 // but self.head = 0
692 //
693 // For each of those there are two more cases:
694 // Insert is closer to tail
695 // Insert is closer to head
696 //
697 // Key: H - self.head
698 // T - self.tail
699 // o - Valid element
700 // x - Element marked for removal
701 // R - Indicates element that is being removed
702 // M - Indicates element was moved
703
704 let idx = self.ptr_index(index);
705 let head = self.head;
706 let tail = self.tail();
707
708 let tmp = unsafe { self.buffer_read(idx) };
709
710 let distance_to_tail = index;
711 let distance_to_head = self.len() - index;
712
713 let contiguous = self.is_contiguous();
714
715 let idx = match (
716 contiguous,
717 distance_to_tail <= distance_to_head,
718 idx >= tail,
719 ) {
720 (true, true, _) => {
721 unsafe {
722 // contiguous, remove closer to tail:
723 //
724 // T R H
725 // [. . . o o x o o o o . . . . . .]
726 //
727 // T H
728 // [. . . . o o o o o o . . . . . .]
729 // M M
730
731 self.copy(tail + 1, tail, index);
732 tail
733 }
734 }
735 (true, false, _) => {
736 unsafe {
737 // contiguous, remove closer to head:
738 //
739 // T R H
740 // [. . . o o o o x o o . . . . . .]
741 //
742 // T H
743 // [. . . o o o o o o . . . . . . .]
744 // M M
745
746 self.copy(idx, idx + 1, head - idx - 1);
747 self.head -= 1;
748 head
749 }
750 }
751 (false, true, true) => {
752 unsafe {
753 // discontiguous, remove closer to tail, tail section:
754 //
755 // H T R
756 // [o o o o o o . . . . . o o x o o]
757 //
758 // H T
759 // [o o o o o o . . . . . . o o o o]
760 // M M
761
762 self.copy(tail + 1, tail, index);
763 tail
764 }
765 }
766 (false, false, false) => {
767 unsafe {
768 // discontiguous, remove closer to head, head section:
769 //
770 // R H T
771 // [o o o o x o o . . . . . . o o o]
772 //
773 // H T
774 // [o o o o o o . . . . . . . o o o]
775 // M M
776
777 self.copy(idx, idx + 1, head - idx - 1);
778 self.head -= 1;
779 head
780 }
781 }
782 (false, false, true) => {
783 unsafe {
784 // discontiguous, remove closer to head, tail section:
785 //
786 // H T R
787 // [o o o . . . . . . o o o o o x o]
788 //
789 // H T
790 // [o o . . . . . . . o o o o o o o]
791 // M M M M
792 //
793 // or quasi-discontiguous, remove next to head, tail section:
794 //
795 // H T R
796 // [. . . . . . . . . o o o o o x o]
797 //
798 // T H
799 // [. . . . . . . . . o o o o o o .]
800 // M
801
802 // draw in elements in the tail section
803 self.copy(idx, idx + 1, T::size() - idx - 1);
804
805 // Prevents underflow.
806 if head != 0 {
807 // copy first element into empty spot
808 self.copy(T::size() - 1, 0, 1);
809
810 // move elements in the head section backwards
811 self.copy(0, 1, head - 1);
812 }
813
814 self.head = T::wrap_sub(self.head, 1);
815 head
816 }
817 }
818 (false, true, false) => {
819 unsafe {
820 // discontiguous, remove closer to tail, head section:
821 //
822 // R H T
823 // [o o x o o o o o o o . . . o o o]
824 //
825 // H T
826 // [o o o o o o o o o o . . . . o o]
827 // M M M M M
828
829 // draw in elements up to idx
830 self.copy(1, 0, idx);
831
832 // copy last element into empty spot
833 self.copy(0, T::size() - 1, 1);
834
835 // move elements from tail to end forward, excluding the last one
836 self.copy(tail + 1, tail, T::size() - tail - 1);
837
838 tail
839 }
840 }
841 };
842
843 self.len -= 1;
844
845 unsafe {
846 // write temporary into shifted location since we need a stable memory location for it!
847 self.buffer_write(idx, tmp);
848 Some(self.buffer_mut(idx))
849 }
850 }
851
852 /// Retains only the elements specified by the predicate.
853 ///
854 /// In other words, remove all elements `e` such that `f(&e)` returns false.
855 /// This method operates in place and preserves the order of the retained
856 /// elements.
857 ///
858 /// # Examples
859 ///
860 /// ```
861 /// use fixed_vec_deque::FixedVecDeque;
862 ///
863 /// let mut buf = FixedVecDeque::<[usize; 8]>::new();
864 /// buf.extend(1..5);
865 /// buf.retain(|&x| x % 2 == 0);
866 /// assert_eq!(buf, [2, 4]);
867 /// ```
868 pub fn retain<F>(&mut self, mut f: F)
869 where
870 F: FnMut(&T::Item) -> bool,
871 {
872 let len = self.len();
873 let mut del = 0;
874
875 for i in 0..len {
876 let off = self.ptr_index(i);
877
878 if !f(unsafe { self.buffer(off) }) {
879 del += 1;
880 } else if del > 0 {
881 self.swap(i - del, i);
882 }
883 }
884
885 if del > 0 {
886 self.truncate(len - del);
887 }
888 }
889
890 /// Returns a front-to-back iterator.
891 ///
892 /// # Examples
893 ///
894 /// ```
895 /// use fixed_vec_deque::FixedVecDeque;
896 ///
897 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
898 /// *buf.push_back() = 5;
899 /// *buf.push_back() = 3;
900 /// *buf.push_back() = 4;
901 ///
902 /// let b: &[_] = &[&5, &3, &4];
903 /// let c: Vec<&u32> = buf.iter().collect();
904 /// assert_eq!(&c[..], b);
905 /// ```
906 pub fn iter(&self) -> Iter<'_, T> {
907 Iter {
908 data: self.data.ptr(),
909 head: self.head,
910 len: self.len,
911 marker: marker::PhantomData,
912 }
913 }
914
915 /// Returns a front-to-back iterator that returns mutable references.
916 ///
917 /// # Examples
918 ///
919 /// ```
920 /// use fixed_vec_deque::FixedVecDeque;
921 ///
922 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
923 /// *buf.push_back() = 5;
924 /// *buf.push_back() = 3;
925 /// *buf.push_back() = 4;
926 /// for num in buf.iter_mut() {
927 /// *num = *num - 2;
928 /// }
929 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
930 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut u32>>()[..], b);
931 /// ```
932 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
933 IterMut {
934 data: self.data.ptr_mut(),
935 head: self.head,
936 len: self.len,
937 marker: marker::PhantomData,
938 }
939 }
940
941 /// Clears the `FixedVecDeque`.
942 ///
943 /// The stored values will _not_ be deleted.
944 ///
945 /// # Examples
946 ///
947 /// ```
948 /// use fixed_vec_deque::FixedVecDeque;
949 ///
950 /// let mut v = FixedVecDeque::<[u32; 1]>::new();
951 /// *v.push_back() = 1;
952 /// v.clear();
953 /// assert!(v.is_empty());
954 /// ```
955 #[inline]
956 pub fn clear(&mut self) {
957 self.head = 0;
958 self.len = 0;
959 }
960
961 /// Returns `true` if the `FixedVecDeque` contains an element equal to the
962 /// given value.
963 ///
964 /// # Examples
965 ///
966 /// ```
967 /// use fixed_vec_deque::FixedVecDeque;
968 ///
969 /// let mut vector = FixedVecDeque::<[u32; 4]>::new();
970 ///
971 /// *vector.push_back() = 0;
972 /// *vector.push_back() = 1;
973 ///
974 /// assert_eq!(vector.contains(&1), true);
975 /// assert_eq!(vector.contains(&10), false);
976 /// ```
977 pub fn contains(&self, x: &T::Item) -> bool
978 where
979 T::Item: PartialEq<T::Item>,
980 {
981 let (a, b) = self.as_slices();
982 a.contains(x) || b.contains(x)
983 }
984
985 /// Returns a pair of slices which contain, in order, the contents of the `FixedVecDeque`.
986 ///
987 /// # Examples
988 ///
989 /// ```
990 /// use fixed_vec_deque::FixedVecDeque;
991 ///
992 /// let mut vector = FixedVecDeque::<[u32; 6]>::new();
993 ///
994 /// *vector.push_back() = 0;
995 /// *vector.push_back() = 1;
996 ///
997 /// *vector.push_front() = 10;
998 /// *vector.push_front() = 9;
999 ///
1000 /// vector.as_mut_slices().0[0] = 42;
1001 /// vector.as_mut_slices().1[0] = 24;
1002 ///
1003 /// assert_eq!(vector.as_slices(), (&[42, 10][..], &[24, 1][..]));
1004 /// ```
1005 #[inline]
1006 pub fn as_mut_slices(&mut self) -> (&mut [T::Item], &mut [T::Item]) {
1007 if self.is_full() {
1008 let head = self.head;
1009 let buf = unsafe { self.buffer_as_mut_slice() };
1010 let (left, right) = buf.split_at(head);
1011 return (right, left);
1012 }
1013
1014 let head = self.head;
1015 let tail = self.tail();
1016 let buf = unsafe { self.buffer_as_mut_slice() };
1017 RingSlices::ring_slices(buf, head, tail)
1018 }
1019
1020 /// Returns a pair of slices which contain, in order, the contents of the `FixedVecDeque`.
1021 ///
1022 /// # Examples
1023 ///
1024 /// ```
1025 /// use fixed_vec_deque::FixedVecDeque;
1026 ///
1027 /// let mut vector = FixedVecDeque::<[u32; 5]>::new();
1028 ///
1029 /// *vector.push_back() = 1;
1030 /// *vector.push_back() = 2;
1031 /// *vector.push_back() = 3;
1032 ///
1033 /// assert_eq!(vector.as_slices(), (&[1, 2, 3][..], &[][..]));
1034 ///
1035 /// *vector.push_front() = 4;
1036 /// *vector.push_front() = 5;
1037 ///
1038 /// assert_eq!(vector.as_slices(), (&[5, 4][..], &[1, 2, 3][..]));
1039 /// ```
1040 #[inline]
1041 pub fn as_slices(&self) -> (&[T::Item], &[T::Item]) {
1042 let buf = unsafe { self.buffer_as_slice() };
1043
1044 if self.len == T::size() {
1045 let (left, right) = buf.split_at(self.head);
1046 return (right, left);
1047 }
1048
1049 let head = self.head;
1050 let tail = T::wrap_sub(head, self.len);
1051 RingSlices::ring_slices(buf, head, tail)
1052 }
1053
1054 /// Retrieves an element in the `FixedVecDeque` by index.
1055 ///
1056 /// Element at index 0 is the front of the queue.
1057 ///
1058 /// # Examples
1059 ///
1060 /// ```
1061 /// use fixed_vec_deque::FixedVecDeque;
1062 ///
1063 /// let mut buf = FixedVecDeque::<[u32; 5]>::new();
1064 /// *buf.push_back() = 3;
1065 /// *buf.push_back() = 4;
1066 /// *buf.push_back() = 5;
1067 /// assert_eq!(buf.get(1), Some(&4));
1068 /// ```
1069 pub fn get(&self, index: usize) -> Option<&T::Item> {
1070 if index < self.len {
1071 let off = self.ptr_index(index);
1072 Some(unsafe { self.buffer(off) })
1073 } else {
1074 None
1075 }
1076 }
1077
1078 /// Retrieves an element in the `FixedVecDeque` mutably by index.
1079 ///
1080 /// Element at index 0 is the front of the queue.
1081 ///
1082 /// # Examples
1083 ///
1084 /// ```
1085 /// use fixed_vec_deque::FixedVecDeque;
1086 ///
1087 /// let mut buf = FixedVecDeque::<[u32; 5]>::new();
1088 /// *buf.push_back() = 3;
1089 /// *buf.push_back() = 4;
1090 /// *buf.push_back() = 5;
1091 /// if let Some(elem) = buf.get_mut(1) {
1092 /// *elem = 7;
1093 /// }
1094 ///
1095 /// assert_eq!(buf[1], 7);
1096 /// ```
1097 pub fn get_mut(&mut self, index: usize) -> Option<&mut T::Item> {
1098 if index < self.len {
1099 let off = self.ptr_index(index);
1100 Some(unsafe { self.buffer_mut(off) })
1101 } else {
1102 None
1103 }
1104 }
1105
1106 /// Swaps elements at indices `i` and `j`.
1107 ///
1108 /// `i` and `j` may be equal.
1109 ///
1110 /// Element at index 0 is the front of the queue.
1111 ///
1112 /// # Panics
1113 ///
1114 /// Panics if either index is out of bounds.
1115 ///
1116 /// # Examples
1117 ///
1118 /// ```
1119 /// use fixed_vec_deque::FixedVecDeque;
1120 ///
1121 /// let mut buf = FixedVecDeque::<[u32; 4]>::new();
1122 /// *buf.push_back() = 3;
1123 /// *buf.push_back() = 4;
1124 /// *buf.push_back() = 5;
1125 /// assert_eq!(buf, [3, 4, 5]);
1126 /// buf.swap(0, 2);
1127 /// assert_eq!(buf, [5, 4, 3]);
1128 /// ```
1129 pub fn swap(&mut self, i: usize, j: usize) {
1130 assert!(i < T::size());
1131 assert!(j < T::size());
1132 let ri = self.ptr_index(i);
1133 let rj = self.ptr_index(j);
1134 let d = self.data.ptr_mut();
1135 unsafe { ptr::swap(d.add(ri), d.add(rj)) }
1136 }
1137
1138 /// Turn `i`, which is a zero-based offset into a ptr index that wraps around the size of this
1139 /// container.
1140 #[inline]
1141 fn ptr_index(&self, i: usize) -> usize {
1142 T::wrap_add(self.tail(), i)
1143 }
1144
1145 /// Get index of tail.
1146 #[inline]
1147 fn tail(&self) -> usize {
1148 T::wrap_sub(self.head, self.len)
1149 }
1150
1151 /// Turn ptr into a slice
1152 #[inline]
1153 unsafe fn buffer_as_slice(&self) -> &[T::Item] {
1154 slice::from_raw_parts(self.data.ptr(), T::size())
1155 }
1156
1157 /// Turn ptr into a mut slice
1158 #[inline]
1159 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T::Item] {
1160 slice::from_raw_parts_mut(self.data.ptr_mut(), T::size())
1161 }
1162
1163 /// Takes a reference of a value from the buffer.
1164 #[inline]
1165 unsafe fn buffer(&self, off: usize) -> &T::Item {
1166 &*self.data.ptr().add(off)
1167 }
1168
1169 /// Takes a mutable reference of a value from the buffer.
1170 #[inline]
1171 unsafe fn buffer_mut(&mut self, off: usize) -> &mut T::Item {
1172 &mut *self.data.ptr_mut().add(off)
1173 }
1174
1175 #[inline]
1176 unsafe fn buffer_read(&mut self, off: usize) -> T::Item {
1177 debug_assert!(off < T::size());
1178 ptr::read(self.data.ptr().add(off))
1179 }
1180
1181 #[inline]
1182 unsafe fn buffer_write(&mut self, off: usize, data: T::Item) {
1183 debug_assert!(off < T::size());
1184 ptr::write(self.data.ptr_mut().add(off), data);
1185 }
1186
1187 #[inline]
1188 fn is_contiguous(&self) -> bool {
1189 self.len != T::size() && self.tail() <= self.head
1190 }
1191
1192 /// Copies a contiguous block of memory len long from src to dst
1193 #[inline]
1194 unsafe fn copy(&mut self, dst: usize, src: usize, len: usize) {
1195 debug_assert!(
1196 dst + len <= T::size(),
1197 "cpy dst={} src={} len={} cap={}",
1198 dst,
1199 src,
1200 len,
1201 T::size()
1202 );
1203
1204 debug_assert!(
1205 src + len <= T::size(),
1206 "cpy dst={} src={} len={} cap={}",
1207 dst,
1208 src,
1209 len,
1210 T::size()
1211 );
1212
1213 let m = self.data.ptr_mut();
1214 ptr::copy(m.add(src), m.add(dst), len);
1215 }
1216}
1217
1218impl<T> FixedVecDeque<T>
1219where
1220 T: Array,
1221 T::Item: Clone,
1222{
1223 /// Modifies the `FixedVecDeque` in-place so that `len()` is equal to new_len,
1224 /// either by removing excess elements from the back or by appending clones of `value`
1225 /// to the back.
1226 ///
1227 /// # Panics
1228 ///
1229 /// Panics if `new_len` is longer than the [`capacity`] of this buffer.
1230 ///
1231 /// # Examples
1232 ///
1233 /// ```
1234 /// use fixed_vec_deque::FixedVecDeque;
1235 ///
1236 /// let mut buf = FixedVecDeque::<[u32; 8]>::new();
1237 /// *buf.push_back() = 5;
1238 /// *buf.push_back() = 10;
1239 /// *buf.push_back() = 15;
1240 /// assert_eq!(buf, [5, 10, 15]);
1241 ///
1242 /// buf.resize(2, 0);
1243 /// assert_eq!(buf, [5, 10]);
1244 ///
1245 /// buf.resize(5, 20);
1246 /// assert_eq!(buf, [5, 10, 20, 20, 20]);
1247 /// ```
1248 ///
1249 /// [`capacity`]: struct.FixedVecDeque.html#method.capacity
1250 pub fn resize(&mut self, new_len: usize, value: T::Item) {
1251 assert!(new_len < T::size(), "resize beyond capacity");
1252
1253 let len = self.len();
1254
1255 if new_len > len {
1256 self.extend(repeat(value).take(new_len - len))
1257 } else {
1258 self.truncate(new_len);
1259 }
1260 }
1261}
1262
1263impl<T> Default for FixedVecDeque<T>
1264where
1265 T: Array,
1266 T::Item: Default,
1267{
1268 #[inline]
1269 fn default() -> Self {
1270 Self::new()
1271 }
1272}
1273
1274impl<A> hash::Hash for FixedVecDeque<A>
1275where
1276 A: Array,
1277 A::Item: hash::Hash,
1278{
1279 fn hash<H: hash::Hasher>(&self, state: &mut H) {
1280 self.len().hash(state);
1281 let (a, b) = self.as_slices();
1282 hash::Hash::hash_slice(a, state);
1283 hash::Hash::hash_slice(b, state);
1284 }
1285}
1286
1287impl<T> Index<usize> for FixedVecDeque<T>
1288where
1289 T: Array,
1290{
1291 type Output = T::Item;
1292
1293 fn index(&self, index: usize) -> &T::Item {
1294 self.get(index).expect("Out of bounds access")
1295 }
1296}
1297
1298impl<T> IndexMut<usize> for FixedVecDeque<T>
1299where
1300 T: Array,
1301{
1302 fn index_mut(&mut self, index: usize) -> &mut T::Item {
1303 self.get_mut(index).expect("Out of bounds access")
1304 }
1305}
1306
1307/// An iterator over the elements of a `FixedVecDeque`.
1308///
1309/// This `struct` is created by the [`iter`] method on [`FixedVecDeque`]. See its
1310/// documentation for more.
1311///
1312/// [`iter`]: struct.FixedVecDeque.html#method.iter
1313/// [`FixedVecDeque`]: struct.FixedVecDeque.html
1314pub struct Iter<'a, T: 'a>
1315where
1316 T: Array,
1317{
1318 data: *const T::Item,
1319 head: usize,
1320 len: usize,
1321 marker: marker::PhantomData<&'a ()>,
1322}
1323
1324impl<'a, T: 'a> Iterator for Iter<'a, T>
1325where
1326 T: Array,
1327{
1328 type Item = &'a T::Item;
1329
1330 fn next(&mut self) -> Option<Self::Item> {
1331 if self.len == 0 {
1332 return None;
1333 }
1334
1335 let tail = T::wrap_sub(self.head, self.len);
1336 self.len -= 1;
1337 Some(unsafe { &*self.data.add(tail) })
1338 }
1339}
1340
1341/// An iterator over the elements of a `FixedVecDeque`.
1342///
1343/// This `struct` is created by the [`iter`] method on [`FixedVecDeque`]. See its
1344/// documentation for more.
1345///
1346/// [`iter`]: struct.FixedVecDeque.html#method.iter
1347/// [`FixedVecDeque`]: struct.FixedVecDeque.html
1348pub struct IterMut<'a, T: 'a>
1349where
1350 T: Array,
1351{
1352 data: *mut T::Item,
1353 head: usize,
1354 len: usize,
1355 marker: marker::PhantomData<&'a ()>,
1356}
1357
1358impl<'a, T: 'a> Iterator for IterMut<'a, T>
1359where
1360 T: Array,
1361{
1362 type Item = &'a mut T::Item;
1363
1364 fn next(&mut self) -> Option<Self::Item> {
1365 if self.len == 0 {
1366 return None;
1367 }
1368
1369 let tail = T::wrap_sub(self.head, self.len);
1370 self.len -= 1;
1371 Some(unsafe { &mut *self.data.add(tail) })
1372 }
1373}
1374
1375impl<'a, T: 'a> IntoIterator for &'a FixedVecDeque<T>
1376where
1377 T: Array,
1378{
1379 type Item = &'a T::Item;
1380 type IntoIter = Iter<'a, T>;
1381
1382 fn into_iter(self) -> Self::IntoIter {
1383 self.iter()
1384 }
1385}
1386
1387impl<A> Extend<A::Item> for FixedVecDeque<A>
1388where
1389 A: Array,
1390{
1391 fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1392 for elt in iter {
1393 *self.push_back() = elt;
1394 }
1395 }
1396}
1397
1398impl<T> fmt::Debug for FixedVecDeque<T>
1399where
1400 T: Array,
1401 T::Item: fmt::Debug,
1402{
1403 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1404 f.debug_list().entries(self).finish()
1405 }
1406}
1407
1408impl<A> FromIterator<A::Item> for FixedVecDeque<A>
1409where
1410 A: Array,
1411 A::Item: Default,
1412{
1413 fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> FixedVecDeque<A> {
1414 let mut deq = FixedVecDeque::new();
1415 deq.extend(iter.into_iter());
1416 deq
1417 }
1418}
1419
1420/// Types that can be used as the backing store for a FixedVecDeque.
1421///
1422/// # Safety
1423///
1424/// Implementor must ensure that the type is array appropriate.
1425pub unsafe trait Array {
1426 /// The type of the array's elements.
1427 type Item;
1428
1429 /// Returns the number of items the array can hold.
1430 fn size() -> usize;
1431
1432 /// Returns a pointer to the first element of the array.
1433 fn ptr(&self) -> *const Self::Item;
1434
1435 /// Returns a mutable pointer to the first element of the array.
1436 fn ptr_mut(&mut self) -> *mut Self::Item;
1437
1438 /// Returns the index in the underlying buffer for a given logical element
1439 /// index + addend.
1440 #[inline]
1441 fn wrap_add(idx: usize, addend: usize) -> usize {
1442 (idx + addend) % Self::size()
1443 }
1444
1445 /// Returns the index in the underlying buffer for a given logical element
1446 /// index - subtrahend.
1447 #[inline]
1448 fn wrap_sub(idx: usize, subtrahend: usize) -> usize {
1449 if subtrahend > idx {
1450 Self::size() - (subtrahend - idx)
1451 } else {
1452 idx - subtrahend
1453 }
1454 }
1455}
1456
1457macro_rules! impl_array(
1458 ($($size:expr),+) => {
1459 $(
1460 unsafe impl<T> Array for [T; $size] where T: Default {
1461 type Item = T;
1462 fn size() -> usize { $size }
1463 fn ptr(&self) -> *const T { self.as_ptr() }
1464 fn ptr_mut(&mut self) -> *mut T { self.as_mut_ptr() }
1465 }
1466 )+
1467 }
1468);
1469
1470impl<A> Eq for FixedVecDeque<A>
1471where
1472 A: Array,
1473 A::Item: Eq,
1474{
1475}
1476
1477impl<A, B> PartialEq<FixedVecDeque<B>> for FixedVecDeque<A>
1478where
1479 A: Array,
1480 B: Array,
1481 A::Item: PartialEq<B::Item>,
1482{
1483 fn eq(&self, other: &FixedVecDeque<B>) -> bool {
1484 if self.len() != other.len() {
1485 return false;
1486 }
1487
1488 let (sa, sb) = self.as_slices();
1489 let (oa, ob) = other.as_slices();
1490
1491 match sa.len().cmp(&oa.len()) {
1492 cmp::Ordering::Less => {
1493 // Always divisible in three sections, for example:
1494 // self: [a b c|d e f]
1495 // other: [0 1 2 3|4 5]
1496 // front = 3, mid = 1,
1497 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
1498 let front = sa.len();
1499 let mid = oa.len() - front;
1500
1501 let (oa_front, oa_mid) = oa.split_at(front);
1502 let (sb_mid, sb_back) = sb.split_at(mid);
1503 debug_assert_eq!(sa.len(), oa_front.len());
1504 debug_assert_eq!(sb_mid.len(), oa_mid.len());
1505 debug_assert_eq!(sb_back.len(), ob.len());
1506 sa == oa_front && sb_mid == oa_mid && sb_back == ob
1507 }
1508 cmp::Ordering::Equal => sa == oa && sb == ob,
1509 cmp::Ordering::Greater => {
1510 let front = oa.len();
1511 let mid = sa.len() - front;
1512
1513 let (sa_front, sa_mid) = sa.split_at(front);
1514 let (ob_mid, ob_back) = ob.split_at(mid);
1515 debug_assert_eq!(sa_front.len(), oa.len());
1516 debug_assert_eq!(sa_mid.len(), ob_mid.len());
1517 debug_assert_eq!(sb.len(), ob_back.len());
1518 sa_front == oa && sa_mid == ob_mid && sb == ob_back
1519 }
1520 }
1521 }
1522}
1523
1524macro_rules! impl_slice_eq {
1525 ($Lhs: ty, $Rhs: ty) => {
1526 impl_slice_eq! { $Lhs, $Rhs, Sized }
1527 };
1528 ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
1529 impl<'a, 'b, A, B> PartialEq<$Rhs> for $Lhs
1530 where
1531 A: Array,
1532 A::Item: $Bound + PartialEq<B>,
1533 {
1534 fn eq(&self, other: &$Rhs) -> bool {
1535 if self.len() != other.len() {
1536 return false;
1537 }
1538 let (sa, sb) = self.as_slices();
1539 let (oa, ob) = other[..].split_at(sa.len());
1540 sa == oa && sb == ob
1541 }
1542 }
1543 };
1544}
1545
1546impl_slice_eq! { FixedVecDeque<A>, Vec<B> }
1547impl_slice_eq! { FixedVecDeque<A>, &'b [B] }
1548impl_slice_eq! { FixedVecDeque<A>, &'b mut [B] }
1549
1550macro_rules! array_impls {
1551 ($($N: expr)+) => {
1552 $(
1553 impl_slice_eq! { FixedVecDeque<A>, [B; $N] }
1554 impl_slice_eq! { FixedVecDeque<A>, &'b [B; $N] }
1555 impl_slice_eq! { FixedVecDeque<A>, &'b mut [B; $N] }
1556 )+
1557 }
1558}
1559
1560array_impls! {
1561 0 1 2 3 4 5 6 7 8 9
1562 10 11 12 13 14 15 16 17 18 19
1563 20 21 22 23 24 25 26 27 28 29
1564 30 31 32
1565}
1566
1567impl<A> PartialOrd for FixedVecDeque<A>
1568where
1569 A: Array,
1570 A::Item: PartialOrd,
1571{
1572 fn partial_cmp(&self, other: &FixedVecDeque<A>) -> Option<cmp::Ordering> {
1573 self.iter().partial_cmp(other.iter())
1574 }
1575}
1576
1577impl<A> Ord for FixedVecDeque<A>
1578where
1579 A: Array,
1580 A::Item: Ord,
1581{
1582 #[inline]
1583 fn cmp(&self, other: &FixedVecDeque<A>) -> cmp::Ordering {
1584 self.iter().cmp(other.iter())
1585 }
1586}
1587
1588impl_array!(
1589 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 24, 32, 36, 0x40, 0x80, 0x100,
1590 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000, 0x20000, 0x40000, 0x80000,
1591 0x100000
1592);
1593
1594/// Returns the two slices that cover the `FixedVecDeque`'s valid range
1595trait RingSlices: Sized {
1596 fn slice(self, from: usize, to: usize) -> Self;
1597 fn split_at(self, i: usize) -> (Self, Self);
1598
1599 fn ring_slices(buf: Self, head: usize, tail: usize) -> (Self, Self) {
1600 let contiguous = tail <= head;
1601 if contiguous {
1602 let (empty, buf) = buf.split_at(0);
1603 (buf.slice(tail, head), empty)
1604 } else {
1605 let (mid, right) = buf.split_at(tail);
1606 let (left, _) = mid.split_at(head);
1607 (right, left)
1608 }
1609 }
1610}
1611
1612impl<'a, T> RingSlices for &'a [T] {
1613 fn slice(self, from: usize, to: usize) -> Self {
1614 &self[from..to]
1615 }
1616
1617 fn split_at(self, i: usize) -> (Self, Self) {
1618 (*self).split_at(i)
1619 }
1620}
1621
1622impl<'a, T> RingSlices for &'a mut [T] {
1623 fn slice(self, from: usize, to: usize) -> Self {
1624 &mut self[from..to]
1625 }
1626
1627 fn split_at(self, i: usize) -> (Self, Self) {
1628 (*self).split_at_mut(i)
1629 }
1630}
1631
1632#[cfg(test)]
1633mod tests {
1634 use super::{Array, FixedVecDeque};
1635 use std::mem;
1636
1637 /// Construct a new and verify that its size is the sum of all it's elements.
1638 fn test_new<T>() -> FixedVecDeque<T>
1639 where
1640 T: Array,
1641 T::Item: Default,
1642 {
1643 let fixed = FixedVecDeque::<T>::new();
1644
1645 assert_eq!(
1646 mem::size_of::<T::Item>() * 4 + mem::size_of::<FixedVecDeque<[Zero; 1]>>(),
1647 mem::size_of::<FixedVecDeque<[T::Item; 4]>>()
1648 );
1649
1650 #[derive(Debug, Default, PartialEq, Eq)]
1651 struct Zero {}
1652
1653 fixed
1654 }
1655
1656 #[test]
1657 fn test_push_back() {
1658 let mut fixed = test_new::<[Foo; 4]>();
1659
1660 #[derive(Debug, Default, PartialEq, Eq)]
1661 struct Foo {
1662 data: u64,
1663 }
1664
1665 fixed.push_back().data = 1;
1666 fixed.push_back().data = 2;
1667
1668 assert_eq!(Some(&mut Foo { data: 1 }), fixed.pop_front());
1669 assert_eq!(Some(&mut Foo { data: 2 }), fixed.pop_front());
1670 assert_eq!(None, fixed.pop_front());
1671 }
1672
1673 // make sure that we correctly ported the various functions, since they depended on sizes being
1674 // aligned to a power of two.
1675 #[test]
1676 #[allow(clippy::reversed_empty_ranges)]
1677 fn test_unaligned_sizes() {
1678 macro_rules! test_size {
1679 ($size:expr) => {
1680 let mut buf = FixedVecDeque::<[u32; $size]>::new();
1681
1682 assert_eq!(buf.back(), None);
1683 assert_eq!(buf.front(), None);
1684 assert_eq!(buf.get(0), None);
1685 assert_eq!(buf.get_mut(0), None);
1686
1687 for i in 1..($size + 1) {
1688 *buf.push_back() = i;
1689
1690 assert_eq!(buf.front(), Some(&1));
1691 assert_eq!(buf.back(), Some(&i));
1692 assert_eq!(buf.get(0), Some(&1));
1693 assert_eq!(buf.get(buf.len() - 1), Some(&i));
1694 assert_eq!(buf[0], 1);
1695 assert_eq!(buf[buf.len() - 1], i);
1696 }
1697
1698 let mut buf = FixedVecDeque::<[u32; $size]>::new();
1699
1700 assert_eq!(buf.back(), None);
1701 assert_eq!(buf.front(), None);
1702 assert_eq!(buf.get(0), None);
1703 assert_eq!(buf.get_mut(0), None);
1704
1705 for i in 1..($size + 1) {
1706 *buf.push_front() = i;
1707
1708 assert_eq!(buf.back(), Some(&1));
1709 assert_eq!(buf.front(), Some(&i));
1710 assert_eq!(buf.get(buf.len() - 1), Some(&1));
1711 assert_eq!(buf.get(0), Some(&i));
1712 assert_eq!(buf[buf.len() - 1], 1);
1713 assert_eq!(buf[0], i);
1714 }
1715 };
1716 }
1717
1718 test_size!(0);
1719 test_size!(1);
1720 test_size!(2);
1721 test_size!(3);
1722 test_size!(4);
1723 test_size!(5);
1724 test_size!(6);
1725 test_size!(7);
1726 test_size!(8);
1727 test_size!(9);
1728 test_size!(10);
1729 test_size!(11);
1730 test_size!(12);
1731 test_size!(13);
1732 test_size!(14);
1733 test_size!(15);
1734 test_size!(16);
1735 test_size!(20);
1736 test_size!(24);
1737 test_size!(32);
1738 test_size!(36);
1739 }
1740
1741 #[test]
1742 fn test_drop() {
1743 let mut a = 0;
1744 let mut b = 0;
1745 let mut c = 0;
1746
1747 {
1748 let mut fixed = FixedVecDeque::<[Foo; 2]>::new();
1749 fixed.push_back().value = Some(&mut a);
1750 fixed.push_back().value = Some(&mut b);
1751 fixed.push_back().value = Some(&mut c);
1752 }
1753
1754 // NB: zero because it will have been overwritten due to the circular nature of the buffer.
1755 assert_eq!(a, 0);
1756 assert_eq!(b, 1);
1757 assert_eq!(c, 1);
1758
1759 #[derive(Default)]
1760 struct Foo<'a> {
1761 value: Option<&'a mut u32>,
1762 }
1763
1764 impl<'a> Drop for Foo<'a> {
1765 fn drop(&mut self) {
1766 if let Some(v) = self.value.take() {
1767 *v += 1;
1768 }
1769 }
1770 }
1771 }
1772
1773 #[test]
1774 fn test_extend() {
1775 let mut deq = FixedVecDeque::<[u32; 4]>::new();
1776 deq.extend(vec![1, 2, 3, 4, 5, 6, 7, 8].into_iter());
1777
1778 assert!(!deq.is_empty());
1779 assert!(deq.is_full());
1780 assert_eq!(deq.iter().collect::<Vec<_>>(), vec![&5, &6, &7, &8]);
1781 }
1782
1783 #[test]
1784 fn test_collect() {
1785 let deq: FixedVecDeque<[u32; 4]> = vec![1, 2, 3, 4, 5, 6, 7, 8].into_iter().collect();
1786
1787 assert!(!deq.is_empty());
1788 assert!(deq.is_full());
1789 assert_eq!(deq.iter().collect::<Vec<_>>(), vec![&5, &6, &7, &8]);
1790 }
1791
1792 #[test]
1793 fn test_clone() {
1794 let a: FixedVecDeque<[u32; 4]> = vec![1, 2, 3, 4].into_iter().collect();
1795 let b = a.clone();
1796 assert_eq!(a, b);
1797 }
1798
1799 #[test]
1800 fn test_swap_front_back_remove() {
1801 fn test(back: bool) {
1802 let mut tester = FixedVecDeque::<[usize; 16]>::new();
1803 let usable_cap = tester.capacity();
1804 let final_len = usable_cap / 2;
1805
1806 for len in 0..final_len {
1807 let expected: FixedVecDeque<[usize; 16]> = if back {
1808 (0..len).collect()
1809 } else {
1810 (0..len).rev().collect()
1811 };
1812 for tail_pos in 0..usable_cap {
1813 tester.head = tail_pos;
1814 tester.len = 0;
1815
1816 if back {
1817 for i in 0..len * 2 {
1818 *tester.push_front() = i;
1819 }
1820 for i in 0..len {
1821 assert_eq!(tester.swap_remove_back(i), Some(&mut (len * 2 - 1 - i)));
1822 }
1823 } else {
1824 for i in 0..len * 2 {
1825 *tester.push_back() = i;
1826 }
1827 for i in 0..len {
1828 let idx = tester.len() - 1 - i;
1829 assert_eq!(tester.swap_remove_front(idx), Some(&mut (len * 2 - 1 - i)));
1830 }
1831 }
1832 assert_eq!(tester, expected);
1833 }
1834 }
1835 }
1836 test(true);
1837 test(false);
1838 }
1839
1840 #[test]
1841 fn test_basic_remove() {
1842 let mut a = FixedVecDeque::<[usize; 16]>::new();
1843 *a.push_front() = 2;
1844 *a.push_front() = 1;
1845 *a.push_back() = 3;
1846 *a.push_back() = 4;
1847
1848 assert_eq!(a, [1, 2, 3, 4]);
1849
1850 assert_eq!(a.remove(2), Some(&mut 3));
1851 assert_eq!(a, [1, 2, 4]);
1852 assert_eq!(a.remove(2), Some(&mut 4));
1853 assert_eq!(a, [1, 2]);
1854 assert_eq!(a.remove(0), Some(&mut 1));
1855 assert_eq!(a, [2]);
1856 assert_eq!(a.remove(0), Some(&mut 2));
1857 assert_eq!(a, []);
1858 }
1859
1860 #[test]
1861 fn test_remove() {
1862 // This test checks that every single combination of tail position, length, and
1863 // removal position is tested. Capacity 15 should be large enough to cover every case.
1864
1865 let mut tester = FixedVecDeque::<[usize; 16]>::new();
1866
1867 // can't guarantee we got 15, so have to get what we got.
1868 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
1869 // this test isn't covering what it wants to
1870 let cap = tester.capacity();
1871
1872 // len is the length *after* removal
1873 for len in 0..cap - 1 {
1874 // 0, 1, 2, .., len - 1
1875 let expected = (0..).take(len).collect::<FixedVecDeque<[usize; 16]>>();
1876 for tail_pos in 0..cap {
1877 for to_remove in 0..len + 1 {
1878 tester.head = tail_pos;
1879 tester.len = 0;
1880
1881 for i in 0..len {
1882 if i == to_remove {
1883 *tester.push_back() = 1234;
1884 }
1885 *tester.push_back() = i;
1886 }
1887 if to_remove == len {
1888 *tester.push_back() = 1234;
1889 }
1890 tester.remove(to_remove);
1891 assert!(tester.tail() < tester.capacity());
1892 assert!(tester.head < tester.capacity());
1893 assert_eq!(tester, expected);
1894 }
1895 }
1896 }
1897 }
1898}
1899
1900#[cfg(all(nightly, test))]
1901mod benches {
1902 extern crate test;
1903
1904 use super::FixedVecDeque;
1905
1906 #[bench]
1907 fn bench_push_back_100(b: &mut test::Bencher) {
1908 let mut deq = FixedVecDeque::<[BigStruct; 0x100]>::new();
1909
1910 b.iter(|| {
1911 for i in 0..100 {
1912 let big = deq.push_back();
1913 big.fields[0] = i;
1914 }
1915
1916 deq.clear();
1917 })
1918 }
1919
1920 #[bench]
1921 fn bench_push_back_100_vec_deque(b: &mut test::Bencher) {
1922 use std::collections::VecDeque;
1923
1924 let mut deq = VecDeque::new();
1925
1926 b.iter(|| {
1927 for i in 0..100 {
1928 let mut big = BigStruct::default();
1929 big.fields[0] = i;
1930 deq.push_back(big);
1931 }
1932
1933 deq.clear();
1934 })
1935 }
1936
1937 pub struct BigStruct {
1938 fields: [u64; 64],
1939 }
1940
1941 impl Default for BigStruct {
1942 fn default() -> Self {
1943 let fields = [0u64; 64];
1944
1945 BigStruct { fields }
1946 }
1947 }
1948}