oxidd_manager_index/terminal_manager/
dynamic.rs

1use std::cell::UnsafeCell;
2use std::hash::{Hash, Hasher};
3use std::iter::FusedIterator;
4use std::marker::PhantomData;
5use std::mem::ManuallyDrop;
6use std::sync::atomic::AtomicU32;
7use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
8
9use crossbeam_utils::CachePadded;
10use linear_hashtbl::raw::RawTable;
11use parking_lot::{Mutex, MutexGuard};
12use rustc_hash::FxHasher;
13
14use oxidd_core::Tag;
15use oxidd_core::error::OutOfMemory;
16use oxidd_core::util::AllocResult;
17
18use crate::manager::{Edge, InnerNodeCons, TerminalManagerCons};
19use crate::node::NodeBase;
20
21use super::TerminalManager;
22
23pub struct DynamicTerminalManager<'id, T, N, ET, const TERMINALS: usize> {
24    store: Box<[UnsafeCell<Slot<T>>]>,
25    state: CachePadded<Mutex<State<'id, N, ET>>>,
26}
27
28struct State<'id, N, ET> {
29    /// Next free index in the `store` of `DynamicTerminalManager`
30    ///
31    /// SAFETY invariant: Unless `next_free` is out of bounds for the store
32    /// array of [`DynamicTerminalManager`], it references an empty [`Slot`]. If
33    /// the state lock is held, there is exclusive access to that slot.
34    next_free: u32,
35
36    /// Set of indices into the `store` field of `DynamicTerminalManager`
37    ///
38    /// The hash values are those of the referenced terminal values.
39    unique_table: RawTable<u32, u32>,
40
41    phantom: PhantomData<Edge<'id, N, ET>>,
42}
43
44union Slot<T> {
45    node: ManuallyDrop<ArcItem<T>>,
46
47    /// SAFETY invariant: Unless `next_free` is out of bounds for the store
48    /// array of [`DynamicTerminalManager`], it references an empty [`Slot`]. If
49    /// the state lock is held, there is exclusive access to that slot.
50    next_free: u32,
51}
52
53struct ArcItem<T> {
54    rc: AtomicU32,
55    value: T,
56}
57
58/// SAFETY: `id` must be a valid terminal ID for `store`
59unsafe fn retain<T>(store: &[UnsafeCell<Slot<T>>], id: usize) {
60    // SAFETY: Since `id` is a valid terminal ID, it is `<= store.len()`.
61    // Furthermore, we have shared access to the referenced slot and the `Slot`
62    // is a `node`.
63    let item = unsafe { &(*store.get_unchecked(id).get()).node };
64    let old_rc = item.rc.fetch_add(1, Relaxed);
65    if old_rc > (u32::MAX >> 1) {
66        std::process::abort(); // prevent overflow
67    }
68}
69
70fn hash<T: Hash>(terminal: &T) -> u64 {
71    let mut hasher = FxHasher::default();
72    terminal.hash(&mut hasher);
73    hasher.finish()
74}
75
76impl<T, N, ET, const TERMINALS: usize> DynamicTerminalManager<'_, T, N, ET, TERMINALS> {
77    const CHECK_TERMINALS: () = assert!(
78        TERMINALS < (1 << (u32::BITS - 1)),
79        "`TERMINALS` is too large"
80    );
81}
82
83impl<'id, T, N, ET, const TERMINALS: usize> TerminalManager<'id, N, ET, TERMINALS>
84    for DynamicTerminalManager<'id, T, N, ET, TERMINALS>
85where
86    T: Eq + Hash,
87    N: NodeBase,
88    ET: Tag,
89{
90    type TerminalNode = T;
91    type TerminalNodeRef<'a>
92        = &'a T
93    where
94        Self: 'a;
95
96    type Iterator<'a>
97        = DynamicTerminalIterator<'a, 'id, T, N, ET>
98    where
99        Self: 'a,
100        'id: 'a;
101
102    fn with_capacity(capacity: u32) -> Self {
103        let () = Self::CHECK_TERMINALS;
104        let capacity = std::cmp::min(TERMINALS, capacity as usize);
105
106        let mut store_vec = Vec::new();
107        let mut i = 0u32;
108        store_vec.resize_with(capacity, || {
109            i += 1;
110            UnsafeCell::new(Slot { next_free: i })
111        });
112
113        Self {
114            store: store_vec.into_boxed_slice(),
115            state: CachePadded::new(Mutex::new(State {
116                next_free: 0,
117                unique_table: RawTable::new(),
118                phantom: PhantomData,
119            })),
120        }
121    }
122
123    #[inline]
124    fn len(&self) -> usize {
125        self.state.lock().unique_table.len()
126    }
127
128    #[inline]
129    unsafe fn get_terminal(&self, id: usize) -> &T {
130        // SAFETY: Since `id` is a valid terminal ID, it is
131        // `<= self.store.len()`. Furthermore, we have shared access to the
132        // referenced `Slot` and the slot is a `node`.
133        &unsafe { &(*self.store.get_unchecked(id).get()).node }.value
134    }
135
136    #[inline]
137    unsafe fn retain(&self, id: usize) {
138        // SAFETY: `id` is a valid terminal ID for `self.store`
139        unsafe { retain(&self.store, id) }
140    }
141
142    #[inline]
143    unsafe fn release(&self, id: usize) {
144        // SAFETY: Since `id` is a valid terminal ID, it is
145        // `<= self.store.len()`. Furthermore, we have shared access to the
146        // referenced `Slot` and the slot is a `node`.
147        let item = unsafe { &(*self.store.get_unchecked(id).get()).node };
148        // Synchronizes-with the load in `Self::gc()`
149        let _old_rc = item.rc.fetch_sub(1, Release);
150        debug_assert!(
151            _old_rc > 1,
152            "dropping the last reference should only happen during garbage collection"
153        );
154    }
155
156    #[inline]
157    fn get_edge(&self, terminal: T) -> AllocResult<Edge<'id, N, ET>> {
158        let mut state = self.state.lock();
159        let hash = hash(&terminal);
160        let id = match state.unique_table.find_or_find_insert_slot(
161            hash,
162            // SAFETY: The IDs stored in the table are valid, hence
163            // `<= self.store.len()`. We have shared access to the referenced
164            // `Slot` and the slot is a `node`.
165            |&id| unsafe { &(*self.store.get_unchecked(id as usize).get()).node }.value == terminal,
166        ) {
167            Ok(slot) => {
168                // SAFETY: `slot` was returned by
169                // `state.unique_table.find_or_find_insert_slot()` and there
170                // were no modifications of the table in between.
171                let id = *unsafe { state.unique_table.get_at_slot_unchecked(slot) };
172                unsafe { self.retain(id as usize) };
173                id
174            }
175            Err(table_slot) => {
176                let id = state.next_free;
177                if id == self.store.len() as u32 {
178                    return Err(OutOfMemory);
179                }
180                // SAFETY: holds by invariant of `state.next_free`
181                let store_slot = unsafe { &mut *self.store.get_unchecked(id as usize).get() };
182                state.next_free = unsafe { store_slot.next_free };
183                store_slot.node = ManuallyDrop::new(ArcItem {
184                    rc: AtomicU32::new(2),
185                    value: terminal,
186                });
187                // SAFETY: `table_slot` was returned by
188                // `state.unique_table.find_or_find_insert_slot()` and there
189                // were no modifications of the table in between.
190                unsafe {
191                    state
192                        .unique_table
193                        .insert_in_slot_unchecked(hash, table_slot, id)
194                };
195                id
196            }
197        };
198
199        Ok(unsafe { Edge::from_terminal_id(id) })
200    }
201
202    #[inline]
203    fn iter<'a>(&'a self) -> Self::Iterator<'a>
204    where
205        Self: 'a,
206    {
207        let state = self.state.lock();
208        let len = state.unique_table.len();
209        DynamicTerminalIterator {
210            store: &self.store,
211            state,
212            next_slot: 0,
213            len,
214        }
215    }
216
217    #[inline(always)]
218    fn gc(&self) -> u32 {
219        let mut collected = 0;
220        let mut state = self.state.lock();
221        // Use a local variable here because otherwise, the borrow checker
222        // complains about `state` being borrowed mutably twice. In case of a
223        // panic (which should not happen) we would potentially loose a few
224        // slots, but this is not a SAFETY issue.
225        let mut next_free = state.next_free;
226        state.unique_table.retain(
227            |&mut id| {
228                // SAFETY: The IDs stored in the table are valid, hence
229                // `<= self.store.len()`. We have shared access to the
230                // referenced `Slot` and the slot is a `node`.
231                let node = unsafe { &(*self.store.get_unchecked(id as usize).get()).node };
232                // The following load synchronizes-with the `fetch_sub()` in
233                // `release()`. Releasing terminal nodes and garbage collection
234                // may run in parallel.
235                node.rc.load(Acquire) != 1
236            },
237            |id| {
238                // SAFETY: as above
239                let slot = unsafe { &mut *self.store.get_unchecked(id as usize).get() };
240                unsafe { ManuallyDrop::drop(&mut slot.node) };
241                slot.next_free = next_free;
242                next_free = id;
243                collected += 1;
244            },
245        );
246        state.next_free = next_free;
247        collected
248    }
249}
250
251unsafe impl<T: Send + Sync, N: Send + Sync, ET: Send + Sync, const TERMINALS: usize> Send
252    for DynamicTerminalManager<'_, T, N, ET, TERMINALS>
253{
254}
255unsafe impl<T: Send + Sync, N: Send + Sync, ET: Send + Sync, const TERMINALS: usize> Sync
256    for DynamicTerminalManager<'_, T, N, ET, TERMINALS>
257{
258}
259
260pub struct DynamicTerminalManagerCons<T>(PhantomData<T>);
261
262impl<
263    T: Hash + Eq + Send + Sync,
264    NC: InnerNodeCons<ET>,
265    ET: Tag + Send + Sync,
266    const TERMINALS: usize,
267> TerminalManagerCons<NC, ET, TERMINALS> for DynamicTerminalManagerCons<T>
268{
269    type TerminalNode = T;
270    type T<'id> = DynamicTerminalManager<'id, T, NC::T<'id>, ET, TERMINALS>;
271}
272
273pub struct DynamicTerminalIterator<'a, 'id, T, N, ET> {
274    store: &'a [UnsafeCell<Slot<T>>],
275    state: MutexGuard<'a, State<'id, N, ET>>,
276    next_slot: usize,
277    len: usize,
278}
279
280impl<'id, T, N: NodeBase, ET: Tag> Iterator for DynamicTerminalIterator<'_, 'id, T, N, ET> {
281    type Item = Edge<'id, N, ET>;
282
283    #[inline(always)]
284    fn next(&mut self) -> Option<Self::Item> {
285        if self.len() == 0 {
286            return None;
287        }
288        self.len -= 1;
289        let unique_table = &self.state.unique_table;
290        // SAFETY: `self.len` is the number of occupied slots
291        // `>= self.next_slot`. Hence, there is a slot `< unique_table.slots()`
292        // that is occupied.
293        while !unsafe { unique_table.is_slot_occupied_unchecked(self.next_slot) } {
294            self.next_slot += 1;
295        }
296        // SAFETY: `self.next_slot` is occupied.
297        let id = *unsafe { unique_table.get_at_slot_unchecked(self.next_slot) };
298        self.next_slot += 1;
299        // SAFETY: `id` was obtained from the unique_table, hence it is a valid
300        // terminal ID for `self.store`.
301        unsafe { retain(self.store, id as usize) };
302        Some(unsafe { Edge::from_terminal_id(id) })
303    }
304
305    #[inline(always)]
306    fn size_hint(&self) -> (usize, Option<usize>) {
307        let len = self.len();
308        (len, Some(len))
309    }
310}
311
312impl<T, N: NodeBase, ET: Tag> FusedIterator for DynamicTerminalIterator<'_, '_, T, N, ET> {}
313
314impl<T, N: NodeBase, ET: Tag> ExactSizeIterator for DynamicTerminalIterator<'_, '_, T, N, ET> {
315    #[inline(always)]
316    fn len(&self) -> usize {
317        self.len
318    }
319}
oxidd_manager_index/terminal_manager/dynamic.rs

oxidd_manager_index/terminal_manager/
dynamic.rs
