Skip to main content

assembly_hashmap/
lib.rs

1//! Single-threaded `u64 → u64` hashmap with x86-64 assembly operations.
2//!
3//! Growth and allocation live in Rust. Lookup, insert variants, remove, clear,
4//! and iteration are implemented in `native/hashmap.S` on x86-64, or in a C
5//! reference of the same algorithm elsewhere.
6//!
7//! ```
8//! use assembly_hashmap::AssemblyHashMap;
9//!
10//! let mut map = AssemblyHashMap::new();
11//! map.put(1, 10);
12//! assert_eq!(map.get(1), Some(10));
13//! ```
14
15use 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/// Allocation failed while constructing or growing the map.
83#[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
94/// Auto-growing `u64 -> u64` map backed by fixed-capacity native tables.
95///
96/// The map owns its allocation. It is deliberately `!Send` and `!Sync` because
97/// the underlying implementation is specified as single-threaded.
98pub struct AssemblyHashMap {
99    raw: NonNull<RawHashMap>,
100    _single_threaded: PhantomData<Rc<()>>,
101}
102
103impl AssemblyHashMap {
104    /// Empty map with the smallest native table.
105    pub fn new() -> Self {
106        Self::with_capacity(0).expect("empty assembly hashmap allocation failed")
107    }
108
109    /// Allocates a map able to hold at least `minimum_capacity` live entries.
110    pub fn with_capacity(minimum_capacity: usize) -> Result<Self, AllocError> {
111        // SAFETY: `hm_create` has no Rust-side preconditions.
112        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        // SAFETY: `self.raw` remains valid until `Drop`.
121        unsafe { hm_len(self.raw.as_ptr()) }
122    }
123
124    pub fn capacity(&self) -> usize {
125        // SAFETY: `self.raw` remains valid until `Drop`.
126        unsafe { hm_capacity(self.raw.as_ptr()) }
127    }
128
129    pub fn is_empty(&self) -> bool {
130        self.len() == 0
131    }
132
133    /// Equivalent to `std::collections::HashMap::get(key).copied()`.
134    pub fn get(&self, key: u64) -> Option<u64> {
135        // SAFETY: the pointer is valid and immutable access does not mutate it.
136        unsafe { hm_get(self.raw.as_ptr(), key) }.option()
137    }
138
139    pub fn contains_key(&self, key: u64) -> bool {
140        // SAFETY: the pointer is valid and this operation does not mutate it.
141        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            // SAFETY: `&mut self` gives exclusive access to the live map.
156            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                        // Tombstones exhausted growth: rebuild at the same size.
164                        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        // Insert directly: a fresh table sized for at least all current live
178        // entries cannot request another rebuild during migration.
179        for (key, value) in self.iter() {
180            // SAFETY: replacement owns a distinct live table.
181            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    /// Ensures space for at least `additional` more elements.
195    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    /// Equivalent to `HashMap::insert`, growing in Rust when necessary.
204    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    /// Equivalent to `HashMap::insert`; panics if native allocation fails.
209    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    /// Inserts only when absent, using one native probe.
215    ///
216    /// Returns the existing value when no insertion occurred.
217    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    /// Returns the current value, inserting `value` with one probe if absent.
223    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    /// Replaces an existing value without inserting a missing key.
230    pub fn replace(&mut self, key: u64, value: u64) -> Option<u64> {
231        // SAFETY: `&mut self` gives exclusive access; replace cannot fill.
232        unsafe { hm_replace(self.raw.as_ptr(), key, value) }.option()
233    }
234
235    pub fn remove(&mut self, key: u64) -> Option<u64> {
236        // SAFETY: `&mut self` gives exclusive access to the live map.
237        unsafe { hm_remove(self.raw.as_ptr(), key) }.option()
238    }
239
240    pub fn clear(&mut self) {
241        // SAFETY: `&mut self` gives exclusive access to the live map.
242        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        // SAFETY: all output pointers are valid, and the immutable borrow keeps
265        // the table alive and prevents mutation for this iterator's lifetime.
266        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        // SAFETY: this is the sole owning pointer and `Drop` runs once.
291        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
305/// True when this build links `native/hashmap.S`; false means it uses the
306/// non-x86-64 C reference operations.
307pub const USING_ASSEMBLY: bool = cfg!(target_arch = "x86_64");