Skip to main content

b_link/
handle.rs

1use std::{
2  cmp::Ordering,
3  fmt,
4  marker::PhantomData,
5  ops::{Deref, DerefMut},
6  sync::Arc,
7};
8
9use crate::{
10  map::{BLinkMap, DEFAULT_PAGE_CAPACITY},
11  node::{NodeKind, NodeReadGuard, NodeWriteGuard},
12};
13
14#[repr(transparent)]
15/// Reference-counted ownership of a stored key.
16///
17/// Leaf entries, internal separators, and high fences can share the same key
18/// allocation. This avoids imposing `K: Clone` on the public map API.
19pub(crate) struct KeyHandle<K> {
20  /// The one owned key allocation shared by tree metadata.
21  inner: Arc<K>,
22}
23
24impl<K> KeyHandle<K> {
25  /// Allocates a new shared handle around an inserted key.
26  pub(crate) fn new(key: K) -> Self {
27    Self {
28      inner: Arc::new(key),
29    }
30  }
31
32  #[inline]
33  /// Borrows the underlying key.
34  pub(crate) fn get(&self) -> &K {
35    &self.inner
36  }
37}
38
39impl<K> AsRef<K> for KeyHandle<K> {
40  fn as_ref(&self) -> &K {
41    self.get()
42  }
43}
44
45impl<K> Deref for KeyHandle<K> {
46  type Target = K;
47
48  fn deref(&self) -> &K {
49    self.get()
50  }
51}
52
53impl<K> Clone for KeyHandle<K> {
54  fn clone(&self) -> Self {
55    Self {
56      inner: Arc::clone(&self.inner),
57    }
58  }
59}
60
61impl<K: PartialEq> PartialEq for KeyHandle<K> {
62  fn eq(&self, other: &Self) -> bool {
63    self.inner.eq(&other.inner)
64  }
65}
66
67impl<K: Eq> Eq for KeyHandle<K> {}
68
69impl<K: PartialOrd> PartialOrd for KeyHandle<K> {
70  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
71    self.inner.partial_cmp(&other.inner)
72  }
73}
74
75impl<K: Ord> Ord for KeyHandle<K> {
76  fn cmp(&self, other: &Self) -> Ordering {
77    self.inner.cmp(&other.inner)
78  }
79}
80
81impl<K: std::hash::Hash> std::hash::Hash for KeyHandle<K> {
82  fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
83    self.inner.hash(state);
84  }
85}
86
87/// A read guard for an entry in a [`BLinkMap`].
88///
89/// The guard keeps its leaf read-locked. This makes the returned key and value
90/// references stable until the guard is dropped.
91///
92/// # Locking
93///
94/// Drop this guard before calling a map operation that may need the same leaf,
95/// especially [`BLinkMap::insert`], [`BLinkMap::remove`], or
96/// [`BLinkMap::get_mut`]. Retaining it can self-deadlock. Holding several entry
97/// guards while acquiring more guards in inconsistent orders can likewise
98/// create a cross-thread lock cycle.
99#[must_use = "the entry remains read-locked only while this guard is held"]
100pub struct EntryRef<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
101  /// Owning page latch that keeps the leaf and its contents stable.
102  guard: NodeReadGuard<K, V, N>,
103  /// Entry location, stable because writers cannot acquire the leaf latch.
104  index: usize,
105  /// Connects the owning guard's lifetime to the map borrow in the public API.
106  _map: PhantomData<&'map BLinkMap<K, V, N>>,
107}
108
109impl<K, V, const N: usize> EntryRef<'_, K, V, N> {
110  /// Wraps a leaf latch and the matching index found under that latch.
111  pub(crate) fn new(guard: NodeReadGuard<K, V, N>, index: usize) -> Self {
112    Self {
113      guard,
114      index,
115      _map: PhantomData,
116    }
117  }
118
119  /// Returns the entry's immutable key.
120  pub fn key(&self) -> &K {
121    &self.entry().key
122  }
123
124  /// Returns the entry's immutable value.
125  pub fn value(&self) -> &V {
126    &self.entry().value
127  }
128
129  /// Resolves the stable index inside the read-latched leaf.
130  fn entry(&self) -> &crate::node::Entry<K, V> {
131    match &self.guard.kind {
132      NodeKind::Internal(_) | NodeKind::Redirect(_) => {
133        unreachable!("an entry guard must hold a leaf")
134      },
135      NodeKind::Leaf(leaf) => &leaf.entries[self.index],
136    }
137  }
138}
139
140impl<K, V, const N: usize> Deref for EntryRef<'_, K, V, N> {
141  type Target = V;
142
143  fn deref(&self) -> &V {
144    self.value()
145  }
146}
147
148impl<K: fmt::Debug, V: fmt::Debug, const N: usize> fmt::Debug
149  for EntryRef<'_, K, V, N>
150{
151  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
152    formatter
153      .debug_struct("EntryRef")
154      .field("key", self.key())
155      .field("value", self.value())
156      .finish()
157  }
158}
159
160/// A write guard for an entry in a [`BLinkMap`].
161///
162/// The guard keeps its leaf write-locked. Mutations through [`DerefMut`] are
163/// visible to later map operations when the guard is dropped.
164///
165/// # Locking
166///
167/// While this guard exists, every other operation targeting the same leaf is
168/// blocked—including reads. Drop it before calling back into the map. Acquiring
169/// multiple mutable guards in different orders across threads can deadlock.
170#[must_use = "the entry remains write-locked only while this guard is held"]
171pub struct EntryMut<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
172  /// Owning exclusive page latch.
173  guard: NodeWriteGuard<K, V, N>,
174  /// Entry location, stable for the duration of the exclusive latch.
175  index: usize,
176  /// Connects the owning guard's lifetime to the map borrow in the public API.
177  _map: PhantomData<&'map BLinkMap<K, V, N>>,
178}
179
180impl<K, V, const N: usize> EntryMut<'_, K, V, N> {
181  /// Wraps an exclusive leaf latch and the matching index found under it.
182  pub(crate) fn new(guard: NodeWriteGuard<K, V, N>, index: usize) -> Self {
183    Self {
184      guard,
185      index,
186      _map: PhantomData,
187    }
188  }
189
190  /// Returns the entry's immutable key.
191  pub fn key(&self) -> &K {
192    &self.entry().key
193  }
194
195  /// Returns the entry's immutable value.
196  pub fn value(&self) -> &V {
197    &self.entry().value
198  }
199
200  /// Returns the entry's value mutably while retaining the leaf write latch.
201  pub fn value_mut(&mut self) -> &mut V {
202    &mut self.entry_mut().value
203  }
204
205  /// Resolves the stable index through an immutable view of the write latch.
206  fn entry(&self) -> &crate::node::Entry<K, V> {
207    match &self.guard.kind {
208      NodeKind::Internal(_) | NodeKind::Redirect(_) => {
209        unreachable!("an entry guard must hold a leaf")
210      },
211      NodeKind::Leaf(leaf) => &leaf.entries[self.index],
212    }
213  }
214
215  /// Resolves the stable index through the exclusive page view.
216  fn entry_mut(&mut self) -> &mut crate::node::Entry<K, V> {
217    match &mut self.guard.kind {
218      NodeKind::Internal(_) | NodeKind::Redirect(_) => {
219        unreachable!("an entry guard must hold a leaf")
220      },
221      NodeKind::Leaf(leaf) => &mut leaf.entries[self.index],
222    }
223  }
224}
225
226impl<K, V, const N: usize> Deref for EntryMut<'_, K, V, N> {
227  type Target = V;
228
229  fn deref(&self) -> &V {
230    self.value()
231  }
232}
233
234impl<K, V, const N: usize> DerefMut for EntryMut<'_, K, V, N> {
235  fn deref_mut(&mut self) -> &mut V {
236    self.value_mut()
237  }
238}
239
240impl<K: fmt::Debug, V: fmt::Debug, const N: usize> fmt::Debug
241  for EntryMut<'_, K, V, N>
242{
243  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
244    formatter
245      .debug_struct("EntryMut")
246      .field("key", self.key())
247      .field("value", self.value())
248      .finish()
249  }
250}