Skip to main content

b_link/
iter.rs

1use std::{
2  borrow::Borrow,
3  cmp::Ordering,
4  fmt,
5  iter::FusedIterator,
6  marker::PhantomData,
7  ops::{Bound, Deref, RangeBounds},
8};
9
10use crate::{
11  handle::KeyHandle,
12  map::{BLinkMap, DEFAULT_PAGE_CAPACITY},
13  node::{NodeKind, NodeReadGuard, Tree},
14  EntryRef,
15};
16
17/// An immutable, ascending iterator over a [`BLinkMap`].
18///
19/// Each yielded [`EntryRef`] read-locks its containing leaf. The iterator keeps
20/// only a shared handle to the last key it returned and re-seeks strictly after
21/// that key on the next call. Consequently page splits, merges, and rotations
22/// cannot make the iterator move backward or yield one key twice.
23///
24/// This is a weakly consistent concurrent iterator: it observes every record
25/// that remains present while the cursor passes it, but a record inserted or
26/// removed concurrently may or may not be observed. It never yields keys out
27/// of order.
28///
29/// # Locking
30///
31/// A yielded guard may be retained after the next call, but doing so keeps its
32/// entire leaf locked. Drop guards promptly. In particular, calling `next`
33/// while retaining a previous item from the same leaf can wait behind a queued
34/// writer, which is itself waiting for that retained item.
35pub struct Iter<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
36  /// Tree being traversed.
37  tree: &'map Tree<K, V, N>,
38  /// Last returned key; its `Arc` survives even if that record is removed.
39  last: Option<KeyHandle<K>>,
40  /// Once exhausted, concurrent inserts do not revive this iterator.
41  finished: bool,
42}
43
44impl<'map, K, V, const N: usize> Iter<'map, K, V, N> {
45  /// Creates a cursor before the first key.
46  pub(crate) fn new(map: &'map BLinkMap<K, V, N>) -> Self {
47    Self {
48      tree: &map.tree,
49      last: None,
50      finished: false,
51    }
52  }
53}
54
55impl<'map, K: Ord, V, const N: usize> Iterator for Iter<'map, K, V, N> {
56  type Item = EntryRef<'map, K, V, N>;
57
58  /// Seeks the least key strictly greater than the previous result.
59  fn next(&mut self) -> Option<Self::Item> {
60    if self.finished {
61      return None;
62    }
63
64    let candidate = match &self.last {
65      None => self.tree.first_entry(),
66      Some(last) => self.tree.entry_at_or_after(last.get(), false),
67    };
68    let Some((guard, index)) = candidate else {
69      self.finished = true;
70      return None;
71    };
72
73    self.last = Some(clone_key(&guard, index));
74    Some(EntryRef::new(guard, index))
75  }
76
77  fn size_hint(&self) -> (usize, Option<usize>) {
78    // Concurrent insertions mean no stable finite upper bound can be promised.
79    (0, None)
80  }
81}
82
83impl<K: Ord, V, const N: usize> FusedIterator for Iter<'_, K, V, N> {}
84
85/// An immutable ascending iterator over a bounded key range.
86///
87/// Items and concurrency semantics are the same as for [`Iter`]. The supplied
88/// range object is stored by value, so both owned bounds and borrowed bounds
89/// are supported without cloning `K` or the borrowed lookup type `Q`.
90pub struct Range<
91  'map,
92  K,
93  V,
94  Q: ?Sized,
95  R,
96  const N: usize = DEFAULT_PAGE_CAPACITY,
97> {
98  /// Tree being traversed.
99  tree: &'map Tree<K, V, N>,
100  /// User-provided start and end bounds.
101  bounds: R,
102  /// Last key returned after the initial bound lookup.
103  last: Option<KeyHandle<K>>,
104  /// Whether the start bound has already been applied.
105  started: bool,
106  /// Sticky exhaustion marker.
107  finished: bool,
108  /// Records the borrowed lookup type without owning one.
109  _query: PhantomData<fn(&Q)>,
110}
111
112impl<'map, K, V, Q: Ord + ?Sized, R, const N: usize>
113  Range<'map, K, V, Q, R, N>
114where
115  R: RangeBounds<Q>,
116{
117  /// Validates and stores a range cursor.
118  pub(crate) fn new(map: &'map BLinkMap<K, V, N>, bounds: R) -> Self {
119    validate_bounds::<Q, R>(&bounds);
120    Self {
121      tree: &map.tree,
122      bounds,
123      last: None,
124      started: false,
125      finished: false,
126      _query: PhantomData,
127    }
128  }
129}
130
131impl<'map, K, V, Q, R, const N: usize> Iterator
132  for Range<'map, K, V, Q, R, N>
133where
134  K: Ord + Borrow<Q>,
135  Q: Ord + ?Sized,
136  R: RangeBounds<Q>,
137{
138  type Item = EntryRef<'map, K, V, N>;
139
140  /// Applies the start bound once, then re-seeks after each returned key.
141  fn next(&mut self) -> Option<Self::Item> {
142    if self.finished {
143      return None;
144    }
145
146    let candidate = if !self.started {
147      self.started = true;
148      match self.bounds.start_bound() {
149        Bound::Unbounded => self.tree.first_entry(),
150        Bound::Included(start) => self.tree.entry_at_or_after(start, true),
151        Bound::Excluded(start) => self.tree.entry_at_or_after(start, false),
152      }
153    } else {
154      let last = self
155        .last
156        .as_ref()
157        .expect("a started, unfinished range has returned a key");
158      self.tree.entry_at_or_after::<K>(last.get(), false)
159    };
160
161    let Some((guard, index)) = candidate else {
162      self.finished = true;
163      return None;
164    };
165
166    let key = clone_key(&guard, index);
167    if !inside_end_bound::<K, Q, R>(&key, &self.bounds) {
168      self.finished = true;
169      return None;
170    }
171
172    self.last = Some(key);
173    Some(EntryRef::new(guard, index))
174  }
175
176  fn size_hint(&self) -> (usize, Option<usize>) {
177    (0, None)
178  }
179}
180
181impl<K, V, Q, R, const N: usize> FusedIterator for Range<'_, K, V, Q, R, N>
182where
183  K: Ord + Borrow<Q>,
184  Q: Ord + ?Sized,
185  R: RangeBounds<Q>,
186{
187}
188
189/// A read guard exposing only the key half of one map record.
190#[must_use = "the key's leaf remains read-locked while this guard is held"]
191pub struct KeyRef<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
192  /// Full record guard supplying the page latch and key reference.
193  entry: EntryRef<'map, K, V, N>,
194}
195
196impl<K, V, const N: usize> KeyRef<'_, K, V, N> {
197  /// Wraps a full entry guard without acquiring another latch.
198  fn new(entry: EntryRef<'_, K, V, N>) -> KeyRef<'_, K, V, N> {
199    KeyRef { entry }
200  }
201
202  /// Returns the guarded key.
203  pub fn get(&self) -> &K {
204    self.entry.key()
205  }
206}
207
208impl<K, V, const N: usize> Deref for KeyRef<'_, K, V, N> {
209  type Target = K;
210
211  fn deref(&self) -> &K {
212    self.get()
213  }
214}
215
216impl<K: fmt::Debug, V, const N: usize> fmt::Debug for KeyRef<'_, K, V, N> {
217  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
218    self.get().fmt(formatter)
219  }
220}
221
222/// A read guard exposing the value and its associated key.
223#[must_use = "the value's leaf remains read-locked while this guard is held"]
224pub struct ValueRef<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
225  /// Full record guard supplying the page latch and references.
226  entry: EntryRef<'map, K, V, N>,
227}
228
229impl<K, V, const N: usize> ValueRef<'_, K, V, N> {
230  /// Wraps a full entry guard without acquiring another latch.
231  fn new(entry: EntryRef<'_, K, V, N>) -> ValueRef<'_, K, V, N> {
232    ValueRef { entry }
233  }
234
235  /// Returns the key associated with this value.
236  pub fn key(&self) -> &K {
237    self.entry.key()
238  }
239
240  /// Returns the guarded value.
241  pub fn get(&self) -> &V {
242    self.entry.value()
243  }
244}
245
246impl<K, V, const N: usize> Deref for ValueRef<'_, K, V, N> {
247  type Target = V;
248
249  fn deref(&self) -> &V {
250    self.get()
251  }
252}
253
254impl<K, V: fmt::Debug, const N: usize> fmt::Debug for ValueRef<'_, K, V, N> {
255  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
256    self.get().fmt(formatter)
257  }
258}
259
260/// An ascending iterator over guarded map keys.
261pub struct Keys<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
262  /// Underlying full-record iterator.
263  inner: Iter<'map, K, V, N>,
264}
265
266impl<'map, K, V, const N: usize> Keys<'map, K, V, N> {
267  /// Creates a key adapter around a full iterator.
268  pub(crate) fn new(map: &'map BLinkMap<K, V, N>) -> Self {
269    Self {
270      inner: Iter::new(map),
271    }
272  }
273}
274
275impl<'map, K: Ord, V, const N: usize> Iterator for Keys<'map, K, V, N> {
276  type Item = KeyRef<'map, K, V, N>;
277
278  fn next(&mut self) -> Option<Self::Item> {
279    self.inner.next().map(KeyRef::new)
280  }
281
282  fn size_hint(&self) -> (usize, Option<usize>) {
283    self.inner.size_hint()
284  }
285}
286
287impl<K: Ord, V, const N: usize> FusedIterator for Keys<'_, K, V, N> {}
288
289/// An ascending iterator over guarded map values.
290pub struct Values<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
291  /// Underlying full-record iterator.
292  inner: Iter<'map, K, V, N>,
293}
294
295impl<'map, K, V, const N: usize> Values<'map, K, V, N> {
296  /// Creates a value adapter around a full iterator.
297  pub(crate) fn new(map: &'map BLinkMap<K, V, N>) -> Self {
298    Self {
299      inner: Iter::new(map),
300    }
301  }
302}
303
304impl<'map, K: Ord, V, const N: usize> Iterator for Values<'map, K, V, N> {
305  type Item = ValueRef<'map, K, V, N>;
306
307  fn next(&mut self) -> Option<Self::Item> {
308    self.inner.next().map(ValueRef::new)
309  }
310
311  fn size_hint(&self) -> (usize, Option<usize>) {
312    self.inner.size_hint()
313  }
314}
315
316impl<K: Ord, V, const N: usize> FusedIterator for Values<'_, K, V, N> {}
317
318/// Clones the shared key handle at a stable leaf index.
319fn clone_key<K, V, const N: usize>(
320  guard: &NodeReadGuard<K, V, N>,
321  index: usize,
322) -> KeyHandle<K> {
323  match &guard.kind {
324    NodeKind::Leaf(leaf) => leaf.entries[index].key.clone(),
325    NodeKind::Internal(_) | NodeKind::Redirect(_) => {
326      unreachable!("an iterator candidate must be a leaf record")
327    },
328  }
329}
330
331/// Enforces the same invalid-range panic conditions as standard ordered maps.
332fn validate_bounds<Q: Ord + ?Sized, R: RangeBounds<Q>>(bounds: &R) {
333  let (start, end) = match (bounds.start_bound(), bounds.end_bound()) {
334    (Bound::Included(start), Bound::Included(end))
335    | (Bound::Included(start), Bound::Excluded(end))
336    | (Bound::Excluded(start), Bound::Included(end))
337    | (Bound::Excluded(start), Bound::Excluded(end)) => (start, end),
338    (Bound::Unbounded, _) | (_, Bound::Unbounded) => return,
339  };
340
341  assert!(start <= end, "range start is greater than range end");
342  assert!(
343    start != end
344      || !matches!(bounds.start_bound(), Bound::Excluded(_))
345      || !matches!(bounds.end_bound(), Bound::Excluded(_)),
346    "range start and end are equal and excluded"
347  );
348}
349
350/// Tests a candidate key against a range's upper bound.
351fn inside_end_bound<K, Q, R>(key: &KeyHandle<K>, bounds: &R) -> bool
352where
353  K: Borrow<Q>,
354  Q: Ord + ?Sized,
355  R: RangeBounds<Q>,
356{
357  match bounds.end_bound() {
358    Bound::Unbounded => true,
359    Bound::Included(end) => key.get().borrow().cmp(end) != Ordering::Greater,
360    Bound::Excluded(end) => key.get().borrow().cmp(end) == Ordering::Less,
361  }
362}
363
364#[cfg(test)]
365mod tests {
366  use std::{
367    ops::Bound,
368    sync::{Arc, Barrier},
369    thread,
370  };
371
372  use crate::BLinkMap;
373
374  #[test]
375  fn iteration_remains_sorted_after_splits_and_merges() {
376    let map = BLinkMap::<u64, u64, 3>::new();
377    for key in 0..1_000 {
378      map.insert(key, key * 10);
379    }
380    for key in (0..1_000).step_by(3) {
381      map.remove(&key);
382    }
383
384    let mut previous = None;
385    let mut count = 0;
386    for entry in &map {
387      if let Some(previous) = previous {
388        assert!(previous < *entry.key());
389      }
390      assert_eq!(*entry.value(), *entry.key() * 10);
391      assert_ne!(*entry.key() % 3, 0);
392      previous = Some(*entry.key());
393      count += 1;
394    }
395    assert_eq!(count, map.len());
396  }
397
398  #[test]
399  fn ranges_honor_owned_borrowed_and_unbounded_endpoints() {
400    let map = BLinkMap::<String, usize, 4>::new();
401    for (key, value) in [
402      ("alpha", 1),
403      ("bravo", 2),
404      ("charlie", 3),
405      ("delta", 4),
406      ("echo", 5),
407    ] {
408      map.insert(String::from(key), value);
409    }
410
411    let mut range = map
412      .range::<str, _>((Bound::Included("bravo"), Bound::Included("delta")));
413    assert_eq!(range.next().unwrap().key(), "bravo");
414    assert_eq!(range.next().unwrap().key(), "charlie");
415    assert_eq!(range.next().unwrap().key(), "delta");
416    assert!(range.next().is_none());
417
418    let mut range =
419      map.range::<str, _>((Bound::Excluded("bravo"), Bound::Unbounded));
420    assert_eq!(range.next().unwrap().key(), "charlie");
421  }
422
423  #[test]
424  #[should_panic(expected = "range start is greater")]
425  fn inverted_range_panics() {
426    let map = BLinkMap::<u64, (), 3>::new();
427    let start = 9;
428    let end = 3;
429    let _ = map.range(start..end);
430  }
431
432  #[test]
433  fn concurrent_iterator_is_monotonic_while_pages_change() {
434    let map = Arc::new(BLinkMap::<u64, u64, 5>::new());
435    for key in 0..2_000 {
436      map.insert(key * 2, key);
437    }
438
439    let start = Arc::new(Barrier::new(2));
440    let writer_map = Arc::clone(&map);
441    let writer_start = Arc::clone(&start);
442    let writer = thread::spawn(move || {
443      writer_start.wait();
444      for key in 0..2_000 {
445        writer_map.insert(key * 2 + 1, key);
446      }
447      for key in (0..4_000).step_by(4) {
448        writer_map.remove(&key);
449      }
450    });
451
452    start.wait();
453    let mut previous = None;
454    for entry in map.iter() {
455      if let Some(previous) = previous {
456        assert!(previous < *entry.key());
457      }
458      previous = Some(*entry.key());
459    }
460
461    writer.join().unwrap();
462    map.assert_valid();
463  }
464}