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

grammers_crypto/
deque_buffer.rs
