oxidd_manager_pointer/terminal_manager/
static.rs

1use std::hash::Hash;
2use std::iter::FusedIterator;
3use std::marker::PhantomData;
4use std::mem::align_of;
5use std::ptr::NonNull;
6
7use oxidd_core::util::AllocResult;
8use oxidd_core::Countable;
9use oxidd_core::Tag;
10
11use crate::manager::DiagramRulesCons;
12use crate::manager::Edge;
13use crate::manager::InnerNodeCons;
14use crate::manager::ManagerDataCons;
15use crate::manager::TerminalManagerCons;
16use crate::node::NodeBase;
17
18use super::TerminalManager;
19
20#[repr(align(128))]
21pub struct StaticTerminalManager<
22    'id,
23    Terminal,
24    InnerNode,
25    EdgeTag,
26    ManagerData,
27    const PAGE_SIZE: usize,
28    const TAG_BITS: u32,
29>(PhantomData<(&'id (), Terminal, InnerNode, EdgeTag, ManagerData)>);
30
31impl<
32        Terminal: Countable,
33        InnerNode,
34        EdgeTag: Tag,
35        ManagerData,
36        const PAGE_SIZE: usize,
37        const TAG_BITS: u32,
38    > StaticTerminalManager<'_, Terminal, InnerNode, EdgeTag, ManagerData, PAGE_SIZE, TAG_BITS>
39{
40    /// All "info" bits of edges: `TAG_BITS` for the `EdgeTag`, one bit for
41    /// inner/terminal node, and `bit_width(Terminal::MAX_VALUE)` bits for the
42    /// terminal value.
43    const ALL_BITS: u32 = TAG_BITS + 1 + (usize::BITS - Terminal::MAX_VALUE.leading_zeros());
44
45    /// Bit mask corresponding to `Self::ALL_BITS`
46    const ALL_BITS_MASK: usize = (1 << Self::ALL_BITS) - 1;
47
48    /// Bit indicating whether an edge points to a terminal or an inner node
49    const TERMINAL_BIT: u32 = TAG_BITS;
50
51    /// Least significant bit of the value
52    const VAL_LSB: u32 = TAG_BITS + 1;
53
54    const ASSERT_SUFFICIENT_ALIGN: () = {
55        assert!(
56            align_of::<Self>() >= 1 << Self::ALL_BITS,
57            "Too many `TAG_BITS` / too large `Terminal::MAX_VALUE`"
58        );
59    };
60}
61
62unsafe impl<
63        'id,
64        Terminal,
65        InnerNode,
66        EdgeTag,
67        ManagerData,
68        const PAGE_SIZE: usize,
69        const TAG_BITS: u32,
70    > TerminalManager<'id, InnerNode, EdgeTag, ManagerData, PAGE_SIZE, TAG_BITS>
71    for StaticTerminalManager<'id, Terminal, InnerNode, EdgeTag, ManagerData, PAGE_SIZE, TAG_BITS>
72where
73    Terminal: Countable + Eq + Hash,
74    InnerNode: NodeBase,
75    EdgeTag: Tag,
76{
77    type TerminalNode = Terminal;
78    type TerminalNodeRef<'a>
79        = Terminal
80    where
81        Self: 'a;
82
83    type Iterator<'a>
84        = StaticTerminalIterator<'id, InnerNode, EdgeTag, TAG_BITS>
85    where
86        Self: 'a,
87        'id: 'a;
88
89    #[inline(always)]
90    unsafe fn new_in(_slot: *mut Self) {
91        let () = Self::ASSERT_SUFFICIENT_ALIGN;
92    }
93
94    #[inline]
95    fn terminal_manager(edge: &Edge<'id, InnerNode, EdgeTag, TAG_BITS>) -> NonNull<Self> {
96        assert!(!edge.is_inner());
97        let ptr = sptr::Strict::map_addr(edge.as_ptr().as_ptr(), |p| p & !Self::ALL_BITS_MASK)
98            as *mut Self;
99        unsafe { NonNull::new_unchecked(ptr) }
100    }
101
102    #[inline(always)]
103    fn len(&self) -> usize {
104        Terminal::MAX_VALUE + 1
105    }
106
107    #[inline]
108    fn deref_edge(&self, edge: &Edge<'id, InnerNode, EdgeTag, TAG_BITS>) -> Terminal {
109        Terminal::from_usize((edge.addr() & Self::ALL_BITS_MASK) >> Self::VAL_LSB)
110    }
111
112    #[inline]
113    fn clone_edge(
114        edge: &Edge<'id, InnerNode, EdgeTag, TAG_BITS>,
115    ) -> Edge<'id, InnerNode, EdgeTag, TAG_BITS> {
116        assert!(!edge.is_inner());
117        let ptr = edge.as_ptr();
118        unsafe { Edge::from_ptr(ptr) }
119    }
120
121    #[inline(always)]
122    fn drop_edge(edge: Edge<'id, InnerNode, EdgeTag, TAG_BITS>) {
123        debug_assert!(!edge.is_inner());
124        std::mem::forget(edge)
125    }
126
127    #[inline]
128    unsafe fn get(
129        this: *const Self,
130        terminal: Terminal,
131    ) -> AllocResult<Edge<'id, InnerNode, EdgeTag, TAG_BITS>> {
132        let ptr = sptr::Strict::map_addr(this as *mut (), |p| {
133            p | (1 << Self::TERMINAL_BIT) | (terminal.as_usize() << Self::VAL_LSB)
134        });
135        Ok(unsafe { Edge::from_ptr(NonNull::new_unchecked(ptr)) })
136    }
137
138    #[inline]
139    unsafe fn iter<'a>(this: *const Self) -> Self::Iterator<'a>
140    where
141        Self: 'a,
142    {
143        let first = sptr::Strict::map_addr(this as *mut (), |p| p | (1 << Self::TERMINAL_BIT));
144        StaticTerminalIterator::new(NonNull::new(first).unwrap(), Terminal::MAX_VALUE + 1)
145    }
146
147    #[inline(always)]
148    fn gc(&self) -> usize {
149        0 // Nothing to collect
150    }
151}
152
153pub struct StaticTerminalManagerCons<Terminal>(PhantomData<Terminal>);
154
155impl<
156        Terminal: Countable + Hash + Eq,
157        NC: InnerNodeCons<ET, TAG_BITS>,
158        ET: Tag,
159        MDC: ManagerDataCons<NC, ET, Self, RC, PAGE_SIZE, TAG_BITS>,
160        RC: DiagramRulesCons<NC, ET, Self, MDC, PAGE_SIZE, TAG_BITS>,
161        const PAGE_SIZE: usize,
162        const TAG_BITS: u32,
163    > TerminalManagerCons<NC, ET, RC, MDC, PAGE_SIZE, TAG_BITS>
164    for StaticTerminalManagerCons<Terminal>
165{
166    type TerminalNode = Terminal;
167    type T<'id> =
168        StaticTerminalManager<'id, Terminal, NC::T<'id>, ET, MDC::T<'id>, PAGE_SIZE, TAG_BITS>;
169}
170
171pub struct StaticTerminalIterator<'id, InnerNode, EdgeTag, const TAG_BITS: u32> {
172    ptr: NonNull<()>,
173    count: usize,
174    phantom: PhantomData<Edge<'id, InnerNode, EdgeTag, TAG_BITS>>,
175}
176
177impl<InnerNode, EdgeTag, const TAG_BITS: u32>
178    StaticTerminalIterator<'_, InnerNode, EdgeTag, TAG_BITS>
179{
180    const TERMINAL_BIT: u32 = TAG_BITS;
181
182    const VAL_LSB: u32 = TAG_BITS + 1;
183
184    pub fn new(first_ptr: NonNull<()>, count: usize) -> Self {
185        assert!(sptr::Strict::addr(first_ptr.as_ptr()) & (1 << Self::TERMINAL_BIT) != 0);
186        Self {
187            ptr: first_ptr,
188            count,
189            phantom: PhantomData,
190        }
191    }
192}
193
194impl<'id, InnerNode: NodeBase, EdgeTag: Tag, const TAG_BITS: u32> Iterator
195    for StaticTerminalIterator<'id, InnerNode, EdgeTag, TAG_BITS>
196{
197    type Item = Edge<'id, InnerNode, EdgeTag, TAG_BITS>;
198
199    fn next(&mut self) -> Option<Self::Item> {
200        if self.count != 0 {
201            let current = self.ptr;
202            self.ptr = {
203                let p =
204                    (self.ptr.as_ptr() as *mut u8).wrapping_offset(1 << Self::VAL_LSB) as *mut ();
205                // SAFETY: cannot be null as the `TERMINAL_BIT` is set
206                unsafe { NonNull::new_unchecked(p) }
207            };
208            self.count -= 1;
209
210            Some(unsafe { Edge::from_ptr(current) })
211        } else {
212            None
213        }
214    }
215
216    fn size_hint(&self) -> (usize, Option<usize>) {
217        (self.count, Some(self.count))
218    }
219}
220
221impl<InnerNode: NodeBase, EdgeTag: Tag, const TAG_BITS: u32> FusedIterator
222    for StaticTerminalIterator<'_, InnerNode, EdgeTag, TAG_BITS>
223{
224}
225
226impl<InnerNode: NodeBase, EdgeTag: Tag, const TAG_BITS: u32> ExactSizeIterator
227    for StaticTerminalIterator<'_, InnerNode, EdgeTag, TAG_BITS>
228{
229    fn len(&self) -> usize {
230        self.count
231    }
232}
oxidd_manager_pointer/terminal_manager/static.rs

oxidd_manager_pointer/terminal_manager/
static.rs
