syd 3.58.0

//
// Syd: rock-solid application kernel
// src/smap.rs: Sharded concurrent map
//
// Copyright (c) 2026 Ali Polatel <alip@chesswob.org>
// Based in part upon the scc crate which is:
//   Copyright (c) wvwwvwwv <wvwwvwwv@proton.me>
//   SPDX-License-Identifier: Apache-2.0
// Based in part upon the dashmap crate which is:
//   Copyright (c) 2025 Joel Wejdenstål <jwejdenstal@icloud.com>
//   SPDX-License-Identifier: MIT
//
// SPDX-License-Identifier: GPL-3.0

// SAFETY: This module has been liberated from unsafe code!
#![forbid(unsafe_code)]
// SAFETY: This module has been liberated from arithmetic side effects!
#![forbid(clippy::arithmetic_side_effects)]
#![forbid(clippy::cast_possible_truncation)]
#![forbid(clippy::cast_possible_wrap)]
#![forbid(clippy::cast_sign_loss)]

//! A sharded concurrent [`SydMap`] backed by [`SydHashMap`].

use std::{
    borrow::Borrow,
    collections::hash_map::Entry,
    hash::{BuildHasher, Hash},
    marker::PhantomData,
    sync::{RwLock, RwLockReadGuard, RwLockWriteGuard, TryLockError},
};

use nix::errno::Errno;

use crate::{
    config::{SMAP_MIN_SHRINK, SMAP_SHARDS},
    hash::{SydHashMap, SydRandomState},
};

type Shard<K, V> = RwLock<SydHashMap<K, V>>;

// Reclaim bucket memory from an over-provisioned shard, keeping 2x headroom.
// SydHashMap only grows, so removals must shrink it or the peak is retained.
fn maybe_shrink<K: Eq + Hash, V>(map: &mut SydHashMap<K, V>) {
    let len = map.len();
    if map.capacity() > SMAP_MIN_SHRINK && len.saturating_mul(4) < map.capacity() {
        map.shrink_to(len.saturating_mul(2));
    }
}

/// Result of a [`SydMap::try_replace_sync`] call.
#[derive(Debug, Eq, PartialEq)]
pub enum ReplaceResult<K> {
    /// Stored key was replaced, previous key is returned.
    Replaced(K),
    /// No entry was found, key is returned.
    NotReplaced(K),
}

/// Result of a non-blocking read, mirroring `dashmap::TryResult`.
#[derive(Debug, Eq, PartialEq)]
pub enum TryResult<R> {
    /// Value was present and shard lock was obtained.
    Present(R),
    /// Shard was not locked and value was absent.
    Absent,
    /// Shard was locked.
    Locked,
}

impl<R> TryResult<R> {
    /// True if value was present.
    pub fn is_present(&self) -> bool {
        matches!(self, TryResult::Present(_))
    }

    /// True if value was absent.
    pub fn is_absent(&self) -> bool {
        matches!(self, TryResult::Absent)
    }

    /// True if shard was locked.
    pub fn is_locked(&self) -> bool {
        matches!(self, TryResult::Locked)
    }

    /// Present value, or None when absent or locked.
    pub fn try_unwrap(self) -> Option<R> {
        match self {
            TryResult::Present(r) => Some(r),
            TryResult::Absent | TryResult::Locked => None,
        }
    }
}

/// Sharded concurrent map over [`SydHashMap`].
#[derive(Debug)]
pub struct SydMap<K, V, const SHARDS: usize = SMAP_SHARDS> {
    state: SydRandomState,
    shards: [Shard<K, V>; SHARDS],
}

impl<K: Eq + Hash, V, const SHARDS: usize> Default for SydMap<K, V, SHARDS> {
    fn default() -> Self {
        const {
            assert!(
                SHARDS.is_power_of_two(),
                "SMAP_SHARDS must be a power of two"
            )
        };
        Self {
            state: SydRandomState::new(),
            shards: std::array::from_fn(|_| {
                RwLock::new(SydHashMap::with_hasher(SydRandomState::new()))
            }),
        }
    }
}

