1//! The `ResourceMetadata` type.
23use alloc::vec::Vec;
45use bit_vec::BitVec;
6use wgt::strict_assert;
78/// A set of resources, holding a `Arc<T>` and epoch for each member.
9///
10/// Testing for membership is fast, and iterating over members is
11/// reasonably fast in practice. Storage consumption is proportional
12/// to the largest id index of any member, not to the number of
13/// members, but a bit vector tracks occupancy, so iteration touches
14/// only occupied elements.
15#[derive(Debug)]
16pub(super) struct ResourceMetadata<T: Clone> {
17/// If the resource with index `i` is a member, `owned[i]` is `true`.
18owned: BitVec<usize>,
1920/// A vector holding clones of members' `T`s.
21resources: Vec<Option<T>>,
22}
2324impl<T: Clone> ResourceMetadata<T> {
25pub(super) fn new() -> Self {
26Self {
27 owned: BitVec::default(),
28 resources: Vec::new(),
29 }
30 }
3132pub(super) fn set_size(&mut self, size: usize) {
33self.resources.resize(size, None);
34 resize_bitvec(&mut self.owned, size);
35 }
3637pub(super) fn clear(&mut self) {
38self.resources.clear();
39self.owned.clear();
40 }
4142/// Ensures a given index is in bounds for all arrays and does
43 /// sanity checks of the presence of a refcount.
44 ///
45 /// In release mode this function is completely empty and is removed.
46#[cfg_attr(not(feature = "strict_asserts"), allow(unused_variables))]
47pub(super) fn tracker_assert_in_bounds(&self, index: usize) {
48strict_assert!(index < self.owned.len());
49strict_assert!(index < self.resources.len());
50strict_assert!(if self.contains(index) {
51self.resources[index].is_some()
52 } else {
53true
54});
55 }
5657/// Returns true if the tracker owns no resources.
58 ///
59 /// This is a O(n) operation.
60pub(super) fn is_empty(&self) -> bool {
61 !self.owned.any()
62 }
6364/// Returns true if the set contains the resource with the given index.
65pub(super) fn contains(&self, index: usize) -> bool {
66self.owned.get(index).unwrap_or(false)
67 }
6869/// Returns true if the set contains the resource with the given index.
70 ///
71 /// # Safety
72 ///
73 /// The given `index` must be in bounds for this `ResourceMetadata`'s
74 /// existing tables. See `tracker_assert_in_bounds`.
75#[inline(always)]
76pub(super) unsafe fn contains_unchecked(&self, index: usize) -> bool {
77unsafe { self.owned.get(index).unwrap_unchecked() }
78 }
7980/// Insert a resource into the set.
81 ///
82 /// Add the resource with the given index, epoch, and reference count to the
83 /// set.
84 ///
85 /// Returns a reference to the newly inserted resource.
86 /// (This allows avoiding a clone/reference count increase in many cases.)
87 ///
88 /// # Safety
89 ///
90 /// The given `index` must be in bounds for this `ResourceMetadata`'s
91 /// existing tables. See `tracker_assert_in_bounds`.
92#[inline(always)]
93pub(super) unsafe fn insert(&mut self, index: usize, resource: T) -> &T {
94self.owned.set(index, true);
95let resource_dst = unsafe { self.resources.get_unchecked_mut(index) };
96 resource_dst.insert(resource)
97 }
9899/// Get the resource with the given index.
100 ///
101 /// # Safety
102 ///
103 /// The given `index` must be in bounds for this `ResourceMetadata`'s
104 /// existing tables. See `tracker_assert_in_bounds`.
105#[inline(always)]
106pub(super) unsafe fn get_resource_unchecked(&self, index: usize) -> &T {
107unsafe {
108self.resources
109 .get_unchecked(index)
110 .as_ref()
111 .unwrap_unchecked()
112 }
113 }
114115/// Returns an iterator over the resources owned by `self`.
116pub(super) fn owned_resources(&self) -> impl Iterator<Item = &T> + '_ {
117if !self.owned.is_empty() {
118self.tracker_assert_in_bounds(self.owned.len() - 1)
119 };
120 iterate_bitvec_indices(&self.owned).map(move |index| {
121let resource = unsafe { self.resources.get_unchecked(index) };
122 resource.as_ref().unwrap()
123 })
124 }
125126/// Returns an iterator over the indices of all resources owned by `self`.
127pub(super) fn owned_indices(&self) -> impl Iterator<Item = usize> + '_ {
128if !self.owned.is_empty() {
129self.tracker_assert_in_bounds(self.owned.len() - 1)
130 };
131 iterate_bitvec_indices(&self.owned)
132 }
133134/// Remove the resource with the given index from the set.
135pub(super) unsafe fn remove(&mut self, index: usize) {
136unsafe {
137*self.resources.get_unchecked_mut(index) = None;
138 }
139self.owned.set(index, false);
140 }
141}
142143/// A source of resource metadata.
144///
145/// This is used to abstract over the various places
146/// trackers can get new resource metadata from.
147pub(super) enum ResourceMetadataProvider<'a, T: Clone> {
148/// Comes directly from explicit values.
149Direct { resource: &'a T },
150/// Comes from another metadata tracker.
151Indirect { metadata: &'a ResourceMetadata<T> },
152}
153impl<T: Clone> ResourceMetadataProvider<'_, T> {
154/// Get a reference to the resource from this.
155 ///
156 /// # Safety
157 ///
158 /// - The index must be in bounds of the metadata tracker if this uses an indirect source.
159#[inline(always)]
160pub(super) unsafe fn get(&self, index: usize) -> &T {
161match self {
162 ResourceMetadataProvider::Direct { resource } => resource,
163 ResourceMetadataProvider::Indirect { metadata } => {
164 metadata.tracker_assert_in_bounds(index);
165 {
166let resource = unsafe { metadata.resources.get_unchecked(index) }.as_ref();
167unsafe { resource.unwrap_unchecked() }
168 }
169 }
170 }
171 }
172}
173174/// Resizes the given bitvec to the given size. I'm not sure why this is hard to do but it is.
175fn resize_bitvec<B: bit_vec::BitBlock>(vec: &mut BitVec<B>, size: usize) {
176let owned_size_to_grow = size.checked_sub(vec.len());
177if let Some(delta) = owned_size_to_grow {
178if delta != 0 {
179 vec.grow(delta, false);
180 }
181 } else {
182 vec.truncate(size);
183 }
184}
185186/// Produces an iterator that yields the indexes of all bits that are set in the bitvec.
187///
188/// Will skip entire usize's worth of bits if they are all false.
189fn iterate_bitvec_indices(ownership: &BitVec<usize>) -> impl Iterator<Item = usize> + '_ {
190const BITS_PER_BLOCK: usize = usize::BITS as usize;
191192let size = ownership.len();
193194 ownership
195 .blocks()
196 .enumerate()
197 .filter(|&(_, word)| word != 0)
198 .flat_map(move |(word_index, mut word)| {
199let bit_start = word_index * BITS_PER_BLOCK;
200let bit_end = (bit_start + BITS_PER_BLOCK).min(size);
201202 (bit_start..bit_end).filter(move |_| {
203let active = word & 0b1 != 0;
204 word >>= 1;
205206 active
207 })
208 })
209}