Struct SequentialMap 

pub struct SequentialMap<K: Key, V: Value> { /* private fields */ }

Non-concurrent map that supports lexicographically ordered range and prefix scans.

Usage

SequentialMap supports both point and scan operations, and tries to be roughly compatible with the standard library’s BTreeMap.

In general, radix trees do not explicitly store keys; they are implicitly encoded in the structure of the tree. This means that operations on SequentialMap generally take references to keys (see Key). Operations that insert and typically would take an owned key, like BTreeMap::insert, instead take a Key::Insert<'_>. Operations that do not insert a new key take a &Key::Borrowed.

Point operations

The main caveat here is that SequentialMap::insert errors if the key is present, whereas BTreeMap::insert updates. (To match the standard library behavior, use SequentialMap::upsert instead.) For more complex conditional logic, the SequentialMap::entry API mimics BTreeMap::entry.

Scan operations

For scan operations, SequentialMap exposes a two-phase API: the caller first selects a subtree (e.g., SequentialMap::prefix or SequentialMap::range_mut). This returns a Shard or ShardMut, which can then be iterated over (e.g., Shard::entries or ShardMut::values_mut). This is in contrast to the standard library, where BTreeMap::range directly returns an iterator.

If the key type (see Key) is dynamically allocated, like BoxedStr, iterating over keys can be expensive, as a key buffer must be updated during traversal, and then cloned once per key. This can be mitigated by (a) iterating over values instead of entries, (b) using the lending API (e.g., EntryIter::lend), which borrows from the iterator’s internal buffer, or (c) using the internal iteration API¹ (e.g., EntryIterMut::try_fold), which also borrows from the iterator and can be much faster.

---

1. Should ideally replace with custom Iterator::try_fold implementation, but this currently uses the unstable Try trait. See also this issue. ↩

Implementations

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

where K: Key, V: Value,

Basic operations

pub const fn new() -> Self

Constructs a new empty map. Does not allocate.

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

where K: Key, V: Value,

Point operations

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

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

Returns whether key has an associated value.

Examples

use arctic::SequentialMap;

let mut map = SequentialMap::<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(&self, key: &K::Borrowed) -> Option<&V>

Returns an immutable reference to the value associated with key.

For a mutable reference, see Map::get_mut.

Examples

use arctic::SequentialMap;

let mut map = SequentialMap::<u64, u64>::new();
map.insert(1, 2).expect("Key is not present");
assert_eq!(map.get(&1), Some(&2));
assert_eq!(map.get(&2), None);

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

Returns a mutable reference to the value associated with key.

For an immutable reference, see Map::get.

Examples

use arctic::SequentialMap;

let mut map = SequentialMap::<u64, u64>::new();
let key = 1;
map.insert(key, 2).expect("Key is not present");
let value = map.get_mut(&key).expect("Key is present");
*value = 3;
assert_eq!(map.get(&key), Some(&3));

pub fn insert<'k>( &mut self, key: K::Insert<'k>, value: V, ) -> Result<&mut V, (&mut V, 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(&mut new_value) if the insert succeeded, or else Err((&mut old_value, new_value)) if there is an existing old_value associated with the key.

Examples

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

let mut map = SequentialMap::<BoxedStr<NonNull>, Box<u64>>::new();
let key = Str::<NonNull>::new("regent").expect("No null byte");

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

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

pub fn upsert<'k>( &mut self, key: K::Insert<'k>, value: V, ) -> Result<(V, &mut V), &mut V>

Unconditionally associate key with value.

Returns Ok((old_value, &mut new_value)) if this updated old_value, or Err(&mut new_value) if there was no value associated with key.

Examples

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

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

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

// Key present, upsert performs update
match map.upsert(key, 26) {
    Ok((old, new)) => {
        assert_eq!(old, 2);
        assert_eq!(*new, 26);
    },
    Err(_) => unreachable!(),
}

