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
17pub struct Iter<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
36 tree: &'map Tree<K, V, N>,
38 last: Option<KeyHandle<K>>,
40 finished: bool,
42}
43
44impl<'map, K, V, const N: usize> Iter<'map, K, V, N> {
45 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 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 (0, None)
80 }
81}
82
83impl<K: Ord, V, const N: usize> FusedIterator for Iter<'_, K, V, N> {}
84
85pub struct Range<
91 'map,
92 K,
93 V,
94 Q: ?Sized,
95 R,
96 const N: usize = DEFAULT_PAGE_CAPACITY,
97> {
98 tree: &'map Tree<K, V, N>,
100 bounds: R,
102 last: Option<KeyHandle<K>>,
104 started: bool,
106 finished: bool,
108 _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 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 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#[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 entry: EntryRef<'map, K, V, N>,
194}
195
196impl<K, V, const N: usize> KeyRef<'_, K, V, N> {
197 fn new(entry: EntryRef<'_, K, V, N>) -> KeyRef<'_, K, V, N> {
199 KeyRef { entry }
200 }
201
202 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#[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 entry: EntryRef<'map, K, V, N>,
227}
228
229impl<K, V, const N: usize> ValueRef<'_, K, V, N> {
230 fn new(entry: EntryRef<'_, K, V, N>) -> ValueRef<'_, K, V, N> {
232 ValueRef { entry }
233 }
234
235 pub fn key(&self) -> &K {
237 self.entry.key()
238 }
239
240 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
260pub struct Keys<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
262 inner: Iter<'map, K, V, N>,
264}
265
266impl<'map, K, V, const N: usize> Keys<'map, K, V, N> {
267 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
289pub struct Values<'map, K, V, const N: usize = DEFAULT_PAGE_CAPACITY> {
291 inner: Iter<'map, K, V, N>,
293}
294
295impl<'map, K, V, const N: usize> Values<'map, K, V, N> {
296 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
318fn 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
331fn 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
350fn 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}