Struct concurrent_map::ConcurrentMap

pub struct ConcurrentMap<K, V, const FANOUT: usize = 64>where
    K: 'static + Clone + Debug + Minimum + Ord + Send + Sync,
    V: 'static + Clone + Debug + Send + Sync,{ /* private fields */ }

A lock-free B+ tree.

If you want to use a custom key type, you must implement the Minimum trait, allowing the left-most side of the tree to be created before inserting any data.

Implementations

impl<K, V, const FANOUT: usize> ConcurrentMap<K, V, FANOUT>where
    K: 'static + Clone + Debug + Minimum + Ord + Send + Sync,
    V: 'static + Clone + Debug + Send + Sync,

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

Atomically get a value out of the tree that is associated with this key.

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

Atomically insert a key-value pair into the tree, returning the previous value associated with this key if one existed.

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

Atomically remove the value associated with this key from the tree, returning the previous value if one existed.

pub fn cas(
    &self,
    key: K,
    old: Option<&V>,
    new: Option<V>
) -> Result<Option<V>, CasFailure<V>>where
    V: PartialEq,

Atomically compare and swap the value associated with this key from the old value to the new one. An old value of None means “only create this value if it does not already exist”. A new value of None means “delete this value, if it matches the provided old value”. If successful, returns the old value if it existed. If unsuccessful, returns the proposed new value.

Examples

let tree = concurrent_map::ConcurrentMap::<usize, usize>::default();

// key 1 does not yet exist
assert_eq!(tree.get(&1), None);

// uniquely create value 10
tree.cas(1, None, Some(10)).unwrap();

assert_eq!(tree.get(&1).unwrap(), 10);

// compare and swap from value 10 to value 20
tree.cas(1, Some(&10_usize), Some(20)).unwrap();

assert_eq!(tree.get(&1).unwrap(), 20);

// if we guess the wrong current value, a CasFailure is returned
// which will tell us what the actual current value is (which we
// failed to provide) and it will give us back our proposed new
// value.
let cas_result = tree.cas(1, Some(&999999_usize), Some(30));

let expected_cas_failure = Err(concurrent_map::CasFailure {
    actual: Some(20),
    returned_new_value: Some(30),
});

assert_eq!(cas_result, expected_cas_failure);

// conditionally delete
tree.cas(1, Some(&20_usize), None).unwrap();

assert_eq!(tree.get(&1), None);

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

Iterate over the tree.

This is not an atomic snapshot, and it caches B+tree leaf nodes as it iterates through them to achieve high throughput. As a result, the following behaviors are possible:

• may (or may not!) return values that were concurrently added to the tree after the iterator was created
• may (or may not!) return items that were concurrently deleted from the tree after the iterator was created
• If a key’s value is changed from one value to another one after this iterator is created, this iterator might return the old or the new value.

But, you can be certain that any key that existed prior to the creation of this iterator, and was not changed during iteration, will be observed as expected.

pub fn range<R: RangeBounds<K>>(&self, range: R) -> Iter<'_, K, V, FANOUT, R>

Iterate over a range of the tree.

This is not an atomic snapshot, and it caches B+tree leaf nodes as it iterates through them to achieve high throughput. As a result, the following behaviors are possible:

• may (or may not!) return values that were concurrently added to the tree after the iterator was created
• may (or may not!) return items that were concurrently deleted from the tree after the iterator was created
• If a key’s value is changed from one value to another one after this iterator is created, this iterator might return the old or the new value.

But, you can be certain that any key that existed prior to the creation of this iterator, and was not changed during iteration, will be observed as expected.

Trait Implementations

impl<K: Clone, V: Clone, const FANOUT: usize> Clone for ConcurrentMap<K, V, FANOUT>where
    K: 'static + Clone + Debug + Minimum + Ord + Send + Sync,
    V: 'static + Clone + Debug + Send + Sync,

fn clone(&self) -> ConcurrentMap<K, V, FANOUT>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, V, const FANOUT: usize> Default for ConcurrentMap<K, V, FANOUT>where
    K: 'static + Clone + Debug + Minimum + Ord + Send + Sync,
    V: 'static + Clone + Debug + Send + Sync,

fn default() -> ConcurrentMap<K, V, FANOUT>

Returns the “default value” for a type.