pub fn update(&mut self, key: &K::Borrowed, value: V) -> Result<(V, &mut V), V>

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

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

Examples

use arctic::SequentialMap;

let mut map = SequentialMap::<[u8; 3], Box<u64>>::new();
let key = [0, 1, 2];

// Key not present, update fails
match map.update(&key, Box::new(5)) {
    Ok(_) => unreachable!(),
    Err(new) => assert_eq!(*new, 5),
}

map.insert(&key, Box::new(9));

// Key present, update succeeds
match map.update(&key, Box::new(10)) {
    Ok((old, new)) => {
        assert_eq!(*old, 9);
        assert_eq!(**new, 10);
    },
    Err(_) => unreachable!(),
}

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

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 Map::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.

Examples

use arctic::SequentialMap;

let mut map = SequentialMap::<u16, u64>::new();
let key = 100;

// Key not present, remove fails
assert!(map.remove(&key).is_none());

map.insert(key, 7);

// Key present, remove succeeds
assert_eq!(map.remove(&key), Some(7));

// Key no longer present
assert!(map.get(&key).is_none());

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

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 Map::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.

pub fn entry<'k>(&mut self, key: K::Insert<'k>) -> Entry<'_, 'k, K, V>

Get a logical entry associated with key (see also std::collections::BTreeMap::entry).

This is a lazy operation, and does not allocate or modify the tree structure.

Examples

use arctic::key::Str;
use arctic::key::NonNull;
use arctic::SequentialMap;

let mut counter = SequentialMap::<&'static Str<NonNull>, u64>::new();
let claw = Str::new("claw").expect("No null byte");
let hotfix = Str::new("hotfix").expect("No null byte");
let hologram = Str::new("hologram").expect("No null byte");

for key in [claw, claw, hotfix, hologram, claw] {
    *counter.entry(key).or_default() += 1;
}

assert_eq!(*counter.get(hologram).unwrap(), 1);
assert_eq!(*counter.get(hotfix).unwrap(), 1);
assert_eq!(*counter.get(claw).unwrap(), 3);

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

where K: Key, V: Value,

Scan operations

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

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

Get an immutable reference to the entire tree.

pub fn prefix<'k>(&self, prefix: K::Read<'k>) -> Shard<'_, 'k, K, V, RangeFull>

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

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

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

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

pub fn all_mut(&mut self) -> ShardMut<'_, 'static, K, V, RangeFull>

Get a mutable reference to the entire tree.

pub fn prefix_mut<'k>( &mut self, prefix: K::Read<'k>, ) -> ShardMut<'_, 'k, K, V, RangeFull>

Get a mutable reference to the subtree of keys beginning with prefix.

pub fn range_mut<'k, R>(&mut self, range: R) -> ShardMut<'_, 'k, K, V, R>

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

Get a mutable reference to the subtree of keys within range.

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

where K: Key, V: Value,

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

Export the exact quiescent Arctic topology without process pointers.

encode must copy or otherwise encode the logical value; the raw value word stored in Arctic is deliberately never exposed.

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

Restore a validated topology and reconstruct its exact adaptive node kinds.

Trait Implementations

impl<K, V> Default for Map<K, V>

where K: Key, V: Value,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for Map<K, V>

where K: Key, V: Value,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

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.

impl<'k, K, V> FromIterator<(<K as Key>::Insert<'k>, V)> for Map<K, V>

where K: Key, V: Value,

fn from_iter<T: IntoIterator<Item = (K::Insert<'k>, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<'g, K, V> IntoIterator for &'g Map<K, V>

where K: Key, V: Value,

type Item = (K, &'g V)

The type of the elements being iterated over.

type IntoIter = EntryIter<'g, 'static, K, V, RangeFull>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'g, K, V> IntoIterator for &'g mut Map<K, V>

where K: Key, V: Value,

type Item = (K, &'g mut V)

The type of the elements being iterated over.

type IntoIter = EntryIterMut<'g, 'static, K, V, RangeFull>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.