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>
impl<K, V, const N: usize> BLinkMap<K, V, N>
Sourcepub fn new() -> Self
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?
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}Sourcepub fn len(&self) -> usize
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.
Sourcepub fn is_empty(&self) -> bool
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§impl<K: Ord, V, const N: usize> BLinkMap<K, V, N>
impl<K: Ord, V, const N: usize> BLinkMap<K, V, N>
Sourcepub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
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?
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}Sourcepub fn get_key_value<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
pub fn get_key_value<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V, N>>
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.
Sourcepub fn get_mut<Q>(&self, key: &Q) -> Option<EntryMut<'_, K, V, N>>
pub fn get_mut<Q>(&self, key: &Q) -> Option<EntryMut<'_, K, V, N>>
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.
Sourcepub fn contains_key<Q>(&self, key: &Q) -> bool
pub fn contains_key<Q>(&self, key: &Q) -> bool
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.
Sourcepub fn insert(&self, key: K, value: V) -> Option<V>
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?
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}Sourcepub fn remove<Q>(&self, key: &Q) -> Option<V>
pub fn remove<Q>(&self, key: &Q) -> Option<V>
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.
Sourcepub fn first_key_value(&self) -> Option<EntryRef<'_, K, V, N>>
pub fn first_key_value(&self) -> Option<EntryRef<'_, K, V, N>>
Returns the least key/value record, guarded by its leaf read latch.
Sourcepub fn last_key_value(&self) -> Option<EntryRef<'_, K, V, N>>
pub fn last_key_value(&self) -> Option<EntryRef<'_, K, V, N>>
Returns the greatest key/value record, guarded by its leaf read latch.
Sourcepub fn iter(&self) -> Iter<'_, K, V, N> ⓘ
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.
Sourcepub fn keys(&self) -> Keys<'_, K, V, N> ⓘ
pub fn keys(&self) -> Keys<'_, K, V, N> ⓘ
Returns a weakly consistent ascending iterator over guarded keys.
Sourcepub fn values(&self) -> Values<'_, K, V, N> ⓘ
pub fn values(&self) -> Values<'_, K, V, N> ⓘ
Returns a weakly consistent ascending iterator over guarded values.
Sourcepub fn range<Q, R>(&self, bounds: R) -> Range<'_, K, V, Q, R, N> ⓘ
pub fn range<Q, R>(&self, bounds: R) -> Range<'_, K, V, Q, R, N> ⓘ
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, V, const N: usize> Extend<(K, V)> for BLinkMap<K, V, N>
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)
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)
fn extend_one(&mut self, item: T)
extend_one)Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one)Source§impl<K: Ord, V, const N: usize> FromIterator<(K, V)> for BLinkMap<K, V, N>
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
fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> Self
Builds a map by repeated concurrent-map insertions.