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> { |
29 | pub fn new() -> Self { |
30 | Buffer { slab: Slab::new() } |
31 | } |
32 | } |
33 | |
34 | impl Deque { |
35 | pub fn new() -> Self { |
36 | Deque { indices: None } |
37 | } |
38 | |
39 | pub fn is_empty(&self) -> bool { |
40 | self.indices.is_none() |
41 | } |
42 | |
43 | pub fn push_back<T>(&mut self, buf: &mut Buffer<T>, value: T) { |
44 | let key = buf.slab.insert(Slot { value, next: None }); |
45 | |
46 | match self.indices { |
47 | Some(ref mut idxs) => { |
48 | buf.slab[idxs.tail].next = Some(key); |
49 | idxs.tail = key; |
50 | } |
51 | None => { |
52 | self.indices = Some(Indices { |
53 | head: key, |
54 | tail: key, |
55 | }); |
56 | } |
57 | } |
58 | } |
59 | |
60 | pub fn push_front<T>(&mut self, buf: &mut Buffer<T>, value: T) { |
61 | let key = buf.slab.insert(Slot { value, next: None }); |
62 | |
63 | match self.indices { |
64 | Some(ref mut idxs) => { |
65 | buf.slab[key].next = Some(idxs.head); |
66 | idxs.head = key; |
67 | } |
68 | None => { |
69 | self.indices = Some(Indices { |
70 | head: key, |
71 | tail: key, |
72 | }); |
73 | } |
74 | } |
75 | } |
76 | |
77 | pub fn pop_front<T>(&mut self, buf: &mut Buffer<T>) -> Option<T> { |
78 | match self.indices { |
79 | Some(mut idxs) => { |
80 | let mut slot = buf.slab.remove(idxs.head); |
81 | |
82 | if idxs.head == idxs.tail { |
83 | assert!(slot.next.is_none()); |
84 | self.indices = None; |
85 | } else { |
86 | idxs.head = slot.next.take().unwrap(); |
87 | self.indices = Some(idxs); |
88 | } |
89 | |
90 | Some(slot.value) |
91 | } |
92 | None => None, |
93 | } |
94 | } |
95 | } |
96 | |