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
|
use parking_lot::Mutex;
use wgt::Backend;
use crate::{
id::{Id, Marker},
Epoch, FastHashMap, Index,
};
use std::{fmt::Debug, marker::PhantomData};
/// A simple structure to allocate [`Id`] identifiers.
///
/// Calling [`alloc`] returns a fresh, never-before-seen id. Calling [`free`]
/// marks an id as dead; it will never be returned again by `alloc`.
///
/// Use `IdentityManager::default` to construct new instances.
///
/// `IdentityManager` returns `Id`s whose index values are suitable for use as
/// indices into a `Storage<T>` that holds those ids' referents:
///
/// - Every live id has a distinct index value. Each live id's index selects a
/// distinct element in the vector.
///
/// - `IdentityManager` prefers low index numbers. If you size your vector to
/// accommodate the indices produced here, the vector's length will reflect
/// the highwater mark of actual occupancy.
///
/// - `IdentityManager` reuses the index values of freed ids before returning
/// ids with new index values. Freed vector entries get reused.
///
/// See the module-level documentation for an overview of how this
/// fits together.
///
/// [`Id`]: crate::id::Id
/// [`Backend`]: wgt::Backend;
/// [`alloc`]: IdentityManager::alloc
/// [`free`]: IdentityManager::free
#[derive(Debug, Default)]
pub(super) struct IdentityValues {
free: Vec<(Index, Epoch)>,
//sorted by Index
used: FastHashMap<Epoch, Vec<Index>>,
count: usize,
}
impl IdentityValues {
/// Allocate a fresh, never-before-seen id with the given `backend`.
///
/// The backend is incorporated into the id, so that ids allocated with
/// different `backend` values are always distinct.
pub fn alloc<T: Marker>(&mut self, backend: Backend) -> Id<T> {
self.count += 1;
match self.free.pop() {
Some((index, epoch)) => Id::zip(index, epoch + 1, backend),
None => {
let epoch = 1;
let used = self.used.entry(epoch).or_insert_with(Default::default);
let index = if let Some(i) = used.iter().max_by_key(|v| *v) {
i + 1
} else {
0
};
used.push(index);
Id::zip(index, epoch, backend)
}
}
}
pub fn mark_as_used<T: Marker>(&mut self, id: Id<T>) -> Id<T> {
self.count += 1;
let (index, epoch, _backend) = id.unzip();
let used = self.used.entry(epoch).or_insert_with(Default::default);
used.push(index);
id
}
/// Free `id`. It will never be returned from `alloc` again.
pub fn release<T: Marker>(&mut self, id: Id<T>) {
let (index, epoch, _backend) = id.unzip();
self.free.push((index, epoch));
self.count -= 1;
}
pub fn count(&self) -> usize {
self.count
}
}
#[derive(Debug)]
pub struct IdentityManager<T: Marker> {
pub(super) values: Mutex<IdentityValues>,
_phantom: PhantomData<T>,
}
impl<T: Marker> IdentityManager<T> {
pub fn process(&self, backend: Backend) -> Id<T> {
self.values.lock().alloc(backend)
}
pub fn mark_as_used(&self, id: Id<T>) -> Id<T> {
self.values.lock().mark_as_used(id)
}
pub fn free(&self, id: Id<T>) {
self.values.lock().release(id)
}
}
impl<T: Marker> IdentityManager<T> {
pub fn new() -> Self {
Self {
values: Mutex::new(IdentityValues::default()),
_phantom: PhantomData,
}
}
}
#[test]
fn test_epoch_end_of_life() {
use crate::id;
let man = IdentityManager::<id::markers::Buffer>::new();
let forced_id = man.mark_as_used(id::BufferId::zip(0, 1, Backend::Empty));
assert_eq!(forced_id.unzip().0, 0);
let id1 = man.process(Backend::Empty);
assert_eq!(id1.unzip().0, 1);
man.free(id1);
let id2 = man.process(Backend::Empty);
// confirm that the epoch 1 is no longer re-used
assert_eq!(id2.unzip().0, 1);
assert_eq!(id2.unzip().1, 2);
}
|
