use std::collections::BTreeMap;
use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Barrier};
use std::time::{Duration, Instant};
use artmap::{ArenaVersionedArtMap, ArtMap, VersionedArtMap};
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
fn budget() -> Duration {
if cfg!(miri) {
return Duration::from_millis(1);
}
let ms = std::env::var("ARTMAP_STRESS_MS")
.ok()
.and_then(|s| s.parse().ok())
.unwrap_or(300);
Duration::from_millis(ms)
}
fn threads() -> usize {
if cfg!(miri) {
2
} else {
4
}
}
fn run<F>(n: usize, f: F)
where
F: Fn(usize, &AtomicBool) + Send + Sync + 'static,
{
let f = Arc::new(f);
let stop = Arc::new(AtomicBool::new(false));
let barrier = Arc::new(Barrier::new(n + 1));
let handles: Vec<_> = (0..n)
.map(|t| {
let (f, stop, barrier) = (Arc::clone(&f), Arc::clone(&stop), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
f(t, &stop);
})
})
.collect();
barrier.wait();
let start = Instant::now();
while start.elapsed() < budget() {
std::thread::sleep(Duration::from_millis(1));
}
stop.store(true, Ordering::Relaxed);
for h in handles {
h.join().unwrap();
}
}
fn key(i: u64) -> [u8; 8] {
i.to_be_bytes()
}
#[test]
fn overwrite_never_hides_the_key() {
let map = Arc::new(ArtMap::<[u8; 8], u64>::new());
for i in 0..64 {
map.insert(key(i), i);
}
let m = Arc::clone(&map);
run(threads(), move |t, stop| {
let mut i = 0u64;
while !stop.load(Ordering::Relaxed) {
i += 1;
if t == 0 {
let old = m.insert(key(i % 64), i);
assert!(old.is_some(), "an overwrite always displaces an entry");
} else {
let k = key(i % 64);
assert!(m.get(&k).is_some(), "get never misses an overwritten key");
assert!(m.contains_key(&k));
assert_eq!(m.range(k..=k).count(), 1, "a point range sees the key");
}
}
});
assert_eq!(map.len(), 64);
}
#[test]
fn sentinels_survive_churn_in_scans() {
const N: u64 = 512;
let map = Arc::new(ArtMap::<[u8; 8], u64>::new());
for i in (0..N).step_by(2) {
map.insert(key(i), i);
}
let m = Arc::clone(&map);
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
while !stop.load(Ordering::Relaxed) {
if t % 2 == 0 {
let k = rng.gen_range(0..N) | 1;
if rng.gen() {
m.insert(key(k), k);
} else {
m.remove(&key(k));
}
} else {
let fwd: Vec<u64> = m
.iter()
.map(|e| u64::from_be_bytes(*e.key()))
.filter(|k| k % 2 == 0)
.collect();
assert_eq!(fwd.len() as u64, N / 2, "every sentinel exactly once");
assert!(fwd.windows(2).all(|w| w[0] < w[1]), "in order");
let rev: Vec<u64> = m
.iter()
.rev()
.map(|e| u64::from_be_bytes(*e.key()))
.filter(|k| k % 2 == 0)
.collect();
assert_eq!(
rev.len() as u64,
N / 2,
"every sentinel exactly once, reversed"
);
let lo = rng.gen_range(0..N / 2) * 2;
let got = m
.range(key(lo)..key(lo + 64))
.filter(|e| u64::from_be_bytes(*e.key()) % 2 == 0)
.count();
assert_eq!(
got as u64,
32.min((N - lo) / 2),
"range sees every sentinel"
);
}
}
});
}
#[test]
fn partitioned_oracle() {
let n = threads();
let map = Arc::new(ArtMap::<Vec<u8>, u64>::new());
let m = Arc::clone(&map);
let totals = Arc::new(AtomicUsize::new(0));
let tot = Arc::clone(&totals);
run(n, move |t, stop| {
let mut rng = StdRng::seed_from_u64(100 + t as u64);
let mut model = BTreeMap::new();
while !stop.load(Ordering::Relaxed) {
let id = rng.gen_range(0..200u64) * n as u64 + t as u64;
let k = format!("p:{}:{id}", id % 7).into_bytes();
match rng.gen_range(0..3) {
0 => {
let v = rng.gen();
assert_eq!(m.insert(k.clone(), v).map(|e| *e), model.insert(k, v));
}
1 => assert_eq!(m.remove(&k).map(|e| *e), model.remove(&k)),
_ => assert_eq!(m.get(&k).map(|e| *e), model.get(&k).copied()),
}
}
tot.fetch_add(model.len(), Ordering::Relaxed);
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), totals.load(Ordering::Relaxed));
map.validate_invariants();
}
#[test]
fn fresh_inserts_and_removes_are_exact_during_prefix_splits() {
let map = Arc::new(ArtMap::<Vec<u8>, u64>::new());
let m = Arc::clone(&map);
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
let k1 = b"abcdefgh:0".to_vec();
let mut i = 0u64;
while !stop.load(Ordering::Relaxed) {
i += 1;
if t == 0 {
assert!(
m.insert(k1.clone(), i).is_none(),
"fresh insert returned Some"
);
assert!(m.get(&k1).is_some(), "own key missing");
assert!(m.remove(&k1).is_some(), "remove of own key returned None");
} else {
let cut = rng.gen_range(1..9);
let mut k = b"abcdefgh".to_vec();
k.truncate(cut);
k.push(rng.gen_range(b'x'..=b'z'));
k.push(t as u8);
if rng.gen() {
m.insert(k, i);
} else {
m.remove(&k);
}
}
}
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), map.iter().count());
map.validate_invariants();
}
fn compaction_family(group: u8) -> (Vec<Vec<u8>>, Vec<Vec<u8>>) {
let chain = |tag: u8, last: u8| {
let mut k = vec![group, tag];
k.extend_from_slice(&[b'-'; 30]);
k.push(last);
k
};
let sentinels = vec![
vec![group, b'a', b's'],
vec![group, b'b', b'x', b'1'],
vec![group, b'b', b'x', b'2'],
chain(b'c', 1),
vec![group, b'f', 0xFF],
];
let mut churn = vec![
vec![group, b'a', b'c'],
vec![group, b'b', b'y'],
chain(b'c', 2),
chain(b'e', 1),
chain(b'e', 2),
];
churn.extend((0..6).map(|i| vec![group, b'd', i]));
churn.extend((0..40).map(|i| vec![group, b'f', i]));
(sentinels, churn)
}
#[test]
fn compaction_churn_never_hides_a_sentinel() {
const GROUPS: u8 = 6;
let map = Arc::new(ArtMap::<Vec<u8>, u64>::new());
let mut sentinels = Vec::new();
let mut churn = Vec::new();
for g in 0..GROUPS {
let (s, c) = compaction_family(g);
sentinels.extend(s);
churn.extend(c);
}
sentinels.sort();
for k in sentinels.iter().chain(&churn) {
map.insert(k.clone(), 0);
}
let (sentinels, churn) = (Arc::new(sentinels), Arc::new(churn));
let m = Arc::clone(&map);
let s = Arc::clone(&sentinels);
let n = threads();
run(n + 1, move |t, stop| {
let mut rng = StdRng::seed_from_u64(700 + t as u64);
let is_sentinel = |k: &Vec<u8>| s.binary_search(k).is_ok();
while !stop.load(Ordering::Relaxed) {
if t == n {
m.shrink_to_fit();
} else if t % 2 == 0 {
let k = &churn[rng.gen_range(0..churn.len())];
if rng.gen() {
m.insert(k.clone(), 1);
} else {
m.remove(k);
}
} else {
for k in s.iter() {
assert!(m.get(k).is_some(), "sentinel {k:?} missed by get");
}
let fwd: Vec<Vec<u8>> = m
.iter()
.map(|e| e.key().clone())
.filter(is_sentinel)
.collect();
assert_eq!(&fwd, &*s, "every sentinel exactly once, in order");
let mut rev: Vec<Vec<u8>> = m
.iter()
.rev()
.map(|e| e.key().clone())
.filter(is_sentinel)
.collect();
rev.reverse();
assert_eq!(&rev, &*s, "every sentinel exactly once, reversed");
let g = rng.gen_range(0..GROUPS);
let got = m
.range(vec![g]..vec![g + 1])
.filter(|e| is_sentinel(e.key()))
.count();
assert_eq!(got, 5, "a group's range sees its sentinels");
}
}
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), map.iter().count());
map.validate_invariants();
map.shrink_to_fit();
map.validate_invariants();
}
#[test]
fn sliding_windows_on_every_thread_stay_compact() {
let n = threads();
let map = Arc::new(ArtMap::<Vec<u8>, u64>::new());
let m = Arc::clone(&map);
let totals = Arc::new(AtomicUsize::new(0));
let tot = Arc::clone(&totals);
run(n, move |t, stop| {
let window = 1 + 17 * t as u64;
let k = |i: u64| {
let mut k = format!("queue:{t}:").into_bytes();
k.extend_from_slice(&i.to_be_bytes());
k
};
let mut i = 0u64;
while !stop.load(Ordering::Relaxed) {
assert!(m.insert(k(i), i).is_none());
if i >= window {
assert_eq!(m.remove(&k(i - window)).map(|e| *e), Some(i - window));
}
assert_eq!(m.get(&k(i)).map(|e| *e), Some(i));
i += 1;
}
tot.fetch_add(i.min(window) as usize, Ordering::Relaxed);
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), totals.load(Ordering::Relaxed));
map.validate_invariants();
}
#[test]
fn clear_against_writers_keeps_len_exact() {
let map = Arc::new(ArtMap::<[u8; 8], u64>::new());
let m = Arc::clone(&map);
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
while !stop.load(Ordering::Relaxed) {
if t == 0 {
m.clear();
assert!(m.len() < 1 << 40, "len never wraps");
} else {
let k = rng.gen_range(0..2048u64);
if rng.gen_ratio(2, 3) {
m.insert(key(k), k);
} else {
m.remove(&key(k));
}
}
}
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), map.iter().count(), "len is exact at quiescence");
map.validate_invariants();
}
#[test]
fn node256_inserters_and_updater() {
for _round in 0..if cfg!(miri) { 1 } else { 20 } {
let map = Arc::new(ArtMap::<Vec<u8>, u64>::new());
for b in 0..64u8 {
map.insert(vec![b], 0);
}
let n = threads();
let barrier = Arc::new(Barrier::new(n));
let handles: Vec<_> = (0..n)
.map(|t| {
let (m, barrier) = (Arc::clone(&map), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
if t == 0 {
for i in 0..512u64 {
m.insert(vec![(i % 64) as u8], i);
}
} else {
for b in (64..=255u8).filter(|b| (*b as usize) % (n - 1) == t - 1) {
assert!(m.insert(vec![b], 1).is_none(), "fresh key returned Some");
assert!(m.insert(vec![b, 1], 1).is_none());
}
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), 256 + 192);
for b in 0..=255u8 {
assert!(map.get(&vec![b]).is_some(), "key {b} lost");
}
map.validate_invariants();
}
}
#[test]
fn shared_first_byte_node256_inserts() {
let map = Arc::new(ArtMap::<[u8; 2], u64>::new());
let n = if cfg!(miri) { 2 } else { 8 };
let barrier = Arc::new(Barrier::new(n));
let handles: Vec<_> = (0..n)
.map(|t| {
let (m, barrier) = (Arc::clone(&map), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
let per = if cfg!(miri) { 4 } else { 64 };
for b0 in 0..per as u8 {
for b1 in (t..256).step_by(n) {
assert!(m.insert([b0, b1 as u8], 1).is_none());
}
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
let mut map = Arc::try_unwrap(map).ok().unwrap();
let per = if cfg!(miri) { 4 } else { 64 };
assert_eq!(map.len(), per * 256);
assert_eq!(map.iter().count(), per * 256);
map.validate_invariants();
}
#[test]
fn handle_outlives_concurrent_remove() {
let map = Arc::new(ArtMap::<String, String>::new());
map.insert("k".into(), "a value that owns heap memory".into());
let e = map.get("k").unwrap();
let m = Arc::clone(&map);
std::thread::spawn(move || {
assert!(m.remove("k").is_some());
for _ in 0..if cfg!(miri) { 64 } else { 4096 } {
let _ = m.get("other");
}
})
.join()
.unwrap();
assert!(e.is_removed());
assert_eq!(e.value(), "a value that owns heap memory");
assert!(!e.remove());
}
#[test]
fn versioned_concurrent_versions_of_one_key() {
let map = Arc::new(VersionedArtMap::<[u8; 8], u64>::new());
let n = threads() as u64;
let per = if cfg!(miri) { 8 } else { 400 };
let barrier = Arc::new(Barrier::new(n as usize));
let handles: Vec<_> = (0..n)
.map(|t| {
let (m, barrier) = (Arc::clone(&map), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
let mut rng = StdRng::seed_from_u64(t);
let mut versions: Vec<u64> = (0..per).map(|i| i * n + t + 1).collect();
for i in (1..versions.len()).rev() {
versions.swap(i, rng.gen_range(0..=i));
}
for v in versions {
for k in 0..4 {
m.insert(key(k), v, v);
if v % 5 == 0 {
m.insert(key(k), v, v); }
}
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
for k in 0..4 {
let all = map.get_all_versions(&key(k));
assert_eq!(all.len() as u64, per * n, "no version lost or duplicated");
assert!(
all.windows(2).all(|w| w[0].0 > w[1].0),
"newest first, strictly"
);
assert!(all.iter().all(|(v, x)| *x == Some(*v)));
}
assert_eq!(map.len(), 4);
}
#[test]
fn versioned_prune_against_inserts_and_prunes() {
let map = Arc::new(VersionedArtMap::<[u8; 8], u64>::new());
let next = Arc::new(AtomicU64::new(1));
let m = Arc::clone(&map);
let nx = Arc::clone(&next);
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
while !stop.load(Ordering::Relaxed) {
let k = key(rng.gen_range(0..8));
match t % 3 {
0 => {
let v = nx.fetch_add(1, Ordering::Relaxed);
m.insert(k, v, v);
}
1 => {
let v = nx.fetch_add(1, Ordering::Relaxed);
m.delete(k, v);
}
_ => {
let min = nx
.load(Ordering::Relaxed)
.saturating_sub(rng.gen_range(0..50));
m.prune_key(&k, min, |_| false);
if let Some((v, x)) = m.get_version_le(&k, u64::MAX) {
assert_eq!(v, x);
}
}
}
}
});
let mut live = 0;
for k in 0..8 {
let all = map.get_all_versions(&key(k));
assert!(all.windows(2).all(|w| w[0].0 > w[1].0));
if all.first().is_some_and(|(_, x)| x.is_some()) {
live += 1;
}
}
assert_eq!(map.len(), live);
}
#[test]
fn versioned_len_under_remove_and_reinsert() {
let map = Arc::new(VersionedArtMap::<[u8; 8], u64>::new());
let next = Arc::new(AtomicU64::new(1));
let (m, nx) = (Arc::clone(&map), Arc::clone(&next));
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
while !stop.load(Ordering::Relaxed) {
let k = key(rng.gen_range(0..4));
let v = nx.fetch_add(1, Ordering::Relaxed);
if rng.gen() {
m.insert(k, v, v);
} else {
#[allow(deprecated)]
let _ = m.remove(&k);
}
std::hint::black_box(m.len());
}
});
let live = (0..4).filter(|k| map.get(&key(*k)).is_some()).count();
assert_eq!(map.len(), live);
}
#[test]
fn arena_versioned_concurrent_versions_of_one_key() {
let map = Arc::new(ArenaVersionedArtMap::<[u8; 8], u64>::with_capacity(
64 << 20,
));
let n = threads() as u64;
let per = if cfg!(miri) { 8 } else { 400 };
let barrier = Arc::new(Barrier::new(n as usize));
let handles: Vec<_> = (0..n)
.map(|t| {
let (m, barrier) = (Arc::clone(&map), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
let mut rng = StdRng::seed_from_u64(t);
let mut versions: Vec<u64> = (0..per).map(|i| i * n + t + 1).collect();
for i in (1..versions.len()).rev() {
versions.swap(i, rng.gen_range(0..=i));
}
for v in versions {
for k in 0..4 {
m.insert(key(k), v, v);
if v % 5 == 0 {
m.insert(key(k), v, v); }
}
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
for k in 0..4 {
let all = map.get_all_versions(&key(k));
assert_eq!(all.len() as u64, per * n, "no version lost or duplicated");
assert!(
all.windows(2).all(|w| w[0].0 > w[1].0),
"newest first, strictly"
);
assert!(all.iter().all(|(v, x)| *x == Some(*v)));
}
assert_eq!(map.len(), 4);
}
#[test]
fn arena_versioned_len_under_delete_and_reinsert() {
const CAP: u64 = 400_000;
let map = Arc::new(ArenaVersionedArtMap::<[u8; 8], u64>::with_capacity(
128 << 20,
));
let next = Arc::new(AtomicU64::new(1));
let (m, nx) = (Arc::clone(&map), Arc::clone(&next));
run(threads(), move |t, stop| {
let mut rng = StdRng::seed_from_u64(t as u64);
while !stop.load(Ordering::Relaxed) {
let v = nx.fetch_add(1, Ordering::Relaxed);
if v > CAP {
break;
}
let k = key(rng.gen_range(0..4));
if rng.gen() {
m.insert(k, v, v);
} else {
m.delete(k, v);
}
std::hint::black_box(m.len());
}
});
let mut live = 0;
for k in 0..4 {
let all = map.get_all_versions(&key(k));
assert!(
all.windows(2).all(|w| w[0].0 > w[1].0),
"chains stay sorted"
);
if all.first().is_some_and(|(_, x)| x.is_some()) {
live += 1;
}
}
assert_eq!(map.len(), live);
assert_eq!(map.iter().count(), live);
}
type Chain = BTreeMap<u64, Option<u64>>;
fn model_prune(model: &mut BTreeMap<Vec<u8>, Chain>, k: &[u8], min: u64) -> usize {
let Some(chain) = model.get_mut(k) else {
return 0;
};
let Some((&t, &tv)) = chain.range(..=min).next_back() else {
return 0;
};
if chain.keys().next_back() == Some(&t) && tv.is_none() {
let n = chain.len();
model.remove(k);
return n;
}
let older: Vec<u64> = chain.range(..t).map(|(&v, _)| v).collect();
for v in &older {
chain.remove(v);
}
older.len()
}
macro_rules! versioned_oracle {
($name:ident, $map:ty, $new:expr, $max_ops:expr) => {
#[test]
fn $name() {
let n = threads();
let map = Arc::new($new);
let sentinels: Vec<Vec<u8>> = (0..8).map(|i| format!("v:{i}").into_bytes()).collect();
for s in &sentinels {
map.insert(s.clone(), 1, 1);
}
let m = Arc::clone(&map);
let totals = Arc::new(AtomicUsize::new(0));
let tot = Arc::clone(&totals);
run(n + 1, move |t, stop| {
if t == n {
while !stop.load(Ordering::Relaxed) {
for s in &sentinels {
assert_eq!(m.get(&s[..]), Some(1), "sentinel {s:?} missed");
}
let seen: Vec<Vec<u8>> = m
.iter()
.map(|e| e.key().clone())
.filter(|k| sentinels.contains(k))
.collect();
assert_eq!(seen, sentinels, "every sentinel once, in order");
}
return;
}
let mut rng = StdRng::seed_from_u64(900 + t as u64);
let mut model: BTreeMap<Vec<u8>, Chain> = BTreeMap::new();
let mut version = 0u64;
while !stop.load(Ordering::Relaxed) && version < $max_ops {
version += 1;
let id = rng.gen_range(0..48u64) * n as u64 + t as u64;
let k = format!("v:{}:{id}", id % 5).into_bytes();
match rng.gen_range(0..7) {
0 | 1 => {
m.insert(k.clone(), version, version);
model
.entry(k.clone())
.or_default()
.insert(version, Some(version));
}
2 => {
m.delete(k.clone(), version);
model.entry(k.clone()).or_default().insert(version, None);
}
3 => assert_eq!(m.remove_key(&k[..]), model.remove(&k).is_some()),
4 => {
let v = model
.get(&k)
.and_then(|c| {
let vs: Vec<u64> = c.keys().copied().collect();
vs.get(rng.gen_range(0..vs.len() + 1)).copied()
})
.unwrap_or(version);
let want = model.get_mut(&k).is_some_and(|c| c.remove(&v).is_some());
if model.get(&k).is_some_and(|c| c.is_empty()) {
model.remove(&k);
}
assert_eq!(m.remove_version(&k[..], v), want, "remove_version {v}");
}
_ => {
let min = version.saturating_sub(rng.gen_range(0..20));
let want = model_prune(&mut model, &k, min);
assert_eq!(m.prune_key(&k[..], min, |_| false), want, "prune at {min}");
}
}
let want: Vec<(u64, Option<u64>)> = model
.get(&k)
.map(|c| c.iter().rev().map(|(&v, &x)| (v, x)).collect())
.unwrap_or_default();
assert_eq!(m.get_all_versions(&k[..]), want, "versions of {k:?}");
}
let live = model
.values()
.filter(|c| c.values().next_back().is_some_and(|x| x.is_some()))
.count();
tot.fetch_add(live, Ordering::Relaxed);
});
let mut map = Arc::try_unwrap(map).ok().unwrap();
assert_eq!(map.len(), totals.load(Ordering::Relaxed) + 8);
map.validate_invariants();
}
};
}
versioned_oracle!(
versioned_oracle_with_removes_and_prunes,
VersionedArtMap<Vec<u8>, u64>,
VersionedArtMap::<Vec<u8>, u64>::new(),
u64::MAX
);
versioned_oracle!(
arena_versioned_oracle_with_removes_and_prunes,
ArenaVersionedArtMap<Vec<u8>, u64>,
ArenaVersionedArtMap::<Vec<u8>, u64>::with_capacity(64 << 20),
40_000
);