impl<K: Eq + Hash, V: PartialEq, const SHARDS: usize> PartialEq for SydMap<K, V, SHARDS> {
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        self.iter_sync(|k, v| other.read_sync(k, |_, o| o == v) == Some(true))
    }
}

/// Builder for [`SydMap`], sourcing its defaults from src/config.rs.
pub struct SydMapBuilder<K, V, const SHARDS: usize = SMAP_SHARDS> {
    capacity: usize,
    _marker: PhantomData<(K, V)>,
}

impl<K: Eq + Hash, V, const SHARDS: usize> Default for SydMapBuilder<K, V, SHARDS> {
    fn default() -> Self {
        Self {
            capacity: 0,
            _marker: PhantomData,
        }
    }
}

impl<K: Eq + Hash, V, const SHARDS: usize> SydMapBuilder<K, V, SHARDS> {
    /// Set initial minimum capacity to reserve at build time.
    pub fn capacity(mut self, capacity: usize) -> Self {
        self.capacity = capacity;
        self
    }

    /// Build map, reserving configured capacity.
    pub fn build(self) -> Result<SydMap<K, V, SHARDS>, Errno> {
        let map = SydMap::default();
        map.try_reserve(self.capacity)?;
        Ok(map)
    }
}

impl<K: Eq + Hash, V, const SHARDS: usize> SydMap<K, V, SHARDS> {
    /// Shard index mask, shard count is a power of two.
    const MASK: u64 = (SHARDS as u64) - 1;

    /// Create a builder for a map.
    pub fn builder() -> SydMapBuilder<K, V, SHARDS> {
        SydMapBuilder::default()
    }

    /// Reserve given additional capacity.
    pub fn try_reserve(&self, additional: usize) -> Result<(), Errno> {
        let additional = additional.div_ceil(SHARDS);
        for shard in &self.shards {
            let mut map = shard.write().unwrap_or_else(|err| err.into_inner());
            map.try_reserve(additional).or(Err(Errno::ENOMEM))?;
        }
        Ok(())
    }

    /// Total capacity of the map.
    pub fn capacity(&self) -> usize {
        self.shards
            .iter()
            .map(|shard| {
                shard
                    .read()
                    .unwrap_or_else(|err| err.into_inner())
                    .capacity()
            })
            .sum()
    }

    fn shard<Q: ?Sized + Hash>(&self, key: &Q) -> &Shard<K, V> {
        match self.shards.get(self.bucket_index(key)) {
            Some(shard) => shard,
            None => &self.shards[0],
        }
    }

