Struct ConcurrentMap 

pub struct ConcurrentMap<K: Key, V: Value, S = Default> { /* private fields */ }

Lock-free concurrent map that supports lexicographically ordered, non-linearizable range and prefix scans.

Usage

Refer to SequentialMap for an introduction. The ConcurrentMap API differs in three ways: concurrent operations, safe memory reclamation, and advanced point operations.

Concurrent operations

Unlike SequentialMap, an instance of ConcurrentMap can be shared and modified concurrently across threads. Methods that usually require a mutable reference (e.g., SequentialMap::upsert) instead use atomics to synchronize internally, allowing them to take an immutable reference (e.g., ConcurrentMap::upsert).

Note that scan operations are not linearizable. They do, however, satisfy weaker guarantees: (a) scans observe keys at most once, in order; and (b) scans observe all keys within bounds that were inserted before the scan starts, and were not removed before the scan ends.

Safe memory reclamation

In order to provide wait-free reads, ConcurrentMap requires a safe memory reclamation (SMR) mechanism to detect when allocations are safe to free. This results in the following API changes:

1. Values are always returned behind guards. For example, while a successful sequential::Map::update returns ownership of the old value, a successful ConcurrentMap::update instead returns an Updated guard that allows references to the old and new value.

   The guard may have other restrictions depending on the SMR implementation: for example, epoch-based SMR cannot free any memory while a guard is alive, and hazard keys currently only support holding a single guard at a time.

2. Values behind guards are always read-only. This can be worked around by either using a value type with internal synchronization (e.g., Box<Mutex<T>>), or by obtaining a mutable reference to ConcurrentMap and then using the sequential API via ConcurrentMap::as_sequential.

3. Values distinguish between inline (e.g., integers) and indirect (e.g., Box<T>). In short, we return Value::Borrowed instead of &V, because the memory location where V itself is stored may be concurrently updated. (See Value for more information.)

Advanced point operations

Point operations can internally fail and retry under contention. We give the caller control over retries by providing variants of point operations (ending in suffix _with, e.g., ConcurrentMap::update_with) that take a closure.

This can be used to efficiently implement lazy value initialization, or synchronization logic where the next value is computed from the current value, and then atomically inserted or updated.

Implementations

impl<K: Key, V: Value, S: Default> Map<K, V, S>

pub fn new() -> Self

Construct an empty map with the default safe memory reclamation state.

impl<K: Key, V: Value, S> Map<K, V, S>

pub const fn with_smr(smr: S) -> Self

Construct an empty map with the given safe memory reclamation state.

impl<K: Key, V: Value, S: Smr<K, V>> Map<K, V, S>

Basic operations

pub fn as_sequential(&mut self) -> &mut Map<K, V>

Get a mutable view as a SequentialMap for temporary access to a more efficient and flexible single-threaded API. For permanent access, use From.

This method is safe because &mut guarantees this thread holds the only reference to the underlying map.

Examples

use core::ops::ControlFlow;
use core::convert::Infallible;
use std::thread;

use arctic::concurrent::smr;
use arctic::ConcurrentMap;
use arctic::Order;
use arctic::sequential;

let mut map = ConcurrentMap::<u32, u64>::default();

// Concurrently insert into map
thread::scope(|scope| {
    let map = &map;
    for id in 0..8 {
        scope.spawn(move || {
            map.insert(id, id as u64).expect("Key is not present");
        });
    }
});

// Access sequential entry API
map.as_sequential()
    .entry(8)
    .or_insert(8);

// Access sequential mutable iteration API
map.as_sequential()
    .range_mut(5..=12)
    .entries_mut(Order::Ascend)
    .try_fold((), |(), (key, value)| {
        assert!(key >= 5);
        assert!(key <= 8, "Inserted up to 8");
        assert_eq!(key, *value as u32);
        *value += 1;
        ControlFlow::<Infallible>::Continue(())
    });

// Sanity check that mutations are visible from concurrent map
let mut len = 0;
map.all()
    .entries(Order::Descend)
    .try_fold((), |(), (key, value)|{
        let expected = if key >= 5 { key + 1 } else { key };
        assert_eq!(*value as u32, expected);
        len += 1;
        ControlFlow::<Infallible>::Continue(())
    });
assert_eq!(len, 9);

pub fn smr(&self) -> &S

Get an immutable reference to the underlying safe memory reclamation state.

pub fn smr_mut(&mut self) -> &mut S

Get a mutable reference to the underlying safe memory reclamation state.

impl<K: Key, V: Value, S: Smr<K, V>> Map<K, V, S>

