clt_database/skiplist/set.rs
1//! A set based on a lock-free skip list. See [`SkipSet`].
2
3use core::{
4 fmt,
5 ops::{Bound, Deref, RangeBounds},
6};
7
8use super::{
9 base::SkiplistAllocator,
10 comparator::{BasicComparator, Comparator},
11 map,
12};
13use crate::alloc::{TryReserveError, TursoAllocator};
14
15/// A set based on a lock-free skip list.
16///
17/// This is an alternative to [`BTreeSet`] which supports
18/// concurrent access across multiple threads.
19///
20/// A custom comparator may be provided, causing all
21/// elements to be ordered by the comparison function used
22/// instead of the standard `Ord` impl. See [`Comparator`].
23///
24/// [`BTreeSet`]: std::collections::BTreeSet
25/// [`Comparator`]: super::comparator::Comparator
26pub struct SkipSet<T, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> {
27 inner: map::SkipMap<T, (), C, A>,
28}
29
30impl<T> SkipSet<T> {
31 /// Returns a new, empty set with the default comparator.
32 ///
33 /// # Example
34 ///
35 /// ```
36 /// use turso_core::skiplist::SkipSet;
37 ///
38 /// let set: SkipSet<i32> = SkipSet::new();
39 /// ```
40 pub fn new() -> Self {
41 Self {
42 inner: map::SkipMap::new(),
43 }
44 }
45}
46
47impl<T, A: SkiplistAllocator> SkipSet<T, BasicComparator, A> {
48 /// Returns a new, empty set with the default comparator that allocates its
49 /// nodes in `alloc`.
50 ///
51 /// # Example
52 ///
53 /// ```
54 /// use turso_core::alloc::TursoAllocator;
55 /// use turso_core::skiplist::SkipSet;
56 ///
57 /// let set: SkipSet<i32, _, TursoAllocator> = SkipSet::new_in(TursoAllocator);
58 /// ```
59 pub fn new_in(alloc: A) -> Self {
60 Self {
61 inner: map::SkipMap::new_in(alloc),
62 }
63 }
64}
65
66impl<T, C> SkipSet<T, C> {
67 /// Returns a new, empty set with the given comparator.
68 ///
69 /// # Example
70 ///
71 /// ```
72 /// use turso_core::skiplist::{SkipSet, comparator::BasicComparator};
73 ///
74 /// let set: SkipSet<i32> = SkipSet::with_comparator(BasicComparator);
75 /// ```
76 pub fn with_comparator(comparator: C) -> Self {
77 Self {
78 inner: map::SkipMap::with_comparator(comparator),
79 }
80 }
81}
82
83impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A> {
84 /// Returns a new, empty set with the given comparator that allocates its
85 /// nodes in `alloc`.
86 ///
87 /// # Example
88 ///
89 /// ```
90 /// use turso_core::alloc::TursoAllocator;
91 /// use turso_core::skiplist::{SkipSet, comparator::BasicComparator};
92 ///
93 /// let set: SkipSet<i32, _, TursoAllocator> =
94 /// SkipSet::with_comparator_in(BasicComparator, TursoAllocator);
95 /// ```
96 pub fn with_comparator_in(comparator: C, alloc: A) -> Self {
97 Self {
98 inner: map::SkipMap::with_comparator_in(comparator, alloc),
99 }
100 }
101
102 /// Returns `true` if the set is empty.
103 ///
104 /// # Example
105 ///
106 /// ```
107 /// use turso_core::skiplist::SkipSet;
108 ///
109 /// let set = SkipSet::new();
110 /// assert!(set.is_empty());
111 ///
112 /// set.insert(1);
113 /// assert!(!set.is_empty());
114 /// ```
115 pub fn is_empty(&self) -> bool {
116 self.inner.is_empty()
117 }
118
119 /// Returns the number of entries in the set.
120 ///
121 /// If the set is being concurrently modified, consider the returned number just an
122 /// approximation without any guarantees.
123 ///
124 /// # Example
125 ///
126 /// ```
127 /// use turso_core::skiplist::SkipSet;
128 ///
129 /// let set = SkipSet::new();
130 /// assert_eq!(set.len(), 0);
131 ///
132 /// set.insert(1);
133 /// assert_eq!(set.len(), 1);
134 /// ```
135 pub fn len(&self) -> usize {
136 self.inner.len()
137 }
138}
139
140impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A>
141where
142 C: Comparator<T>,
143{
144 /// Returns the entry with the smallest key.
145 ///
146 /// # Example
147 ///
148 /// ```
149 /// use turso_core::skiplist::SkipSet;
150 ///
151 /// let set = SkipSet::new();
152 /// set.insert(1);
153 /// assert_eq!(*set.front().unwrap(), 1);
154 /// set.insert(2);
155 /// assert_eq!(*set.front().unwrap(), 1);
156 /// ```
157 pub fn front(&self) -> Option<Entry<'_, T, C, A>> {
158 self.inner.front().map(Entry::new)
159 }
160
161 /// Returns the entry with the largest key.
162 ///
163 /// # Example
164 ///
165 /// ```
166 /// use turso_core::skiplist::SkipSet;
167 ///
168 /// let set = SkipSet::new();
169 /// set.insert(1);
170 /// assert_eq!(*set.back().unwrap(), 1);
171 /// set.insert(2);
172 /// assert_eq!(*set.back().unwrap(), 2);
173 /// ```
174 pub fn back(&self) -> Option<Entry<'_, T, C, A>> {
175 self.inner.back().map(Entry::new)
176 }
177
178 /// Returns `true` if the set contains a value for the specified key.
179 ///
180 /// # Example
181 ///
182 /// ```
183 /// use turso_core::skiplist::SkipSet;
184 ///
185 /// let set: SkipSet<_> = (1..=3).collect();
186 /// assert!(set.contains(&1));
187 /// assert!(!set.contains(&4));
188 /// ```
189 pub fn contains<Q>(&self, key: &Q) -> bool
190 where
191 C: Comparator<T, Q>,
192 Q: ?Sized,
193 {
194 self.inner.contains_key(key)
195 }
196
197 /// Returns an entry with the specified `key`.
198 ///
199 /// # Example
200 ///
201 /// ```
202 /// use turso_core::skiplist::SkipSet;
203 ///
204 /// let set: SkipSet<_> = (1..=3).collect();
205 /// assert_eq!(*set.get(&3).unwrap(), 3);
206 /// assert!(set.get(&4).is_none());
207 /// ```
208 pub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, T, C, A>>
209 where
210 C: Comparator<T, Q>,
211 Q: ?Sized,
212 {
213 self.inner.get(key).map(Entry::new)
214 }
215
216 /// Returns an `Entry` pointing to the lowest element whose key is above
217 /// the given bound. If no such element is found then `None` is
218 /// returned.
219 ///
220 /// # Example
221 ///
222 /// ```
223 /// use turso_core::skiplist::SkipSet;
224 /// use std::ops::Bound::*;
225 ///
226 /// let set = SkipSet::new();
227 /// set.insert(6);
228 /// set.insert(7);
229 /// set.insert(12);
230 ///
231 /// let greater_than_five = set.lower_bound(Excluded(&5)).unwrap();
232 /// assert_eq!(*greater_than_five, 6);
233 ///
234 /// let greater_than_six = set.lower_bound(Excluded(&6)).unwrap();
235 /// assert_eq!(*greater_than_six, 7);
236 ///
237 /// let greater_than_thirteen = set.lower_bound(Excluded(&13));
238 /// assert!(greater_than_thirteen.is_none());
239 /// ```
240 pub fn lower_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T, C, A>>
241 where
242 C: Comparator<T, Q>,
243 Q: ?Sized,
244 {
245 self.inner.lower_bound(bound).map(Entry::new)
246 }
247
248 /// Returns an `Entry` pointing to the highest element whose key is below
249 /// the given bound. If no such element is found then `None` is
250 /// returned.
251 ///
252 /// # Example
253 ///
254 /// ```
255 /// use turso_core::skiplist::SkipSet;
256 /// use std::ops::Bound::*;
257 ///
258 /// let set = SkipSet::new();
259 /// set.insert(6);
260 /// set.insert(7);
261 /// set.insert(12);
262 ///
263 /// let less_than_eight = set.upper_bound(Excluded(&8)).unwrap();
264 /// assert_eq!(*less_than_eight, 7);
265 ///
266 /// let less_than_six = set.upper_bound(Excluded(&6));
267 /// assert!(less_than_six.is_none());
268 /// ```
269 pub fn upper_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T, C, A>>
270 where
271 C: Comparator<T, Q>,
272 Q: ?Sized,
273 {
274 self.inner.upper_bound(bound).map(Entry::new)
275 }
276
277 /// Finds an entry with the specified key, or inserts a new `key`-`value` pair if none exist.
278 ///
279 /// # Example
280 ///
281 /// ```
282 /// use turso_core::skiplist::SkipSet;
283 ///
284 /// let set = SkipSet::new();
285 /// let entry = set.get_or_insert(2);
286 /// assert_eq!(*entry, 2);
287 /// ```
288 pub fn get_or_insert(&self, key: T) -> Entry<'_, T, C, A> {
289 Entry::new(self.inner.get_or_insert(key, ()))
290 }
291
292 /// Fallible version of [`get_or_insert`](Self::get_or_insert): returns an error instead of
293 /// aborting the process when node allocation fails.
294 ///
295 /// On error the set is unchanged and `key` is dropped.
296 ///
297 /// # Example
298 ///
299 /// ```
300 /// use turso_core::skiplist::SkipSet;
301 ///
302 /// let set = SkipSet::new();
303 /// let entry = set.try_get_or_insert(2).unwrap();
304 /// assert_eq!(*entry, 2);
305 /// ```
306 pub fn try_get_or_insert(&self, key: T) -> Result<Entry<'_, T, C, A>, TryReserveError> {
307 self.inner.try_get_or_insert(key, ()).map(Entry::new)
308 }
309
310 /// Returns an iterator over all entries in the set.
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// use turso_core::skiplist::SkipSet;
316 ///
317 /// let set = SkipSet::new();
318 /// set.insert(6);
319 /// set.insert(7);
320 /// set.insert(12);
321 ///
322 /// let mut set_iter = set.iter();
323 /// assert_eq!(*set_iter.next().unwrap(), 6);
324 /// assert_eq!(*set_iter.next().unwrap(), 7);
325 /// assert_eq!(*set_iter.next().unwrap(), 12);
326 /// assert!(set_iter.next().is_none());
327 /// ```
328 pub fn iter(&self) -> Iter<'_, T, C, A> {
329 Iter {
330 inner: self.inner.iter(),
331 }
332 }
333
334 /// Returns an iterator over a subset of entries in the set.
335 ///
336 /// # Example
337 ///
338 /// ```
339 /// use turso_core::skiplist::SkipSet;
340 ///
341 /// let set = SkipSet::new();
342 /// set.insert(6);
343 /// set.insert(7);
344 /// set.insert(12);
345 ///
346 /// let mut set_range = set.range(5..=8);
347 /// assert_eq!(*set_range.next().unwrap(), 6);
348 /// assert_eq!(*set_range.next().unwrap(), 7);
349 /// assert!(set_range.next().is_none());
350 /// ```
351 pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, T, C, A>
352 where
353 R: RangeBounds<Q>,
354 C: Comparator<T, Q>,
355 Q: ?Sized,
356 {
357 Range {
358 inner: self.inner.range(range),
359 }
360 }
361}
362
363impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A>
364where
365 C: Comparator<T>,
366 T: Send + 'static,
367{
368 /// Inserts a `key`-`value` pair into the set and returns the new entry.
369 ///
370 /// If there is an existing entry with this key, it will be removed before inserting the new
371 /// one.
372 ///
373 /// # Example
374 ///
375 /// ```
376 /// use turso_core::skiplist::SkipSet;
377 ///
378 /// let set = SkipSet::new();
379 /// set.insert(2);
380 /// assert_eq!(*set.get(&2).unwrap(), 2);
381 /// ```
382 pub fn insert(&self, key: T) -> Entry<'_, T, C, A> {
383 Entry::new(self.inner.insert(key, ()))
384 }
385
386 /// Fallible version of [`insert`](Self::insert): returns an error instead of aborting the
387 /// process when node allocation fails.
388 ///
389 /// On error the set is unchanged and `key` is dropped.
390 ///
391 /// # Example
392 ///
393 /// ```
394 /// use turso_core::skiplist::SkipSet;
395 ///
396 /// let set = SkipSet::new();
397 /// set.try_insert(2).unwrap();
398 /// assert_eq!(*set.get(&2).unwrap(), 2);
399 /// ```
400 pub fn try_insert(&self, key: T) -> Result<Entry<'_, T, C, A>, TryReserveError> {
401 self.inner.try_insert(key, ()).map(Entry::new)
402 }
403
404 /// Removes an entry with the specified key from the set and returns it.
405 ///
406 /// The value will not actually be dropped until all references to it have gone
407 /// out of scope.
408 ///
409 /// # Example
410 ///
411 /// ```
412 /// use turso_core::skiplist::SkipSet;
413 ///
414 /// let set = SkipSet::new();
415 /// set.insert(2);
416 /// assert_eq!(*set.remove(&2).unwrap(), 2);
417 /// assert!(set.remove(&2).is_none());
418 /// ```
419 pub fn remove<Q>(&self, key: &Q) -> Option<Entry<'_, T, C, A>>
420 where
421 C: Comparator<T, Q>,
422 Q: ?Sized,
423 {
424 self.inner.remove(key).map(Entry::new)
425 }
426
427 /// Removes an entry from the front of the set.
428 /// Returns the removed entry.
429 ///
430 /// The value will not actually be dropped until all references to it have gone
431 /// out of scope.
432 ///
433 /// # Example
434 ///
435 /// ```
436 /// use turso_core::skiplist::SkipSet;
437 ///
438 /// let set = SkipSet::new();
439 /// set.insert(1);
440 /// set.insert(2);
441 ///
442 /// assert_eq!(*set.pop_front().unwrap(), 1);
443 /// assert_eq!(*set.pop_front().unwrap(), 2);
444 ///
445 /// // All entries have been removed now.
446 /// assert!(set.is_empty());
447 /// ```
448 pub fn pop_front(&self) -> Option<Entry<'_, T, C, A>> {
449 self.inner.pop_front().map(Entry::new)
450 }
451
452 /// Removes an entry from the back of the set.
453 /// Returns the removed entry.
454 ///
455 /// The value will not actually be dropped until all references to it have gone
456 /// out of scope.
457 ///
458 /// # Example
459 ///
460 /// ```
461 /// use turso_core::skiplist::SkipSet;
462 ///
463 /// let set = SkipSet::new();
464 /// set.insert(1);
465 /// set.insert(2);
466 ///
467 /// assert_eq!(*set.pop_back().unwrap(), 2);
468 /// assert_eq!(*set.pop_back().unwrap(), 1);
469 ///
470 /// // All entries have been removed now.
471 /// assert!(set.is_empty());
472 /// ```
473 pub fn pop_back(&self) -> Option<Entry<'_, T, C, A>> {
474 self.inner.pop_back().map(Entry::new)
475 }
476
477 /// Iterates over the set and removes every entry.
478 ///
479 /// # Example
480 ///
481 /// ```
482 /// use turso_core::skiplist::SkipSet;
483 ///
484 /// let set = SkipSet::new();
485 /// set.insert(1);
486 /// set.insert(2);
487 ///
488 /// set.clear();
489 /// assert!(set.is_empty());
490 /// ```
491 pub fn clear(&self) {
492 self.inner.clear();
493 }
494}
495
496impl<T, C> Default for SkipSet<T, C>
497where
498 C: Default,
499{
500 fn default() -> Self {
501 Self::with_comparator(Default::default())
502 }
503}
504
505impl<T, C, A: SkiplistAllocator> fmt::Debug for SkipSet<T, C, A>
506where
507 C: Comparator<T>,
508 T: fmt::Debug,
509{
510 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
511 f.pad("SkipSet { .. }")
512 }
513}
514
515impl<T, C, A: SkiplistAllocator> IntoIterator for SkipSet<T, C, A> {
516 type Item = T;
517 type IntoIter = IntoIter<T, A>;
518
519 fn into_iter(self) -> Self::IntoIter {
520 IntoIter {
521 inner: self.inner.into_iter(),
522 }
523 }
524}
525
526impl<'a, T, C, A: SkiplistAllocator> IntoIterator for &'a SkipSet<T, C, A>
527where
528 C: Comparator<T>,
529{
530 type Item = Entry<'a, T, C, A>;
531 type IntoIter = Iter<'a, T, C, A>;
532
533 fn into_iter(self) -> Self::IntoIter {
534 self.iter()
535 }
536}
537
538impl<T, C> FromIterator<T> for SkipSet<T, C>
539where
540 C: Comparator<T> + Default,
541{
542 fn from_iter<I>(iter: I) -> Self
543 where
544 I: IntoIterator<Item = T>,
545 {
546 let s = Self::default();
547 for t in iter {
548 s.get_or_insert(t);
549 }
550 s
551 }
552}
553
554/// A reference-counted entry in a set.
555pub struct Entry<'a, T, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> {
556 inner: map::Entry<'a, T, (), C, A>,
557}
558
559impl<'a, T, C, A: SkiplistAllocator> Entry<'a, T, C, A> {
560 fn new(inner: map::Entry<'a, T, (), C, A>) -> Self {
561 Self { inner }
562 }
563
564 /// Returns a reference to the value.
565 pub fn value(&self) -> &'a T {
566 self.inner.key()
567 }
568
569 /// Returns `true` if the entry is removed from the set.
570 pub fn is_removed(&self) -> bool {
571 self.inner.is_removed()
572 }
573}
574
575impl<T, C, A: SkiplistAllocator> Entry<'_, T, C, A>
576where
577 C: Comparator<T>,
578{
579 /// Moves to the next entry in the set.
580 pub fn move_next(&mut self) -> bool {
581 self.inner.move_next()
582 }
583
584 /// Moves to the previous entry in the set.
585 pub fn move_prev(&mut self) -> bool {
586 self.inner.move_prev()
587 }
588
589 /// Returns the next entry in the set.
590 pub fn next(&self) -> Option<Self> {
591 self.inner.next().map(Entry::new)
592 }
593
594 /// Returns the previous entry in the set.
595 pub fn prev(&self) -> Option<Self> {
596 self.inner.prev().map(Entry::new)
597 }
598}
599
600impl<T, C, A: SkiplistAllocator> Entry<'_, T, C, A>
601where
602 C: Comparator<T>,
603 T: Send + 'static,
604{
605 /// Removes the entry from the set.
606 ///
607 /// Returns `true` if this call removed the entry and `false` if it was already removed.
608 pub fn remove(&self) -> bool {
609 self.inner.remove()
610 }
611}
612
613impl<T, C, A: SkiplistAllocator> Clone for Entry<'_, T, C, A> {
614 fn clone(&self) -> Self {
615 Self {
616 inner: self.inner.clone(),
617 }
618 }
619}
620
621impl<T, C, A: SkiplistAllocator> fmt::Debug for Entry<'_, T, C, A>
622where
623 T: fmt::Debug,
624{
625 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
626 f.debug_struct("Entry")
627 .field("value", self.value())
628 .finish()
629 }
630}
631
632impl<T, C, A: SkiplistAllocator> Deref for Entry<'_, T, C, A> {
633 type Target = T;
634
635 fn deref(&self) -> &Self::Target {
636 self.value()
637 }
638}
639
640/// An owning iterator over the entries of a `SkipSet`.
641pub struct IntoIter<T, A: SkiplistAllocator = TursoAllocator> {
642 inner: map::IntoIter<T, (), A>,
643}
644
645impl<T, A: SkiplistAllocator> Iterator for IntoIter<T, A> {
646 type Item = T;
647
648 fn next(&mut self) -> Option<Self::Item> {
649 self.inner.next().map(|(k, ())| k)
650 }
651}
652
653impl<T, A: SkiplistAllocator> fmt::Debug for IntoIter<T, A> {
654 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
655 f.pad("IntoIter { .. }")
656 }
657}
658
659/// An iterator over the entries of a `SkipSet`.
660pub struct Iter<'a, T, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> {
661 inner: map::Iter<'a, T, (), C, A>,
662}
663
664impl<'a, T, C, A: SkiplistAllocator> Iterator for Iter<'a, T, C, A>
665where
666 C: Comparator<T>,
667{
668 type Item = Entry<'a, T, C, A>;
669
670 fn next(&mut self) -> Option<Self::Item> {
671 self.inner.next().map(Entry::new)
672 }
673}
674
675impl<T, C, A: SkiplistAllocator> DoubleEndedIterator for Iter<'_, T, C, A>
676where
677 C: Comparator<T>,
678{
679 fn next_back(&mut self) -> Option<Self::Item> {
680 self.inner.next_back().map(Entry::new)
681 }
682}
683
684impl<T, C, A: SkiplistAllocator> fmt::Debug for Iter<'_, T, C, A> {
685 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
686 f.pad("Iter { .. }")
687 }
688}
689
690/// An iterator over a subset of entries of a `SkipSet`.
691pub struct Range<'a, Q, R, T, C = BasicComparator, A: SkiplistAllocator = TursoAllocator>
692where
693 C: Comparator<T> + Comparator<T, Q>,
694 R: RangeBounds<Q>,
695 Q: ?Sized,
696{
697 inner: map::Range<'a, Q, R, T, (), C, A>,
698}
699
700impl<'a, Q, R, T, C, A: SkiplistAllocator> Iterator for Range<'a, Q, R, T, C, A>
701where
702 C: Comparator<T> + Comparator<T, Q>,
703 R: RangeBounds<Q>,
704 Q: ?Sized,
705{
706 type Item = Entry<'a, T, C, A>;
707
708 fn next(&mut self) -> Option<Self::Item> {
709 self.inner.next().map(Entry::new)
710 }
711}
712
713impl<Q, R, T, C, A: SkiplistAllocator> DoubleEndedIterator for Range<'_, Q, R, T, C, A>
714where
715 C: Comparator<T> + Comparator<T, Q>,
716 R: RangeBounds<Q>,
717 Q: ?Sized,
718{
719 fn next_back(&mut self) -> Option<Self::Item> {
720 self.inner.next_back().map(Entry::new)
721 }
722}
723
724impl<Q, R, T, C, A: SkiplistAllocator> fmt::Debug for Range<'_, Q, R, T, C, A>
725where
726 C: Comparator<T> + Comparator<T, Q>,
727 T: fmt::Debug,
728 R: RangeBounds<Q> + fmt::Debug,
729 Q: ?Sized,
730{
731 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
732 f.debug_struct("Range")
733 .field("range", &self.inner.inner.range)
734 .field("head", &self.inner.inner.head.as_ref().map(|e| e.key()))
735 .field("tail", &self.inner.inner.tail.as_ref().map(|e| e.key()))
736 .finish()
737 }
738}