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
use wgt::Backend;
use crate::{
id::{Id, Marker},
lock::{rank, Mutex},
Epoch, Index,
};
use std::{fmt::Debug, marker::PhantomData};
#[derive(Copy, Clone, Debug, PartialEq)]
enum IdSource {
External,
Allocated,
None,
}
/// A simple structure to allocate [`Id`] identifiers.
///
/// Calling [`alloc`] returns a fresh, never-before-seen id. Calling [`release`]
/// marks an id as dead; it will never be returned again by `alloc`.
///
/// `IdentityValues` returns `Id`s whose index values are suitable for use as
/// indices into a `Vec<T>` that holds those ids' referents:
///
/// - Every live id has a distinct index value. Every live id's index
/// selects a distinct element in the vector.
///
/// - `IdentityValues` 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.
///
/// - `IdentityValues` reuses the index values of freed ids before returning
/// ids with new index values. Freed vector entries get reused.
///
/// [`Id`]: crate::id::Id
/// [`Backend`]: wgt::Backend;
/// [`alloc`]: IdentityValues::alloc
/// [`release`]: IdentityValues::release
#[derive(Debug)]
pub(super) struct IdentityValues {
free: Vec<(Index, Epoch)>,
next_index: Index,
count: usize,
// Sanity check: The allocation logic works under the assumption that we don't
// do a mix of allocating ids from here and providing ids manually for the same
// storage container.
id_source: IdSource,
}
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> {
assert!(
self.id_source != IdSource::External,
"Mix of internally allocated and externally provided IDs"
);
self.id_source = IdSource::Allocated;
self.count += 1;
match self.free.pop() {
Some((index, epoch)) => Id::zip(index, epoch + 1, backend),
None => {
let index = self.next_index;
self.next_index += 1;
let epoch = 1;
Id::zip(index, epoch, backend)
}
}
}
pub fn mark_as_used<T: Marker>(&mut self, id: Id<T>) -> Id<T> {
assert!(
self.id_source != IdSource::Allocated,
"Mix of internally allocated and externally provided IDs"
);
self.id_source = IdSource::External;
self.count += 1;
id
}
/// Free `id`. It will never be returned from `alloc` again.
pub fn release<T: Marker>(&mut self, id: Id<T>) {
if let IdSource::Allocated = self.id_source {
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(
rank::IDENTITY_MANAGER_VALUES,
IdentityValues {
free: Vec::new(),
next_index: 0,
count: 0,
id_source: IdSource::None,
},
),
_phantom: PhantomData,
}
}
}
#[test]
fn test_epoch_end_of_life() {
use crate::id;
let man = IdentityManager::<id::markers::Buffer>::new();
let id1 = man.process(Backend::Empty);
assert_eq!(id1.unzip(), (0, 1, Backend::Empty));
man.free(id1);
let id2 = man.process(Backend::Empty);
// confirm that the epoch 1 is no longer re-used
assert_eq!(id2.unzip(), (0, 2, Backend::Empty));
}