Point operations

This set of operations operates on a single key-value pair.

These operations are linearizable.

pub fn contains_key(&self, key: &K::Borrowed) -> bool

Returns whether key has an associated value.

Examples

use arctic::ConcurrentMap;

let mut map = ConcurrentMap::<u64, u64>::new();
map.insert(1, 2).expect("Key is not present");
assert!(map.contains_key(&1));
assert!(!map.contains_key(&2));

pub fn get<'g>(&'g self, key: &K::Borrowed) -> Option<Shared<'g, K, V, S>>

Returns an immutable reference to the value associated with key.

For a mutable reference, see ConcurrentMap::as_sequential and SequentialMap::get_mut. There is no way to safely get a mutable reference to a value from an immutable Map.

Examples

use arctic::ConcurrentMap;

let map = ConcurrentMap::<u64, u64>::default();
let key = 64;

assert!(map.get(&key).is_none());

match map.insert(key, 3) {
    Err(_) => unreachable!(),
    Ok(new) => assert_eq!(*new, 3),
}

match map.get(&key) {
    None => unreachable!(),
    Some(value) => assert_eq!(*value, 3),
}

pub fn insert<'g, 'k>( &'g self, key: K::Insert<'k>, value: V, ) -> Result<Shared<'g, K, V, S>, (Shared<'g, K, V, S>, V)>

If there is no value associated with key, associate it with value.

This is not the same behavior as the standard library (e.g., std::collections::BTreeMap::insert); see Map::upsert if an existing value should be updated instead.)

Returns Ok(&new_value) if the insert succeeded, or else Err((&old_value, new_value)) if there is an existing old_value associated with the key.

See ConcurrentMap::insert_with for dynamic control flow and value construction.

Examples

use arctic::key::Str;
use arctic::key::NonNull;
use arctic::ConcurrentMap;

let map = ConcurrentMap::<&'static Str<NonNull>, u64>::default();
let key = Str::new("korlex").expect("No null byte");

// Key is not present, insert succeeds
match map.insert(key, 3) {
    Err(_) => unreachable!(),
    Ok(new) => assert_eq!(*new, 3),
}

// Key is present, insert fails
match map.insert(key, 5) {
    Err((old, new)) => {
        assert_eq!(*old, 3);
        assert_eq!(new, 5);
    }
    Ok(_) => unreachable!(),
}

pub fn upsert<'k>(&self, key: K::Insert<'k>, value: V) -> Upserted<'_, K, V, S>

Unconditionally associate key with value.

Returns an Upserted guard that provides immutable references to the (optional) old value and the newly updated (or inserted) value.

See ConcurrentMap::upsert_with for dynamic control flow and value construction.

Examples

use arctic::key::BoxedStr;
use arctic::key::Terminated;
use arctic::key::Str;
use arctic::ConcurrentMap;

let map = ConcurrentMap::<BoxedStr<Terminated<b'\n'>>, u64>::default();
let key = Str::new("arqad\n").expect("Newline terminated");

// Key is not present, upsert performs insert
let upserted = map.upsert(key, 3);
assert_eq!(upserted.old(), None);
assert_eq!(*upserted.new(), 3);

// Key is present, upsert performs update
let upserted = map.upsert(key, 5);
assert_eq!(upserted.old().copied(), Some(3));
assert_eq!(*upserted.new(), 5);

pub fn update<'g>( &'g self, key: &K::Borrowed, value: V, ) -> Result<Updated<'g, K, V, S>, V>

If there is a value associated with key, update it to value.

Returns Ok((&old_value, &new_value)) if the update succeeded, or else Err(new_value) if there was no old value associated with key.

See ConcurrentMap::update_with for dynamic control flow and value construction.

Examples

use arctic::ConcurrentMap;

let map = ConcurrentMap::<u32, Box<u64>>::default();

match map.update(&37, Box::new(5)) {
    Err(new) => assert_eq!(*new, 5),
    Ok(_) => unreachable!(),
}

match map.insert(37, Box::new(3)) {
    Err(_) => unreachable!(),
    Ok(new) => assert_eq!(*new, 3),
}

match map.update(&37, Box::new(5)) {
    Err(_) => unreachable!(),
    Ok(updated) => {
        assert_eq!(*updated.old(), 3);
        assert_eq!(*updated.new(), 5);
    },
}

pub fn remove<'g>(&'g self, key: &K::Borrowed) -> Option<Owned<'g, K, V, S>>

If there is a value associated with key, remove it from the map, recursively removing empty tree nodes.

