Struct SkipMap 

pub struct SkipMap<K, V, C = BasicComparator, A: SkiplistAllocator = TursoAllocator> { /* 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.

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

Implementations

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

pub fn new() -> Self

Returns a new, empty map with the default comparator.

Example

use turso_core::skiplist::SkipMap;

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

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

pub fn new_in(alloc: A) -> Self

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

Example

use turso_core::alloc::TursoAllocator;
use turso_core::skiplist::SkipMap;

let map: SkipMap<i32, &str, _, TursoAllocator> = SkipMap::new_in(TursoAllocator);

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

pub fn with_comparator(comparator: C) -> Self

Returns a new, empty map with the given comparator.

Example

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

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

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

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

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

Example

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

let map: SkipMap<i32, &str, _, TursoAllocator> =
    SkipMap::with_comparator_in(BasicComparator, TursoAllocator);

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

Example

use turso_core::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 turso_core::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, C, A: SkiplistAllocator> SkipMap<K, V, C, A>

where C: Comparator<K>,

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

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 turso_core::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, C, A>>

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 turso_core::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 get_or_insert(&self, key: K, value: V) -> Entry<'_, K, V, C, A>

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 turso_core::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 try_get_or_insert( &self, key: K, value: V, ) -> Result<Entry<'_, 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 map is unchanged and both key and value are dropped.

Example

use turso_core::skiplist::SkipMap;

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

pub fn get_or_insert_with<F>( &self, key: K, value_fn: F, ) -> Entry<'_, 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

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

Example

use turso_core::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 try_get_or_insert_with<F>( &self, key: K, value_fn: F, ) -> Result<Entry<'_, 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 map is unchanged and both key and the value built by value_fn are dropped.

Example

use turso_core::skiplist::SkipMap;

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

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

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 turso_core::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);
}

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

where C: Comparator<K>,

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

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

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

Example

use turso_core::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, C, A>>

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

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

Example

use turso_core::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, 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.

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

Example

use turso_core::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 range<Q, R>(&self, range: R) -> Range<'_, Q, R, K, V, C, A>

where R: RangeBounds<Q>, C: Comparator<K, Q>, Q: ?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 turso_core::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, C, A: SkiplistAllocator> SkipMap<K, V, C, A>

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

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

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 turso_core::skiplist::SkipMap;

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

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

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

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

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

Example

use turso_core::skiplist::SkipMap;

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

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

pub fn compare_insert<F>( &self, key: K, value: V, compare_fn: F, ) -> Entry<'_, 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.

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

Example

use turso_core::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 try_compare_insert<F>( &self, key: K, value: V, compare_fn: F, ) -> Result<Entry<'_, 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 map is unchanged and both key and value are dropped.

Example

use turso_core::skiplist::SkipMap;

let map = SkipMap::new();
map.try_insert("key", 1).unwrap();
map.try_compare_insert("key", 2, |x| x < &2).unwrap();
assert_eq!(*map.get("key").unwrap().value(), 2);

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

where C: Comparator<K, Q>, Q: ?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 turso_core::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, C, A>>

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 turso_core::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, C, A>>

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 turso_core::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 turso_core::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, C, A: SkiplistAllocator> Debug for SkipMap<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> Default for SkipMap<K, V, C>

where C: Default,

fn default() -> Self

Returns the “default value” for a type.

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

where C: Comparator<K> + Default,

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

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

Creates a value from an iterator.

impl<K, V, C, A: SkiplistAllocator> IntoIterator for SkipMap<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<'a, K, V, C, A: SkiplistAllocator> IntoIterator for &'a SkipMap<K, V, C, A>

where C: Comparator<K>,

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.