assembly-hashmap 0.1.0

A single-threaded u64→u64 hashmap with x86-64 assembly operations and Rust-side growth.
Documentation
//! Single-threaded `u64 → u64` hashmap with x86-64 assembly operations.
//!
//! Growth and allocation live in Rust. Lookup, insert variants, remove, clear,
//! and iteration are implemented in `native/hashmap.S` on x86-64, or in a C
//! reference of the same algorithm elsewhere.
//!
//! ```
//! use assembly_hashmap::AssemblyHashMap;
//!
//! let mut map = AssemblyHashMap::new();
//! map.put(1, 10);
//! assert_eq!(map.get(1), Some(10));
//! ```

use std::fmt;
use std::marker::PhantomData;
use std::ptr::NonNull;
use std::rc::Rc;

#[repr(C)]
struct RawHashMap {
    _private: [u8; 0],
}

#[repr(C)]
#[derive(Clone, Copy)]
struct RawOption {
    status: u64,
    value: u64,
}

type NativeInsert = unsafe extern "C" fn(*mut RawHashMap, u64, u64) -> RawOption;

unsafe extern "C" {
    fn hm_create(min_items: usize) -> *mut RawHashMap;
    fn hm_destroy(map: *mut RawHashMap);
    fn hm_len(map: *const RawHashMap) -> usize;
    fn hm_capacity(map: *const RawHashMap) -> usize;
    fn hm_put(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
    fn hm_put_if_absent(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
    fn hm_get_or_insert(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
    fn hm_replace(map: *mut RawHashMap, key: u64, value: u64) -> RawOption;
    fn hm_get(map: *const RawHashMap, key: u64) -> RawOption;
    fn hm_remove(map: *mut RawHashMap, key: u64) -> RawOption;
    fn hm_contains(map: *const RawHashMap, key: u64) -> u64;
    fn hm_clear(map: *mut RawHashMap);
    fn hm_iter_next(
        map: *const RawHashMap,
        cursor: *mut usize,
        key: *mut u64,
        value: *mut u64,
    ) -> u64;
}

enum NativeOutcome {
    Absent,
    Present(u64),
    Rebuild,
}

impl RawOption {
    fn outcome(self) -> NativeOutcome {
        match self.status {
            0 => NativeOutcome::Absent,
            1 => NativeOutcome::Present(self.value),
            2 => NativeOutcome::Rebuild,
            other => panic!("assembly hashmap returned invalid status {other}"),
        }
    }

    fn option(self) -> Option<u64> {
        match self.outcome() {
            NativeOutcome::Absent => None,
            NativeOutcome::Present(value) => Some(value),
            NativeOutcome::Rebuild => {
                panic!("non-inserting assembly operation requested a rebuild")
            }
        }
    }
}

/// Allocation failed while constructing or growing the map.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct AllocError;

impl fmt::Display for AllocError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str("failed to allocate assembly hashmap")
    }
}

impl std::error::Error for AllocError {}

/// Auto-growing `u64 -> u64` map backed by fixed-capacity native tables.
///
/// The map owns its allocation. It is deliberately `!Send` and `!Sync` because
/// the underlying implementation is specified as single-threaded.
pub struct AssemblyHashMap {
    raw: NonNull<RawHashMap>,
    _single_threaded: PhantomData<Rc<()>>,
}

impl AssemblyHashMap {
    /// Empty map with the smallest native table.
    pub fn new() -> Self {
        Self::with_capacity(0).expect("empty assembly hashmap allocation failed")
    }

    /// Allocates a map able to hold at least `minimum_capacity` live entries.
    pub fn with_capacity(minimum_capacity: usize) -> Result<Self, AllocError> {
        // SAFETY: `hm_create` has no Rust-side preconditions.
        let raw = NonNull::new(unsafe { hm_create(minimum_capacity) }).ok_or(AllocError)?;
        Ok(Self {
            raw,
            _single_threaded: PhantomData,
        })
    }

    pub fn len(&self) -> usize {
        // SAFETY: `self.raw` remains valid until `Drop`.
        unsafe { hm_len(self.raw.as_ptr()) }
    }

    pub fn capacity(&self) -> usize {
        // SAFETY: `self.raw` remains valid until `Drop`.
        unsafe { hm_capacity(self.raw.as_ptr()) }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Equivalent to `std::collections::HashMap::get(key).copied()`.
    pub fn get(&self, key: u64) -> Option<u64> {
        // SAFETY: the pointer is valid and immutable access does not mutate it.
        unsafe { hm_get(self.raw.as_ptr(), key) }.option()
    }

    pub fn contains_key(&self, key: u64) -> bool {
        // SAFETY: the pointer is valid and this operation does not mutate it.
        match unsafe { hm_contains(self.raw.as_ptr(), key) } {
            0 => false,
            1 => true,
            other => panic!("assembly hashmap returned invalid boolean {other}"),
        }
    }

    fn try_native_insert(
        &mut self,
        operation: NativeInsert,
        key: u64,
        value: u64,
    ) -> Result<Option<u64>, AllocError> {
        loop {
            // SAFETY: `&mut self` gives exclusive access to the live map.
            match unsafe { operation(self.raw.as_ptr(), key, value) }.outcome() {
                NativeOutcome::Absent => return Ok(None),
                NativeOutcome::Present(previous) => return Ok(Some(previous)),
                NativeOutcome::Rebuild => {
                    let len = self.len();
                    let capacity = self.capacity();
                    let target = if len < capacity {
                        // Tombstones exhausted growth: rebuild at the same size.
                        capacity
                    } else {
                        capacity.checked_mul(2).ok_or(AllocError)?
                    };
                    self.rebuild(target)?;
                }
            }
        }
    }

    fn rebuild(&mut self, minimum_capacity: usize) -> Result<(), AllocError> {
        let replacement = Self::with_capacity(minimum_capacity)?;

        // Insert directly: a fresh table sized for at least all current live
        // entries cannot request another rebuild during migration.
        for (key, value) in self.iter() {
            // SAFETY: replacement owns a distinct live table.
            match unsafe { hm_put(replacement.raw.as_ptr(), key, value) }.outcome() {
                NativeOutcome::Absent => {}
                NativeOutcome::Present(_) | NativeOutcome::Rebuild => {
                    panic!("fresh assembly table rejected migration")
                }
            }
        }

        let mut replacement = replacement;
        std::mem::swap(self, &mut replacement);
        Ok(())
    }

    /// Ensures space for at least `additional` more elements.
    pub fn reserve(&mut self, additional: usize) -> Result<(), AllocError> {
        let required = self.len().checked_add(additional).ok_or(AllocError)?;
        if required > self.capacity() {
            self.rebuild(required)?;
        }
        Ok(())
    }

    /// Equivalent to `HashMap::insert`, growing in Rust when necessary.
    pub fn try_put(&mut self, key: u64, value: u64) -> Result<Option<u64>, AllocError> {
        self.try_native_insert(hm_put, key, value)
    }

    /// Equivalent to `HashMap::insert`; panics if native allocation fails.
    pub fn put(&mut self, key: u64, value: u64) -> Option<u64> {
        self.try_put(key, value)
            .expect("failed to grow assembly hashmap")
    }

    /// Inserts only when absent, using one native probe.
    ///
    /// Returns the existing value when no insertion occurred.
    pub fn put_if_absent(&mut self, key: u64, value: u64) -> Option<u64> {
        self.try_native_insert(hm_put_if_absent, key, value)
            .expect("failed to grow assembly hashmap")
    }

    /// Returns the current value, inserting `value` with one probe if absent.
    pub fn get_or_insert(&mut self, key: u64, value: u64) -> u64 {
        self.try_native_insert(hm_get_or_insert, key, value)
            .expect("failed to grow assembly hashmap")
            .unwrap_or(value)
    }

    /// Replaces an existing value without inserting a missing key.
    pub fn replace(&mut self, key: u64, value: u64) -> Option<u64> {
        // SAFETY: `&mut self` gives exclusive access; replace cannot fill.
        unsafe { hm_replace(self.raw.as_ptr(), key, value) }.option()
    }

    pub fn remove(&mut self, key: u64) -> Option<u64> {
        // SAFETY: `&mut self` gives exclusive access to the live map.
        unsafe { hm_remove(self.raw.as_ptr(), key) }.option()
    }

    pub fn clear(&mut self) {
        // SAFETY: `&mut self` gives exclusive access to the live map.
        unsafe { hm_clear(self.raw.as_ptr()) };
    }

    pub fn iter(&self) -> Iter<'_> {
        Iter {
            map: self,
            cursor: 0,
        }
    }
}

pub struct Iter<'a> {
    map: &'a AssemblyHashMap,
    cursor: usize,
}

