fixed_queue/
vec_deque.rs

1use core::fmt;
2use core::mem::MaybeUninit;
3use core::ops::{Index, IndexMut};
4use core::{ptr, slice};
5
6pub struct VecDeque<T, const N: usize> {
7    buf: MaybeUninit<[T; N]>,
8    end: usize,
9    //Tail always points to the first element
10    start: usize,
11    is_full: bool,
12}
13impl<T, const N: usize> VecDeque<T, N> {
14    const CAPACITY: usize = N;
15    pub const fn new() -> Self {
16        VecDeque {
17            buf: MaybeUninit::uninit(),
18            end: 0,
19            start: 0,
20            is_full: false,
21        }
22    }
23    fn ptr(&self) -> *mut T {
24        self.buf.as_ptr() as *mut T
25    }
26    pub fn capacity(&self) -> usize {
27        Self::CAPACITY
28    }
29    pub fn len(&self) -> usize {
30        let start = self.start;
31        let end = self.end;
32        if self.is_full() {
33            self.capacity()
34        } else if end >= start {
35            end - start
36        } else {
37            self.capacity() - start + end
38        }
39    }
40    pub fn is_empty(&self) -> bool {
41        self.start == self.end && !self.is_full
42    }
43    pub fn is_full(&self) -> bool {
44        self.is_full
45    }
46    #[inline]
47    unsafe fn buffer_read(&mut self, off: usize) -> T {
48        ptr::read(self.ptr().add(off))
49    }
50    #[inline]
51    unsafe fn buffer_write(&mut self, off: usize, value: T) {
52        ptr::write(self.ptr().add(off), value);
53    }
54    #[inline]
55    fn wrap_add(&self, idx: usize, addend: usize) -> usize {
56        let (index, overflow) = idx.overflowing_add(addend);
57        if index >= self.capacity() || overflow {
58            index.wrapping_sub(self.capacity())
59        } else {
60            index
61        }
62    }
63    #[inline]
64    fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
65        let (index, overflow) = idx.overflowing_sub(subtrahend);
66        if overflow {
67            index.wrapping_add(self.capacity())
68        } else {
69            index
70        }
71    }
72    pub fn get(&self, index: usize) -> Option<&T> {
73        if index < self.len() {
74            let idx = self.wrap_add(self.start, index);
75            unsafe { Some(&*self.ptr().add(idx)) }
76        } else {
77            None
78        }
79    }
80    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
81        if index < self.len() {
82            let idx = self.wrap_add(self.start, index);
83            unsafe { Some(&mut *self.ptr().add(idx)) }
84        } else {
85            None
86        }
87    }
88    pub fn as_slices(&self) -> (&[T], &[T]) {
89        let ptr = self.ptr() as *const T;
90        if self.end >= self.start && !self.is_full {
91            (
92                unsafe { slice::from_raw_parts(ptr.add(self.start), self.end - self.start) },
93                &mut [],
94            )
95        } else {
96            (
97                unsafe { slice::from_raw_parts(ptr.add(self.start), N - self.start) },
98                unsafe { slice::from_raw_parts(ptr, self.end) },
99            )
100        }
101    }
102    pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
103        let ptr = self.ptr();
104        if self.end >= self.start && !self.is_full {
105            (
106                unsafe { slice::from_raw_parts_mut(ptr.add(self.start), self.end - self.start) },
107                &mut [],
108            )
109        } else {
110            (
111                unsafe { slice::from_raw_parts_mut(ptr.add(self.start), N - self.start) },
112                unsafe { slice::from_raw_parts_mut(ptr, self.end) },
113            )
114        }
115    }
116    pub fn clear(&mut self) {
117        let (a, b) = self.as_mut_slices();
118        unsafe { ptr::drop_in_place(a) };
119        unsafe { ptr::drop_in_place(b) };
120        self.end = 0;
121        self.start = 0;
122        self.is_full = false;
123    }
124    pub fn pop_front(&mut self) -> Option<T> {
125        if self.is_empty() {
126            None
127        } else {
128            let start = self.start;
129            self.start = self.wrap_add(self.start, 1);
130            if self.is_full {
131                self.is_full = false;
132            }
133            unsafe { Some(self.buffer_read(start)) }
134        }
135    }
136    pub fn pop_back(&mut self) -> Option<T> {
137        if self.is_empty() {
138            None
139        } else {
140            self.end = self.wrap_sub(self.end, 1);
141            let end = self.end;
142            if self.is_full {
143                self.is_full = false;
144            }
145            unsafe { Some(self.buffer_read(end)) }
146        }
147    }
148    pub fn push_front(&mut self, value: T) -> Result<(), T> {
149        if self.is_full() {
150            return Err(value);
151        }
152
153        if self.len() == self.capacity() - 1 {
154            self.is_full = true;
155        }
156        self.start = self.wrap_sub(self.start, 1);
157        unsafe { self.buffer_write(self.start, value) };
158        Ok(())
159    }
160    pub fn push_back(&mut self, value: T) -> Result<(), T> {
161        if self.is_full() {
162            return Err(value);
163        }
164
165        if self.len() == self.capacity() - 1 {
166            self.is_full = true;
167        }
168        unsafe { self.buffer_write(self.end, value) };
169        self.end = self.wrap_add(self.end, 1);
170        Ok(())
171    }
172}
173impl<T, const N: usize> Index<usize> for VecDeque<T, N> {
174    type Output = T;
175
176    #[inline]
177    fn index(&self, index: usize) -> &T {
178        self.get(index).expect("Out of bounds access")
179    }
180}
181
182impl<T, const N: usize> IndexMut<usize> for VecDeque<T, N> {
183    #[inline]
184    fn index_mut(&mut self, index: usize) -> &mut T {
185        self.get_mut(index).expect("Out of bounds access")
186    }
187}
188impl<T: fmt::Debug, const N: usize> fmt::Debug for VecDeque<T, N> {
189    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
190        fmt::Debug::fmt(&self.as_slices(), f)
191    }
192}
193impl<T, const N: usize> Drop for VecDeque<T, N> {
194    fn drop(&mut self) {
195        self.clear()
196    }
197}
fixed_queue/vec_deque.rs

fixed_queue/
vec_deque.rs
