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")
}
}
}
}
#[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 {}
pub struct AssemblyHashMap {
raw: NonNull<RawHashMap>,
_single_threaded: PhantomData<Rc<()>>,
}
impl AssemblyHashMap {
pub fn new() -> Self {
Self::with_capacity(0).expect("empty assembly hashmap allocation failed")
}
pub fn with_capacity(minimum_capacity: usize) -> Result<Self, AllocError> {
let raw = NonNull::new(unsafe { hm_create(minimum_capacity) }).ok_or(AllocError)?;
Ok(Self {
raw,
_single_threaded: PhantomData,
})
}
pub fn len(&self) -> usize {
unsafe { hm_len(self.raw.as_ptr()) }
}
pub fn capacity(&self) -> usize {
unsafe { hm_capacity(self.raw.as_ptr()) }
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn get(&self, key: u64) -> Option<u64> {
unsafe { hm_get(self.raw.as_ptr(), key) }.option()
}
pub fn contains_key(&self, key: u64) -> bool {
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 {
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 {
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)?;
for (key, value) in self.iter() {
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(())
}
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(())
}
pub fn try_put(&mut self, key: u64, value: u64) -> Result<Option<u64>, AllocError> {
self.try_native_insert(hm_put, key, value)
}
pub fn put(&mut self, key: u64, value: u64) -> Option<u64> {
self.try_put(key, value)
.expect("failed to grow assembly hashmap")
}
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")
}
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)
}
pub fn replace(&mut self, key: u64, value: u64) -> Option<u64> {
unsafe { hm_replace(self.raw.as_ptr(), key, value) }.option()
}
pub fn remove(&mut self, key: u64) -> Option<u64> {
unsafe { hm_remove(self.raw.as_ptr(), key) }.option()
}
pub fn clear(&mut self) {
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;
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) {
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()
}
}
pub const USING_ASSEMBLY: bool = cfg!(target_arch = "x86_64");