Struct SkipList 

pub struct SkipList<K, V, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> { /* private fields */ }

A lock-free skip list.

Implementations

impl<K, V> SkipList<K, V>

pub fn new(collector: Collector) -> Self

Returns a new, empty skip list.

impl<K, V, A: SkiplistAllocator> SkipList<K, V, BasicComparator, A>

pub fn new_in(collector: Collector, alloc: A) -> Self

Returns a new, empty skip list that allocates its nodes in alloc.

impl<K, V, C> SkipList<K, V, C>

pub fn with_comparator(collector: Collector, comparator: C) -> Self

Returns a new, empty skip list using the given comparator.

impl<K, V, C, A: SkiplistAllocator> SkipList<K, V, C, A>

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

Returns a new, empty skip list using the given comparator, allocating its nodes in alloc.

pub fn is_empty(&self) -> bool

Returns true if the skip list is empty.

pub fn len(&self) -> usize

Returns the number of entries in the skip list.

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

impl<K, V, C, A: SkiplistAllocator> SkipList<K, V, C, A>

where C: Comparator<K>,

pub fn front<'a: 'g, 'g>( &'a self, guard: &'g Guard, ) -> Option<Entry<'a, 'g, K, V, C, A>>

Returns the entry with the smallest key.

pub fn back<'a: 'g, 'g>( &'a self, guard: &'g Guard, ) -> Option<Entry<'a, 'g, K, V, C, A>>

Returns the entry with the largest key.

pub fn contains_key<Q>(&self, key: &Q, guard: &Guard) -> bool

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

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

pub fn get<'a: 'g, 'g, Q>( &'a self, key: &Q, guard: &'g Guard, ) -> Option<Entry<'a, 'g, K, V, C, A>>

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

Returns an entry with the specified key.

pub fn lower_bound<'a: 'g, 'g, Q>( &'a self, bound: Bound<&Q>, guard: &'g Guard, ) -> Option<Entry<'a, 'g, K, V, C, A>>

where C: Comparator<K, 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.

pub fn upper_bound<'a: 'g, 'g, Q>( &'a self, bound: Bound<&Q>, guard: &'g Guard, ) -> Option<Entry<'a, 'g, K, V, C, A>>

where C: Comparator<K, 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.

pub fn get_or_insert( &self, key: K, value: V, guard: &Guard, ) -> RefEntry<'_, K, V, C, A>

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

pub fn try_get_or_insert( &self, key: K, value: V, guard: &Guard, ) -> Result<RefEntry<'_, K, V, C, A>, TryReserveError>

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

On error the skip list is unchanged and both key and value are dropped.

pub fn get_or_insert_with<F>( &self, key: K, value: F, guard: &Guard, ) -> RefEntry<'_, K, V, C, A>

where F: FnOnce() -> V,

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

Note: Another thread may write key value first, leading to the result of this closure discarded. If closure is modifying some other state (such as shared counters or shared objects), it may lead to undesired behaviour such as counters being changed without result of closure inserted

pub fn try_get_or_insert_with<F>( &self, key: K, value: F, guard: &Guard, ) -> Result<RefEntry<'_, K, V, C, A>, TryReserveError>

where F: FnOnce() -> V,

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

On error the skip list is unchanged and both key and the value built by value are dropped.

pub fn iter<'a: 'g, 'g>(&'a self, guard: &'g Guard) -> Iter<'a, 'g, K, V, C, A>

Returns an iterator over all entries in the skip list.

pub fn ref_iter(&self) -> RefIter<'_, K, V, C, A>

Returns an iterator over all entries in the skip list.

pub fn range<'a: 'g, 'g, Q, R>( &'a self, range: R, guard: &'g Guard, ) -> Range<'a, 'g, Q, R, K, V, C, A>

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

Returns an iterator over a subset of entries in the skip list.

pub fn ref_range<'a, Q, R>(&'a self, range: R) -> RefRange<'a, Q, R, K, V, C, A>

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

Returns an iterator over a subset of entries in the skip list.

impl<K, V, C, A: SkiplistAllocator> SkipList<K, V, C, A>

where C: Comparator<K>, K: Send + 'static, V: Send + 'static,

pub fn insert( &self, key: K, value: V, guard: &Guard, ) -> RefEntry<'_, K, V, C, A>

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

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

pub fn try_insert( &self, key: K, value: V, guard: &Guard, ) -> Result<RefEntry<'_, K, V, C, A>, TryReserveError>

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

On error the skip list is unchanged and both key and value are dropped.

pub fn compare_insert<F>( &self, key: K, value: V, compare_fn: F, guard: &Guard, ) -> RefEntry<'_, K, V, C, A>

where F: Fn(&V) -> bool,

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

If there is an existing entry with this key and compare(entry.value) returns true, it will be removed before inserting the new one. The closure will not be called if the key is not present.

pub fn try_compare_insert<F>( &self, key: K, value: V, compare_fn: F, guard: &Guard, ) -> Result<RefEntry<'_, K, V, C, A>, TryReserveError>

where F: Fn(&V) -> bool,

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

On error the skip list is unchanged and both key and value are dropped.

pub fn remove<Q>( &self, key: &Q, guard: &Guard, ) -> Option<RefEntry<'_, K, V, C, A>>

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

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

pub fn pop_front(&self, guard: &Guard) -> Option<RefEntry<'_, K, V, C, A>>

Removes an entry from the front of the skip list.

pub fn pop_back(&self, guard: &Guard) -> Option<RefEntry<'_, K, V, C, A>>

Removes an entry from the back of the skip list.

pub fn clear(&self, guard: &mut Guard)

Iterates over the map and removes every entry.

Trait Implementations

impl<K, V, C, A: SkiplistAllocator> Debug for SkipList<K, V, C, A>

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V, C, A: SkiplistAllocator> Drop for SkipList<K, V, C, A>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<K, V, C, A: SkiplistAllocator> IntoIterator for SkipList<K, V, C, A>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Send + Sync, V: Send + Sync, C: Send + Sync, A: SkiplistAllocator> Send for SkipList<K, V, C, A>

impl<K: Send + Sync, V: Send + Sync, C: Send + Sync, A: SkiplistAllocator> Sync for SkipList<K, V, C, A>