Struct scc::tree_index::TreeIndex
source · [−]pub struct TreeIndex<K, V> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync, { /* private fields */ }
Expand description
Scalable concurrent B+ tree.
TreeIndex
is a B+ tree variant that is optimized for read operations. Read operations, such
as read, scan, are neither blocked nor interrupted by other threads. Write operations, such as
insert, remove, do not block if they do not entail structural changes to the tree.
Notes
TreeIndex
methods are linearlizable, however its iterator methods are not; Visitor
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.
The key statistics for TreeIndex
- The maximum number of key-value pairs that a leaf can store: 14.
- The maximum number of leaves or child nodes that a node can point to: 15.
- The size of metadata per key-value pair in a leaf: ~3-byte.
Implementations
sourceimpl<K, V> TreeIndex<K, V> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync,
impl<K, V> TreeIndex<K, V> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync,
sourcepub fn insert(&self, key: K, value: V) -> Result<(), (K, V)>
pub fn insert(&self, key: K, value: 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.read(&1, |k, v| *v).unwrap(), 10);
sourcepub async fn insert_async(&self, key: K, value: V) -> Result<(), (K, V)>
pub async fn insert_async(&self, key: K, value: V) -> Result<(), (K, V)>
Inserts a key-value pair.
It is an asynchronous method returning an impl Future
for the caller to await or poll.
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);
sourcepub fn remove<Q>(&self, key_ref: &Q) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub fn remove<Q>(&self, key_ref: &Q) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
Removes a key-value pair.
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));
sourcepub async fn remove_async<Q>(&self, key_ref: &Q) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub async fn remove_async<Q>(&self, key_ref: &Q) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
Removes a key-value pair.
It is an asynchronous method returning an impl Future
for the caller to await or poll.
Examples
use scc::TreeIndex;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let future_remove = treeindex.remove_async(&1);
sourcepub fn remove_if<Q, F: FnMut(&V) -> bool>(
&self,
key_ref: &Q,
condition: F
) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub fn remove_if<Q, F: FnMut(&V) -> bool>(
&self,
key_ref: &Q,
condition: F
) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
Removes a key-value pair if the given condition is met.
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));
sourcepub async fn remove_if_async<Q, F: FnMut(&V) -> bool>(
&self,
key_ref: &Q,
condition: F
) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub async fn remove_if_async<Q, F: FnMut(&V) -> bool>(
&self,
key_ref: &Q,
condition: F
) -> bool where
K: Borrow<Q>,
Q: Ord + ?Sized,
Removes a key-value pair if the given condition is met.
It is an asynchronous method returning an impl Future
for the caller to await or poll.
Examples
use scc::TreeIndex;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let future_remove = treeindex.remove_if_async(&1, |v| *v == 0);
sourcepub fn read<Q, R, F: FnOnce(&Q, &V) -> R>(
&self,
key_ref: &Q,
reader: F
) -> Option<R> where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub fn read<Q, R, F: FnOnce(&Q, &V) -> R>(
&self,
key_ref: &Q,
reader: F
) -> Option<R> where
K: Borrow<Q>,
Q: Ord + ?Sized,
Reads a key-value pair.
It returns None
if the key does not exist.
Examples
use scc::TreeIndex;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
assert!(treeindex.read(&1, |k, v| *v).is_none());
sourcepub fn read_with<'b, Q, R, F: FnOnce(&Q, &'b V) -> R>(
&self,
key_ref: &Q,
reader: F,
barrier: &'b Barrier
) -> Option<R> where
K: Borrow<Q>,
Q: Ord + ?Sized,
pub fn read_with<'b, Q, R, F: FnOnce(&Q, &'b V) -> R>(
&self,
key_ref: &Q,
reader: F,
barrier: &'b Barrier
) -> Option<R> where
K: Borrow<Q>,
Q: Ord + ?Sized,
Reads a key-value pair using the supplied Barrier
.
It enables the caller to use the value reference outside the method. It returns None
if the key does not exist.
Examples
use scc::TreeIndex;
use scc::ebr::Barrier;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let barrier = Barrier::new();
assert!(treeindex.read_with(&1, |k, v| v, &barrier).is_none());
sourcepub fn iter<'t, 'b>(&'t self, barrier: &'b Barrier) -> Visitor<'t, 'b, K, V>ⓘNotable traits for Visitor<'t, 'b, K, V>impl<'t, 'b, K, V> Iterator for Visitor<'t, 'b, K, V> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync, type Item = (&'b K, &'b V);
pub fn iter<'t, 'b>(&'t self, barrier: &'b Barrier) -> Visitor<'t, 'b, K, V>ⓘNotable traits for Visitor<'t, 'b, K, V>impl<'t, 'b, K, V> Iterator for Visitor<'t, 'b, K, V> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync, type Item = (&'b K, &'b V);
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync, type Item = (&'b K, &'b V);
Returns a Visitor
.
The returned Visitor
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::Barrier;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let barrier = Barrier::new();
let mut visitor = treeindex.iter(&barrier);
assert!(visitor.next().is_none());
sourcepub fn range<'t, 'b, R: RangeBounds<K>>(
&'t self,
range: R,
barrier: &'b Barrier
) -> Range<'t, 'b, K, V, R>ⓘNotable traits for Range<'t, 'b, K, V, R>impl<'t, 'b, K, V, R> Iterator for Range<'t, 'b, K, V, R> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync,
R: RangeBounds<K>, type Item = (&'b K, &'b V);
pub fn range<'t, 'b, R: RangeBounds<K>>(
&'t self,
range: R,
barrier: &'b Barrier
) -> Range<'t, 'b, K, V, R>ⓘNotable traits for Range<'t, 'b, K, V, R>impl<'t, 'b, K, V, R> Iterator for Range<'t, 'b, K, V, R> where
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync,
R: RangeBounds<K>, type Item = (&'b K, &'b V);
K: 'static + Clone + Ord + Send + Sync,
V: 'static + Clone + Send + Sync,
R: RangeBounds<K>, type Item = (&'b K, &'b V);
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::Barrier;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let barrier = Barrier::new();
assert_eq!(treeindex.range(4..=8, &barrier).count(), 0);
Trait Implementations
Auto Trait Implementations
impl<K, V> RefUnwindSafe for TreeIndex<K, V>
impl<K, V> Send for TreeIndex<K, V>
impl<K, V> Sync for TreeIndex<K, V>
impl<K, V> Unpin for TreeIndex<K, V>
impl<K, V> !UnwindSafe for TreeIndex<K, V>
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more