This method is slow because it must keep a traversal stack, and scan and delete empty nodes. See ConcurrentMap::remove_non_recursive for a faster, but potentially memory-intensive alternative.

Returns Some(&old_value) if the remove succeeded, or else None if there was no old value associated with key.

See ConcurrentMap::remove_with for dynamic control flow.

Examples

use arctic::ConcurrentMap;

let map = ConcurrentMap::<u128, u64>::default();
let key = 0xabc;

assert!(map.remove(&key).is_none());
map.insert(key, 5).expect("Key is not present");
match map.remove(&key) {
    None => unreachable!(),
    Some(removed) => assert_eq!(*removed, 5),
}

pub fn remove_non_recursive( &self, key: &K::Borrowed, ) -> Option<Owned<'_, K, V, S>>

If there is a value associated with key, remove it from the map, without recursively removing empty tree nodes.

This method is much faster than ConcurrentMap::remove, because no traversal stack or node scanning and replacement is necessary; however, it means the memory usage of the tree is no longer correlated with the number of keys and values it contains.

This method should only be used if removals are rare or removed keys are expected to be reinserted.

Returns Some(&old_value) if the remove succeeded, or else None if there was no old value associated with key.

See ConcurrentMap::remove_non_recursive_with for dynamic control flow.

impl<K, V, S> Map<K, V, S>

where K: Key, V: Value, S: Smr<K, V>,

Scan operations

This set of operations allows the caller to select a subtree (by prefix or range) for non-linearizable iteration.

pub fn all(&self) -> Shard<'_, 'static, K, V, RangeFull, Guard<'_, K, V, S>>

Get an immutable reference to the entire tree.

Examples

use arctic::ConcurrentMap;
use arctic::Order;

let map = ConcurrentMap::<u64, u64>::default();
map.insert(1, 2).expect("Key not present");
map.insert(3, 4).expect("Key not present");

assert_eq!(map.all().entries(Order::Ascend).count(), 2);

pub fn prefix<'g, 'k>( &'g self, prefix: impl Into<K::Read<'k>>, ) -> Shard<'g, 'k, K, V, RangeFull, Guard<'g, K, V, S>>

Get an immutable reference to the subtree of keys beginning with prefix.

Examples

use arctic::concurrent;
use arctic::ConcurrentMap;
use arctic::key::BoxedStr;
use arctic::key::NonNull;
use arctic::key::Str;
use arctic::Order;

let map = ConcurrentMap::<BoxedStr<NonNull>, Box<u64>>::default();

for (key, value) in [("prefix-one", 3), ("prefix-two", 2), ("three", 1)] {
    map.insert(
        Str::new(key).expect("No null byte"),
        Box::new(value),
    ).expect("Key not present");
}

// Get all key value pairs where key starts with prefix
//
// Need a temporary binding here since lifetimes of references
// returned from iterators is tied to this shard
//
// Note: prefix does not need to satisfy any particular invariants;
// can be invalid UTF-8 or contain null or terminator bytes
let prefix = map.prefix("prefix");

let entries: concurrent::EntryIter<_, _, _> = prefix.entries(Order::Ascend);

// WARNING: using `entries` as `Iterator` requires cloning keys,
// which is expensive here due to BoxedStr keys
assert_eq!(entries.count(), 2);

// Can use lending iterator API to avoid cloning
let mut entries: concurrent::EntryIter<_, _, _> = prefix.entries(Order::Ascend);
while let Some((key, _)) = entries.lend() {
    assert!(key.as_str().starts_with("prefix"));
}

pub fn range<'g, 'k, R>( &'g self, range: R, ) -> Shard<'g, 'k, K, V, R, Guard<'g, K, V, S>>

where R: Range<K::Read<'k>>,

Get an immutable reference to the subtree of keys within range.

Examples

use arctic::ConcurrentMap;
use arctic::Order;

let map = ConcurrentMap::<u64, u64>::default();
map.insert(1, 2).expect("Key not present");
map.insert(3, 4).expect("Key not present");
map.insert(5, 6).expect("Key not present");

let range = map.range(3..=7);

for (key, value) in range.entries(Order::Descend) {
    assert!((3..=7).contains(&key));
}

impl<K, V, S> Map<K, V, S>

where K: Key, V: Value, S: Smr<K, V>,

Advanced point operations

This set of operations extends the point operations to take a closure, allowing the caller to dynamically break out of an operation or lazily allocate a value. Importantly, this closure can observe the value currently associated with a key before deciding what to do, which enables more complex coordination in a concurrent setting.

For example, a concurrent counter could use ConcurrentMap::upsert_with to either insert one or update the current count by one, or an index could use ConcurrentMap::remove_with to remove a value only if it hasn’t been concurrently updated.

These operations are linearizable.

pub fn insert_with<'g, 'k, F>( &'g self, key: K::Insert<'k>, insert: F, ) -> Result<Shared<'g, K, V, S>, (Shared<'g, K, V, S>, Option<V>)>

