Struct scc::tree_index::TreeIndex
source · pub struct TreeIndex<K, V> { /* private fields */ }
Expand description
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§
source§impl<K, V> TreeIndex<K, V>
impl<K, V> TreeIndex<K, V>
sourcepub fn insert(&self, key: K, val: V) -> Result<(), (K, V)>
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);
sourcepub async fn insert_async(&self, key: K, val: V) -> Result<(), (K, V)>
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);
sourcepub fn remove<Q>(&self, key: &Q) -> bool
pub fn remove<Q>(&self, key: &Q) -> bool
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));
sourcepub async fn remove_async<Q>(&self, key: &Q) -> bool
pub async fn remove_async<Q>(&self, key: &Q) -> bool
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);
sourcepub fn remove_if<Q, F: FnMut(&V) -> bool>(&self, key: &Q, condition: F) -> bool
pub fn remove_if<Q, F: FnMut(&V) -> bool>(&self, key: &Q, condition: F) -> bool
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));
sourcepub async fn remove_if_async<Q, F: FnMut(&V) -> bool>(
&self,
key: &Q,
condition: F,
) -> bool
pub async fn remove_if_async<Q, F: FnMut(&V) -> bool>( &self, key: &Q, condition: F, ) -> bool
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);
sourcepub fn remove_range<R: RangeBounds<K>>(&self, range: R)
pub fn remove_range<R: RangeBounds<K>>(&self, range: R)
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. Also, no asynchronous version of this method is provided
which will be added once
Issue 123
is
resolved.
§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));
sourcepub fn peek<'g, Q>(&self, key: &Q, guard: &'g Guard) -> Option<&'g V>
pub fn peek<'g, Q>(&self, key: &Q, guard: &'g Guard) -> Option<&'g V>
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::TreeIndex;
use scc::ebr::Guard;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
let guard = Guard::new();
assert!(treeindex.peek(&1, &guard).is_none());
sourcepub fn peek_with<Q, R, F: FnOnce(&Q, &V) -> R>(
&self,
key: &Q,
reader: F,
) -> Option<R>
pub fn peek_with<Q, R, F: FnOnce(&Q, &V) -> R>( &self, key: &Q, reader: F, ) -> Option<R>
Peeks a key-value pair without acquiring locks.
Returns None
if the key does not exist.
§Examples
use scc::TreeIndex;
let treeindex: TreeIndex<u64, u32> = TreeIndex::new();
assert!(treeindex.peek_with(&1, |k, v| *v).is_none());
sourcepub fn iter<'t, 'g>(&'t self, guard: &'g Guard) -> Iter<'t, 'g, K, V> ⓘ
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());
sourcepub fn range<'t, 'g, R: RangeBounds<K>>(
&'t self,
range: R,
guard: &'g Guard,
) -> Range<'t, 'g, K, V, R> ⓘ
pub fn range<'t, 'g, R: RangeBounds<K>>( &'t self, range: R, guard: &'g Guard, ) -> Range<'t, 'g, K, V, R> ⓘ
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§
Auto Trait Implementations§
impl<K, V> !Freeze for TreeIndex<K, V>
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§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)