Skip to main content

BLinkMap

Struct BLinkMap 

Source
pub struct BLinkMap<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> { /* private fields */ }
Expand description

A concurrent ordered map backed by a B-link tree.

N is the exact allocation capacity for separators or entries in a page. Full pages split before another item is inserted. N must be at least three; omitting it uses DEFAULT_PAGE_CAPACITY.

Reads and ordinary writes use one page latch. Splits, rotations, and merges use top-down latch crabbing: a writer briefly owns a parent and one or two adjacent children, repairs them, then releases the parent before descending. No tree-wide structure lock serializes writers. Each page carries lower and upper fences, a right sibling, and a forwarding state for stale references, so completed key operations are linearizable at their destination leaf.

§Key ordering

Keys must retain the same ordering for their entire time in the map. Do not mutate ordering-relevant state through interior mutability. For borrowed lookups, the ordering of K: Borrow<Q> must agree with both K::Ord and Q::Ord, just as it must for standard ordered maps.

§Entry guards and locking

EntryRef and EntryMut lock an entire leaf, not only one record. Drop a guard before invoking another operation that could target that leaf. Re-entering the map while a conflicting guard is alive can deadlock, and acquiring several guards in inconsistent orders can create lock cycles.

Implementations§

Source§

impl<K, V, const N: usize> BLinkMap<K, V, N>

Source

pub fn new() -> Self

Creates an empty map with one allocated leaf page.

§Panics

Panics when N < 3, when the capacity arithmetic overflows, or when a backing page layout cannot be represented. Allocation failure is handled by Rust’s global allocation-error handler.

Examples found in repository?
examples/basic.rs (line 4)
3fn main() {
4  let map = BLinkMap::<u64, String>::new();
5  map.insert(7, String::from("seven"));
6
7  let set = BLinkSet::<u64>::new();
8  set.insert(7);
9
10  let value = map.get(&7).expect("the example inserted key 7");
11
12  println!(
13    "map[7] = {}, set contains 7 = {}",
14    value.value(),
15    set.contains(&7)
16  );
17}
Source

pub fn len(&self) -> usize

Returns the number of entries currently in the map.

During concurrent mutation this is a momentary atomic observation, not a transactionally consistent snapshot of other operations.

Source

pub fn is_empty(&self) -> bool

Returns true when the map has no entries at the instant it is observed.

Like BLinkMap::len, this result can become stale immediately when other threads mutate the map.

Source

pub fn clear(&mut self)

Removes every entry and returns the map to one empty root leaf.

The exclusive &mut self borrow proves that no entry guard or concurrent operation can still reference the old tree through this map. Individual pages are reclaimed as their internal Arc owners are dropped.

Source§

impl<K: Ord, V, const N: usize> BLinkMap<K, V, N>

Source

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

Returns a read guard for key, or None when the key is absent.

The returned guard keeps the whole destination leaf read-locked. Its key and value references remain stable, but it must be dropped before a conflicting operation on that leaf to avoid deadlock.

The borrowed form Q must use an ordering consistent with K.

Examples found in repository?
examples/basic.rs (line 10)
3fn main() {
4  let map = BLinkMap::<u64, String>::new();
5  map.insert(7, String::from("seven"));
6
7  let set = BLinkSet::<u64>::new();
8  set.insert(7);
9
10  let value = map.get(&7).expect("the example inserted key 7");
11
12  println!(
13    "map[7] = {}, set contains 7 = {}",
14    value.value(),
15    set.contains(&7)
16  );
17}
Source

pub fn get_key_value<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
where K: Borrow<Q>, Q: Ord + ?Sized,

Returns a read guard exposing both the stored key and value.

This is an explicitly named counterpart to BLinkMap::get; both return the same EntryRef because that guard already supplies EntryRef::key and EntryRef::value.

Source

pub fn get_mut<Q>(&self, key: &Q) -> Option<EntryMut<'_, K, V, N>>
where K: Borrow<Q>, Q: Ord + ?Sized,

Returns a write guard for key, or None when the key is absent.

The guard exclusively locks the entire destination leaf and supports mutation through EntryMut::value_mut or DerefMut. Drop it before calling any other map operation that could visit the same leaf.

The borrowed form Q must use an ordering consistent with K.

Source

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

Returns true when the map contains key at the operation’s linearization point. The temporary leaf read latch is released before this returns.

