Struct concurrent_map::ConcurrentMap

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

A lock-free B+ tree.

Note that this structure is Send but NOT Sync, despite being a lock-free tree. This is because the inner reclamation system, provided by the ebr crate completely avoids atomic operations in its hot path for efficiency. If you want to share ConcurrentMap between threads, simply clone it, and this will set up a new efficient thread-local memory reclamation state.

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. If you wish to perform scans in reverse lexicographical order, you may instead implement Maximum for your key type and use std::cmp::Reverse.

The FANOUT const generic must be greater than 3. This const generic controls how large the fixed-size array for either child pointers (for index nodes) or values (for leaf nodes) will be. A higher value may make reads and scans faster, but writes will be slower because each modification performs a read-copy-update of the full node. In some cases, it may be preferable to wrap complex values in an Arc to avoid higher copy costs.

The LOCAL_GC_BUFFER_SIZE const generic must be greater than 0. This controls the epoch-based reclamation granularity. Garbage is placed into fixed-size arrays, and garbage collection only happens after this array fills up and a final timestamp is assigned to it. Lower values will cause replaced values to be dropped more quickly, but the efficiency will be lower. Values that are extremely high may cause undesirable memory usage because it will take more time to fill up each thread-local garbage segment.

Implementations

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

pub fn get<Q>(&self, key: &Q) -> Option<V>where
    K: Borrow<Q>,
    Q: Ord + ?Sized,

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<Q>(&self, key: &Q) -> Option<V>where
    K: Borrow<Q>,
    Q: Ord + ?Sized,

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

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

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 len(&self) -> usize

A lagging, eventually-consistent length count. This is NOT atomically updated with [insert] / [remove] / [cas], but is updated after those operations complete their atomic modifications to the shared map.

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

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, LOCAL_GC_BUFFER_SIZE, 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, const LOCAL_GC_BUFFER_SIZE: usize> Clone for ConcurrentMap<K, V, FANOUT, LOCAL_GC_BUFFER_SIZE>where
    K: 'static + Clone + Minimum + Ord + Send + Sync,
    V: 'static + Clone + Send + Sync,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

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

Returns the “default value” for a type.

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

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, FANOUT, LOCAL_GC_BUFFER_SIZE, RangeFull>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.