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
9pub const DEFAULT_PAGE_CAPACITY: usize = 32;
12
13pub struct BLinkMap<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
40 pub(crate) tree: Tree<K, V, N>,
42}
43
44impl<K, V, const N: usize> BLinkMap<K, V, N> {
45 pub fn new() -> Self {
53 Self { tree: Tree::new() }
54 }
55
56 pub fn len(&self) -> usize {
61 self.tree.len()
62 }
63
64 pub fn is_empty(&self) -> bool {
69 self.len() == 0
70 }
71
72 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 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 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 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 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 pub fn insert(&self, key: K, value: V) -> Option<V> {
147 self.tree.insert(key, value)
148 }
149
150 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 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 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 pub fn iter(&self) -> Iter<'_, K, V, N> {
185 Iter::new(self)
186 }
187
188 pub fn keys(&self) -> Keys<'_, K, V, N> {
190 Keys::new(self)
191 }
192
193 pub fn values(&self) -> Values<'_, K, V, N> {
195 Values::new(self)
196 }
197
198 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 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 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 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 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 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 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}