1 use slab::Slab;
2 
3 /// Buffers frames for multiple streams.
4 #[derive(Debug)]
5 pub struct Buffer<T> {
6     slab: Slab<Slot<T>>,
7 }
8 
9 /// A sequence of frames in a `Buffer`
10 #[derive(Debug)]
11 pub struct Deque {
12     indices: Option<Indices>,
13 }
14 
15 /// Tracks the head & tail for a sequence of frames in a `Buffer`.
16 #[derive(Debug, Default, Copy, Clone)]
17 struct Indices {
18     head: usize,
19     tail: usize,
20 }
21 
22 #[derive(Debug)]
23 struct Slot<T> {
24     value: T,
25     next: Option<usize>,
26 }
27 
28 impl<T> Buffer<T> {
new() -> Self29     pub fn new() -> Self {
30         Buffer { slab: Slab::new() }
31     }
32 
is_empty(&self) -> bool33     pub fn is_empty(&self) -> bool {
34         self.slab.is_empty()
35     }
36 }
37 
38 impl Deque {
new() -> Self39     pub fn new() -> Self {
40         Deque { indices: None }
41     }
42 
is_empty(&self) -> bool43     pub fn is_empty(&self) -> bool {
44         self.indices.is_none()
45     }
46 
push_back<T>(&mut self, buf: &mut Buffer<T>, value: T)47     pub fn push_back<T>(&mut self, buf: &mut Buffer<T>, value: T) {
48         let key = buf.slab.insert(Slot { value, next: None });
49 
50         match self.indices {
51             Some(ref mut idxs) => {
52                 buf.slab[idxs.tail].next = Some(key);
53                 idxs.tail = key;
54             }
55             None => {
56                 self.indices = Some(Indices {
57                     head: key,
58                     tail: key,
59                 });
60             }
61         }
62     }
63 
push_front<T>(&mut self, buf: &mut Buffer<T>, value: T)64     pub fn push_front<T>(&mut self, buf: &mut Buffer<T>, value: T) {
65         let key = buf.slab.insert(Slot { value, next: None });
66 
67         match self.indices {
68             Some(ref mut idxs) => {
69                 buf.slab[key].next = Some(idxs.head);
70                 idxs.head = key;
71             }
72             None => {
73                 self.indices = Some(Indices {
74                     head: key,
75                     tail: key,
76                 });
77             }
78         }
79     }
80 
pop_front<T>(&mut self, buf: &mut Buffer<T>) -> Option<T>81     pub fn pop_front<T>(&mut self, buf: &mut Buffer<T>) -> Option<T> {
82         match self.indices {
83             Some(mut idxs) => {
84                 let mut slot = buf.slab.remove(idxs.head);
85 
86                 if idxs.head == idxs.tail {
87                     assert!(slot.next.is_none());
88                     self.indices = None;
89                 } else {
90                     idxs.head = slot.next.take().unwrap();
91                     self.indices = Some(idxs);
92                 }
93 
94                 Some(slot.value)
95             }
96             None => None,
97         }
98     }
99 }
100