Skip to main content

b_link/
set.rs

1use std::{
2  borrow::Borrow,
3  fmt,
4  iter::{FromIterator, FusedIterator},
5  ops::{Deref, RangeBounds},
6};
7
8use crate::{
9  iter::{Iter, Range},
10  map::{BLinkMap, DEFAULT_PAGE_CAPACITY},
11  EntryRef,
12};
13
14/// A concurrent ordered set backed by [`BLinkMap`].
15///
16/// Values are stored as map keys with zero-sized `()` payloads, so the set has
17/// the same page-latch concurrency, fence correction, split, merge, and memory
18/// reclamation behavior as the map. `N` is the maximum stable records or
19/// separators per page and defaults to [`DEFAULT_PAGE_CAPACITY`].
20///
21/// Lookup and iteration return [`SetRef`] guards rather than bare references.
22/// Each guard read-locks its whole leaf; drop it before a conflicting operation
23/// on the same part of the set.
24pub struct BLinkSet<T, const N: usize = DEFAULT_PAGE_CAPACITY> {
25  /// Map storage; unit values add no per-record payload bytes.
26  map: BLinkMap<T, (), N>,
27}
28
29impl<T, const N: usize> BLinkSet<T, N> {
30  /// Creates an empty set.
31  ///
32  /// # Panics
33  ///
34  /// Panics under the same invalid-capacity and allocation conditions as
35  /// [`BLinkMap::new`].
36  pub fn new() -> Self {
37    Self {
38      map: BLinkMap::new(),
39    }
40  }
41
42  /// Returns the number of values observed by the set's atomic counter.
43  pub fn len(&self) -> usize {
44    self.map.len()
45  }
46
47  /// Returns true when the set is empty at the instant it is observed.
48  pub fn is_empty(&self) -> bool {
49    self.map.is_empty()
50  }
51
52  /// Removes every value and restores one empty root leaf.
53  pub fn clear(&mut self) {
54    self.map.clear();
55  }
56}
57
58impl<T: Ord, const N: usize> BLinkSet<T, N> {
59  /// Returns true when an ordering-compatible borrowed value is present.
60  pub fn contains<Q>(&self, value: &Q) -> bool
61  where
62    T: Borrow<Q>,
63    Q: Ord + ?Sized,
64  {
65    self.map.contains_key(value)
66  }
67
68  /// Returns a guard for the stored value equal to `value`.
69  pub fn get<Q>(&self, value: &Q) -> Option<SetRef<'_, T, N>>
70  where
71    T: Borrow<Q>,
72    Q: Ord + ?Sized,
73  {
74    self.map.get(value).map(SetRef::new)
75  }
76
77  /// Inserts `value`, returning true only when it was not already present.
78  pub fn insert(&self, value: T) -> bool {
79    self.map.insert(value, ()).is_none()
80  }
81
82  /// Removes `value`, returning true only when a record was present.
83  ///
84  /// Deletion performs the map's complete borrow/merge/unlink/root-collapse
85  /// protocol; it does not leave empty non-root leaf pages behind. A removed
86  /// value that remains useful as a routing fence may keep its allocation alive
87  /// until that fence changes or the set is dropped.
88  pub fn remove<Q>(&self, value: &Q) -> bool
89  where
90    T: Borrow<Q>,
91    Q: Ord + ?Sized,
92  {
93    self.map.remove(value).is_some()
94  }
95
96  /// Returns a guard for the least value.
97  pub fn first(&self) -> Option<SetRef<'_, T, N>> {
98    self.map.first_key_value().map(SetRef::new)
99  }
100
101  /// Returns a guard for the greatest value.
102  pub fn last(&self) -> Option<SetRef<'_, T, N>> {
103    self.map.last_key_value().map(SetRef::new)
104  }
105
106  /// Returns a weakly consistent ascending iterator over guarded values.
107  pub fn iter(&self) -> SetIter<'_, T, N> {
108    SetIter::new(self)
109  }
110
111  /// Returns a weakly consistent ascending iterator over `bounds`.
112  ///
113  /// # Panics
114  ///
115  /// Panics for an inverted range or equal bounds that are both excluded.
116  pub fn range<Q, R>(&self, bounds: R) -> SetRange<'_, T, Q, R, N>
117  where
118    T: Borrow<Q>,
119    Q: Ord + ?Sized,
120    R: RangeBounds<Q>,
121  {
122    SetRange {
123      inner: self.map.range(bounds),
124    }
125  }
126
127  /// Returns true when this set and `other` share no value.
128  ///
129  /// Concurrent mutation makes this a weakly consistent traversal rather than
130  /// a transaction spanning both sets.
131  pub fn is_disjoint(&self, other: &Self) -> bool {
132    if std::ptr::eq(self, other) {
133      return self.is_empty();
134    }
135
136    let (smaller, larger) = if self.len() <= other.len() {
137      (self, other)
138    } else {
139      (other, self)
140    };
141
142    for value in smaller {
143      if larger.contains(value.get()) {
144        return false;
145      }
146    }
147    true
148  }
149
150  /// Returns true when every observed value in this set is in `other`.
151  ///
152  /// Concurrent mutation makes this a weakly consistent traversal rather than
153  /// an atomic relation between two sets.
154  pub fn is_subset(&self, other: &Self) -> bool {
155    if std::ptr::eq(self, other) {
156      return true;
157    }
158    if self.len() > other.len() {
159      return false;
160    }
161
162    for value in self {
163      if !other.contains(value.get()) {
164        return false;
165      }
166    }
167    true
168  }
169
170  /// Returns true when every observed value in `other` is in this set.
171  pub fn is_superset(&self, other: &Self) -> bool {
172    other.is_subset(self)
173  }
174}
175
176impl<T, const N: usize> Default for BLinkSet<T, N> {
177  fn default() -> Self {
178    Self::new()
179  }
180}
181
182impl<T: Ord, const N: usize> Extend<T> for BLinkSet<T, N> {
183  /// Inserts every value, ignoring duplicates.
184  fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I) {
185    for value in iterable {
186      self.insert(value);
187    }
188  }
189}
190
191impl<T: Ord, const N: usize> FromIterator<T> for BLinkSet<T, N> {
192  /// Builds a set from an arbitrary value iterator.
193  fn from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self {
194    let mut set = Self::new();
195    set.extend(iterable);
196    set
197  }
198}
199
200impl<T: Ord, const N: usize> PartialEq for BLinkSet<T, N> {
201  /// Compares weakly consistent ordered views of both sets.
202  fn eq(&self, other: &Self) -> bool {
203    std::ptr::eq(self, other)
204      || (self.len() == other.len() && self.is_subset(other))
205  }
206}
207
208impl<T: Ord, const N: usize> Eq for BLinkSet<T, N> {}
209
210impl<T: Ord + fmt::Debug, const N: usize> fmt::Debug for BLinkSet<T, N> {
211  /// Formats a weakly consistent ascending view of the set.
212  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
213    let mut debug = formatter.debug_set();
214    for value in self {
215      debug.entry(value.get());
216    }
217    debug.finish()
218  }
219}
220
221/// A read guard for one value stored in a [`BLinkSet`].
222///
223/// The guard owns the underlying map entry guard and therefore read-locks the
224/// entire leaf until it is dropped.
225#[must_use = "the set value's leaf remains read-locked while held"]
226pub struct SetRef<'set, T, const N: usize = DEFAULT_PAGE_CAPACITY> {
227  /// Unit-valued map record supplying the key reference and latch.
228  entry: EntryRef<'set, T, (), N>,
229}
230
231impl<T, const N: usize> SetRef<'_, T, N> {
232  /// Wraps the backing map's entry guard.
233  fn new(entry: EntryRef<'_, T, (), N>) -> SetRef<'_, T, N> {
234    SetRef { entry }
235  }
236
237  /// Returns the guarded set value.
238  pub fn get(&self) -> &T {
239    self.entry.key()
240  }
241}
242
243impl<T, const N: usize> Deref for SetRef<'_, T, N> {
244  type Target = T;
245
246  fn deref(&self) -> &T {
247    self.get()
248  }
249}
250
251impl<T: fmt::Debug, const N: usize> fmt::Debug for SetRef<'_, T, N> {
252  fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
253    self.get().fmt(formatter)
254  }
255}
256
257/// A weakly consistent ascending iterator over a [`BLinkSet`].
258pub struct SetIter<'set, T, const N: usize = DEFAULT_PAGE_CAPACITY> {
259  /// Backing map record iterator.
260  inner: Iter<'set, T, (), N>,
261}
262
263impl<'set, T: Ord, const N: usize> SetIter<'set, T, N> {
264  /// Creates a set adapter over the map iterator.
265  fn new(set: &'set BLinkSet<T, N>) -> Self {
266    Self {
267      inner: set.map.iter(),
268    }
269  }
270}
271
272impl<'set, T: Ord, const N: usize> Iterator for SetIter<'set, T, N> {
273  type Item = SetRef<'set, T, N>;
274
275  fn next(&mut self) -> Option<Self::Item> {
276    self.inner.next().map(SetRef::new)
277  }
278
279  fn size_hint(&self) -> (usize, Option<usize>) {
280    self.inner.size_hint()
281  }
282}
283
284impl<T: Ord, const N: usize> FusedIterator for SetIter<'_, T, N> {}
285
286/// A weakly consistent ascending iterator over a bounded set range.
287pub struct SetRange<
288  'set,
289  T,
290  Q: ?Sized,
291  R,
292  const N: usize = DEFAULT_PAGE_CAPACITY,
293> {
294  /// Backing map range iterator.
295  inner: Range<'set, T, (), Q, R, N>,
296}
297
298impl<'set, T, Q, R, const N: usize> Iterator for SetRange<'set, T, Q, R, N>
299where
300  T: Ord + Borrow<Q>,
301  Q: Ord + ?Sized,
302  R: RangeBounds<Q>,
303{
304  type Item = SetRef<'set, T, N>;
305
306  fn next(&mut self) -> Option<Self::Item> {
307    self.inner.next().map(SetRef::new)
308  }
309
310  fn size_hint(&self) -> (usize, Option<usize>) {
311    self.inner.size_hint()
312  }
313}
314
315impl<T, Q, R, const N: usize> FusedIterator for SetRange<'_, T, Q, R, N>
316where
317  T: Ord + Borrow<Q>,
318  Q: Ord + ?Sized,
319  R: RangeBounds<Q>,
320{
321}
322
323impl<'set, T: Ord, const N: usize> IntoIterator for &'set BLinkSet<T, N> {
324  type Item = SetRef<'set, T, N>;
325  type IntoIter = SetIter<'set, T, N>;
326
327  /// Creates the same guarded iterator as [`BLinkSet::iter`].
328  fn into_iter(self) -> Self::IntoIter {
329    self.iter()
330  }
331}
332
333#[cfg(test)]
334mod tests {
335  use std::{
336    sync::{Arc, Barrier},
337    thread,
338  };
339
340  use super::*;
341
342  #[test]
343  fn set_operations_ranges_and_relations() {
344    let set = BLinkSet::<u64, 3>::new();
345    for value in 0..100 {
346      assert!(set.insert(value));
347      assert!(!set.insert(value));
348    }
349
350    assert_eq!(set.first().map(|value| *value), Some(0));
351    assert_eq!(set.last().map(|value| *value), Some(99));
352
353    let mut expected = 20;
354    for value in set.range(20..30) {
355      assert_eq!(*value, expected);
356      expected += 1;
357    }
358    assert_eq!(expected, 30);
359
360    let evens = BLinkSet::<u64, 3>::new();
361    for value in (0..100).step_by(2) {
362      evens.insert(value);
363    }
364    assert!(evens.is_subset(&set));
365    assert!(set.is_superset(&evens));
366    assert!(!set.is_disjoint(&evens));
367
368    let distant = BLinkSet::<u64, 3>::new();
369    distant.insert(1_000);
370    assert!(set.is_disjoint(&distant));
371
372    for value in 0..100 {
373      assert!(set.remove(&value));
374    }
375    assert!(set.is_empty());
376    set.map.assert_valid();
377  }
378
379  #[test]
380  fn set_collect_extend_and_clear() {
381    let mut set: BLinkSet<u64, 4> = (0..50).collect();
382    set.extend(25..75);
383    assert_eq!(set.len(), 75);
384    assert!(format!("{set:?}").starts_with("{0, 1, 2"));
385    set.clear();
386    assert!(set.is_empty());
387  }
388
389  #[test]
390  fn concurrent_set_writers_split_and_merge() {
391    const THREADS: usize = 6;
392    const PER_THREAD: usize = 500;
393
394    let set = Arc::new(BLinkSet::<usize, 5>::new());
395    let start = Arc::new(Barrier::new(THREADS));
396    let workers = std::array::from_fn::<_, THREADS, _>(|thread_index| {
397      let set = Arc::clone(&set);
398      let start = Arc::clone(&start);
399      thread::spawn(move || {
400        start.wait();
401        for offset in 0..PER_THREAD {
402          assert!(set.insert(thread_index * PER_THREAD + offset));
403        }
404        for offset in (0..PER_THREAD).step_by(2) {
405          assert!(set.remove(&(thread_index * PER_THREAD + offset)));
406        }
407      })
408    });
409
410    for worker in workers {
411      worker.join().unwrap();
412    }
413
414    assert_eq!(set.len(), THREADS * PER_THREAD / 2);
415    set.map.assert_valid();
416  }
417}