The borrowed form Q must use an ordering consistent with K.

Source

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

Inserts key and value, returning the previous value if the key was already present.

A non-splitting insert locks only its destination leaf. A structural insert splits full pages top-down while holding only the affected parent and child, allowing writers in disjoint subtrees to continue concurrently.

Examples found in repository?
examples/basic.rs (line 5)
3fn main() {
4  let map = BLinkMap::<u64, String>::new();
5  map.insert(7, String::from("seven"));
6
7  let set = BLinkSet::<u64>::new();
8  set.insert(7);
9
10  let value = map.get(&7).expect("the example inserted key 7");
11
12  println!(
13    "map[7] = {}, set contains 7 = {}",
14    value.value(),
15    set.contains(&7)
16  );
17}
Source

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

Removes key, returning its value when present.

Before descending into a minimally occupied page, deletion borrows from a sibling or merges two pages. Merged pages are removed from their parent and sibling chain, while stale Arc handles see a forwarding page until they drain. Empty internal root levels are collapsed before this returns. A removed key that also serves as a surviving fence or separator may keep its shared key allocation alive until that boundary changes or the map is dropped; the user value is returned immediately.

The borrowed form Q must use an ordering consistent with K.

Source

pub fn first_key_value(&self) -> Option<EntryRef<'_, K, V, N>>

Returns the least key/value record, guarded by its leaf read latch.

Source

pub fn last_key_value(&self) -> Option<EntryRef<'_, K, V, N>>

Returns the greatest key/value record, guarded by its leaf read latch.

Source

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

Returns a weakly consistent ascending iterator over guarded records.

See Iter for its concurrent visibility and leaf-locking semantics.

Source

pub fn keys(&self) -> Keys<'_, K, V, N> ⓘ

Returns a weakly consistent ascending iterator over guarded keys.

Source

pub fn values(&self) -> Values<'_, K, V, N> ⓘ

Returns a weakly consistent ascending iterator over guarded values.

Source

pub fn range<Q, R>(&self, bounds: R) -> Range<'_, K, V, Q, R, N> ⓘ
where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>,

Returns an ascending iterator over records whose keys lie in bounds.

Borrowed bounds are supported when their ordering agrees with K.

§Panics

Panics when the start is greater than the end, or when equal start and end bounds are both excluded.

Trait Implementations§

Source§

impl<K: Ord + Debug, V: Debug, const N: usize> Debug for BLinkMap<K, V, N>

Source§

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

Formats a weakly consistent ordered view, dropping each guard promptly.

Source§

impl<K, V, const N: usize> Default for BLinkMap<K, V, N>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<K: Ord, V, const N: usize> Extend<(K, V)> for BLinkMap<K, V, N>

Source§

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iterable: T)

Inserts every pair, replacing values for duplicate keys.

Source§

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more
Source§

impl<K: Ord, V, const N: usize> FromIterator<(K, V)> for BLinkMap<K, V, N>

Source§

fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> Self

Builds a map by repeated concurrent-map insertions.

Source§

impl<'map, K: Ord, V, const N: usize> IntoIterator for &'map BLinkMap<K, V, N>

Source§

fn into_iter(self) -> Self::IntoIter

Creates the same guarded iterator as BLinkMap::iter.

Source§

type Item = EntryRef<'map, K, V, N>

The type of the elements being iterated over.
Source§

type IntoIter = Iter<'map, K, V, N>

Which kind of iterator are we turning this into?

Auto Trait Implementations§

§

impl<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> !Freeze for BLinkMap<K, V, N>

§

impl<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> !RefUnwindSafe for BLinkMap<K, V, N>

§

impl<K, V, const N: usize = DEFAULT_PAGE_CAPACITY> !UnwindSafe for BLinkMap<K, V, N>

§

impl<K, V, const N: usize> Send for BLinkMap<K, V, N>
where Tree<K, V, N>: Send,

§

impl<K, V, const N: usize> Sync for BLinkMap<K, V, N>
where Tree<K, V, N>: Sync,

§

impl<K, V, const N: usize> Unpin for BLinkMap<K, V, N>
where Tree<K, V, N>: Unpin,

§

impl<K, V, const N: usize> UnsafeUnpin for BLinkMap<K, V, N>
where Tree<K, V, N>: UnsafeUnpin,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.