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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
use core::fmt;
use std::{
marker::PhantomData,
ops::{Add, Deref, Sub},
ptr::NonNull,
};
use super::pq_rc_cell::PqRcCell;
/// Priority-Queue Reference Counted pointer type.
/// Allows mutable access to the owned value if `self` has the highest priority.
pub struct PqRc<T, Priority: Ord + Copy> {
prio: Priority,
ptr: NonNull<PqRcCell<T, Priority>>,
_t_marker: PhantomData<T>,
_p_marker: PhantomData<Priority>,
}
impl<T, Priority> PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
{
fn alloc_ptr() -> NonNull<PqRcCell<T, Priority>> {
// SAFETY:
// > This function is unsafe because undefined behavior can result if
// > the caller does not ensure that layout has non-zero size.
// The size of a `PqRcCell` is at least the size of a `BTreeMap`, which
// is non-zero.
let ptr = unsafe { std::alloc::alloc(PqRcCell::<T, Priority>::LAYOUT) };
let ptr = ptr as *mut PqRcCell<T, Priority>;
match NonNull::new(ptr) {
Some(ptr) => ptr,
None => std::alloc::handle_alloc_error(PqRcCell::<T, Priority>::LAYOUT),
}
}
pub fn new(value: T, priority: Priority) -> Self {
let cell = PqRcCell::new(value, priority);
// SAFETY: `cell` knows about the `PqRc` that we're about to create since
// the `new` function registers the priority.
unsafe { Self::from_cell_and_prio(cell, priority) }
}
/// # Safety
/// `cell` must register the priority of the `PqRc` that will be created
/// by this function.
unsafe fn from_cell_and_prio(cell: PqRcCell<T, Priority>, prio: Priority) -> Self {
let ptr = Self::alloc_ptr();
// SAFETY: TODO[safety argument omitted]
unsafe {
ptr.as_uninit_mut().write(cell);
}
Self {
prio,
ptr,
_t_marker: Default::default(),
_p_marker: Default::default(),
}
}
/// # Safety
/// * `ptr` must point to an existing `PqRcCell`.
unsafe fn from_prio_and_ptr(prio: Priority, ptr: NonNull<PqRcCell<T, Priority>>) -> Self {
unsafe {
// Because `ptr` refers to an existing `PqRcCell` and we're creating
// a new `PqRc`, we **gotta** increment the count!
ptr.as_ref().incr_count(prio);
}
Self {
prio,
ptr,
_t_marker: Default::default(),
_p_marker: Default::default(),
}
}
pub fn priority(this: &Self) -> Priority {
this.prio
}
#[allow(dead_code)]
pub fn ref_count(this: &Self) -> usize {
PqRcCell::ref_count(this.cell_ref())
}
fn cell_ref(&self) -> &PqRcCell<T, Priority> {
unsafe { self.ptr.as_ref() }
}
/// # Safety
/// TODO[document safety invariants]
pub unsafe fn with_inner_raising_prio<'a, F, O>(this: &'a Self, action: F) -> O
where
F: FnMut(Option<&'a mut T>) -> O,
{
// TODO[safety argument omitted]
let cell_ref_mut = unsafe { this.ptr.as_ptr().as_mut().unwrap_unchecked() };
PqRcCell::with_inner_raising_prio(cell_ref_mut, this.prio, action)
}
/// If `this` has the highest priority (and no one else does), then give `action` a mutable
/// reference to the inner `T` value. Otherwise, pass `None` to the action to let it do
/// something else.
///
/// # Safety
///
/// * `action` may not mutate `this.ptr.value` in any way that is visible to other `PqRc`s.
pub unsafe fn with_inner_lowering_prio<'a, F, O>(this: &'a Self, action: F) -> O
where
F: FnMut(Option<&'a mut T>) -> O,
{
// TODO[safety argument omitted]
let cell_ref_mut = unsafe { this.ptr.as_ptr().as_mut().unwrap_unchecked() };
PqRcCell::with_inner_lowering_prio(cell_ref_mut, this.prio, action)
}
/// A new `PqRc` `x` is returned from this function where `x`'s priority is
/// the priority of `self` **plus** the priority returned by the closure
/// that gets called.
///
/// # Arguments
/// * `new_prio_mut` accepts a **mutable** reference to the inner value, and
/// should return a priority difference (increase).
/// * `new_prio_ref` accepts an **immutable** reference to the inner value,
/// and should return a priority difference (increase) *AND* a new `T` value.
///
/// # Safety
/// With the provided `&mut`, you **must not** mutate the inner value in a
/// way that is visible to any other `PqRc` (except the new one just created).
pub unsafe fn mutate_or_clone_raising_prio<'a>(
this: &'a Self,
on_mut_action: impl Fn(&'a mut T) -> Priority,
on_ref_action: impl Fn(&'a T) -> (Priority, T),
) -> Self {
// SAFETY: TODO
// OLD ----v
// `inner_ref` will be mutated according to `new_prio_mut`, whose
// requirements are listed in this function's safety section, and are the
// same as those required by `try_as_mut`.
unsafe {
Self::with_inner_raising_prio(this, |inner| {
match inner {
Some(inner_ref) => {
let new_prio = on_mut_action(inner_ref);
// SAFETY: `this.ptr` points to a valid `PqRcCell` because `this`
// is assumed to be valid at start of this function.
Self::from_prio_and_ptr(this.prio + new_prio, this.ptr)
}
None => {
let (new_prio, new_value) = on_ref_action(this.deref());
Self::new(new_value, this.prio + new_prio)
}
}
})
}
}
/// Create a new pointer to the shared inner `T` but with a new priority.
pub fn clone_with_priority(this: &Self, new_prio: Priority) -> PqRc<T, Priority> {
let new = Self {
prio: new_prio,
ptr: this.ptr,
_t_marker: Default::default(),
_p_marker: Default::default(),
};
Self::cell_ref(&new).incr_count(new.prio);
new
}
pub fn next_highest_priority(this: &PqRc<T, Priority>) -> Option<Priority> {
PqRcCell::next_highest_priority(this.cell_ref())
}
pub fn inner(this: &Self) -> &T {
PqRcCell::inner(this.cell_ref())
}
}
impl<T, Priority> Clone for PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
{
fn clone(&self) -> Self {
Self::clone_with_priority(self, self.prio)
}
}
impl<T, Priority: Ord + Copy> Drop for PqRc<T, Priority> {
fn drop(&mut self) {
unsafe {
self.ptr.as_mut().decr_count(self.prio);
}
if PqRcCell::ref_count(unsafe { self.ptr.as_ref() }) == 0 {
#[cfg(test)]
{
use crate::pq_rc::pq_rc_cell;
pq_rc_cell::new_counts::incr_total_drop_count();
}
// TODO[safety argument omitted]
unsafe {
// Call the cell's destructor.
std::ptr::drop_in_place(self.ptr.as_mut() as *mut _);
}
// SAFETY:
// * ptr must denote a block of memory currently allocated via this
// allocator
// - Yes, a `PqRc` allocs `ptr` with the same allocator as this
// one.
// * layout must be the same layout that was used to allocate that
// block of memory.
// - Yep, its the same layout.
unsafe {
let ptr_bytes = self.ptr.as_ptr() as *mut u8;
std::alloc::dealloc(ptr_bytes, PqRcCell::<T, Priority>::LAYOUT);
}
}
}
}
impl<T, Priority> Deref for PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
{
type Target = T;
fn deref(&self) -> &Self::Target {
self.cell_ref().deref()
}
}
impl<U, T, Priority> PartialEq<U> for PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
T: PartialEq<U>,
{
fn eq(&self, other: &U) -> bool {
self.cell_ref().deref().eq(other)
}
}
impl<T, Priority> fmt::Debug for PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
PqRc::inner(self).fmt(f)
}
}
impl<T, Priority> fmt::Display for PqRc<T, Priority>
where
Priority: Ord + Copy + Add<Output = Priority> + Sub<Output = Priority>,
T: fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
PqRc::inner(self).fmt(f)
}
}