1use std::fmt;
16use std::marker::PhantomData;
17use std::ptr::NonNull;
18use std::rc::Rc;
19
20#[repr(C)]
21struct RawHashMap {
22 _private: [u8; 0],
23}
24
25#[repr(C)]
26#[derive(Clone, Copy)]
27struct RawOption {
28 status: u64,
29 value: u64,
30}
31
32type NativeInsert = unsafe extern "C" fn(*mut RawHashMap, u64, u64) -> RawOption;
33
34unsafe extern "C" {
35 fn hm_create(min_items: usize) -> *mut RawHashMap;
36 fn hm_destroy(map: *mut RawHashMap);
37 fn hm_len(map: *const RawHashMap) -> usize;
38 fn hm_capacity(map: *const RawHashMap) -> usize;
39 fn hm_put(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
40 fn hm_put_if_absent(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
41 fn hm_get_or_insert(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
42 fn hm_replace(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
43 fn hm_get(map: *const RawHashMap, key: u64) -> RawOption;
44 fn hm_remove(map: *mut RawHashMap, key: u64) -> RawOption;
45 fn hm_contains(map: *const RawHashMap, key: u64) -> u64;
46 fn hm_clear(map: *mut RawHashMap);
47 fn hm_iter_next(
48 map: *const RawHashMap,
49 cursor: *mut usize,
50 key: *mut u64,
51 value: *mut u64,
52 ) -> u64;
53}
54
55enum NativeOutcome {
56 Absent,
57 Present(u64),
58 Rebuild,
59}
60
61impl RawOption {
62 fn outcome(self) -> NativeOutcome {
63 match self.status {
64 0 => NativeOutcome::Absent,
65 1 => NativeOutcome::Present(self.value),
66 2 => NativeOutcome::Rebuild,
67 other => panic!("assembly hashmap returned invalid status {other}"),
68 }
69 }
70
71 fn option(self) -> Option<u64> {
72 match self.outcome() {
73 NativeOutcome::Absent => None,
74 NativeOutcome::Present(value) => Some(value),
75 NativeOutcome::Rebuild => {
76 panic!("non-inserting assembly operation requested a rebuild")
77 }
78 }
79 }
80}
81
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub struct AllocError;
85
86impl fmt::Display for AllocError {
87 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
88 formatter.write_str("failed to allocate assembly hashmap")
89 }
90}
91
92impl std::error::Error for AllocError {}
93
94pub struct AssemblyHashMap {
99 raw: NonNull<RawHashMap>,
100 _single_threaded: PhantomData<Rc<()>>,
101}
102
103impl AssemblyHashMap {
104 pub fn new() -> Self {
106 Self::with_capacity(0).expect("empty assembly hashmap allocation failed")
107 }
108
109 pub fn with_capacity(minimum_capacity: usize) -> Result<Self, AllocError> {
111 let raw = NonNull::new(unsafe { hm_create(minimum_capacity) }).ok_or(AllocError)?;
113 Ok(Self {
114 raw,
115 _single_threaded: PhantomData,
116 })
117 }
118
119 pub fn len(&self) -> usize {
120 unsafe { hm_len(self.raw.as_ptr()) }
122 }
123
124 pub fn capacity(&self) -> usize {
125 unsafe { hm_capacity(self.raw.as_ptr()) }
127 }
128
129 pub fn is_empty(&self) -> bool {
130 self.len() == 0
131 }
132
133 pub fn get(&self, key: u64) -> Option<u64> {
135 unsafe { hm_get(self.raw.as_ptr(), key) }.option()
137 }
138
139 pub fn contains_key(&self, key: u64) -> bool {
140 match unsafe { hm_contains(self.raw.as_ptr(), key) } {
142 0 => false,
143 1 => true,
144 other => panic!("assembly hashmap returned invalid boolean {other}"),
145 }
146 }
147
148 fn try_native_insert(
149 &mut self,
150 operation: NativeInsert,
151 key: u64,
152 value: u64,
153 ) -> Result<Option<u64>, AllocError> {
154 loop {
155 match unsafe { operation(self.raw.as_ptr(), key, value) }.outcome() {
157 NativeOutcome::Absent => return Ok(None),
158 NativeOutcome::Present(previous) => return Ok(Some(previous)),
159 NativeOutcome::Rebuild => {
160 let len = self.len();
161 let capacity = self.capacity();
162 let target = if len < capacity {
163 capacity
165 } else {
166 capacity.checked_mul(2).ok_or(AllocError)?
167 };
168 self.rebuild(target)?;
169 }
170 }
171 }
172 }
173
174 fn rebuild(&mut self, minimum_capacity: usize) -> Result<(), AllocError> {
175 let replacement = Self::with_capacity(minimum_capacity)?;
176
177 for (key, value) in self.iter() {
180 match unsafe { hm_put(replacement.raw.as_ptr(), key, value) }.outcome() {
182 NativeOutcome::Absent => {}
183 NativeOutcome::Present(_) | NativeOutcome::Rebuild => {
184 panic!("fresh assembly table rejected migration")
185 }
186 }
187 }
188
189 let mut replacement = replacement;
190 std::mem::swap(self, &mut replacement);
191 Ok(())
192 }
193
194 pub fn reserve(&mut self, additional: usize) -> Result<(), AllocError> {
196 let required = self.len().checked_add(additional).ok_or(AllocError)?;
197 if required > self.capacity() {
198 self.rebuild(required)?;
199 }
200 Ok(())
201 }
202
203 pub fn try_put(&mut self, key: u64, value: u64) -> Result<Option<u64>, AllocError> {
205 self.try_native_insert(hm_put, key, value)
206 }
207
208 pub fn put(&mut self, key: u64, value: u64) -> Option<u64> {
210 self.try_put(key, value)
211 .expect("failed to grow assembly hashmap")
212 }
213
214 pub fn put_if_absent(&mut self, key: u64, value: u64) -> Option<u64> {
218 self.try_native_insert(hm_put_if_absent, key, value)
219 .expect("failed to grow assembly hashmap")
220 }
221
222 pub fn get_or_insert(&mut self, key: u64, value: u64) -> u64 {
224 self.try_native_insert(hm_get_or_insert, key, value)
225 .expect("failed to grow assembly hashmap")
226 .unwrap_or(value)
227 }
228
229 pub fn replace(&mut self, key: u64, value: u64) -> Option<u64> {
231 unsafe { hm_replace(self.raw.as_ptr(), key, value) }.option()
233 }
234
235 pub fn remove(&mut self, key: u64) -> Option<u64> {
236 unsafe { hm_remove(self.raw.as_ptr(), key) }.option()
238 }
239
240 pub fn clear(&mut self) {
241 unsafe { hm_clear(self.raw.as_ptr()) };
243 }
244
245 pub fn iter(&self) -> Iter<'_> {
246 Iter {
247 map: self,
248 cursor: 0,
249 }
250 }
251}
252
253pub struct Iter<'a> {
254 map: &'a AssemblyHashMap,
255 cursor: usize,
256}
257
258impl Iterator for Iter<'_> {
259 type Item = (u64, u64);
260
261 fn next(&mut self) -> Option<Self::Item> {
262 let mut key = 0;
263 let mut value = 0;
264 let present = unsafe {
267 hm_iter_next(
268 self.map.raw.as_ptr(),
269 &mut self.cursor,
270 &mut key,
271 &mut value,
272 )
273 };
274 match present {
275 0 => None,
276 1 => Some((key, value)),
277 other => panic!("assembly iterator returned invalid boolean {other}"),
278 }
279 }
280}
281
282impl Default for AssemblyHashMap {
283 fn default() -> Self {
284 Self::new()
285 }
286}
287
288impl Drop for AssemblyHashMap {
289 fn drop(&mut self) {
290 unsafe { hm_destroy(self.raw.as_ptr()) };
292 }
293}
294
295impl fmt::Debug for AssemblyHashMap {
296 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
297 formatter
298 .debug_struct("AssemblyHashMap")
299 .field("len", &self.len())
300 .field("capacity", &self.capacity())
301 .finish_non_exhaustive()
302 }
303}
304
305pub const USING_ASSEMBLY: bool = cfg!(target_arch = "x86_64");