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
14pub struct BLinkSet<T, const N: usize = DEFAULT_PAGE_CAPACITY> {
25 map: BLinkMap<T, (), N>,
27}
28
29impl<T, const N: usize> BLinkSet<T, N> {
30 pub fn new() -> Self {
37 Self {
38 map: BLinkMap::new(),
39 }
40 }
41
42 pub fn len(&self) -> usize {
44 self.map.len()
45 }
46
47 pub fn is_empty(&self) -> bool {
49 self.map.is_empty()
50 }
51
52 pub fn clear(&mut self) {
54 self.map.clear();
55 }
56}
57
58impl<T: Ord, const N: usize> BLinkSet<T, N> {
59 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 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 pub fn insert(&self, value: T) -> bool {
79 self.map.insert(value, ()).is_none()
80 }
81
82 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 pub fn first(&self) -> Option<SetRef<'_, T, N>> {
98 self.map.first_key_value().map(SetRef::new)
99 }
100
101 pub fn last(&self) -> Option<SetRef<'_, T, N>> {
103 self.map.last_key_value().map(SetRef::new)
104 }
105
106 pub fn iter(&self) -> SetIter<'_, T, N> {
108 SetIter::new(self)
109 }
110
111 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 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 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 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 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 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 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 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#[must_use = "the set value's leaf remains read-locked while held"]
226pub struct SetRef<'set, T, const N: usize = DEFAULT_PAGE_CAPACITY> {
227 entry: EntryRef<'set, T, (), N>,
229}
230
231impl<T, const N: usize> SetRef<'_, T, N> {
232 fn new(entry: EntryRef<'_, T, (), N>) -> SetRef<'_, T, N> {
234 SetRef { entry }
235 }
236
237 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
257pub struct SetIter<'set, T, const N: usize = DEFAULT_PAGE_CAPACITY> {
259 inner: Iter<'set, T, (), N>,
261}
262
263impl<'set, T: Ord, const N: usize> SetIter<'set, T, N> {
264 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
286pub struct SetRange<
288 'set,
289 T,
290 Q: ?Sized,
291 R,
292 const N: usize = DEFAULT_PAGE_CAPACITY,
293> {
294 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 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}