impl Iterator for Iter<'_> {
    type Item = (u64, u64);

    fn next(&mut self) -> Option<Self::Item> {
        let mut key = 0;
        let mut value = 0;
        // SAFETY: all output pointers are valid, and the immutable borrow keeps
        // the table alive and prevents mutation for this iterator's lifetime.
        let present = unsafe {
            hm_iter_next(
                self.map.raw.as_ptr(),
                &mut self.cursor,
                &mut key,
                &mut value,
            )
        };
        match present {
            0 => None,
            1 => Some((key, value)),
            other => panic!("assembly iterator returned invalid boolean {other}"),
        }
    }
}

impl Default for AssemblyHashMap {
    fn default() -> Self {
        Self::new()
    }
}

impl Drop for AssemblyHashMap {
    fn drop(&mut self) {
        // SAFETY: this is the sole owning pointer and `Drop` runs once.
        unsafe { hm_destroy(self.raw.as_ptr()) };
    }
}

impl fmt::Debug for AssemblyHashMap {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter
            .debug_struct("AssemblyHashMap")
            .field("len", &self.len())
            .field("capacity", &self.capacity())
            .finish_non_exhaustive()
    }
}

/// True when this build links `native/hashmap.S`; false means it uses the
/// non-x86-64 C reference operations.
pub const USING_ASSEMBLY: bool = cfg!(target_arch = "x86_64");