1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
use std::{
marker::{PhantomData, PhantomPinned},
pin::Pin,
sync::Arc,
};
/**
* A queue based on an intrusive list.
*/
pub(crate) struct Queue<T: Queueable> {
head: QueueEntry,
_phantom: PhantomData<T>,
}
impl<T: Queueable> Queue<T> {
/* safety: caller must init() queue after it is pinned */
pub(crate) const unsafe fn new() -> Self {
Self {
head: QueueEntry::new(),
_phantom: PhantomData,
}
}
/* safety: init must be called once after the queue is pinned */
pub(crate) const unsafe fn init(self: Pin<&mut Self>) {
let s = unsafe { &mut self.get_unchecked_mut().head };
s.prev = std::ptr::from_mut(s);
s.next = std::ptr::from_mut(s);
}
/**
* Push an entry onto the queue.
*
* If the entry is already queued it will be unqueued and added to this
* queue.
* - If the entry is not queued: Add to this queue and hold reference.
* - If the entry is queued on another queue: Remove from other queue
* and add to this queue, without changing reference count.
* - If the entry is queued on this queue: remove from queue and add to
* end of queue, without changing reference count.
*/
pub(crate) fn push(mut self: Pin<&mut Self>, entry: Pin<Arc<T>>) {
let was_queued = entry.with_entry(|mut e| {
let was_queued = e.is_queued();
e.as_mut().unqueue();
unsafe {
let s = self.as_mut().get_unchecked_mut();
let e = e.get_unchecked_mut();
e.next = s.head.next;
e.prev = &raw mut s.head;
(*s.head.next).prev = e;
s.head.next = e;
}
was_queued
});
if !was_queued {
/* reference now belongs to the list */
let _ = Arc::into_raw(unsafe { Pin::into_inner_unchecked(entry) });
}
}
/**
* Pop an entry from the queue.
*
* Returns None if the queue is empty.
*
* Returns ownership of the entry to the caller.
*/
pub(crate) fn pop(self: Pin<&mut Self>) -> Option<Pin<Arc<T>>> {
(!self.is_empty()).then(|| {
/* get last entry */
let mut entry = unsafe { Pin::new_unchecked(&mut *self.head.prev) };
/* remove it from the list */
entry.as_mut().unqueue();
/* reconstruct reference */
T::from_entry(entry.as_ref())
})
}
/**
* Release a queued entry.
*
* If the entry was queued on any queue, unqueue and release ownership
* from the queue.
*/
pub(crate) fn release(self: Pin<&mut Self>, entry: Pin<Arc<T>>) {
entry.with_entry(|mut e| {
if e.is_queued() {
/* reconstruct then drop reference */
let _ = T::from_entry(e.as_ref());
}
e.as_mut().unqueue();
});
}
/**
* Test if queue is empty.
*/
pub(crate) fn is_empty(&self) -> bool {
std::ptr::eq(self.head.prev, &raw const self.head)
}
}
impl<T: Queueable> Drop for Queue<T> {
fn drop(&mut self) {
let mut this = unsafe { Pin::new_unchecked(self) };
while this.as_mut().pop().is_some() {}
}
}
#[derive(Debug)]
pub(crate) struct QueueEntry {
prev: *mut Self,
next: *mut Self,
_pinned: PhantomPinned,
}
impl QueueEntry {
pub(crate) const fn new() -> Self {
Self {
prev: std::ptr::null_mut(),
next: std::ptr::null_mut(),
_pinned: PhantomPinned,
}
}
fn unqueue(self: Pin<&mut Self>) {
if !self.is_queued() {
return;
}
unsafe {
let s = self.get_unchecked_mut();
(*s.prev).next = s.next;
(*s.next).prev = s.prev;
s.prev = std::ptr::null_mut();
}
}
/**
* Test if entry is queued.
*/
pub(crate) const fn is_queued(&self) -> bool {
!self.prev.is_null()
}
}
pub(crate) trait Queueable {
fn with_entry<R, F: FnMut(Pin<&mut QueueEntry>) -> R>(self: &Pin<Arc<Self>>, f: F) -> R;
fn from_entry(entry: Pin<&QueueEntry>) -> Pin<Arc<Self>>;
}