Struct concurrent_map::ConcurrentMap

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

A 100% lock-free B+ tree.

One thing that might seem strange compared to other concurrent structures in the Rust ecosystem, is that all of the methods require a mutable self reference. This is intentional, and stems from the fact that each ConcurrentMap object holds a fully-owned local garbage bag for epoch-based reclamation, backed by the ebr crate. Epoch-based reclamation is at the heart of the concurrent Rust ecosystem, but existing popular implementations tend to incur significant overhead due to an over-reliance on shared state. This crate (and the backing ebr crate) takes a different approach. It may seem unfamiliar, but it allows for far higher efficiency, and this approach may become more prevalent over time as more people realize that this is how to make one of the core aspects underlying many of our concurrent data structures to be made more efficient.

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

Implementations

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

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

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

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

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

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

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

pub fn cas<KArc: Into<Arc<K>>>(
    &mut self,
    key: KArc,
    old: Option<&V>,
    new: Option<V>
) -> Result<Option<Arc<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 mut 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), Some(20)).unwrap();

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

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

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

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

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>>(&mut self, range: R) -> Iter<'_, K, V, 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> Clone for ConcurrentMap<K, V>where
    K: 'static + Debug + Minimum + Ord + Send + Sync,
    V: 'static + Debug + Send + Sync,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Returns the “default value” for a type.