Skip to main content

b_link/
map.rs

1use std::{borrow::Borrow, fmt, iter::FromIterator, ops::RangeBounds};
2
3use crate::{
4  handle::{EntryMut, EntryRef},
5  iter::{Iter, Keys, Range, Values},
6  node::Tree,
7};
8
9/// The maximum stable entries/separators per page when [`BLinkMap`] is named
10/// without an explicit const capacity argument.
11pub const DEFAULT_PAGE_CAPACITY: usize = 32;
12
13/// A concurrent ordered map backed by a B-link tree.
14///
15/// `N` is the exact allocation capacity for separators or entries in a page.
16/// Full pages split before another item is inserted. `N` must be at least
17/// three; omitting it uses [`DEFAULT_PAGE_CAPACITY`].
18///
19/// Reads and ordinary writes use one page latch. Splits, rotations, and merges
20/// use top-down latch crabbing: a writer briefly owns a parent and one or two
21/// adjacent children, repairs them, then releases the parent before descending.
22/// No tree-wide structure lock serializes writers. Each page carries lower and
23/// upper fences, a right sibling, and a forwarding state for stale references,
24/// so completed key operations are linearizable at their destination leaf.
25///
26/// # Key ordering
27///
28/// Keys must retain the same ordering for their entire time in the map. Do not
29/// mutate ordering-relevant state through interior mutability. For borrowed
30/// lookups, the ordering of `K: Borrow<Q>` must agree with both `K::Ord` and
31/// `Q::Ord`, just as it must for standard ordered maps.
32///
33/// # Entry guards and locking
34///
35/// [`EntryRef`] and [`EntryMut`] lock an entire leaf, not only one record. Drop
36/// a guard before invoking another operation that could target that leaf.
37/// Re-entering the map while a conflicting guard is alive can deadlock, and
38/// acquiring several guards in inconsistent orders can create lock cycles.
39pub struct BLinkMap<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
40  /// Internal page owner and algorithm implementation.
41  pub(crate) tree: Tree<K, V, N>,
42}
43
44impl<K, V, const N: usize> BLinkMap<K, V, N> {
45  /// Creates an empty map with one allocated leaf page.
46  ///
47  /// # Panics
48  ///
49  /// Panics when `N < 3`, when the capacity arithmetic overflows, or when a
50  /// backing page layout cannot be represented. Allocation failure is handled
51  /// by Rust's global allocation-error handler.
52  pub fn new() -> Self {
53    Self { tree: Tree::new() }
54  }
55
56  /// Returns the number of entries currently in the map.
57  ///
58  /// During concurrent mutation this is a momentary atomic observation, not a
59  /// transactionally consistent snapshot of other operations.
60  pub fn len(&self) -> usize {
61    self.tree.len()
62  }
63
64  /// Returns true when the map has no entries at the instant it is observed.
65  ///
66  /// Like [`BLinkMap::len`], this result can become stale immediately when
67  /// other threads mutate the map.
68  pub fn is_empty(&self) -> bool {
69    self.len() == 0
70  }
71
72  /// Removes every entry and returns the map to one empty root leaf.
73  ///
74  /// The exclusive `&mut self` borrow proves that no entry guard or concurrent
75  /// operation can still reference the old tree through this map. Individual
76  /// pages are reclaimed as their internal `Arc` owners are dropped.
77  pub fn clear(&mut self) {
78    self.tree = Tree::new();
79  }
80}
81
82impl<K: Ord, V, const N: usize> BLinkMap<K, V, N> {
83  /// Returns a read guard for `key`, or `None` when the key is absent.
84  ///
85  /// The returned guard keeps the whole destination leaf read-locked. Its key
86  /// and value references remain stable, but it must be dropped before a
87  /// conflicting operation on that leaf to avoid deadlock.
88  ///
89  /// The borrowed form `Q` must use an ordering consistent with `K`.
90  pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
91  where
92    K: Borrow<Q>,
93    Q: Ord + ?Sized,
94  {
95    let (guard, index) = self.tree.get(key)?;
96    Some(EntryRef::new(guard, index))
97  }
98
99  /// Returns a read guard exposing both the stored key and value.
100  ///
101  /// This is an explicitly named counterpart to [`BLinkMap::get`]; both
102  /// return the same [`EntryRef`] because that guard already supplies
103  /// [`EntryRef::key`] and [`EntryRef::value`].
104  pub fn get_key_value<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
105  where
106    K: Borrow<Q>,
107    Q: Ord + ?Sized,
108  {
109    self.get(key)
110  }
111
112  /// Returns a write guard for `key`, or `None` when the key is absent.
113  ///
114  /// The guard exclusively locks the entire destination leaf and supports
115  /// mutation through [`EntryMut::value_mut`] or `DerefMut`. Drop it before
116  /// calling any other map operation that could visit the same leaf.
117  ///
118  /// The borrowed form `Q` must use an ordering consistent with `K`.
119  pub fn get_mut<Q>(&self, key: &Q) -> Option<EntryMut<'_, K, V, N>>
120  where
121    K: Borrow<Q>,
122    Q: Ord + ?Sized,
123  {
124    let (guard, index) = self.tree.get_mut(key)?;
125    Some(EntryMut::new(guard, index))
126  }
127
128  /// Returns true when the map contains `key` at the operation's linearization
129  /// point. The temporary leaf read latch is released before this returns.
130  ///
131  /// The borrowed form `Q` must use an ordering consistent with `K`.
132  pub fn contains_key<Q>(&self, key: &Q) -> bool
133  where
134    K: Borrow<Q>,
135    Q: Ord + ?Sized,
136  {
137    self.get(key).is_some()
138  }
139
140  /// Inserts `key` and `value`, returning the previous value if the key was
141  /// already present.
142  ///
143  /// A non-splitting insert locks only its destination leaf. A structural
144  /// insert splits full pages top-down while holding only the affected parent
145  /// and child, allowing writers in disjoint subtrees to continue concurrently.
146  pub fn insert(&self, key: K, value: V) -> Option<V> {
147    self.tree.insert(key, value)
148  }
149
150  /// Removes `key`, returning its value when present.
151  ///
152  /// Before descending into a minimally occupied page, deletion borrows from a
153  /// sibling or merges two pages. Merged pages are removed from their parent
154  /// and sibling chain, while stale `Arc` handles see a forwarding page until
155  /// they drain. Empty internal root levels are collapsed before this returns.
156  /// A removed key that also serves as a surviving fence or separator may keep
157  /// its shared key allocation alive until that boundary changes or the map is
158  /// dropped; the user value is returned immediately.
159  ///
160  /// The borrowed form `Q` must use an ordering consistent with `K`.
161  pub fn remove<Q>(&self, key: &Q) -> Option<V>
162  where
163    K: Borrow<Q>,
164    Q: Ord + ?Sized,
165  {
166    self.tree.remove(key)
167  }
168
169  /// Returns the least key/value record, guarded by its leaf read latch.
170  pub fn first_key_value(&self) -> Option<EntryRef<'_, K, V, N>> {
171    let (guard, index) = self.tree.first_entry()?;
172    Some(EntryRef::new(guard, index))
173  }
174
175  /// Returns the greatest key/value record, guarded by its leaf read latch.
176  pub fn last_key_value(&self) -> Option<EntryRef<'_, K, V, N>> {
177    let (guard, index) = self.tree.last_entry()?;
178    Some(EntryRef::new(guard, index))
179  }
180
181  /// Returns a weakly consistent ascending iterator over guarded records.
182  ///
183  /// See [`Iter`] for its concurrent visibility and leaf-locking semantics.
184  pub fn iter(&self) -> Iter<'_, K, V, N> {
185    Iter::new(self)
186  }
187
188  /// Returns a weakly consistent ascending iterator over guarded keys.
189  pub fn keys(&self) -> Keys<'_, K, V, N> {
190    Keys::new(self)
191  }
192
193  /// Returns a weakly consistent ascending iterator over guarded values.
194  pub fn values(&self) -> Values<'_, K, V, N> {
195    Values::new(self)
196  }
197
198  /// Returns an ascending iterator over records whose keys lie in `bounds`.
199  ///
200  /// Borrowed bounds are supported when their ordering agrees with `K`.
201  ///
202  /// # Panics
203  ///
204  /// Panics when the start is greater than the end, or when equal start and
205  /// end bounds are both excluded.
206  pub fn range<Q, R>(&self, bounds: R) -> Range<'_, K, V, Q, R, N>
207  where
208    K: Borrow<Q>,
209    Q: Ord + ?Sized,
210    R: RangeBounds<Q>,
211  {
212    Range::new(self, bounds)
213  }
214
215  #[cfg(test)]
216  pub(crate) fn assert_valid(&self) {
217    if let Err(error) = self.tree.validate() {
218      panic!("B-link tree invariant violated: {error}");
219    }
220  }
221
222  #[cfg(test)]
223  fn height(&self) -> usize {
224    self.tree.height()
225  }
226}
227
228impl<K, V, const N: usize> Default for BLinkMap<K, V, N> {
229  fn default() -> Self {
230    Self::new()
231  }
232}
233
234impl<K: Ord, V, const N: usize> Extend<(K, V)> for BLinkMap<K, V, N> {
235  /// Inserts every pair, replacing values for duplicate keys.
236  fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iterable: T) {
237    for (key, value) in iterable {
238      self.insert(key, value);
239    }
240  }
241}
242
243impl<K: Ord, V, const N: usize> FromIterator<(K, V)> for BLinkMap<K, V, N> {
244  /// Builds a map by repeated concurrent-map insertions.
245  fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> Self {
246    let mut map = Self::new();
247    map.extend(iterable);
248    map
249  }
250}
251
252impl<'map, K: Ord, V, const N: usize> IntoIterator
253  for &'map BLinkMap<K, V, N>
254{
255  type Item = EntryRef<'map, K, V, N>;
256  type IntoIter = Iter<'map, K, V, N>;
257
258  /// Creates the same guarded iterator as [`BLinkMap::iter`].
259  fn into_iter(self) -> Self::IntoIter {
260    self.iter()
261  }
262}
263
264impl<K: Ord + fmt::Debug, V: fmt::Debug, const N: usize> fmt::Debug
265  for BLinkMap<K, V, N>
266{
267  /// Formats a weakly consistent ordered view, dropping each guard promptly.
268  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
269    let mut debug = formatter.debug_map();
270    let mut iterator = self.iter();
271
272    for entry in &mut iterator {
273      debug.entry(entry.key(), entry.value());
274    }
275
276    debug.finish()
277  }
278}
279
280#[cfg(test)]
281mod tests {
282  use std::{
283    collections::BTreeMap,
284    sync::{mpsc, Arc, Barrier},
285    thread,
286    time::Duration,
287  };
288
289  use super::*;
290
291  type TestMap = BLinkMap<u64, u64, 3>;
292
293  #[test]
294  fn basic_map_operations_and_entry_guards() {
295    let map = TestMap::new();
296
297    assert!(map.is_empty());
298    assert_eq!(map.insert(10, 100), None);
299    assert_eq!(map.insert(20, 200), None);
300    assert_eq!(map.insert(10, 500), Some(100));
301    assert_eq!(map.len(), 2);
302    assert!(map.contains_key(&20));
303
304    let entry = map.get(&10).unwrap();
305    assert_eq!(entry.key(), &10);
306    assert_eq!(entry.value(), &500);
307    drop(entry);
308
309    {
310      let mut entry = map.get_mut(&10).unwrap();
311      assert_eq!(entry.key(), &10);
312      *entry += 1;
313    }
314
315    assert_eq!(map.remove(&10), Some(501));
316    assert_eq!(map.remove(&10), None);
317    assert_eq!(map.len(), 1);
318    map.assert_valid();
319  }
320
321  #[test]
322  fn grows_through_leaf_internal_and_root_splits() {
323    let map = TestMap::new();
324
325    for key in 0..2_000 {
326      assert_eq!(map.insert(key, key * 10), None);
327    }
328
329    assert!(map.height() >= 4);
330    map.assert_valid();
331
332    for key in 0..2_000 {
333      assert_eq!(map.get(&key).map(|entry| *entry), Some(key * 10));
334    }
335  }
336
337  #[test]
338  fn reverse_insertion_complete_deletion_and_reinsertion() {
339    let map = TestMap::new();
340
341    for key in (0..1_000).rev() {
342      map.insert(key, key);
343    }
344    for key in 0..1_000 {
345      assert_eq!(map.remove(&key), Some(key));
346    }
347
348    assert!(map.is_empty());
349    map.assert_valid();
350
351    for key in (0..1_000).rev() {
352      assert_eq!(map.insert(key, key + 1), None);
353    }
354
355    map.assert_valid();
356  }
357
358  fn differential_trace<const CAPACITY: usize>() {
359    let map = BLinkMap::<u64, u64, CAPACITY>::new();
360    let mut reference = BTreeMap::new();
361    let mut state = 0x9e37_79b9_7f4a_7c15_u64;
362
363    for step in 0..20_000 {
364      state = state
365        .wrapping_mul(6_364_136_223_846_793_005)
366        .wrapping_add(1_442_695_040_888_963_407);
367
368      let key = (state >> 17) % 400;
369      let value = state.rotate_left(23);
370
371      match state % 4 {
372        0 | 1 => {
373          assert_eq!(map.insert(key, value), reference.insert(key, value));
374        },
375        2 => {
376          assert_eq!(map.remove(&key), reference.remove(&key));
377        },
378        _ => {
379          assert_eq!(
380            map.get(&key).map(|entry| *entry),
381            reference.get(&key).copied()
382          );
383        },
384      }
385
386      if step % 257 == 0 {
387        map.assert_valid();
388      }
389    }
390
391    assert_eq!(map.len(), reference.len());
392    for key in 0..400 {
393      assert_eq!(
394        map.get(&key).map(|entry| *entry),
395        reference.get(&key).copied()
396      );
397    }
398    map.assert_valid();
399  }
400
401  #[test]
402  fn matches_btree_map_at_multiple_page_capacities() {
403    differential_trace::<3>();
404    differential_trace::<4>();
405    differential_trace::<5>();
406    differential_trace::<8>();
407  }
408
409  #[test]
410  fn borrowed_lookup_does_not_require_cloning_keys() {
411    #[derive(Eq, Ord, PartialEq, PartialOrd)]
412    struct NonClone(u64);
413
414    let map = BLinkMap::<NonClone, u64, 3>::new();
415    map.insert(NonClone(7), 70);
416
417    assert_eq!(map.get(&NonClone(7)).map(|entry| *entry), Some(70));
418
419    let strings = BLinkMap::<String, u64, 3>::new();
420    strings.insert(String::from("alpha"), 1);
421    assert!(strings.contains_key("alpha"));
422    assert_eq!(strings.get("alpha").map(|entry| *entry), Some(1));
423    *strings.get_mut("alpha").unwrap() = 2;
424    assert_eq!(strings.remove("alpha"), Some(2));
425    assert!(!strings.contains_key("alpha"));
426  }
427
428  #[test]
429  #[should_panic(expected = "capacity must be at least 3")]
430  fn rejects_too_small_page_capacity() {
431    let _ = BLinkMap::<u64, u64, 2>::new();
432  }
433
434  #[test]
435  fn concurrent_disjoint_inserts() {
436    let map = Arc::new(BLinkMap::<u64, u64, 8>::new());
437
438    let threads = std::array::from_fn::<_, 8, _>(|thread_id| {
439      let map = Arc::clone(&map);
440
441      thread::spawn(move || {
442        for offset in 0..1_000 {
443          let key = thread_id as u64 * 1_000 + offset;
444          assert_eq!(map.insert(key, key), None);
445        }
446      })
447    });
448
449    for thread in threads {
450      thread.join().unwrap();
451    }
452
453    assert_eq!(map.len(), 8_000);
454    map.assert_valid();
455
456    for key in 0..8_000 {
457      assert_eq!(map.get(&key).map(|entry| *entry), Some(key));
458    }
459  }
460
461  #[test]
462  fn concurrent_same_key_operations_are_linearizable() {
463    const THREADS: usize = 8;
464
465    let map = Arc::new(BLinkMap::<u64, u64, 3>::new());
466    let barrier = Arc::new(Barrier::new(THREADS));
467    let inserters = std::array::from_fn::<_, THREADS, _>(|value| {
468      let map = Arc::clone(&map);
469      let barrier = Arc::clone(&barrier);
470
471      thread::spawn(move || {
472        barrier.wait();
473        map.insert(1, value as u64)
474      })
475    });
476
477    // One insert creates the entry. Every later insert returns the value it
478    // replaced, while exactly one submitted value remains in the leaf.
479    let mut saw_value = [false; THREADS];
480    let mut new_key_results = 0;
481
482    for inserter in inserters {
483      match inserter.join().unwrap() {
484        Some(value) => {
485          let slot = &mut saw_value[value as usize];
486          assert!(!*slot);
487          *slot = true;
488        },
489        None => new_key_results += 1,
490      }
491    }
492
493    assert_eq!(new_key_results, 1);
494    let final_value = *map.get(&1).unwrap();
495    assert!(!saw_value[final_value as usize]);
496    saw_value[final_value as usize] = true;
497    assert!(saw_value.into_iter().all(|seen| seen));
498    assert_eq!(map.len(), 1);
499
500    let barrier = Arc::new(Barrier::new(THREADS));
501    let removers = std::array::from_fn::<_, THREADS, _>(|_| {
502      let map = Arc::clone(&map);
503      let barrier = Arc::clone(&barrier);
504
505      thread::spawn(move || {
506        barrier.wait();
507        map.remove(&1)
508      })
509    });
510
511    let mut removed = 0;
512    for remover in removers {
513      if remover.join().unwrap().is_some() {
514        removed += 1;
515      }
516    }
517
518    assert_eq!(removed, 1);
519    assert!(map.is_empty());
520    map.assert_valid();
521  }
522
523  #[test]
524  fn stable_keys_never_disappear_during_splits() {
525    const READERS: usize = 4;
526
527    let map = Arc::new(BLinkMap::<u64, u64, 3>::new());
528    for key in 0..1_000 {
529      map.insert(key * 2, key);
530    }
531
532    let barrier = Arc::new(Barrier::new(READERS + 1));
533    let writer_map = Arc::clone(&map);
534    let writer_barrier = Arc::clone(&barrier);
535    let writer = thread::spawn(move || {
536      writer_barrier.wait();
537      for key in 0..1_000 {
538        writer_map.insert(key * 2 + 1, key);
539      }
540    });
541
542    let readers = std::array::from_fn::<_, READERS, _>(|_| {
543      let map = Arc::clone(&map);
544      let barrier = Arc::clone(&barrier);
545
546      thread::spawn(move || {
547        barrier.wait();
548        for _ in 0..4 {
549          for key in 0..1_000 {
550            assert_eq!(map.get(&(key * 2)).map(|entry| *entry), Some(key));
551          }
552        }
553      })
554    });
555
556    writer.join().unwrap();
557    for reader in readers {
558      reader.join().unwrap();
559    }
560
561    map.assert_valid();
562  }
563
564  #[test]
565  fn stable_keys_never_disappear_during_rotations_and_merges() {
566    const READERS: usize = 4;
567
568    let map = Arc::new(BLinkMap::<u64, u64, 5>::new());
569    for key in 0..4_000 {
570      map.insert(key, key * 10);
571    }
572
573    let barrier = Arc::new(Barrier::new(READERS + 1));
574    let remover_map = Arc::clone(&map);
575    let remover_barrier = Arc::clone(&barrier);
576    let remover = thread::spawn(move || {
577      remover_barrier.wait();
578      for key in (1..4_000).step_by(2) {
579        assert_eq!(remover_map.remove(&key), Some(key * 10));
580      }
581    });
582
583    let readers = std::array::from_fn::<_, READERS, _>(|_| {
584      let map = Arc::clone(&map);
585      let barrier = Arc::clone(&barrier);
586      thread::spawn(move || {
587        barrier.wait();
588        for _ in 0..3 {
589          for key in (0..4_000).step_by(2) {
590            assert_eq!(map.get(&key).map(|entry| *entry), Some(key * 10));
591          }
592        }
593      })
594    });
595
596    remover.join().unwrap();
597    for reader in readers {
598      reader.join().unwrap();
599    }
600
601    assert_eq!(map.len(), 2_000);
602    map.assert_valid();
603  }
604
605  #[test]
606  fn concurrent_get_mut_and_remove() {
607    let map = Arc::new(BLinkMap::<u64, u64, 8>::new());
608    for key in 0..4_000 {
609      map.insert(key, 0);
610    }
611
612    let writers = std::array::from_fn::<_, 4, _>(|thread_id| {
613      let map = Arc::clone(&map);
614
615      thread::spawn(move || {
616        for offset in 0..1_000 {
617          let key = thread_id as u64 * 1_000 + offset;
618          *map.get_mut(&key).unwrap() += 1;
619        }
620      })
621    });
622
623    for writer in writers {
624      writer.join().unwrap();
625    }
626
627    let removers = std::array::from_fn::<_, 4, _>(|thread_id| {
628      let map = Arc::clone(&map);
629
630      thread::spawn(move || {
631        for offset in 0..500 {
632          let key = thread_id as u64 * 1_000 + offset;
633          assert_eq!(map.remove(&key), Some(1));
634        }
635      })
636    });
637
638    for remover in removers {
639      remover.join().unwrap();
640    }
641
642    assert_eq!(map.len(), 2_000);
643    map.assert_valid();
644  }
645
646  #[test]
647  fn held_leaf_guard_does_not_convoy_a_distant_structural_writer() {
648    let map = Arc::new(BLinkMap::<u64, u64, 5>::new());
649    for key in 0..2_000 {
650      map.insert(key, key);
651    }
652
653    // Retain the far-left leaf latch while another thread grows and repeatedly
654    // splits the far-right branch. Ancestor crabbing uses try-latches, so it
655    // never waits for this leaf while holding the root or a shared ancestor.
656    let held_left_leaf = map.get_mut(&0).unwrap();
657    let worker_map = Arc::clone(&map);
658    let (finished_tx, finished_rx) = mpsc::channel();
659    let worker = thread::spawn(move || {
660      for key in 2_000..4_000 {
661        worker_map.insert(key, key);
662      }
663      finished_tx.send(()).unwrap();
664    });
665
666    finished_rx.recv_timeout(Duration::from_secs(5)).expect(
667      "a distant structural writer was convoyed behind a leaf guard",
668    );
669    drop(held_left_leaf);
670    worker.join().unwrap();
671
672    assert_eq!(map.len(), 4_000);
673    map.assert_valid();
674  }
675}