    fn read_shard<Q: ?Sized + Hash>(&self, key: &Q) -> RwLockReadGuard<'_, SydHashMap<K, V>> {
        self.shard(key)
            .read()
            .unwrap_or_else(|err| err.into_inner())
    }

    fn write_shard<Q: ?Sized + Hash>(&self, key: &Q) -> RwLockWriteGuard<'_, SydHashMap<K, V>> {
        self.shard(key)
            .write()
            .unwrap_or_else(|err| err.into_inner())
    }

    /// Shard index of given key.
    pub fn bucket_index<Q: ?Sized + Hash>(&self, key: &Q) -> usize {
        usize::try_from(self.state.hash_one(key) & Self::MASK).unwrap_or(0)
    }

    /// Insert a key-value pair, returning `Errno::EEXIST` if already occupied.
    pub fn try_insert_sync(&self, key: K, val: V) -> Result<(), Errno> {
        let mut map = self.write_shard(&key);
        if map.contains_key(&key) {
            return Err(Errno::EEXIST);
        }
        map.try_reserve(1).or(Err(Errno::ENOMEM))?;
        map.insert(key, val);
        Ok(())
    }

    /// Insert or replace a key-value pair, returning old value.
    pub fn try_upsert_sync(&self, key: K, val: V) -> Result<Option<V>, Errno> {
        let mut map = self.write_shard(&key);
        map.try_reserve(1).or(Err(Errno::ENOMEM))?;
        Ok(map.insert(key, val))
    }

    /// Replace stored key of an existing entry with given equal key.
    pub fn try_replace_sync(&self, key: K) -> Result<ReplaceResult<K>, Errno> {
        let mut map = self.write_shard(&key);
        map.try_reserve(1).or(Err(Errno::ENOMEM))?;
        if let Some((old, val)) = map.remove_entry(&key) {
            map.insert(key, val);
            Ok(ReplaceResult::Replaced(old))
        } else {
            Ok(ReplaceResult::NotReplaced(key))
        }
    }

    /// Run closure on entry for the key, capacity for one insert is reserved.
    pub fn try_entry_sync<R>(
        &self,
        key: K,
        f: impl FnOnce(Entry<'_, K, V>) -> R,
    ) -> Result<R, Errno> {
        let mut map = self.write_shard(&key);
        map.try_reserve(1).or(Err(Errno::ENOMEM))?;
        Ok(f(map.entry(key)))
    }

    /// Non-blocking [`Self::try_entry_sync`], None if shard lock is contended.
    pub fn try_entry<R>(
        &self,
        key: K,
        f: impl FnOnce(Entry<'_, K, V>) -> R,
    ) -> Result<Option<R>, Errno> {
        let mut map = match self.shard(&key).try_write() {
            Ok(map) => map,
            Err(TryLockError::Poisoned(err)) => err.into_inner(),
            Err(TryLockError::WouldBlock) => return Ok(None),
        };
        map.try_reserve(1).or(Err(Errno::ENOMEM))?;
        Ok(Some(f(map.entry(key))))
    }

    /// Run closure on a shared reference to the value, if any.
    pub fn read_sync<Q, R>(&self, key: &Q, f: impl FnOnce(&K, &V) -> R) -> Option<R>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let map = self.read_shard(key);
        map.get_key_value(key).map(|(k, v)| f(k, v))
    }

    /// Non-blocking [`Self::read_sync`], Locked if shard lock is contended.
    pub fn try_read_sync<Q, R>(&self, key: &Q, f: impl FnOnce(&K, &V) -> R) -> TryResult<R>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let map = match self.shard(key).try_read() {
            Ok(map) => map,
            Err(TryLockError::Poisoned(err)) => err.into_inner(),
            Err(TryLockError::WouldBlock) => return TryResult::Locked,
        };
        match map.get_key_value(key) {
            Some((k, v)) => TryResult::Present(f(k, v)),
            None => TryResult::Absent,
        }
    }

    /// Run closure on a mutable reference to the value, if any.
    pub fn update_sync<Q, R>(&self, key: &Q, f: impl FnOnce(&Q, &mut V) -> R) -> Option<R>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let mut map = self.write_shard(key);
        map.get_mut(key).map(|v| f(key, v))
    }

    /// Non-blocking [`Self::update_sync`], Locked if shard lock is contended.
    pub fn try_update_sync<Q, R>(&self, key: &Q, f: impl FnOnce(&Q, &mut V) -> R) -> TryResult<R>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let mut map = match self.shard(key).try_write() {
            Ok(map) => map,
            Err(TryLockError::Poisoned(err)) => err.into_inner(),
            Err(TryLockError::WouldBlock) => return TryResult::Locked,
        };
        match map.get_mut(key) {
            Some(v) => TryResult::Present(f(key, v)),
            None => TryResult::Absent,
        }
    }

    /// Remove and return the entry for the key, if any.
    pub fn remove_sync<Q>(&self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let mut map = self.write_shard(key);
        let removed = map.remove_entry(key);
        if removed.is_some() {
            maybe_shrink(&mut map);
        }
        removed
    }

    /// Remove the entry when the closure on the shared value returns true.
    pub fn remove_if_sync<Q>(&self, key: &Q, f: impl FnOnce(&K, &V) -> bool) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let mut map = self.write_shard(key);
        if map.get_key_value(key).map(|(k, v)| f(k, v)) == Some(true) {
            let removed = map.remove_entry(key);
            maybe_shrink(&mut map);
            removed
        } else {
            None
        }
    }

    /// Remove the entry when the closure on the mutable value returns true.
    pub fn remove_if_mut_sync<Q>(&self, key: &Q, f: impl FnOnce(&mut V) -> bool) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let mut map = self.write_shard(key);
        if map.get_mut(key).map(f) == Some(true) {
            let removed = map.remove_entry(key);
            maybe_shrink(&mut map);
            removed
        } else {
            None
        }
    }

    /// Keep only the entries for which the closure returns true.
    pub fn retain_sync(&self, mut f: impl FnMut(&K, &mut V) -> bool) {
        for shard in &self.shards {
            let mut map = shard.write().unwrap_or_else(|err| err.into_inner());
            map.retain(|k, v| f(k, v));
            maybe_shrink(&mut map);
        }
    }

    /// Remove all entries and reclaim capacity.
    pub fn clear_sync(&self) {
        for shard in &self.shards {
            let mut map = shard.write().unwrap_or_else(|err| err.into_inner());
            map.clear();
            map.shrink_to_fit();
        }
    }

    /// Reclaim excess capacity across all shards.
    pub fn shrink_to_fit(&self) {
        for shard in &self.shards {
            let mut map = shard.write().unwrap_or_else(|err| err.into_inner());
            map.shrink_to_fit();
        }
    }

    /// Visit entries until the closure returns false, true if fully iterated.
    pub fn iter_sync(&self, mut f: impl FnMut(&K, &V) -> bool) -> bool {
        for shard in &self.shards {
            let map = shard.read().unwrap_or_else(|err| err.into_inner());
            for (k, v) in map.iter() {
                if !f(k, v) {
                    return false;
                }
            }
        }
        true
    }

    /// Visit entries mutably until the closure returns false, true if fully iterated.
    pub fn iter_mut_sync(&self, mut f: impl FnMut(&K, &mut V) -> bool) -> bool {
        for shard in &self.shards {
            let mut map = shard.write().unwrap_or_else(|err| err.into_inner());
            for (k, v) in map.iter_mut() {
                if !f(k, v) {
                    return false;
                }
            }
        }
        true
    }

    /// True if the closure returns true for any entry.
    pub fn any_sync(&self, mut pred: impl FnMut(&K, &V) -> bool) -> bool {
        !self.iter_sync(|k, v| !pred(k, v))
    }

    /// True if the map contains the key.
    pub fn contains_sync<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        let map = self.read_shard(key);
        map.contains_key(key)
    }

    /// Number of entries in the map.
    pub fn len(&self) -> usize {
        self.shards
            .iter()
            .map(|shard| shard.read().unwrap_or_else(|err| err.into_inner()).len())
            .sum()
    }

    /// True if the map is empty.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Create a new map from an iterator of key-value pairs.
    pub fn try_from_iter(iter: impl IntoIterator<Item = (K, V)>) -> Result<Self, Errno> {
        let map = Self::default();
        for (key, val) in iter {
            let _ = map.try_upsert_sync(key, val)?;
        }
        Ok(map)
    }
}

