Struct SkipSet 

pub struct SkipSet<T> { /* private fields */ }

A set based on a lock-free skip list.

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

Implementations

impl<T> SkipSet<T>

pub fn new() -> Self

Returns a new, empty set.

Example

use crossbeam_skiplist::SkipSet;

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

pub fn is_empty(&self) -> bool

Returns true if the set is empty.

Example

use crossbeam_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 crossbeam_skiplist::SkipSet;

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

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

impl<T> SkipSet<T>

where T: Ord,

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

Returns the entry with the smallest key.

Example

use crossbeam_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>>

Returns the entry with the largest key.

Example

use crossbeam_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 T: Borrow<Q>, Q: Ord + ?Sized,

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

Example

use crossbeam_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>>

where T: Borrow<Q>, Q: Ord + ?Sized,

Returns an entry with the specified key.

Example

use crossbeam_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>>

where T: Borrow<Q>, Q: Ord + ?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 crossbeam_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>>

where T: Borrow<Q>, Q: Ord + ?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 crossbeam_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>

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

Example

use crossbeam_skiplist::SkipSet;

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

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

Returns an iterator over all entries in the set.

Examples

use crossbeam_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>

where T: Borrow<Q>, R: RangeBounds<Q>, Q: Ord + ?Sized,

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

Example

use crossbeam_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> SkipSet<T>

where T: Ord + Send + 'static,

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

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 crossbeam_skiplist::SkipSet;

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

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

where T: Borrow<Q>, Q: Ord + ?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 crossbeam_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>>

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 crossbeam_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>>

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 crossbeam_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 crossbeam_skiplist::SkipSet;

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

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

Trait Implementations

impl<T> Debug for SkipSet<T>

where T: Ord + Debug,

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

Formats the value using the given formatter.

impl<T> Default for SkipSet<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> FromIterator<T> for SkipSet<T>

where T: Ord,

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

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a SkipSet<T>

where T: Ord,

type Item = Entry<'a, T>

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T> IntoIterator for SkipSet<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.