Struct crossbeam_skiplist_piedb::set::SkipSet
source · [−]pub struct SkipSet<T> { /* private fields */ }
Expand description
A set based on a lock-free skip list.
This is an alternative to BTreeSet
which supports
concurrent access across multiple threads.
Implementations
sourceimpl<T> SkipSet<T>
impl<T> SkipSet<T>
sourcepub fn new() -> SkipSet<T>
pub fn new() -> SkipSet<T>
Returns a new, empty set.
Example
use crossbeam_skiplist::SkipSet;
let set: SkipSet<i32> = SkipSet::new();
sourcepub fn is_empty(&self) -> bool
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());
sourcepub fn len(&self) -> usize
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);
sourceimpl<T> SkipSet<T> where
T: Ord,
impl<T> SkipSet<T> where
T: Ord,
sourcepub fn front(&self) -> Option<Entry<'_, T>>
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);
sourcepub fn back(&self) -> Option<Entry<'_, T>>
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);
sourcepub fn contains<Q>(&self, key: &Q) -> bool where
T: Borrow<Q>,
Q: Ord + ?Sized,
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));
sourcepub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, T>> where
T: Borrow<Q>,
Q: Ord + ?Sized,
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());
sourcepub fn lower_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T>> where
T: Borrow<Q>,
Q: Ord + ?Sized,
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());
sourcepub fn upper_bound<'a, Q>(&'a self, bound: Bound<&Q>) -> Option<Entry<'a, T>> where
T: Borrow<Q>,
Q: Ord + ?Sized,
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());
sourcepub fn get_or_insert(&self, key: T) -> Entry<'_, T>
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);
sourcepub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> where
T: Ord, type Item = Entry<'a, T>;
pub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> where
T: Ord, type Item = Entry<'a, T>;
T: Ord, type Item = Entry<'a, 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());
sourcepub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, T>ⓘNotable traits for Range<'a, Q, R, T>impl<'a, Q, R, T> Iterator for Range<'a, Q, R, T> where
T: Ord + Borrow<Q>,
R: RangeBounds<Q>,
Q: Ord + ?Sized, type Item = Entry<'a, T>;
where
T: Borrow<Q>,
R: RangeBounds<Q>,
Q: Ord + ?Sized,
pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, T>ⓘNotable traits for Range<'a, Q, R, T>impl<'a, Q, R, T> Iterator for Range<'a, Q, R, T> where
T: Ord + Borrow<Q>,
R: RangeBounds<Q>,
Q: Ord + ?Sized, type Item = Entry<'a, T>;
where
T: Borrow<Q>,
R: RangeBounds<Q>,
Q: Ord + ?Sized,
T: Ord + Borrow<Q>,
R: RangeBounds<Q>,
Q: Ord + ?Sized, type Item = Entry<'a, T>;
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());
sourceimpl<T> SkipSet<T> where
T: Ord + Send + 'static,
impl<T> SkipSet<T> where
T: Ord + Send + 'static,
sourcepub fn insert(&self, key: T) -> Entry<'_, T>
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);
sourcepub fn remove<Q>(&self, key: &Q) -> Option<Entry<'_, T>> where
T: Borrow<Q>,
Q: Ord + ?Sized,
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());
sourcepub fn pop_front(&self) -> Option<Entry<'_, T>>
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());
sourcepub fn pop_back(&self) -> Option<Entry<'_, T>>
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());
Trait Implementations
sourceimpl<T> FromIterator<T> for SkipSet<T> where
T: Ord,
impl<T> FromIterator<T> for SkipSet<T> where
T: Ord,
sourcefn from_iter<I>(iter: I) -> SkipSet<T> where
I: IntoIterator<Item = T>,
fn from_iter<I>(iter: I) -> SkipSet<T> where
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
sourceimpl<T> IntoIterator for SkipSet<T>
impl<T> IntoIterator for SkipSet<T>
sourceimpl<'a, T> IntoIterator for &'a SkipSet<T> where
T: Ord,
impl<'a, T> IntoIterator for &'a SkipSet<T> where
T: Ord,
Auto Trait Implementations
impl<T> !RefUnwindSafe for SkipSet<T>
impl<T> Send for SkipSet<T> where
T: Send + Sync,
impl<T> Sync for SkipSet<T> where
T: Send + Sync,
impl<T> Unpin for SkipSet<T>
impl<T> !UnwindSafe for SkipSet<T>
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more