Source code

Revision control

Other Tools

1
/* This Source Code Form is subject to the terms of the Mozilla Public
2
* License, v. 2.0. If a copy of the MPL was not distributed with this
3
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5
//! A generic backing store for caches.
6
//!
7
//! `FreeList` is a simple vector-backed data structure where each entry in the
8
//! vector contains an Option<T>. It maintains an index-based (rather than
9
//! pointer-based) free list to efficiently locate the next unused entry. If all
10
//! entries are occupied, insertion appends a new element to the vector.
11
//!
12
//! It also supports both strong and weak handle semantics. There is exactly one
13
//! (non-Clonable) strong handle per occupied entry, which must be passed by
14
//! value into `free()` to release an entry. Strong handles can produce an
15
//! unlimited number of (Clonable) weak handles, which are used to perform
16
//! lookups which may fail of the entry has been freed. A per-entry epoch ensures
17
//! that weak handle lookups properly fail even if the entry has been freed and
18
//! reused.
19
//!
20
//! TODO(gw): Add an occupied list head, for fast iteration of the occupied list
21
//! to implement retain() style functionality.
22
23
use std::{fmt, u32};
24
use std::marker::PhantomData;
25
26
#[derive(Debug, Copy, Clone, MallocSizeOf, PartialEq)]
27
#[cfg_attr(feature = "capture", derive(Serialize))]
28
#[cfg_attr(feature = "replay", derive(Deserialize))]
29
struct Epoch(u32);
30
31
impl Epoch {
32
/// Mints a new epoch.
33
///
34
/// We start at 1 so that 0 is always an invalid epoch.
35
fn new() -> Self {
36
Epoch(1)
37
}
38
39
/// Returns an always-invalid epoch.
40
fn invalid() -> Self {
41
Epoch(0)
42
}
43
}
44
45
#[cfg_attr(feature = "capture", derive(Serialize))]
46
#[cfg_attr(feature = "replay", derive(Deserialize))]
47
pub struct FreeListHandle<M> {
48
index: u32,
49
epoch: Epoch,
50
_marker: PhantomData<M>,
51
}
52
53
/// More-compact textual representation for debug logging.
54
impl<M> fmt::Debug for FreeListHandle<M> {
55
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
56
f.debug_struct("StrongHandle")
57
.field("index", &self.index)
58
.field("epoch", &self.epoch.0)
59
.finish()
60
}
61
}
62
63
impl<M> FreeListHandle<M> {
64
pub fn weak(&self) -> WeakFreeListHandle<M> {
65
WeakFreeListHandle {
66
index: self.index,
67
epoch: self.epoch,
68
_marker: PhantomData,
69
}
70
}
71
72
pub fn invalid() -> Self {
73
Self {
74
index: 0,
75
epoch: Epoch::invalid(),
76
_marker: PhantomData,
77
}
78
}
79
}
80
81
impl<M> Clone for WeakFreeListHandle<M> {
82
fn clone(&self) -> Self {
83
WeakFreeListHandle {
84
index: self.index,
85
epoch: self.epoch,
86
_marker: PhantomData,
87
}
88
}
89
}
90
91
impl<M> PartialEq for WeakFreeListHandle<M> {
92
fn eq(&self, other: &Self) -> bool {
93
self.index == other.index && self.epoch == other.epoch
94
}
95
}
96
97
#[cfg_attr(feature = "capture", derive(Serialize))]
98
#[cfg_attr(feature = "replay", derive(Deserialize))]
99
#[derive(MallocSizeOf)]
100
pub struct WeakFreeListHandle<M> {
101
index: u32,
102
epoch: Epoch,
103
_marker: PhantomData<M>,
104
}
105
106
/// More-compact textual representation for debug logging.
107
impl<M> fmt::Debug for WeakFreeListHandle<M> {
108
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
109
f.debug_struct("WeakHandle")
110
.field("index", &self.index)
111
.field("epoch", &self.epoch.0)
112
.finish()
113
}
114
}
115
116
impl<M> WeakFreeListHandle<M> {
117
/// Returns an always-invalid handle.
118
pub fn invalid() -> Self {
119
Self {
120
index: 0,
121
epoch: Epoch::invalid(),
122
_marker: PhantomData,
123
}
124
}
125
}
126
127
#[derive(Debug)]
128
#[cfg_attr(feature = "capture", derive(Serialize))]
129
#[cfg_attr(feature = "replay", derive(Deserialize))]
130
struct Slot<T> {
131
next: Option<u32>,
132
epoch: Epoch,
133
value: Option<T>,
134
}
135
136
#[derive(Debug)]
137
#[cfg_attr(feature = "capture", derive(Serialize))]
138
#[cfg_attr(feature = "replay", derive(Deserialize))]
139
pub struct FreeList<T, M> {
140
slots: Vec<Slot<T>>,
141
free_list_head: Option<u32>,
142
active_count: usize,
143
_marker: PhantomData<M>,
144
}
145
146
pub enum UpsertResult<T, M> {
147
Updated(T),
148
Inserted(FreeListHandle<M>),
149
}
150
151
impl<T, M> FreeList<T, M> {
152
/// Mints a new `FreeList` with no entries.
153
///
154
/// Triggers a 1-entry allocation.
155
pub fn new() -> Self {
156
// We guarantee that we never have zero entries by starting with one
157
// free entry. This allows WeakFreeListHandle::invalid() to work
158
// without adding any additional branches.
159
let first_slot = Slot {
160
next: None,
161
epoch: Epoch::new(),
162
value: None,
163
};
164
FreeList {
165
slots: vec![first_slot],
166
free_list_head: Some(0),
167
active_count: 0,
168
_marker: PhantomData,
169
}
170
}
171
172
pub fn clear(&mut self) {
173
self.slots.truncate(1);
174
self.slots[0] = Slot {
175
next: None,
176
epoch: Epoch::new(),
177
value: None,
178
};
179
self.free_list_head = Some(0);
180
self.active_count = 0;
181
}
182
183
#[allow(dead_code)]
184
pub fn get(&self, id: &FreeListHandle<M>) -> &T {
185
self.slots[id.index as usize].value.as_ref().unwrap()
186
}
187
188
#[allow(dead_code)]
189
pub fn get_mut(&mut self, id: &FreeListHandle<M>) -> &mut T {
190
self.slots[id.index as usize].value.as_mut().unwrap()
191
}
192
193
pub fn get_opt(&self, id: &WeakFreeListHandle<M>) -> Option<&T> {
194
let slot = &self.slots[id.index as usize];
195
if slot.epoch == id.epoch {
196
slot.value.as_ref()
197
} else {
198
None
199
}
200
}
201
202
pub fn get_opt_mut(&mut self, id: &WeakFreeListHandle<M>) -> Option<&mut T> {
203
let slot = &mut self.slots[id.index as usize];
204
if slot.epoch == id.epoch {
205
slot.value.as_mut()
206
} else {
207
None
208
}
209
}
210
211
// Perform a database style UPSERT operation. If the provided
212
// handle is a valid entry, update the value and return the
213
// previous data. If the provided handle is invalid, then
214
// insert the data into a new slot and return the new handle.
215
pub fn upsert(&mut self, id: &WeakFreeListHandle<M>, data: T) -> UpsertResult<T, M> {
216
if self.slots[id.index as usize].epoch == id.epoch {
217
let slot = &mut self.slots[id.index as usize];
218
let result = UpsertResult::Updated(slot.value.take().unwrap());
219
slot.value = Some(data);
220
result
221
} else {
222
UpsertResult::Inserted(self.insert(data))
223
}
224
}
225
226
pub fn insert(&mut self, item: T) -> FreeListHandle<M> {
227
self.active_count += 1;
228
229
match self.free_list_head {
230
Some(free_index) => {
231
let slot = &mut self.slots[free_index as usize];
232
233
// Remove from free list.
234
self.free_list_head = slot.next;
235
slot.next = None;
236
slot.value = Some(item);
237
238
FreeListHandle {
239
index: free_index,
240
epoch: slot.epoch,
241
_marker: PhantomData,
242
}
243
}
244
None => {
245
let index = self.slots.len() as u32;
246
let epoch = Epoch::new();
247
248
self.slots.push(Slot {
249
next: None,
250
epoch,
251
value: Some(item),
252
});
253
254
FreeListHandle {
255
index,
256
epoch,
257
_marker: PhantomData,
258
}
259
}
260
}
261
}
262
263
pub fn free(&mut self, id: FreeListHandle<M>) -> T {
264
self.active_count -= 1;
265
let slot = &mut self.slots[id.index as usize];
266
slot.next = self.free_list_head;
267
slot.epoch = Epoch(slot.epoch.0 + 1);
268
self.free_list_head = Some(id.index);
269
slot.value.take().unwrap()
270
}
271
272
#[allow(dead_code)]
273
pub fn len(&self) -> usize {
274
self.active_count
275
}
276
}