pinned_queue/
lib.rs

1use std::collections::VecDeque;
2use std::pin::Pin;
3
4pub struct Block<T>(VecDeque<T>);
5
6impl<T> Block<T> {
7	fn new(capacity: usize) -> Block<T> {
8		Block(VecDeque::with_capacity(capacity))
9	}
10
11	fn is_empty(&self) -> bool {
12		self.0.len() == 0
13	}
14
15	fn get(&self, index: usize) -> Option<Pin<&T>> {
16		self.0.get(index).map(|p| unsafe { Pin::new_unchecked(p) })
17	}
18
19	fn get_mut(&mut self, index: usize) -> Option<Pin<&mut T>> {
20		self.0.get_mut(index).map(|p| unsafe { Pin::new_unchecked(p) })
21	}
22
23	fn push_back(&mut self, item: T) {
24		assert!(self.0.len() < self.0.capacity());
25		self.0.push_back(item);
26	}
27
28	fn pop_front(&mut self) {
29		self.0.drain(0..1);
30	}
31
32	fn replace(&mut self, index: usize, item: T) {
33		*self.0.get_mut(index).unwrap() = item;
34	}
35}
36
37#[derive(Default)]
38pub struct PinnedQueue<T> {
39	blocks: VecDeque<Block<T>>,
40	head: usize,
41	len: usize,
42}
43
44impl<T> PinnedQueue<T> {
45	pub const fn new() -> PinnedQueue<T> {
46		PinnedQueue { blocks: VecDeque::new(), head: 0, len: 0 }
47	}
48
49	/// Returns the number of elements in the queue.
50	pub fn len(&self) -> usize {
51		self.len
52	}
53
54	pub fn is_empty(&self) -> bool {
55		self.len == 0
56	}
57
58	/// Provides a pinned reference to the element at the given index.
59	pub fn get(&self, index: usize) -> Option<Pin<&T>> {
60		if index > self.len {
61			None
62		} else {
63			let (outer, inner) = split_index(self.head, index);
64			self.blocks[outer].get(inner)
65		}
66	}
67
68	/// Provides a pinned mutable reference to the element at the given index.
69	pub fn get_mut(&mut self, index: usize) -> Option<Pin<&mut T>> {
70		if index > self.len {
71			None
72		} else {
73			let (outer, inner) = split_index(self.head, index);
74			self.blocks[outer].get_mut(inner)
75		}
76	}
77
78	/// Provides a pinned mutable reference to the last element.
79	pub fn last_mut(&mut self) -> Option<Pin<&mut T>> {
80		self.get_mut(self.len)
81	}
82
83	/// Appends an element to the end of the queue.
84	pub fn push_back(&mut self, item: T) {
85		let head_outer = outer_index(self.head);
86		let outer = outer_index(self.head + self.len);
87
88		if outer - head_outer >= self.blocks.len() {
89			self.blocks.push_back(Block::new(1 << outer));
90		}
91
92		self.blocks[outer - head_outer].push_back(item);
93		self.len += 1;
94	}
95
96	/// Removes the first element and returns `true`, or `false` if the queue is empty.
97	pub fn pop_front(&mut self) -> bool {
98		if self.is_empty() {
99			return false;
100		}
101
102		self.len -= 1;
103		self.head += 1;
104		self.blocks[0].pop_front();
105
106		if self.blocks[0].is_empty() {
107			self.blocks.pop_front();
108		}
109		true
110	}
111
112	/// Replaces the element at the given index with another one.
113	pub fn replace(&mut self, index: usize, item: T) {
114		let (outer, inner) = split_index(self.head, index);
115		self.blocks[outer].replace(inner, item);
116	}
117}
118
119fn outer_index(index: usize) -> usize {
120	(usize::BITS - (index + 1).leading_zeros() - 1) as usize
121}
122
123fn split_index(head: usize, index: usize) -> (usize, usize) {
124	let outer = outer_index(index + head);
125	let inner = (head + index + 1) & (!(1 << outer));
126	let head_outer = outer_index(head);
127	let head_inner = (head + 1) & (!(1 << head_outer));
128	if head_inner > inner {
129		(outer - head_outer - 1, head_inner - inner)
130	} else {
131		(outer - head_outer, inner - head_inner)
132	}
133}
134
135#[cfg(test)]
136mod tests {
137	use crate::{outer_index, split_index};
138
139	#[test]
140	fn outer() {
141		assert_eq!(0, outer_index(0));
142		assert_eq!(1, outer_index(1));
143		assert_eq!(1, outer_index(2));
144		assert_eq!(2, outer_index(3));
145		assert_eq!(16, outer_index(65535));
146	}
147
148	#[test]
149	fn split() {
150		assert_eq!((0, 0), split_index(0, 0));
151		assert_eq!((1, 0), split_index(0, 1));
152		assert_eq!((1, 1), split_index(0, 2));
153
154		assert_eq!((0, 0), split_index(1, 0));
155		assert_eq!((0, 1), split_index(1, 1));
156		assert_eq!((1, 0), split_index(1, 2));
157
158		assert_eq!((3, 1), split_index(2, 15));
159	}
160}
pinned_queue/lib.rs

pinned_queue/
lib.rs