where F: FnOnce() -> V,

If there is no value associated with key, call the provided insert closure to compute a new value.

The closure is called at most once, even under contention; the value will be reused once allocated.

Returns Ok(&new_value) if the insert succeeded, or else Err((&old_value, new_value)) if there is an existing old_value associated with the key. new_value is None if the closure was never called, or Some if this insert was pre-empted by a concurrent insert to the same key.

Examples

use core::ops::ControlFlow;

use arctic::ConcurrentMap;
use arctic::key::BoxedStr;
use arctic::key::NonNull;
use arctic::key::Str;

let map = ConcurrentMap::<BoxedStr<NonNull>, Box<u64>>::default();
let key = Str::new("zipir").expect("No null byte");

// Key not present, new value lazily allocated
match map.insert_with(key, || Box::new(10)) {
    Ok(new) => {
        assert_eq!(*new, 10);
    }
    Err(_) => unreachable!(),
}

// Key present, new value not allocated
match map.insert_with(key, || Box::new(15)) {
    Ok(_) => unreachable!(),
    Err((old, new)) => {
        assert_eq!(*old, 10);
        assert!(new.is_none());
    },
}

pub fn upsert_with<'g, 'k, F>( &'g self, key: K::Insert<'k>, initial: Option<V>, upsert: F, ) -> Upsert<'g, K, V, S>

where F: FnMut(Option<&V::Borrowed>, &mut Option<V>) -> ControlFlow<(), V>,

Associate key with value, calling the provided upsert closure to break or compute a new value.

The closure may be called multiple times under contention, and takes an immutable reference to the current value (if there is one), as well as initial (on the first call) or Some(prev_value) (on subsequent calls); use Option::take to move out of the option.

Returns an Upsert enum.

Examples

use core::ops::ControlFlow;

use arctic::ConcurrentMap;
use arctic::concurrent::map::Upsert;

let map = ConcurrentMap::<u16, Box<u64>>::default();
let key = 20;

// Key not present, closure continues, new value lazily allocated
match map.upsert_with(key, None, |old, new| {
    assert!(old.is_none());
    assert!(new.is_none());
    ControlFlow::Continue(Box::new(9))
}) {
    Upsert::Success(upserted) => {
        assert!(upserted.old().is_none());
        assert_eq!(*upserted.new(), 9);
    },
    Upsert::Break { .. } => unreachable!(),
}

// Key present, closure breaks, new value not allocated
match map.upsert_with(key, None, |old, new| {
    assert!(old.copied() == Some(9));
    assert!(new.is_none());
    ControlFlow::Break(())
}) {
    Upsert::Success(_) => unreachable!(),
    Upsert::Break { old, new } => {
        assert_eq!(old.as_deref().copied(), Some(9));
        assert!(new.is_none());
    },
}

// Key present, closure continues, new value lazily allocated (and reused under contention)
match map.upsert_with(key, None, |old, new| {
    let next = old.copied().unwrap_or(0) + 1;

    ControlFlow::Continue(
        new.take()
            // Reuse allocation under contention
            .map(|mut new: Box<u64>| {
                *new = next;
                new
            })
            // Allocate new value
            .unwrap_or_else(|| Box::new(next)))
}) {
    Upsert::Success(updated) => {
        assert_eq!(updated.old().copied(), Some(9));
        assert_eq!(*updated.new(), 10);
    }
    _ => unreachable!(),
}

pub fn update_with<'g, F>( &'g self, key: &K::Borrowed, initial: Option<V>, update: F, ) -> Update<'g, K, V, S>

where F: FnMut(&V::Borrowed, &mut Option<V>) -> ControlFlow<(), V>,

If there is a value associated with key, call the provided update closure to break or compute a new value.

The closure may be called multiple times under contention, and takes an immutable reference to the current value, as well as initial (on the first call) or Some(prev_value) (on subsequent calls); use Option::take to move out of the option.

Returns an Update enum.

Examples

use core::ops::ControlFlow;

use arctic::ConcurrentMap;
use arctic::concurrent::map::Update;

let map = ConcurrentMap::<u64, Box<u64>>::default();
let key = 5;

