naga/arena/
handle_set.rs

1//! The [`HandleSet`] type and associated definitions.
2
3use crate::arena::{Arena, Handle, UniqueArena};
4
5/// A set of `Handle<T>` values.
6#[derive(Debug)]
7pub struct HandleSet<T> {
8    /// Bound on indexes of handles stored in this set.
9    len: usize,
10
11    /// `members[i]` is true if the handle with index `i` is a member.
12    members: bit_set::BitSet,
13
14    /// This type is indexed by values of type `T`.
15    as_keys: core::marker::PhantomData<T>,
16}
17
18impl<T> HandleSet<T> {
19    /// Return a new, empty `HandleSet`.
20    pub fn new() -> Self {
21        Self {
22            len: 0,
23            members: bit_set::BitSet::new(),
24            as_keys: core::marker::PhantomData,
25        }
26    }
27
28    pub fn is_empty(&self) -> bool {
29        self.members.is_empty()
30    }
31
32    /// Return a new, empty `HandleSet`, sized to hold handles from `arena`.
33    pub fn for_arena(arena: &impl ArenaType<T>) -> Self {
34        let len = arena.len();
35        Self {
36            len,
37            members: bit_set::BitSet::with_capacity(len),
38            as_keys: core::marker::PhantomData,
39        }
40    }
41
42    /// Remove all members from `self`.
43    pub fn clear(&mut self) {
44        self.members.clear();
45    }
46
47    /// Remove all members from `self`, and reserve space to hold handles from `arena`.
48    pub fn clear_for_arena(&mut self, arena: &impl ArenaType<T>) {
49        self.members.clear();
50        self.members.reserve_len(arena.len());
51    }
52
53    /// Return an iterator over all handles that could be made members
54    /// of this set.
55    pub fn all_possible(&self) -> impl Iterator<Item = Handle<T>> {
56        super::Range::full_range_from_size(self.len)
57    }
58
59    /// Add `handle` to the set.
60    ///
61    /// Return `true` if `handle` was not already present in the set.
62    pub fn insert(&mut self, handle: Handle<T>) -> bool {
63        self.members.insert(handle.index())
64    }
65
66    /// Remove `handle` from the set.
67    ///
68    /// Returns `true` if `handle` was present in the set.
69    pub fn remove(&mut self, handle: Handle<T>) -> bool {
70        self.members.remove(handle.index())
71    }
72
73    /// Add handles from `iter` to the set.
74    pub fn insert_iter(&mut self, iter: impl IntoIterator<Item = Handle<T>>) {
75        for handle in iter {
76            self.insert(handle);
77        }
78    }
79
80    /// Add all of the handles that can be included in this set.
81    pub fn add_all(&mut self) {
82        self.members.get_mut().set_all();
83    }
84
85    pub fn contains(&self, handle: Handle<T>) -> bool {
86        self.members.contains(handle.index())
87    }
88
89    /// Return an iterator over all handles in `self`.
90    pub fn iter(&self) -> impl '_ + Iterator<Item = Handle<T>> {
91        self.members.iter().map(Handle::from_usize)
92    }
93
94    /// Removes and returns the numerically largest handle in the set, or `None`
95    /// if the set is empty.
96    pub fn pop(&mut self) -> Option<Handle<T>> {
97        let members = core::mem::take(&mut self.members);
98        let mut vec = members.into_bit_vec();
99        let result = vec.iter_mut().enumerate().rev().find_map(|(i, mut bit)| {
100            if *bit {
101                *bit = false;
102                Some(i)
103            } else {
104                None
105            }
106        });
107        self.members = bit_set::BitSet::from_bit_vec(vec);
108        result.map(Handle::from_usize)
109    }
110}
111
112impl<T> Default for HandleSet<T> {
113    fn default() -> Self {
114        Self::new()
115    }
116}
117
118pub trait ArenaType<T> {
119    fn len(&self) -> usize;
120}
121
122impl<T> ArenaType<T> for Arena<T> {
123    fn len(&self) -> usize {
124        self.len()
125    }
126}
127
128impl<T: core::hash::Hash + Eq> ArenaType<T> for UniqueArena<T> {
129    fn len(&self) -> usize {
130        self.len()
131    }
132}
naga/arena/handle_set.rs

naga/arena/
handle_set.rs
