Struct TreeIndex

pub struct TreeIndex<K, V> { /* private fields */ }

Scalable concurrent B-plus tree.

TreeIndex is a concurrent and asynchronous B-plus tree variant that is optimized for read operations. Read operations, such as read, iteration over entries, are neither blocked nor interrupted by other threads or tasks. Write operations, such as insert, remove, do not block if structural changes are not required.

Notes

TreeIndex methods are linearizable, however its iterator methods are not; Iter and Range are only guaranteed to observe events happened before the first call to Iterator::next.

The key features of TreeIndex

• Lock-free-read: read and scan operations do not modify shared data and are never blocked.
• Near lock-free write: write operations do not block unless a structural change is needed.
• No busy waiting: each node has a wait queue to avoid spinning.
• Immutability: the data in the container is immutable until it becomes unreachable.

The key statistics for TreeIndex

• The maximum number of entries that a leaf can contain: 14.
• The maximum number of leaves or child nodes that a node can point to: 15.

Locking behavior

Read access is always lock-free and non-blocking. Write access to an entry is also lock-free and non-blocking as long as no structural changes are required. However, when nodes are being split or merged by a write operation, other write operations on keys in the affected range are blocked.

Unwind safety

TreeIndex is impervious to out-of-memory errors and panics in user specified code on one condition; K::drop and V::drop must not panic.

Implementations

impl<K, V> TreeIndex<K, V>

pub const fn new() -> Self

Creates an empty TreeIndex.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

pub fn clear(&self)

Clears the TreeIndex.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

treeindex.clear();
assert_eq!(treeindex.len(), 0);

pub fn depth(&self) -> usize

Returns the depth of the TreeIndex.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
assert_eq!(treeindex.depth(), 0);

impl<K, V> TreeIndex<K, V>

where K: 'static + Clone + Ord, V: 'static + Clone,

pub fn insert(&self, key: K, val: V) -> Result<(), (K, V)>

Inserts a key-value pair.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 10).is_ok());
assert_eq!(treeindex.insert(1, 11).err().unwrap(), (1, 11));
assert_eq!(treeindex.peek_with(&1, |k, v| *v).unwrap(), 10);

pub async fn insert_async(&self, key: K, val: V) -> Result<(), (K, V)>

Inserts a key-value pair.

It is an asynchronous method returning an impl Future for the caller to await.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let future_insert = treeindex.insert_async(1, 10);

pub fn remove<Q>(&self, key: &Q) -> bool

where Q: Comparable<K> + ?Sized,

Removes a key-value pair.

Returns false if the key does not exist.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(!treeindex.remove(&1));
assert!(treeindex.insert(1, 10).is_ok());
assert!(treeindex.remove(&1));

pub async fn remove_async<Q>(&self, key: &Q) -> bool

where Q: Comparable<K> + ?Sized,

Removes a key-value pair.

Returns false if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let future_remove = treeindex.remove_async(&1);

pub fn remove_if<Q, F: FnMut(&V) -> bool>(&self, key: &Q, condition: F) -> bool

where Q: Comparable<K> + ?Sized,

Removes a key-value pair if the given condition is met.

Returns false if the key does not exist or the condition was not met.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 10).is_ok());
assert!(!treeindex.remove_if(&1, |v| *v == 0));
assert!(treeindex.remove_if(&1, |v| *v == 10));

pub async fn remove_if_async<Q, F: FnMut(&V) -> bool>( &self, key: &Q, condition: F, ) -> bool

where Q: Comparable<K> + ?Sized,

Removes a key-value pair if the given condition is met.

Returns false if the key does not exist or the condition was not met. It is an asynchronous method returning an impl Future for the caller to await.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let future_remove = treeindex.remove_if_async(&1, |v| *v == 0);

pub fn remove_range<Q, R: RangeBounds<Q>>(&self, range: R)

where Q: Comparable<K> + ?Sized,

Removes keys in the specified range.

This method removes internal nodes that are definitely contained in the specified range first, and then removes remaining entries individually.

Notes

Internally, multiple internal node locks need to be acquired, thus making this method susceptible to lock starvation.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for k in 2..8 {
    assert!(treeindex.insert(k, 1).is_ok());
}

treeindex.remove_range(3..8);

assert!(treeindex.contains(&2));
assert!(!treeindex.contains(&3));

pub async fn remove_range_async<Q, R: RangeBounds<Q>>(&self, range: R)

where Q: Comparable<K> + ?Sized,

Removes keys in the specified range.

This method removes internal nodes that are definitely contained in the specified range first, and then removes remaining entries individually.

It is an asynchronous method returning an impl Future for the caller to await.

Notes

