Struct SkipSet 

pub struct SkipSet<T, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> { /* private fields */ }

A set based on a lock-free skip list.

This is an alternative to BTreeSet which supports concurrent access across multiple threads.

A custom comparator may be provided, causing all elements to be ordered by the comparison function used instead of the standard Ord impl. See Comparator.

Implementations

impl<T> SkipSet<T>

pub fn new() -> Self

Returns a new, empty set with the default comparator.

Example

use turso_core::skiplist::SkipSet;

let set: SkipSet<i32> = SkipSet::new();

impl<T, A: SkiplistAllocator> SkipSet<T, BasicComparator, A>

pub fn new_in(alloc: A) -> Self

Returns a new, empty set with the default comparator that allocates its nodes in alloc.

Example

use turso_core::alloc::TursoAllocator;
use turso_core::skiplist::SkipSet;

let set: SkipSet<i32, _, TursoAllocator> = SkipSet::new_in(TursoAllocator);

impl<T, C> SkipSet<T, C>

pub fn with_comparator(comparator: C) -> Self

Returns a new, empty set with the given comparator.

Example

use turso_core::skiplist::{SkipSet, comparator::BasicComparator};

let set: SkipSet<i32> = SkipSet::with_comparator(BasicComparator);

impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A>

pub fn with_comparator_in(comparator: C, alloc: A) -> Self

Returns a new, empty set with the given comparator that allocates its nodes in alloc.

Example

use turso_core::alloc::TursoAllocator;
use turso_core::skiplist::{SkipSet, comparator::BasicComparator};

let set: SkipSet<i32, _, TursoAllocator> =
    SkipSet::with_comparator_in(BasicComparator, TursoAllocator);

pub fn is_empty(&self) -> bool

Returns true if the set is empty.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
assert!(set.is_empty());

set.insert(1);
assert!(!set.is_empty());

pub fn len(&self) -> usize

Returns the number of entries in the set.

If the set is being concurrently modified, consider the returned number just an approximation without any guarantees.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
assert_eq!(set.len(), 0);

set.insert(1);
assert_eq!(set.len(), 1);

impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A>

where C: Comparator<T>,

pub fn front(&self) -> Option<Entry<'_, T, C, A>>

Returns the entry with the smallest key.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(1);
assert_eq!(*set.front().unwrap(), 1);
set.insert(2);
assert_eq!(*set.front().unwrap(), 1);

pub fn back(&self) -> Option<Entry<'_, T, C, A>>

Returns the entry with the largest key.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(1);
assert_eq!(*set.back().unwrap(), 1);
set.insert(2);
assert_eq!(*set.back().unwrap(), 2);

pub fn contains<Q>(&self, key: &Q) -> bool

where C: Comparator<T, Q>, Q: ?Sized,

Returns true if the set contains a value for the specified key.

Example

use turso_core::skiplist::SkipSet;

let set: SkipSet<_> = (1..=3).collect();
assert!(set.contains(&1));
assert!(!set.contains(&4));

pub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, T, C, A>>

where C: Comparator<T, Q>, Q: ?Sized,

Returns an entry with the specified key.

Example

use turso_core::skiplist::SkipSet;

let set: SkipSet<_> = (1..=3).collect();
assert_eq!(*set.get(&3).unwrap(), 3);
assert!(set.get(&4).is_none());

pub fn lower_bound<'a, Q>( &'a self, bound: Bound<&Q>, ) -> Option<Entry<'a, T, C, A>>

where C: Comparator<T, Q>, Q: ?Sized,

Returns an Entry pointing to the lowest element whose key is above the given bound. If no such element is found then None is returned.

Example

use turso_core::skiplist::SkipSet;
use std::ops::Bound::*;

let set = SkipSet::new();
set.insert(6);
set.insert(7);
set.insert(12);

let greater_than_five = set.lower_bound(Excluded(&5)).unwrap();
assert_eq!(*greater_than_five, 6);

let greater_than_six = set.lower_bound(Excluded(&6)).unwrap();
assert_eq!(*greater_than_six, 7);

let greater_than_thirteen = set.lower_bound(Excluded(&13));
assert!(greater_than_thirteen.is_none());

pub fn upper_bound<'a, Q>( &'a self, bound: Bound<&Q>, ) -> Option<Entry<'a, T, C, A>>

where C: Comparator<T, Q>, Q: ?Sized,

Returns an Entry pointing to the highest element whose key is below the given bound. If no such element is found then None is returned.

Example

use turso_core::skiplist::SkipSet;
use std::ops::Bound::*;

