arctic-map 0.1.4

#![cfg(feature = "rand")]

use core::borrow::Borrow as _;
use core::convert::Infallible;
use core::fmt::Debug;
use core::ops::Bound;
use core::ops::ControlFlow;
use std::collections::BTreeMap;
use std::thread;

use arctic::concurrent::Map;
use arctic::key::BoxedStr;
use arctic::key::NonNull;
use rand::Rng as _;
use rand::RngExt as _;
use rand::SeedableRng;

trait Orthogonal: ::arctic::Key {
    fn is_thread(key: Self::Insert<'_>, thread: u8) -> bool;
    fn mask(self, thread: u8) -> Self;
}

impl Orthogonal for u64 {
    fn is_thread(key: Self::Insert<'_>, thread: u8) -> bool {
        key as u8 == thread
    }

    fn mask(mut self, thread: u8) -> Self {
        self &= !(u8::MAX as u64);
        self |= thread as u64;
        self
    }
}

impl Orthogonal for BoxedStr<NonNull> {
    fn is_thread(key: Self::Insert<'_>, thread: u8) -> bool {
        key.as_str().as_bytes().last() == Some(&(thread + 1))
    }

    fn mask(self, thread: u8) -> Self {
        let mut string = self.into_boxed_slice().into_string();
        assert!(thread < 0b0111_1111);
        string.push((thread + 1) as char);
        unsafe { Self::new_unchecked(string.into_boxed_str()) }
    }
}

enum Op {
    Upsert,
    Update,
    Insert,
    Remove,
    Get,
    Range,
}

static OPS: &[Op] = &[
    Op::Upsert,
    Op::Update,
    Op::Insert,
    Op::Remove,
    Op::Get,
    Op::Range,
];

#[test]
fn orthogonal_u64_u64() {
    orthogonal::<u64>();
}

#[test]
fn orthogonal_boxed_str_non_null_u64() {
    orthogonal::<BoxedStr<NonNull>>();
}

// Can't cfg trait bound in where clause
#[cfg(feature = "smr-hazard")]
trait Hazard: arctic::concurrent::smr::hazard::Key {}
#[cfg(feature = "smr-hazard")]
impl<K: arctic::concurrent::smr::hazard::Key> Hazard for K {}
#[cfg(not(feature = "smr-hazard"))]
trait Hazard {}
#[cfg(not(feature = "smr-hazard"))]
impl<K> Hazard for K {}

fn orthogonal<K>()
where
    K: ::arctic::Key + Orthogonal + Debug + Ord + Clone + Hazard,
    K::Borrowed: Debug + Eq + Ord,
    rand::distr::StandardUniform: rand::distr::Distribution<K>,
{
    let map = &Map::<
        K,
        u64,
        // Can't define type alias with unused type parameters or that uses outside types
        cfg_select! {
            feature = "smr-hazard" => {
                ::arctic::concurrent::smr::Hazard::<K, u64>
            }
            feature = "smr-epoch" => {
                ::arctic::concurrent::smr::Epoch
            }
            feature = "smr-seize" => {
                ::arctic::concurrent::smr::Seize
            }
            _ => {
                ::arctic::concurrent::smr::NoOp
            }
        },
    >::new();

    let ops = &rand::distr::slice::Choose::new(OPS).unwrap();

    thread::scope(|scope| {
        for thread in 0..16 {
            scope.spawn(move || {
                let mut rng = rand::rngs::Xoshiro256PlusPlus::seed_from_u64(thread);
                let mut expected = BTreeMap::<K, u64>::new();

                for _ in 0..10_000 {
                    let key = rng.random::<K>().mask(thread as u8);

                    match rng.sample(ops) {
                        Op::Upsert => {
                            let value = rng.next_u64();
                            let upserted = map.upsert(key.as_insert(), value);
                            assert_eq!(upserted.old(), expected.insert(key.clone(), value).as_ref());
                            assert_eq!(*upserted.new(), value);
                        }
                        Op::Update => {
                            let value = rng.next_u64();
                            match map.update(key.borrow(), value) {
                                Ok(updated) => {
                                    assert_eq!(Some(updated.old()), expected.insert(key.clone(), value).as_ref());
                                    assert_eq!(*updated.new(), value);
                                }
                                Err(new) => {
                                    assert!(expected.get(key.borrow()).is_none());
                                    assert_eq!(new, value);
                                }
                            }
                        },
                        Op::Insert => {
                            let value = rng.next_u64();
                            match map.insert(key.as_insert(), value) {
                                Ok(new) => {
                                    assert!(expected.insert(key.clone(), value).is_none());
                                    assert_eq!(*new, value);
                                }
                                Err((old, new)) => {
                                    assert_eq!(Some(&*old), expected.get(key.borrow()));
                                    assert_eq!(new, value);
                                }
                            }
                        },
                        Op::Remove => {
                            assert_eq!(map.remove(key.borrow()).as_deref(), expected.remove(key.borrow()).as_ref());
                        }
                        Op::Get => {
                            assert_eq!(map.get(key.borrow()).as_deref(), expected.get(key.borrow()));
                        }
                        Op::Range => {
                            let descend = rng.random::<bool>();
                            let mut lower = rng.random::<K>();
                            let mut upper = rng.random::<K>();

                            if lower > upper {
                                core::mem::swap(&mut lower, &mut upper);
                            }

                            let actual = map.range(lower.borrow()..=upper.borrow());
                            let expected = expected.range((Bound::Included(lower.borrow()), Bound::Included(upper.borrow())));
                            let mut expected = if descend {
                                Box::new(expected.rev())
                            } else {
                                Box::new(expected) as Box<dyn Iterator<Item = _>>
                            };

                            macro_rules! compare {
                                () => {
                                    |(), (key_actual, value_actual)| {
                                        if !K::is_thread(key_actual, thread as u8) {
                                            return ControlFlow::<Infallible>::Continue(());
                                        }

                                        let key_actual = key_actual.borrow();
                                        let (key_expected, value_expected) = expected.next().unwrap();
                                        assert_eq!(
                                            key_actual,
                                            key_expected.borrow(),
                                            "actual key: {key_actual:x?}, expected key: {key_expected:x?}, lower: {lower:x?}, upper: {upper:x?}",
                                        );
                                        assert_eq!(
                                            value_actual, value_expected,
                                            "actual value: {value_actual:x?}, expected value: {value_expected:x?}",
                                        );
                                        ControlFlow::<Infallible>::Continue(())
                                    }
                                };
                            }

                            if descend {
                                actual
                                    .entries(arctic::Order::Descend)
                                    .try_fold((), compare!())
                            } else {
                                actual
                                    .entries(arctic::Order::Ascend)
                                    .try_fold((), compare!())
                            };

                            let next = expected.next();
                            assert!(next.is_none(), "Missing entry {next:?}");
                        }
                    }
                }
            });
        }
    });
}