impl<K: Eq + Hash + Clone, V: Clone, const SHARDS: usize> SydMap<K, V, SHARDS> {
    /// Create a deep copy of the map.
    pub fn try_clone(&self) -> Result<Self, Errno> {
        let map = Self::default();
        let mut errno = None;
        self.iter_sync(|k, v| {
            if let Err(err) = map.try_upsert_sync(k.clone(), v.clone()) {
                errno = Some(err);
                return false;
            }
            true
        });
        match errno {
            Some(errno) => Err(errno),
            None => Ok(map),
        }
    }
}

#[cfg(test)]
mod tests {
    use std::{
        hash::Hasher,
        sync::{
            atomic::{AtomicUsize, Ordering},
            Arc,
        },
        thread,
    };

    use super::*;

    #[derive(Debug)]
    struct MaybeEq(u64, u64);

    impl Eq for MaybeEq {}

    impl Hash for MaybeEq {
        fn hash<H: Hasher>(&self, state: &mut H) {
            self.0.hash(state);
        }
    }

    impl PartialEq for MaybeEq {
        fn eq(&self, other: &Self) -> bool {
            self.0 == other.0
        }
    }

    struct R(Arc<AtomicUsize>);

    impl R {
        fn new(cnt: &Arc<AtomicUsize>) -> R {
            cnt.fetch_add(1, Ordering::Relaxed);
            R(Arc::clone(cnt))
        }
    }

