grammers_crypto/
deque_buffer.rs

1// Copyright 2020 - developers of the `grammers` project.
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9use std::{
10    ops::{Index, IndexMut},
11    slice::SliceIndex,
12};
13
14/// A growable buffer with the properties of a deque.
15///
16/// Unlike the standard [`VecDeque`](std::collections::VecDeque),
17/// this buffer is designed to not need explicit calls to `make_contiguous`
18/// and minimize the amount of memory moves.
19#[derive(Clone, Debug)]
20pub struct DequeBuffer<T: Copy + Default> {
21    buffer: Vec<T>,
22    head: usize,
23    default_head: usize,
24}
25
26impl<T: Copy + Default> DequeBuffer<T> {
27    /// Creates an empty deque buffer with space for at least `back_capacity` elements in the back,
28    /// and exactly `front_capacity` elements in the front.
29    pub fn with_capacity(back_capacity: usize, front_capacity: usize) -> Self {
30        let mut buffer = Vec::with_capacity(front_capacity + back_capacity);
31        buffer.extend((0..front_capacity).map(|_| T::default()));
32        Self {
33            buffer,
34            head: front_capacity,
35            default_head: front_capacity,
36        }
37    }
38
39    /// Clears the buffer, removing all values.
40    pub fn clear(&mut self) {
41        self.buffer.truncate(self.default_head);
42        self.buffer.fill(T::default());
43        self.head = self.default_head;
44    }
45
46    /// Extend the front by copying the elements from `slice`.
47    pub fn extend_front(&mut self, slice: &[T]) {
48        if self.head >= slice.len() {
49            self.head -= slice.len()
50        } else {
51            let shift = slice.len() - self.head;
52            self.buffer.extend((0..shift).map(|_| T::default()));
53            self.buffer.rotate_right(shift);
54            self.head = 0;
55        }
56        self.buffer[self.head..self.head + slice.len()].copy_from_slice(slice);
57    }
58
59    /// Appends an element to the back of the buffer.
60    pub fn push(&mut self, value: T) {
61        self.buffer.push(value)
62    }
63
64    /// Returns `true` if the buffer is empty.
65    pub fn is_empty(&self) -> bool {
66        self.head == self.buffer.len()
67    }
68
69    /// Returns the number of elements in the buffer.
70    pub fn len(&self) -> usize {
71        self.buffer.len() - self.head
72    }
73}
74
75impl<T: Copy + Default> AsRef<[T]> for DequeBuffer<T> {
76    fn as_ref(&self) -> &[T] {
77        &self.buffer[self.head..]
78    }
79}
80
81impl<T: Copy + Default> AsMut<[T]> for DequeBuffer<T> {
82    fn as_mut(&mut self) -> &mut [T] {
83        &mut self.buffer[self.head..]
84    }
85}
86
87impl<T: Copy + Default, I: SliceIndex<[T]>> Index<I> for DequeBuffer<T> {
88    type Output = I::Output;
89
90    fn index(&self, index: I) -> &Self::Output {
91        self.as_ref().index(index)
92    }
93}
94
95impl<T: Copy + Default, I: SliceIndex<[T]>> IndexMut<I> for DequeBuffer<T> {
96    fn index_mut(&mut self, index: I) -> &mut Self::Output {
97        self.as_mut().index_mut(index)
98    }
99}
100
101impl<T: Copy + Default> Extend<T> for DequeBuffer<T> {
102    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
103        self.buffer.extend(iter)
104    }
105}
106
107impl<'a, T: Copy + Default + 'a> Extend<&'a T> for DequeBuffer<T> {
108    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
109        self.buffer.extend(iter)
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    /// Pretty-print a ring buffer, including values, capacity, and head position.
118    fn repr(ring: &DequeBuffer<u8>) -> String {
119        use std::fmt::Write as _;
120
121        let mut repr = String::new();
122        repr.push('[');
123        ring.buffer.iter().enumerate().for_each(|(i, c)| {
124            repr.push(if ring.head == i { '|' } else { ' ' });
125            write!(repr, "{c}").unwrap();
126        });
127        repr.push(if ring.head == ring.buffer.len() {
128            '|'
129        } else {
130            ' '
131        });
132        (ring.buffer.len()..ring.buffer.capacity()).for_each(|_| {
133            repr.push('?');
134            repr.push(' ');
135        });
136        repr.push(']');
137        repr
138    }
139
140    #[allow(clippy::len_zero)]
141    fn sanity_checks(ring: &DequeBuffer<u8>) {
142        assert_eq!(ring.as_ref().len(), ring.len());
143        assert_eq!(ring.is_empty(), ring.len() == 0);
144    }
145
146    #[test]
147    fn initialization() {
148        let buffer = DequeBuffer::<u8>::with_capacity(0, 0);
149        sanity_checks(&buffer);
150        assert!(buffer.is_empty());
151        assert_eq!(repr(&buffer), "[|]");
152
153        let buffer = DequeBuffer::<u8>::with_capacity(0, 4);
154        sanity_checks(&buffer);
155        assert!(buffer.is_empty());
156        assert_eq!(repr(&buffer), "[ 0 0 0 0|]");
157
158        let buffer = DequeBuffer::<u8>::with_capacity(4, 0);
159        sanity_checks(&buffer);
160        assert!(buffer.is_empty());
161        assert_eq!(repr(&buffer), "[|? ? ? ? ]");
162
163        let buffer = DequeBuffer::<u8>::with_capacity(2, 4);
164        sanity_checks(&buffer);
165        assert!(buffer.is_empty());
166        assert_eq!(repr(&buffer), "[ 0 0 0 0|? ? ]");
167    }
168
169    #[test]
170    fn shift_extends_if_needed() {
171        let mut buffer = DequeBuffer::<u8>::with_capacity(2, 4);
172
173        buffer.extend_front(&[3, 3, 3]);
174        sanity_checks(&buffer);
175        assert_eq!(repr(&buffer), "[ 0|3 3 3 ? ? ]");
176
177        buffer.extend_front(&[1]);
178        sanity_checks(&buffer);
179        assert_eq!(repr(&buffer), "[|1 3 3 3 ? ? ]");
180
181        buffer.extend_front(&[2, 2]);
182        sanity_checks(&buffer);
183        assert_eq!(repr(&buffer), "[|2 2 1 3 3 3 ]");
184
185        let mut buffer = DequeBuffer::<u8>::with_capacity(2, 4);
186
187        buffer.extend_front(&[5, 5, 5, 5, 5]);
188        sanity_checks(&buffer);
189        assert_eq!(repr(&buffer), "[|5 5 5 5 5 ? ]");
190
191        buffer.extend_front(&[2, 2]);
192        sanity_checks(&buffer);
193        assert!(repr(&buffer).starts_with("[|2 2 5 5 5 5 5 ?")); // don't assume Vec's growth
194    }
195
196    #[test]
197    fn mutates_as_expected() {
198        let mut buffer = DequeBuffer::<u8>::with_capacity(6, 4);
199
200        buffer.extend(1..=2);
201        sanity_checks(&buffer);
202        assert_eq!(repr(&buffer), "[ 0 0 0 0|1 2 ? ? ? ? ]");
203
204        buffer.push(3);
205        sanity_checks(&buffer);
206        assert_eq!(repr(&buffer), "[ 0 0 0 0|1 2 3 ? ? ? ]");
207
208        buffer.extend_front(&[4, 5, 6]);
209        sanity_checks(&buffer);
210        assert_eq!(repr(&buffer), "[ 0|4 5 6 1 2 3 ? ? ? ]");
211
212        buffer.clear();
213        assert_eq!(repr(&buffer), "[ 0 0 0 0|? ? ? ? ? ? ]");
214    }
215}
grammers_crypto/deque_buffer.rs

grammers_crypto/
deque_buffer.rs