let set = SkipSet::new();
set.insert(6);
set.insert(7);
set.insert(12);

let less_than_eight = set.upper_bound(Excluded(&8)).unwrap();
assert_eq!(*less_than_eight, 7);

let less_than_six = set.upper_bound(Excluded(&6));
assert!(less_than_six.is_none());

pub fn get_or_insert(&self, key: T) -> Entry<'_, T, C, A>

Finds an entry with the specified key, or inserts a new key-value pair if none exist.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
let entry = set.get_or_insert(2);
assert_eq!(*entry, 2);

pub fn try_get_or_insert( &self, key: T, ) -> Result<Entry<'_, T, C, A>, TryReserveError>

Fallible version of get_or_insert: returns an error instead of aborting the process when node allocation fails.

On error the set is unchanged and key is dropped.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
let entry = set.try_get_or_insert(2).unwrap();
assert_eq!(*entry, 2);

pub fn iter(&self) -> Iter<'_, T, C, A>

Returns an iterator over all entries in the set.

Examples

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(6);
set.insert(7);
set.insert(12);

let mut set_iter = set.iter();
assert_eq!(*set_iter.next().unwrap(), 6);
assert_eq!(*set_iter.next().unwrap(), 7);
assert_eq!(*set_iter.next().unwrap(), 12);
assert!(set_iter.next().is_none());

pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, T, C, A>

where R: RangeBounds<Q>, C: Comparator<T, Q>, Q: ?Sized,

Returns an iterator over a subset of entries in the set.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(6);
set.insert(7);
set.insert(12);

let mut set_range = set.range(5..=8);
assert_eq!(*set_range.next().unwrap(), 6);
assert_eq!(*set_range.next().unwrap(), 7);
assert!(set_range.next().is_none());

impl<T, C, A: SkiplistAllocator> SkipSet<T, C, A>

where C: Comparator<T>, T: Send + 'static,

pub fn insert(&self, key: T) -> Entry<'_, T, C, A>

Inserts a key-value pair into the set and returns the new entry.

If there is an existing entry with this key, it will be removed before inserting the new one.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(2);
assert_eq!(*set.get(&2).unwrap(), 2);

pub fn try_insert(&self, key: T) -> Result<Entry<'_, T, C, A>, TryReserveError>

Fallible version of insert: returns an error instead of aborting the process when node allocation fails.

On error the set is unchanged and key is dropped.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.try_insert(2).unwrap();
assert_eq!(*set.get(&2).unwrap(), 2);

pub fn remove<Q>(&self, key: &Q) -> Option<Entry<'_, T, C, A>>

where C: Comparator<T, Q>, Q: ?Sized,

Removes an entry with the specified key from the set and returns it.

The value will not actually be dropped until all references to it have gone out of scope.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(2);
assert_eq!(*set.remove(&2).unwrap(), 2);
assert!(set.remove(&2).is_none());

pub fn pop_front(&self) -> Option<Entry<'_, T, C, A>>

Removes an entry from the front of the set. Returns the removed entry.

The value will not actually be dropped until all references to it have gone out of scope.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(1);
set.insert(2);

assert_eq!(*set.pop_front().unwrap(), 1);
assert_eq!(*set.pop_front().unwrap(), 2);

// All entries have been removed now.
assert!(set.is_empty());

pub fn pop_back(&self) -> Option<Entry<'_, T, C, A>>

Removes an entry from the back of the set. Returns the removed entry.

The value will not actually be dropped until all references to it have gone out of scope.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(1);
set.insert(2);

assert_eq!(*set.pop_back().unwrap(), 2);
assert_eq!(*set.pop_back().unwrap(), 1);

// All entries have been removed now.
assert!(set.is_empty());

pub fn clear(&self)

Iterates over the set and removes every entry.

Example

use turso_core::skiplist::SkipSet;

let set = SkipSet::new();
set.insert(1);
set.insert(2);

set.clear();
assert!(set.is_empty());

Trait Implementations

impl<T, C, A: SkiplistAllocator> Debug for SkipSet<T, C, A>

where C: Comparator<T>, T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, C> Default for SkipSet<T, C>

where C: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, C> FromIterator<T> for SkipSet<T, C>

where C: Comparator<T> + Default,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T, C, A: SkiplistAllocator> IntoIterator for SkipSet<T, C, A>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, C, A: SkiplistAllocator> IntoIterator for &'a SkipSet<T, C, A>

where C: Comparator<T>,

type Item = Entry<'a, T, C, A>

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, C, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.