// Key not present, closure never called, new value not allocated
match map.update_with(&key, None, |_, _| unreachable!()) {
    Update::Absent { new } => assert!(new.is_none()),
    Update::Success { .. } | Update::Break { .. } => unreachable!(),
}

map.insert(key, Box::new(29)).expect("Key not present");

// Key present, closure breaks, new value not allocated
match map.update_with(&key, None, |_, _| ControlFlow::Break(())) {
    Update::Break { old, new } => {
        assert_eq!(*old, 29);
        assert!(new.is_none());
    }
    Update::Absent { .. } | Update::Success { .. } => unreachable!(),
}

// Key present, closure continues, new value lazily allocated (and reused under contention)
match map.update_with(&key, None, |old, new| {
    ControlFlow::Continue(
        new.take()
            // Reuse allocation under contention
            .map(|mut new: Box<u64>| {
                *new = *old + 1;
                new
            })
            // Allocate new value
            .unwrap_or_else(|| Box::new(*old + 1)))
}) {
    Update::Success(updated) => {
        assert_eq!(*updated.old(), 29);
        assert_eq!(*updated.new(), 30);
    }
    Update::Absent { .. } | Update::Break { .. } => unreachable!(),
}

pub fn remove_with<'g, F>( &'g self, key: &K::Borrowed, remove: F, ) -> Remove<'g, K, V, S>

where F: FnMut(&V::Borrowed) -> ControlFlow<(), ()>,

If there is a value associated with key, call remove to determine whether to remove the value, recursively removing empty tree nodes.

Returns a Remove enum.

See also: ConcurrentMap::remove, ConcurrentMap::remove_non_recursive, ConcurrentMap::remove_non_recursive_with.

Examples

use core::ops::ControlFlow;

use arctic::ConcurrentMap;
use arctic::concurrent::map::Remove;

let map = ConcurrentMap::<u128, u64>::default();
let key = 0xfeed;

// Key not present, closure never called
match map.remove_with(&key, |_| unreachable!()) {
    Remove::Absent => (),
    Remove::Success { .. } | Remove::Break { .. } => unreachable!(),
}

map.insert(key, 1).expect("Key not present");

// Key present, closure breaks, value not removed
match map.remove_with(&key, |old| {
    assert_eq!(*old, 1);
    ControlFlow::Break(())
}) {
    Remove::Break { old } => assert_eq!(*old, 1),
    Remove::Absent | Remove::Success { .. } => unreachable!(),
}

assert_eq!(map.get(&key).as_deref().copied(), Some(1));

// Key present, closure continues, value removed
match map.remove_with(&key, |old| {
    if *old > 0 {
        ControlFlow::Continue(())
    } else {
        ControlFlow::Break(())
    }
}) {
    Remove::Success { old } => assert_eq!(*old, 1),
    Remove::Absent | Remove::Break { .. } => unreachable!(),
}

assert!(map.get(&key).is_none());

pub fn remove_non_recursive_with<F>( &self, key: &K::Borrowed, remove: F, ) -> Remove<'_, K, V, S>

where F: FnMut(&V::Borrowed) -> ControlFlow<(), ()>,

If there is a value associated with key, call remove to determine whether to remove the value, without recursively removing empty tree nodes.

See warning on Map::remove_non_recursive.

Returns a Remove enum.

See also: ConcurrentMap::remove, ConcurrentMap::remove_with, ConcurrentMap::remove_non_recursive.

impl<K, V, S> Map<K, V, S>

where K: Key, V: Value, S: Smr<K, V>,

pub fn export_topology<T>( &mut self, encode: impl FnMut(&V) -> T, ) -> Result<Topology<T>, Error>

Export an exact topology through an exclusive sequential view.

Requiring &mut self prevents concurrent mutation while the snapshot is captured and adds no synchronization to point operations.

impl<K, V, S> Map<K, V, S>

where K: Key, V: Value, S: Smr<K, V> + Default,

pub fn from_topology<T>( topology: Topology<T>, decode: impl FnMut(T) -> V, ) -> Result<Self, Error>

Restore a concurrent map from a validated pointer-free topology.

Trait Implementations

impl<K: Key, V: Value, S: Default> Default for Map<K, V, S>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, S> From<Map<K, V, S>> for Map<K, V>

where K: Key, V: Value,

fn from(map: Map<K, V, S>) -> Map<K, V>

Converts to this type from the input type.

impl<K, V, S> From<Map<K, V>> for Map<K, V, S>

where K: Key, V: Value, S: Default,

fn from(seq: Map<K, V>) -> Self

Converts to this type from the input type.