Struct crossbeam_skiplist::SkipMap

pub struct SkipMap<K, V> { /* private fields */ }

An ordered map based on a lock-free skip list.

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

Implementations

impl<K, V> SkipMap<K, V>

pub fn new() -> Self

Returns a new, empty map.

Example

use crossbeam_skiplist::SkipMap;

let map: SkipMap<i32, &str> = SkipMap::new();

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

Example

use crossbeam_skiplist::SkipMap;

let map: SkipMap<&str, &str> = SkipMap::new();
assert!(map.is_empty());

map.insert("key", "value");
assert!(!map.is_empty());

pub fn len(&self) -> usize

Returns the number of entries in the map.

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

Example

use crossbeam_skiplist::SkipMap;

let map = SkipMap::new();
map.insert(0, 1);
assert_eq!(map.len(), 1);

for x in 1..=5 {
    map.insert(x, x + 1);
}

assert_eq!(map.len(), 6);

impl<K, V> SkipMap<K, V>

where K: Ord,

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

Returns the entry with the smallest key.

This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let numbers = SkipMap::new();
numbers.insert(5, "five");
assert_eq!(*numbers.front().unwrap().value(), "five");
numbers.insert(6, "six");
assert_eq!(*numbers.front().unwrap().value(), "five");

pub fn back(&self) -> Option<Entry<'_, K, V>>

Returns the entry with the largest key.

This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let numbers = SkipMap::new();
numbers.insert(5, "five");
assert_eq!(*numbers.back().unwrap().value(), "five");
numbers.insert(6, "six");
assert_eq!(*numbers.back().unwrap().value(), "six");

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

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

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

Example

use crossbeam_skiplist::SkipMap;

let ages = SkipMap::new();
ages.insert("Bill Gates", 64);

assert!(ages.contains_key(&"Bill Gates"));
assert!(!ages.contains_key(&"Steve Jobs"));

pub fn get<Q>(&self, key: &Q) -> Option<Entry<'_, K, V>>

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

Returns an entry with the specified key.

This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let numbers: SkipMap<&str, i32> = SkipMap::new();
assert!(numbers.get("six").is_none());

numbers.insert("six", 6);
assert_eq!(*numbers.get("six").unwrap().value(), 6);

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

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

This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;
use std::ops::Bound::*;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

let greater_than_five = numbers.lower_bound(Excluded(&5)).unwrap();
assert_eq!(*greater_than_five.value(), "six");

let greater_than_six = numbers.lower_bound(Excluded(&6)).unwrap();
assert_eq!(*greater_than_six.value(), "seven");

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

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

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

This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;
use std::ops::Bound::*;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

let less_than_eight = numbers.upper_bound(Excluded(&8)).unwrap();
assert_eq!(*less_than_eight.value(), "seven");

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

pub fn get_or_insert(&self, key: K, value: V) -> Entry<'_, K, V>

Finds an entry with the specified key, or inserts a new key-value pair if none exist. This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let ages = SkipMap::new();
let gates_age = ages.get_or_insert("Bill Gates", 64);
assert_eq!(*gates_age.value(), 64);

ages.insert("Steve Jobs", 65);
let jobs_age = ages.get_or_insert("Steve Jobs", -1);
assert_eq!(*jobs_age.value(), 65);

pub fn get_or_insert_with<F>(&self, key: K, value_fn: F) -> Entry<'_, K, V>

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 This function returns an Entry which can be used to access the key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let ages = SkipMap::new();
let gates_age = ages.get_or_insert_with("Bill Gates", || 64);
assert_eq!(*gates_age.value(), 64);

ages.insert("Steve Jobs", 65);
let jobs_age = ages.get_or_insert_with("Steve Jobs", || -1);
assert_eq!(*jobs_age.value(), 65);

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

Returns an iterator over all entries in the map, sorted by key.

This iterator returns Entrys which can be used to access keys and their associated values.

Examples

use crossbeam_skiplist::SkipMap;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

// Print then numbers from least to greatest
for entry in numbers.iter() {
    let number = entry.key();
    let number_str = entry.value();
    println!("{} is {}", number, number_str);
}

pub fn range<Q, R>(&self, range: R) -> Range<'_, Q, R, K, V>

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

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

This iterator returns Entrys which can be used to access keys and their associated values.

Example

use crossbeam_skiplist::SkipMap;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

// Print all numbers in the map between 5 and 8.
for entry in numbers.range(5..=8) {
    let number = entry.key();
    let number_str = entry.value();
    println!("{} is {}", number, number_str);
}

impl<K, V> SkipMap<K, V>

where K: Ord + Send + 'static, V: Send + 'static,

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

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

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

This function returns an Entry which can be used to access the inserted key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let map = SkipMap::new();
map.insert("key", "value");

assert_eq!(*map.get("key").unwrap().value(), "value");

pub fn compare_insert<F>( &self, key: K, value: V, compare_fn: F ) -> Entry<'_, K, V>

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.

This function returns an Entry which can be used to access the inserted key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let map = SkipMap::new();
map.insert("key", 1);
map.compare_insert("key", 0, |x| x < &0);
assert_eq!(*map.get("key").unwrap().value(), 1);
map.compare_insert("key", 2, |x| x < &2);
assert_eq!(*map.get("key").unwrap().value(), 2);
map.compare_insert("absent_key", 0, |_| false);
assert_eq!(*map.get("absent_key").unwrap().value(), 0);

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

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

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

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

This function returns an Entry which can be used to access the removed key’s associated value.

Example

use crossbeam_skiplist::SkipMap;

let map: SkipMap<&str, &str> = SkipMap::new();
assert!(map.remove("invalid key").is_none());

map.insert("key", "value");
assert_eq!(*map.remove("key").unwrap().value(), "value");

pub fn pop_front(&self) -> Option<Entry<'_, K, V>>

Removes the entry with the lowest key from the map. 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::SkipMap;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

assert_eq!(*numbers.pop_front().unwrap().value(), "six");
assert_eq!(*numbers.pop_front().unwrap().value(), "seven");
assert_eq!(*numbers.pop_front().unwrap().value(), "twelve");

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

pub fn pop_back(&self) -> Option<Entry<'_, K, V>>

Removes the entry with the greatest key from the map. 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::SkipMap;

let numbers = SkipMap::new();
numbers.insert(6, "six");
numbers.insert(7, "seven");
numbers.insert(12, "twelve");

assert_eq!(*numbers.pop_back().unwrap().value(), "twelve");
assert_eq!(*numbers.pop_back().unwrap().value(), "seven");
assert_eq!(*numbers.pop_back().unwrap().value(), "six");

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

pub fn clear(&self)

Removes all entries from the map.

Example

use crossbeam_skiplist::SkipMap;

let people = SkipMap::new();
people.insert("Bill", "Gates");
people.insert("Steve", "Jobs");

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

Trait Implementations

impl<K, V> Debug for SkipMap<K, V>

where K: Ord + Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V> Default for SkipMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> FromIterator<(K, V)> for SkipMap<K, V>

where K: Ord,

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

where I: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<'a, K, V> IntoIterator for &'a SkipMap<K, V>

where K: Ord,

type Item = Entry<'a, K, V>

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<K, V> IntoIterator for SkipMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.