Internally, multiple internal node locks need to be acquired, thus making this method susceptible to lock starvation.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for k in 2..8 {
    assert!(treeindex.insert(k, 1).is_ok());
}

let future_remove_range = treeindex.remove_range_async(3..8);

pub fn peek<'g, Q>(&self, key: &Q, guard: &'g Guard) -> Option<&'g V>

where Q: Comparable<K> + ?Sized,

Returns a guarded reference to the value for the specified key without acquiring locks.

Returns None if the key does not exist. The returned reference can survive as long as the associated Guard is alive.

Examples

use scc::ebr::Guard;
use std::sync::Arc;
use scc::TreeIndex;

let treeindex: TreeIndex<Arc<str>, u32> = TreeIndex::new();

let guard = Guard::new();
assert!(treeindex.peek("foo", &guard).is_none());

treeindex.insert("foo".into(), 1).expect("insert in empty TreeIndex");

pub fn peek_with<Q, R, F: FnOnce(&K, &V) -> R>( &self, key: &Q, reader: F, ) -> Option<R>

where Q: Comparable<K> + ?Sized,

Peeks a key-value pair without acquiring locks.

Returns None if the key does not exist.

Examples

use std::sync::Arc;
use scc::TreeIndex;

let treeindex: TreeIndex<Arc<str>, u32> = TreeIndex::new();

assert!(treeindex.peek_with("foo", |k, v| *v).is_none());

treeindex.insert("foo".into(), 1).expect("insert in empty TreeIndex");

let key: Arc<str> = treeindex
    .peek_with("foo", |k, _v| Arc::clone(k))
    .expect("peek_with by borrowed key");

pub fn peek_entry<'g, Q>( &self, key: &Q, guard: &'g Guard, ) -> Option<(&'g K, &'g V)>

where Q: Comparable<K> + ?Sized,

Returns a guarded reference to the key-value pair for the specified key without acquiring locks.

Returns None if the key does not exist. The returned reference can survive as long as the associated Guard is alive.

Examples

use scc::ebr::Guard;
use std::sync::Arc;
use scc::TreeIndex;

let treeindex: TreeIndex<Arc<str>, u32> = TreeIndex::new();

let guard = Guard::new();
assert!(treeindex.peek_entry("foo", &guard).is_none());

treeindex.insert("foo".into(), 1).expect("insert in empty TreeIndex");

let key: Arc<str> = treeindex
    .peek_entry("foo", &guard)
    .map(|(k, _v)| Arc::clone(k))
    .expect("peek_entry by borrowed key");

pub fn contains<Q>(&self, key: &Q) -> bool

where Q: Comparable<K> + ?Sized,

Returns true if the TreeIndex contains the key.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::default();

assert!(!treeindex.contains(&1));
assert!(treeindex.insert(1, 0).is_ok());
assert!(treeindex.contains(&1));

pub fn len(&self) -> usize

Returns the size of the TreeIndex.

It internally scans all the leaf nodes, and therefore the time complexity is O(N).

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
assert_eq!(treeindex.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the TreeIndex is empty.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.is_empty());

pub fn iter<'t, 'g>(&'t self, guard: &'g Guard) -> Iter<'t, 'g, K, V>

Returns an Iter.

The returned Iter starts scanning from the minimum key-value pair. Key-value pairs are scanned in ascending order, and key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed. However, it is possible to visit removed key-value pairs momentarily.

Examples

use scc::TreeIndex;
use scc::ebr::Guard;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let guard = Guard::new();
let mut iter = treeindex.iter(&guard);
assert!(iter.next().is_none());

pub fn range<'t, 'g, Q, R: RangeBounds<Q>>( &'t self, range: R, guard: &'g Guard, ) -> Range<'t, 'g, K, V, Q, R>

where Q: Comparable<K> + ?Sized,

Returns a Range that scans keys in the given range.

Key-value pairs in the range are scanned in ascending order, and key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed. However, it is possible to visit removed key-value pairs momentarily.

Examples

use scc::TreeIndex;
use scc::ebr::Guard;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let guard = Guard::new();
assert_eq!(treeindex.range(4..=8, &guard).count(), 0);

Trait Implementations

impl<K, V> Clone for TreeIndex<K, V>

where K: 'static + Clone + Ord, V: 'static + Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for TreeIndex<K, V>

where K: 'static + Clone + Debug + Ord, V: 'static + Clone + Debug,

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

Formats the value using the given formatter.

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

fn default() -> Self

Creates a TreeIndex with the default parameters.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::default();

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

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V> PartialEq for TreeIndex<K, V>

where K: 'static + Clone + Ord, V: 'static + Clone + PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V> UnwindSafe for TreeIndex<K, V>