use std::{borrow::Borrow, fmt, iter::FromIterator, ops::RangeBounds};
use crate::{
handle::{EntryMut, EntryRef},
iter::{Iter, Keys, Range, Values},
node::Tree,
};
pub const DEFAULT_PAGE_CAPACITY: usize = 32;
pub struct BLinkMap<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
pub(crate) tree: Tree<K, V, N>,
}
impl<K, V, const N: usize> BLinkMap<K, V, N> {
pub fn new() -> Self {
Self { tree: Tree::new() }
}
pub fn len(&self) -> usize {
self.tree.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn clear(&mut self) {
self.tree = Tree::new();
}
}
impl<K: Ord, V, const N: usize> BLinkMap<K, V, N> {
pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
let (guard, index) = self.tree.get(key)?;
Some(EntryRef::new(guard, index))
}
pub fn get_key_value<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
self.get(key)
}
pub fn get_mut<Q>(&self, key: &Q) -> Option<EntryMut<'_, K, V, N>>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
let (guard, index) = self.tree.get_mut(key)?;
Some(EntryMut::new(guard, index))
}
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
self.get(key).is_some()
}
pub fn insert(&self, key: K, value: V) -> Option<V> {
self.tree.insert(key, value)
}
pub fn remove<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
self.tree.remove(key)
}
pub fn first_key_value(&self) -> Option<EntryRef<'_, K, V, N>> {
let (guard, index) = self.tree.first_entry()?;
Some(EntryRef::new(guard, index))
}
pub fn last_key_value(&self) -> Option<EntryRef<'_, K, V, N>> {
let (guard, index) = self.tree.last_entry()?;
Some(EntryRef::new(guard, index))
}
pub fn iter(&self) -> Iter<'_, K, V, N> {
Iter::new(self)
}
pub fn keys(&self) -> Keys<'_, K, V, N> {
Keys::new(self)
}
pub fn values(&self) -> Values<'_, K, V, N> {
Values::new(self)
}
pub fn range<Q, R>(&self, bounds: R) -> Range<'_, K, V, Q, R, N>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
R: RangeBounds<Q>,
{
Range::new(self, bounds)
}
#[cfg(test)]
pub(crate) fn assert_valid(&self) {
if let Err(error) = self.tree.validate() {
panic!("B-link tree invariant violated: {error}");
}
}
#[cfg(test)]
fn height(&self) -> usize {
self.tree.height()
}
}
impl<K, V, const N: usize> Default for BLinkMap<K, V, N> {
fn default() -> Self {
Self::new()
}
}
impl<K: Ord, V, const N: usize> Extend<(K, V)> for BLinkMap<K, V, N> {
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iterable: T) {
for (key, value) in iterable {
self.insert(key, value);
}
}
}
impl<K: Ord, V, const N: usize> FromIterator<(K, V)> for BLinkMap<K, V, N> {
fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> Self {
let mut map = Self::new();
map.extend(iterable);
map
}
}
impl<'map, K: Ord, V, const N: usize> IntoIterator
for &'map BLinkMap<K, V, N>
{
type Item = EntryRef<'map, K, V, N>;
type IntoIter = Iter<'map, K, V, N>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<K: Ord + fmt::Debug, V: fmt::Debug, const N: usize> fmt::Debug
for BLinkMap<K, V, N>
{
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut debug = formatter.debug_map();
let mut iterator = self.iter();
for entry in &mut iterator {
debug.entry(entry.key(), entry.value());
}
debug.finish()
}
}
#[cfg(test)]
mod tests {
use std::{
collections::BTreeMap,
sync::{mpsc, Arc, Barrier},
thread,
time::Duration,
};
use super::*;
type TestMap = BLinkMap<u64, u64, 3>;
#[test]
fn basic_map_operations_and_entry_guards() {
let map = TestMap::new();
assert!(map.is_empty());
assert_eq!(map.insert(10, 100), None);
assert_eq!(map.insert(20, 200), None);
assert_eq!(map.insert(10, 500), Some(100));
assert_eq!(map.len(), 2);
assert!(map.contains_key(&20));
let entry = map.get(&10).unwrap();
assert_eq!(entry.key(), &10);
assert_eq!(entry.value(), &500);
drop(entry);
{
let mut entry = map.get_mut(&10).unwrap();
assert_eq!(entry.key(), &10);
*entry += 1;
}
assert_eq!(map.remove(&10), Some(501));
assert_eq!(map.remove(&10), None);
assert_eq!(map.len(), 1);
map.assert_valid();
}
#[test]
fn grows_through_leaf_internal_and_root_splits() {
let map = TestMap::new();
for key in 0..2_000 {
assert_eq!(map.insert(key, key * 10), None);
}
assert!(map.height() >= 4);
map.assert_valid();
for key in 0..2_000 {
assert_eq!(map.get(&key).map(|entry| *entry), Some(key * 10));
}
}
#[test]
fn reverse_insertion_complete_deletion_and_reinsertion() {
let map = TestMap::new();
for key in (0..1_000).rev() {
map.insert(key, key);
}
for key in 0..1_000 {
assert_eq!(map.remove(&key), Some(key));
}
assert!(map.is_empty());
map.assert_valid();
for key in (0..1_000).rev() {
assert_eq!(map.insert(key, key + 1), None);
}
map.assert_valid();
}
fn differential_trace<const CAPACITY: usize>() {
let map = BLinkMap::<u64, u64, CAPACITY>::new();
let mut reference = BTreeMap::new();
let mut state = 0x9e37_79b9_7f4a_7c15_u64;
for step in 0..20_000 {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
let key = (state >> 17) % 400;
let value = state.rotate_left(23);
match state % 4 {
0 | 1 => {
assert_eq!(map.insert(key, value), reference.insert(key, value));
},
2 => {
assert_eq!(map.remove(&key), reference.remove(&key));
},
_ => {
assert_eq!(
map.get(&key).map(|entry| *entry),
reference.get(&key).copied()
);
},
}
if step % 257 == 0 {
map.assert_valid();
}
}
assert_eq!(map.len(), reference.len());
for key in 0..400 {
assert_eq!(
map.get(&key).map(|entry| *entry),
reference.get(&key).copied()
);
}
map.assert_valid();
}
#[test]
fn matches_btree_map_at_multiple_page_capacities() {
differential_trace::<3>();
differential_trace::<4>();
differential_trace::<5>();
differential_trace::<8>();
}
#[test]
fn borrowed_lookup_does_not_require_cloning_keys() {
#[derive(Eq, Ord, PartialEq, PartialOrd)]
struct NonClone(u64);
let map = BLinkMap::<NonClone, u64, 3>::new();
map.insert(NonClone(7), 70);
assert_eq!(map.get(&NonClone(7)).map(|entry| *entry), Some(70));
let strings = BLinkMap::<String, u64, 3>::new();
strings.insert(String::from("alpha"), 1);
assert!(strings.contains_key("alpha"));
assert_eq!(strings.get("alpha").map(|entry| *entry), Some(1));
*strings.get_mut("alpha").unwrap() = 2;
assert_eq!(strings.remove("alpha"), Some(2));
assert!(!strings.contains_key("alpha"));
}
#[test]
#[should_panic(expected = "capacity must be at least 3")]
fn rejects_too_small_page_capacity() {
let _ = BLinkMap::<u64, u64, 2>::new();
}
#[test]
fn concurrent_disjoint_inserts() {
let map = Arc::new(BLinkMap::<u64, u64, 8>::new());
let threads = std::array::from_fn::<_, 8, _>(|thread_id| {
let map = Arc::clone(&map);
thread::spawn(move || {
for offset in 0..1_000 {
let key = thread_id as u64 * 1_000 + offset;
assert_eq!(map.insert(key, key), None);
}
})
});
for thread in threads {
thread.join().unwrap();
}
assert_eq!(map.len(), 8_000);
map.assert_valid();
for key in 0..8_000 {
assert_eq!(map.get(&key).map(|entry| *entry), Some(key));
}
}
#[test]
fn concurrent_same_key_operations_are_linearizable() {
const THREADS: usize = 8;
let map = Arc::new(BLinkMap::<u64, u64, 3>::new());
let barrier = Arc::new(Barrier::new(THREADS));
let inserters = std::array::from_fn::<_, THREADS, _>(|value| {
let map = Arc::clone(&map);
let barrier = Arc::clone(&barrier);
thread::spawn(move || {
barrier.wait();
map.insert(1, value as u64)
})
});
let mut saw_value = [false; THREADS];
let mut new_key_results = 0;
for inserter in inserters {
match inserter.join().unwrap() {
Some(value) => {
let slot = &mut saw_value[value as usize];
assert!(!*slot);
*slot = true;
},
None => new_key_results += 1,
}
}
assert_eq!(new_key_results, 1);
let final_value = *map.get(&1).unwrap();
assert!(!saw_value[final_value as usize]);
saw_value[final_value as usize] = true;
assert!(saw_value.into_iter().all(|seen| seen));
assert_eq!(map.len(), 1);
let barrier = Arc::new(Barrier::new(THREADS));
let removers = std::array::from_fn::<_, THREADS, _>(|_| {
let map = Arc::clone(&map);
let barrier = Arc::clone(&barrier);
thread::spawn(move || {
barrier.wait();
map.remove(&1)
})
});
let mut removed = 0;
for remover in removers {
if remover.join().unwrap().is_some() {
removed += 1;
}
}
assert_eq!(removed, 1);
assert!(map.is_empty());
map.assert_valid();
}
#[test]
fn stable_keys_never_disappear_during_splits() {
const READERS: usize = 4;
let map = Arc::new(BLinkMap::<u64, u64, 3>::new());
for key in 0..1_000 {
map.insert(key * 2, key);
}
let barrier = Arc::new(Barrier::new(READERS + 1));
let writer_map = Arc::clone(&map);
let writer_barrier = Arc::clone(&barrier);
let writer = thread::spawn(move || {
writer_barrier.wait();
for key in 0..1_000 {
writer_map.insert(key * 2 + 1, key);
}
});
let readers = std::array::from_fn::<_, READERS, _>(|_| {
let map = Arc::clone(&map);
let barrier = Arc::clone(&barrier);
thread::spawn(move || {
barrier.wait();
for _ in 0..4 {
for key in 0..1_000 {
assert_eq!(map.get(&(key * 2)).map(|entry| *entry), Some(key));
}
}
})
});
writer.join().unwrap();
for reader in readers {
reader.join().unwrap();
}
map.assert_valid();
}
#[test]
fn stable_keys_never_disappear_during_rotations_and_merges() {
const READERS: usize = 4;
let map = Arc::new(BLinkMap::<u64, u64, 5>::new());
for key in 0..4_000 {
map.insert(key, key * 10);
}
let barrier = Arc::new(Barrier::new(READERS + 1));
let remover_map = Arc::clone(&map);
let remover_barrier = Arc::clone(&barrier);
let remover = thread::spawn(move || {
remover_barrier.wait();
for key in (1..4_000).step_by(2) {
assert_eq!(remover_map.remove(&key), Some(key * 10));
}
});
let readers = std::array::from_fn::<_, READERS, _>(|_| {
let map = Arc::clone(&map);
let barrier = Arc::clone(&barrier);
thread::spawn(move || {
barrier.wait();
for _ in 0..3 {
for key in (0..4_000).step_by(2) {
assert_eq!(map.get(&key).map(|entry| *entry), Some(key * 10));
}
}
})
});
remover.join().unwrap();
for reader in readers {
reader.join().unwrap();
}
assert_eq!(map.len(), 2_000);
map.assert_valid();
}
#[test]
fn concurrent_get_mut_and_remove() {
let map = Arc::new(BLinkMap::<u64, u64, 8>::new());
for key in 0..4_000 {
map.insert(key, 0);
}
let writers = std::array::from_fn::<_, 4, _>(|thread_id| {
let map = Arc::clone(&map);
thread::spawn(move || {
for offset in 0..1_000 {
let key = thread_id as u64 * 1_000 + offset;
*map.get_mut(&key).unwrap() += 1;
}
})
});
for writer in writers {
writer.join().unwrap();
}
let removers = std::array::from_fn::<_, 4, _>(|thread_id| {
let map = Arc::clone(&map);
thread::spawn(move || {
for offset in 0..500 {
let key = thread_id as u64 * 1_000 + offset;
assert_eq!(map.remove(&key), Some(1));
}
})
});
for remover in removers {
remover.join().unwrap();
}
assert_eq!(map.len(), 2_000);
map.assert_valid();
}
#[test]
fn held_leaf_guard_does_not_convoy_a_distant_structural_writer() {
let map = Arc::new(BLinkMap::<u64, u64, 5>::new());
for key in 0..2_000 {
map.insert(key, key);
}
let held_left_leaf = map.get_mut(&0).unwrap();
let worker_map = Arc::clone(&map);
let (finished_tx, finished_rx) = mpsc::channel();
let worker = thread::spawn(move || {
for key in 2_000..4_000 {
worker_map.insert(key, key);
}
finished_tx.send(()).unwrap();
});
finished_rx.recv_timeout(Duration::from_secs(5)).expect(
"a distant structural writer was convoyed behind a leaf guard",
);
drop(held_left_leaf);
worker.join().unwrap();
assert_eq!(map.len(), 4_000);
map.assert_valid();
}
}