    impl Clone for R {
        fn clone(&self) -> Self {
            self.0.fetch_add(1, Ordering::Relaxed);
            R(Arc::clone(&self.0))
        }
    }

    impl Drop for R {
        fn drop(&mut self) {
            self.0.fetch_sub(1, Ordering::Relaxed);
        }
    }

    #[test]
    fn test_new_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_default_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert!(map.is_empty());
    }

    #[test]
    fn test_try_with_capacity_1() {
        let map: SydMap<u64, u64> = SydMap::builder().capacity(1024).build().unwrap_or_default();
        assert!(map.capacity() >= 1024);
        assert!(map.is_empty());
    }

    #[test]
    fn test_try_reserve_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_reserve(1024), Ok(()));
        assert!(map.capacity() >= 1024);
    }

    #[test]
    fn test_capacity_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..1024 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        assert!(map.capacity() >= 1024);
    }

    #[test]
    fn test_bucket_index_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..1024_u64 {
            assert!(map.bucket_index(&i) < SMAP_SHARDS);
            assert_eq!(map.bucket_index(&i), map.bucket_index(&i));
        }
    }

    #[test]
    fn test_try_insert_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
    }

    #[test]
    fn test_try_insert_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.try_insert_sync(1, 11), Err(Errno::EEXIST));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
    }

    #[test]
    fn test_try_upsert_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_upsert_sync(1, 10), Ok(None));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
    }

    #[test]
    fn test_try_upsert_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_upsert_sync(1, 10), Ok(None));
        assert_eq!(map.try_upsert_sync(1, 11), Ok(Some(10)));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(11));
    }

    #[test]
    fn test_try_replace_sync_1() {
        let map: SydMap<MaybeEq, u64> = SydMap::default();
        assert_eq!(
            map.try_replace_sync(MaybeEq(1, 7)),
            Ok(ReplaceResult::NotReplaced(MaybeEq(1, 7)))
        );
        assert!(map.is_empty());
    }

    #[test]
    fn test_try_replace_sync_2() {
        let map: SydMap<MaybeEq, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(MaybeEq(1, 7), 10), Ok(()));
        let result = map.try_replace_sync(MaybeEq(1, 11));
        assert!(matches!(result, Ok(ReplaceResult::Replaced(MaybeEq(1, 7)))));
        assert_eq!(
            map.read_sync(&MaybeEq(1, 0), |k, v| (k.1, *v)),
            Some((11, 10))
        );
    }

    #[test]
    fn test_try_entry_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        let vacant = map.try_entry_sync(1, |e| match e {
            Entry::Occupied(_) => false,
            Entry::Vacant(v) => {
                v.insert(10);
                true
            }
        });
        assert_eq!(vacant, Ok(true));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
    }

    #[test]
    fn test_try_entry_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        let occupied = map.try_entry_sync(1, |e| match e {
            Entry::Occupied(mut o) => {
                *o.get_mut() = 11;
                true
            }
            Entry::Vacant(_) => false,
        });
        assert_eq!(occupied, Ok(true));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(11));
    }

    #[test]
    fn test_try_entry_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        let vacant = map.try_entry(1, |e| match e {
            Entry::Occupied(_) => false,
            Entry::Vacant(v) => {
                v.insert(10);
                true
            }
        });
        assert_eq!(vacant, Ok(Some(true)));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
    }

    #[test]
    fn test_try_entry_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        let contended = map.update_sync(&1, |_, _| map.try_entry(1, |_| ()));
        assert_eq!(contended, Some(Ok(None)));
    }

    #[test]
    fn test_read_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.read_sync(&1, |_, v| *v), None);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.read_sync(&1, |k, v| k.saturating_add(*v)), Some(11));
    }

    #[test]
    fn test_read_sync_2() {
        let map: SydMap<String, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(String::from("k"), 10), Ok(()));
        assert_eq!(map.read_sync("k", |_, v| *v), Some(10));
        assert_eq!(map.read_sync("o", |_, v| *v), None);
    }

    #[test]
    fn test_update_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.update_sync(&1, |_, v| *v), None);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(
            map.update_sync(&1, |_, v| std::mem::replace(v, 11)),
            Some(10)
        );
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(11));
    }

    #[test]
    fn test_remove_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.remove_sync(&1), None);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.remove_sync(&1), Some((1, 10)));
        assert_eq!(map.read_sync(&1, |_, v| *v), None);
    }

    #[test]
    fn test_remove_if_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.remove_if_sync(&1, |_, _| true), None);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.remove_if_sync(&1, |_, v| *v == 0), None);
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
        assert_eq!(
            map.remove_if_sync(&1, |k, v| *k == 1 && *v == 10),
            Some((1, 10))
        );
        assert_eq!(map.read_sync(&1, |_, v| *v), None);
    }

    #[test]
    fn test_remove_if_mut_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.remove_if_mut_sync(&1, |_| true), None);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.remove_if_mut_sync(&1, |v| *v == 0), None);
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(10));
        assert_eq!(map.remove_if_mut_sync(&1, |v| *v == 10), Some((1, 10)));
        assert_eq!(map.read_sync(&1, |_, v| *v), None);
    }

    #[test]
    fn test_remove_if_mut_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(
            map.remove_if_mut_sync(&1, |v| {
                *v = 0;
                false
            }),
            None
        );
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(0));
    }

    #[test]
    fn test_retain_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        map.retain_sync(|k, _| k % 2 == 0);
        assert_eq!(map.len(), 50);
        assert!(map.contains_sync(&2));
        assert!(!map.contains_sync(&3));
    }

    #[test]
    fn test_clear_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        map.clear_sync();
        assert!(map.is_empty());
        assert!(!map.contains_sync(&0));
    }

    #[test]
    fn test_clear_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let peak = map.capacity();
        map.clear_sync();
        assert!(map.capacity() < peak / 100);
    }

    #[test]
    fn test_remove_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let peak = map.capacity();
        for i in 0..100000 {
            assert_eq!(map.remove_sync(&i), Some((i, i)));
        }
        assert!(map.is_empty());
        assert!(map.capacity() < peak / 100);
    }

    #[test]
    fn test_retain_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let peak = map.capacity();
        map.retain_sync(|_, _| false);
        assert!(map.is_empty());
        assert!(map.capacity() < peak / 100);
    }

    #[test]
    fn test_remove_if_mut_sync_3() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let peak = map.capacity();
        for i in 0..100000 {
            assert_eq!(map.remove_if_mut_sync(&i, |_| true), Some((i, i)));
        }
        assert!(map.capacity() < peak / 100);
    }

    #[test]
    fn test_shrink_to_fit_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        map.retain_sync(|k, _| *k < 4);
        map.clear_sync();
        for i in 0..100000 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let peak = map.capacity();
        map.retain_sync(|_, _| false);
        map.shrink_to_fit();
        assert!(map.capacity() < peak / 100);
    }

    #[test]
    fn test_try_reserve_2() {
        let map: SydMap<i32, i32> = SydMap::default();
        assert_eq!(map.try_reserve(usize::MAX), Err(Errno::ENOMEM));
    }

    #[test]
    fn test_try_read_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_read_sync(&1, |_, v| *v), TryResult::Absent);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(map.try_read_sync(&1, |_, v| *v), TryResult::Present(10));
    }

    #[test]
    fn test_try_read_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        let locked = map.update_sync(&1, |_, _| map.try_read_sync(&1, |_, v| *v));
        assert_eq!(locked, Some(TryResult::Locked));
    }

    #[test]
    fn test_try_update_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_update_sync(&1, |_, v| *v), TryResult::Absent);
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert_eq!(
            map.try_update_sync(&1, |_, v| std::mem::replace(v, 11)),
            TryResult::Present(10)
        );
        assert_eq!(map.read_sync(&1, |_, v| *v), Some(11));
    }

    #[test]
    fn test_try_update_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        let locked = map.read_sync(&1, |_, _| map.try_update_sync(&1, |_, v| *v));
        assert_eq!(locked, Some(TryResult::Locked));
    }

    #[test]
    fn test_try_result_1() {
        let present: TryResult<u64> = TryResult::Present(7);
        assert!(present.is_present());
        assert_eq!(present.try_unwrap(), Some(7));
        assert!(TryResult::<u64>::Absent.is_absent());
        assert_eq!(TryResult::<u64>::Absent.try_unwrap(), None);
        assert!(TryResult::<u64>::Locked.is_locked());
        assert_eq!(TryResult::<u64>::Locked.try_unwrap(), None);
    }

    #[test]
    fn test_multiple_hashes_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(
                map.try_upsert_sync(0, i),
                Ok(if i == 0 { None } else { Some(i - 1) })
            );
            assert!(map.try_upsert_sync(i, i).is_ok());
        }
        for i in 1..100 {
            assert_eq!(map.read_sync(&i, |k, v| (*k, *v)), Some((i, i)));
        }
        assert_eq!(map.read_sync(&0, |_, v| *v), Some(99));
    }

    #[test]
    fn test_iter_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let mut count: u64 = 0;
        assert!(map.iter_sync(|_, _| {
            count = count.saturating_add(1);
            true
        }));
        assert_eq!(count, 100);
    }

    #[test]
    fn test_iter_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let mut count: u64 = 0;
        assert!(!map.iter_sync(|_, _| {
            count = count.saturating_add(1);
            false
        }));
        assert_eq!(count, 1);
    }

    #[test]
    fn test_iter_mut_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        assert!(map.iter_mut_sync(|_, v| {
            *v = v.saturating_add(1);
            true
        }));
        assert_eq!(map.read_sync(&0, |_, v| *v), Some(1));
        assert_eq!(map.read_sync(&99, |_, v| *v), Some(100));
    }

    #[test]
    fn test_iter_mut_sync_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let mut count: u64 = 0;
        assert!(!map.iter_mut_sync(|_, _| {
            count = count.saturating_add(1);
            false
        }));
        assert_eq!(count, 1);
    }

    #[test]
    fn test_any_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert!(!map.any_sync(|_, _| true));
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        assert!(map.any_sync(|k, _| *k == 50));
        assert!(!map.any_sync(|k, _| *k == 100));
    }

    #[test]
    fn test_contains_sync_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert!(!map.contains_sync(&1));
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert!(map.contains_sync(&1));
    }

    #[test]
    fn test_len_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.len(), 0);
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        assert_eq!(map.len(), 100);
    }

    #[test]
    fn test_is_empty_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        assert!(map.is_empty());
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert!(!map.is_empty());
    }

    #[test]
    fn test_try_from_iter_1() {
        let map: SydMap<u64, u64> =
            SydMap::try_from_iter((0_u64..100).map(|i| (i, i))).unwrap_or_default();
        assert_eq!(map.len(), 100);
        assert_eq!(map.read_sync(&99, |_, v| *v), Some(99));
    }

    #[test]
    fn test_try_clone_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
        }
        let dup = map.try_clone().unwrap_or_default();
        assert_eq!(dup.len(), 100);
        assert_eq!(dup.remove_sync(&0), Some((0, 0)));
        assert!(map.contains_sync(&0));
    }

    #[test]
    fn test_try_clone_2() {
        let cnt = Arc::new(AtomicUsize::new(0));
        let map: SydMap<u64, R> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, R::new(&cnt)), Ok(()));
        }
        assert_eq!(cnt.load(Ordering::Relaxed), 100);
        let dup = map.try_clone().map_err(|_| ()).map(|m| m.len());
        assert_eq!(dup, Ok(100));
        assert_eq!(cnt.load(Ordering::Relaxed), 100);
        drop(map);
        assert_eq!(cnt.load(Ordering::Relaxed), 0);
    }

    #[test]
    fn test_partial_eq_1() {
        let map: SydMap<u64, u64> = SydMap::default();
        let dup: SydMap<u64, u64> = SydMap::default();
        assert!(map == dup);
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, i), Ok(()));
            assert_eq!(dup.try_insert_sync(i, i), Ok(()));
        }
        assert!(map == dup);
    }

    #[test]
    fn test_partial_eq_2() {
        let map: SydMap<u64, u64> = SydMap::default();
        let dup: SydMap<u64, u64> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, 10), Ok(()));
        assert!(map != dup);
        assert_eq!(dup.try_insert_sync(1, 11), Ok(()));
        assert!(map != dup);
    }

    #[test]
    fn test_sydmap_1() {
        let map: Arc<SydMap<u64, u64>> = Arc::new(SydMap::default());
        let handles: Vec<_> = (0u64..8)
            .map(|t| {
                let map = Arc::clone(&map);
                thread::Builder::new()
                    .name(format!("test_sydmap_1_{t}"))
                    .spawn(move || {
                        for i in 0..100 {
                            let key = t.saturating_mul(100).saturating_add(i);
                            assert_eq!(map.try_insert_sync(key, key), Ok(()));
                        }
                    })
                    .ok()
            })
            .collect();
        for h in handles.into_iter().flatten() {
            let _ = h.join();
        }
        assert_eq!(map.len(), 800);
        for i in 0..800 {
            assert!(map.contains_sync(&i));
        }
    }

    #[test]
    fn test_sydmap_2() {
        let cnt = Arc::new(AtomicUsize::new(0));
        let map: SydMap<u64, R> = SydMap::default();
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, R::new(&cnt)), Ok(()));
        }
        assert_eq!(cnt.load(Ordering::Relaxed), 100);
        assert!(map.remove_sync(&0).is_some());
        assert_eq!(cnt.load(Ordering::Relaxed), 99);
        map.retain_sync(|k, _| k % 2 == 0);
        assert_eq!(cnt.load(Ordering::Relaxed), 49);
        map.clear_sync();
        assert_eq!(cnt.load(Ordering::Relaxed), 0);
        for i in 0..100 {
            assert_eq!(map.try_insert_sync(i, R::new(&cnt)), Ok(()));
        }
        drop(map);
        assert_eq!(cnt.load(Ordering::Relaxed), 0);
    }

    #[test]
    fn test_sydmap_3() {
        let map: Arc<SydMap<u64, u64>> = Arc::new(SydMap::default());
        let handles: Vec<_> = (0u64..4)
            .map(|t| {
                let map = Arc::clone(&map);
                thread::Builder::new()
                    .name(format!("test_sydmap_3_{t}"))
                    .spawn(move || {
                        for i in 0..256 {
                            let key = t.saturating_mul(256).saturating_add(i);
                            assert_eq!(map.try_insert_sync(key, key), Ok(()));
                            assert_eq!(map.read_sync(&key, |_, v| *v), Some(key));
                            assert_eq!(map.update_sync(&key, |_, v| *v), Some(key));
                            assert_eq!(map.remove_sync(&key), Some((key, key)));
                        }
                    })
                    .ok()
            })
            .collect();
        for h in handles.into_iter().flatten() {
            let _ = h.join();
        }
        assert!(map.is_empty());
    }

    #[test]
    fn test_sydmap_4() {
        let val = String::from("v");
        let map: SydMap<u64, &str> = SydMap::default();
        assert_eq!(map.try_insert_sync(1, &val), Ok(()));
        assert_eq!(map.read_sync(&1, |_, v| *v), Some("v"));
        drop(map);
        drop(val);
    }
}