wgpu_core/
identity.rs

1use alloc::vec::Vec;
2use core::{fmt::Debug, marker::PhantomData};
3
4use crate::{
5    id::{Id, Marker},
6    lock::{rank, Mutex},
7    Epoch, Index,
8};
9
10#[derive(Copy, Clone, Debug, PartialEq)]
11enum IdSource {
12    External,
13    Allocated,
14    None,
15}
16
17/// A simple structure to allocate [`Id`] identifiers.
18///
19/// Calling [`alloc`] returns a fresh, never-before-seen id. Calling [`release`]
20/// marks an id as dead; it will never be returned again by `alloc`.
21///
22/// `IdentityValues` returns `Id`s whose index values are suitable for use as
23/// indices into a `Vec<T>` that holds those ids' referents:
24///
25/// - Every live id has a distinct index value. Every live id's index
26///   selects a distinct element in the vector.
27///
28/// - `IdentityValues` prefers low index numbers. If you size your vector to
29///   accommodate the indices produced here, the vector's length will reflect
30///   the highwater mark of actual occupancy.
31///
32/// - `IdentityValues` reuses the index values of freed ids before returning
33///   ids with new index values. Freed vector entries get reused.
34///
35/// [`Id`]: crate::id::Id
36/// [`alloc`]: IdentityValues::alloc
37/// [`release`]: IdentityValues::release
38#[derive(Debug)]
39pub(super) struct IdentityValues {
40    free: Vec<(Index, Epoch)>,
41    next_index: Index,
42    count: usize,
43    // Sanity check: The allocation logic works under the assumption that we don't
44    // do a mix of allocating ids from here and providing ids manually for the same
45    // storage container.
46    id_source: IdSource,
47}
48
49impl IdentityValues {
50    /// Allocate a fresh, never-before-seen id with the given `backend`.
51    ///
52    /// The backend is incorporated into the id, so that ids allocated with
53    /// different `backend` values are always distinct.
54    pub fn alloc<T: Marker>(&mut self) -> Id<T> {
55        assert!(
56            self.id_source != IdSource::External,
57            "Mix of internally allocated and externally provided IDs"
58        );
59        self.id_source = IdSource::Allocated;
60
61        self.count += 1;
62        match self.free.pop() {
63            Some((index, epoch)) => Id::zip(index, epoch + 1),
64            None => {
65                let index = self.next_index;
66                self.next_index += 1;
67                let epoch = 1;
68                Id::zip(index, epoch)
69            }
70        }
71    }
72
73    pub fn mark_as_used<T: Marker>(&mut self, id: Id<T>) -> Id<T> {
74        assert!(
75            self.id_source != IdSource::Allocated,
76            "Mix of internally allocated and externally provided IDs"
77        );
78        self.id_source = IdSource::External;
79
80        self.count += 1;
81        id
82    }
83
84    /// Free `id`. It will never be returned from `alloc` again.
85    pub fn release<T: Marker>(&mut self, id: Id<T>) {
86        if let IdSource::Allocated = self.id_source {
87            let (index, epoch) = id.unzip();
88            self.free.push((index, epoch));
89        }
90        self.count -= 1;
91    }
92
93    pub fn count(&self) -> usize {
94        self.count
95    }
96}
97
98#[derive(Debug)]
99pub struct IdentityManager<T: Marker> {
100    pub(super) values: Mutex<IdentityValues>,
101    _phantom: PhantomData<T>,
102}
103
104impl<T: Marker> IdentityManager<T> {
105    pub fn process(&self) -> Id<T> {
106        self.values.lock().alloc()
107    }
108    pub fn mark_as_used(&self, id: Id<T>) -> Id<T> {
109        self.values.lock().mark_as_used(id)
110    }
111    pub fn free(&self, id: Id<T>) {
112        self.values.lock().release(id)
113    }
114}
115
116impl<T: Marker> IdentityManager<T> {
117    pub fn new() -> Self {
118        Self {
119            values: Mutex::new(
120                rank::IDENTITY_MANAGER_VALUES,
121                IdentityValues {
122                    free: Vec::new(),
123                    next_index: 0,
124                    count: 0,
125                    id_source: IdSource::None,
126                },
127            ),
128            _phantom: PhantomData,
129        }
130    }
131}
132
133#[test]
134fn test_epoch_end_of_life() {
135    use crate::id;
136    let man = IdentityManager::<id::markers::Buffer>::new();
137    let id1 = man.process();
138    assert_eq!(id1.unzip(), (0, 1));
139    man.free(id1);
140    let id2 = man.process();
141    // confirm that the epoch 1 is no longer re-used
142    assert_eq!(id2.unzip(), (0, 2));
143}