commonlibsse_ng\re\b\BSTHashMap/
entry.rs

1use core::marker::PhantomData;
2use core::num::NonZeroUsize;
3use core::ptr::NonNull;
4
5/// Used as a sentinel value(a special value indicating the end of a table) used within a table
6const SENTINEL_ADDRESS: usize = 0xdeadbeef;
7
8/// Sentinel-aware unique pointer
9#[derive(Debug)]
10#[repr(transparent)]
11pub struct SentinelPtr<T: ?Sized> {
12    ptr: NonNull<T>,
13}
14
15impl<T: ?Sized> Copy for SentinelPtr<T> {}
16impl<T: ?Sized> Clone for SentinelPtr<T> {
17    #[inline]
18    fn clone(&self) -> Self {
19        *self
20    }
21}
22
23impl<T> Default for SentinelPtr<T> {
24    #[inline]
25    fn default() -> Self {
26        Self::sentinel()
27    }
28}
29
30impl<T: ?Sized> PartialEq for SentinelPtr<T> {
31    fn eq(&self, other: &Self) -> bool {
32        core::ptr::addr_eq(self.ptr.as_ptr(), other.ptr.as_ptr())
33    }
34}
35
36impl<T> SentinelPtr<T> {
37    /// Create sentinel ptr
38    #[inline]
39    pub const fn sentinel() -> Self {
40        let ptr = core::ptr::without_provenance_mut(SENTINEL_ADDRESS);
41        Self { ptr: unsafe { NonNull::new_unchecked(ptr) } }
42    }
43}
44
45impl<T: ?Sized> SentinelPtr<T> {
46    /// Create from NonNull
47    pub const fn new(ptr: *mut T) -> Option<Self> {
48        match NonNull::new(ptr) {
49            Some(ptr) => Some(Self { ptr }),
50            None => None,
51        }
52    }
53
54    pub const fn from_non_null(ptr: NonNull<T>) -> Self {
55        Self { ptr }
56    }
57
58    /// Is this a sentinel?
59    pub fn is_sentinel(&self) -> bool {
60        self.ptr.addr() == unsafe { NonZeroUsize::new_unchecked(SENTINEL_ADDRESS) }
61    }
62
63    /// Returns Some(ptr) if not sentinel
64    pub fn as_unique(&self) -> Option<NonNull<T>> {
65        if self.is_sentinel() { None } else { Some(self.ptr) }
66    }
67
68    /// Adds an offset to the pointer
69    ///
70    /// # Safety
71    /// Caller must ensure pointer arithmetic is valid
72    pub const unsafe fn add(self, offset: usize) -> Self
73    where
74        T: Sized,
75    {
76        Self { ptr: unsafe { self.ptr.add(offset) } }
77    }
78
79    #[inline]
80    pub const fn as_ptr(&self) -> *mut T {
81        self.ptr.as_ptr()
82    }
83
84    #[inline]
85    pub const fn as_non_null(&self) -> NonNull<T> {
86        self.ptr
87    }
88
89    /// Returns the reference
90    ///
91    /// Return `None` if this is a sentinel address.
92    ///
93    /// # Safety
94    /// Caller must ensure this is not a sentinel
95    pub unsafe fn as_non_sentinel_ref<'a>(&self) -> Option<&'a T> {
96        if self.is_sentinel() {
97            return None;
98        }
99
100        unsafe { Some(self.ptr.as_ref()) }
101    }
102
103    /// Returns the mutable reference
104    ///
105    /// Return `None` if this is a sentinel address.
106    /// # Safety
107    /// Caller must ensure this is not a sentinel
108    pub unsafe fn as_non_sentinel_mut<'a>(&mut self) -> Option<&'a mut T> {
109        if self.is_sentinel() {
110            return None;
111        }
112
113        unsafe { Some(self.ptr.as_mut()) }
114    }
115
116    /// Returns reference regardless of sentinel. Use with care.
117    ///
118    /// # Safety
119    /// - May cause UB if this is a sentinel.
120    #[inline]
121    pub const unsafe fn as_ref<'a>(&self) -> &'a T {
122        unsafe { self.ptr.as_ref() }
123    }
124
125    /// Returns mutable reference regardless of sentinel. Use with care.
126    ///
127    /// # Safety
128    /// - May cause UB if this is a sentinel.
129    #[inline]
130    pub const unsafe fn as_mut<'a>(&mut self) -> &'a mut T {
131        unsafe { self.ptr.as_mut() }
132    }
133
134    pub fn addr(&self) -> NonZeroUsize {
135        self.ptr.addr()
136    }
137}
138
139impl<T> SentinelPtr<[T]> {
140    /// Returns the length of the slice
141    pub const fn len(&self) -> usize {
142        self.ptr.len()
143    }
144
145    #[inline]
146    pub const fn slice_from_raw_parts(data: NonNull<T>, len: usize) -> Self {
147        Self { ptr: NonNull::slice_from_raw_parts(data, len) }
148    }
149}
150
151impl<T: ?Sized> From<&T> for SentinelPtr<T> {
152    /// Converts a `&T` to a `NonNull<T>`.
153    ///
154    /// This conversion is safe and infallible since references cannot be null.
155    #[inline]
156    fn from(r: &T) -> Self {
157        Self { ptr: NonNull::from(r) }
158    }
159}
160
161/// Data storage unidirectional linked list of hashmaps formed on the heap or stack.
162///
163/// There is a possibility that this storage may always be zero
164/// because of the timing of the zero initialization when the `reserve` method of the hashmap is called.
165///
166/// Therefore, use [`Option`].
167#[repr(C)]
168#[derive(Debug)]
169pub struct EntryType<Pair> {
170    /// key, value pair
171    pub(super) value_data: Pair,
172    pub(super) next: Option<SentinelPtr<EntryType<Pair>>>,
173}
174const _: () = {
175    // To avoid memory access violations, the smallest type (e.g., u8) other than the zero size
176    // type must be larger than the sentinel size (4 bytes). or larger.
177    const SIZE: usize = core::mem::size_of::<EntryType<u8>>();
178    assert!(SIZE == 0x10);
179};
180
181impl<Pair> EntryType<Pair> where Pair: Default {}
182
183impl<Pair> Default for EntryType<Pair> {
184    fn default() -> Self {
185        unsafe { core::mem::zeroed() }
186    }
187}
188
189impl<Pair> EntryType<Pair> {
190    /// Return `true` if already occupied.
191    ///
192    /// C++: `has_value`
193    ///
194    /// # How do we know if it's occupied by looking at the next pointer?
195    ///
196    /// The assumption is that `alloc_zeroed` is used.
197    /// In this case, whether `has_next` is a null pointer or exists can be used to determine if it has been pushed or not.
198    /// Since next is chained or a sentinel pointer is inserted at the time of `push`, the presence of a null pointer automatically proves that it is empty.
199    #[inline]
200    pub const fn is_occupied(&self) -> bool {
201        self.next.is_some()
202    }
203
204    #[inline]
205    pub fn destroy(&mut self) {
206        if self.next.take().is_some() {
207            unsafe { core::ptr::drop_in_place(&mut self.value_data) };
208        }
209        debug_assert!(!self.is_occupied());
210    }
211
212    /// Set value_data & next
213    #[inline]
214    pub fn push(&mut self, value: Pair, next: Option<SentinelPtr<Self>>) {
215        self.destroy();
216        self.value_data = value;
217        self.next = next;
218        debug_assert!(self.is_occupied());
219    }
220
221    #[inline]
222    pub const fn steal(&mut self) -> Option<Pair> {
223        Some(core::mem::replace(&mut self.value_data, unsafe { core::mem::zeroed() }))
224    }
225
226    #[inline]
227    pub fn iter(&self) -> Iter<'_, Pair> {
228        Iter { current: Some(SentinelPtr::from(self)), _marker: PhantomData }
229    }
230}
231
232#[derive(Debug)]
233pub struct Iter<'a, Pair> {
234    pub(crate) current: Option<SentinelPtr<EntryType<Pair>>>,
235    _marker: PhantomData<&'a Pair>,
236}
237
238impl<Pair> Iter<'_, Pair> {
239    #[inline]
240    pub const fn new(current: Option<SentinelPtr<EntryType<Pair>>>) -> Self {
241        Self { current, _marker: PhantomData }
242    }
243}
244
245impl<'a, Pair> Iterator for Iter<'a, Pair> {
246    type Item = &'a EntryType<Pair>;
247
248    fn next(&mut self) -> Option<Self::Item> {
249        let current_ptr = self.current?;
250        let current_ref = unsafe { current_ptr.as_non_sentinel_ref()? };
251        self.current = current_ref.next;
252        Some(current_ref)
253    }
254}
255
256impl<'a, Pair> IntoIterator for &'a EntryType<Pair> {
257    type Item = &'a EntryType<Pair>;
258    type IntoIter = Iter<'a, Pair>;
259
260    fn into_iter(self) -> Self::IntoIter {
261        Iter { current: Some(SentinelPtr::from(self)), _marker: PhantomData }
262    }
263}
commonlibsse_ng\re\b\BSTHashMap/entry.rs

commonlibsse_ng\re\b\BSTHashMap/
entry.rs
