pub struct BzTree<K: Ord, V> { /* private fields */ }
Expand description
BzTree data structure.
Key-value trait bounds
Keys should implement Ord and Clone, values should be Clone, Send and Sync.
Because of nature of concurrent trees, node split/merge operations are optimistic and can fail: implementation creates copy of nodes which is a part of split/merge process and try to replace existing node by new one. At one point in time, 2 nodes can points to the same key-value pair. To reduce count of unsafe code inside tree implementation, key and values should implement Clone.
Visibility of changes
Changes made by insert
and delete
operations will be immediately visible through
get
/scan
operations if insert
/delete
happens before get
/scan
.
Scan/range
operation may see tree updates which made concurrently with scanner progress, e.g.
scanner doesn’t provide snapshot view of tree.
Memory reclamation
BzTree uses crossbeam_epoch::Guard memory reclamation to free memory of removed/replaced key-values. Because of internal representation of tree nodes, drop of some removed keys can be delayed until node split/merge. This limitation caused by ‘sorted’ space inside tree node which uses binary search to locate keys inside. Current implementation of binary search should have an access to removed/replaced keys during search.
Heap allocation
BzTree allocates memory for nodes on heap. Key and values in leaf nodes(e.g., nodes which stores actual user data) stored directly in node memory without additional heap allocations. Links to other nodes, stored in interim nodes, allocated on heap.
Thread safety
BzTree can be safely shared between threads, e.g. it implements Send ans Sync.
Implementations
sourceimpl<K, V> BzTree<K, V>where
K: Clone + Ord,
V: Clone + Send + Sync,
impl<K, V> BzTree<K, V>where
K: Clone + Ord,
V: Clone + Send + Sync,
sourcepub fn with_node_size(node_size: u16) -> BzTree<K, V>
pub fn with_node_size(node_size: u16) -> BzTree<K, V>
Create new tree with passed node size.
sourcepub fn insert(&self, key: K, value: V, guard: &Guard) -> bool
pub fn insert(&self, key: K, value: V, guard: &Guard) -> bool
Insert key-value pair to tree if no elements with same key already exists.
Return
Returns true if key-value pair successfully inserted, otherwise false if key already in tree.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
let key = "key".to_string();
assert!(tree.insert(key.clone(), 1, &guard));
assert!(!tree.insert(key.clone(), 5, &guard));
sourcepub fn upsert<'g>(&'g self, key: K, value: V, guard: &'g Guard) -> Option<&'g V>
pub fn upsert<'g>(&'g self, key: K, value: V, guard: &'g Guard) -> Option<&'g V>
Insert key-value pair if not already exists, otherwise replace value of existing element.
Return
Returns value previously associated with same key or None
.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
let key = "key".to_string();
assert!(matches!(tree.upsert(key.clone(), 10, &guard), None));
assert!(matches!(tree.upsert(key.clone(), 11, &guard), Some(10)));
sourcepub fn delete<'g, Q>(&'g self, key: &Q, guard: &'g Guard) -> Option<&'g V>where
K: Borrow<Q>,
Q: Ord + Clone,
pub fn delete<'g, Q>(&'g self, key: &Q, guard: &'g Guard) -> Option<&'g V>where
K: Borrow<Q>,
Q: Ord + Clone,
Delete value associated with key.
Return
Returns removed value if key found in tree.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
let key = "key".to_string();
assert!(tree.insert(key.clone(), 10, &guard));
assert!(matches!(tree.delete(&key, &guard), Some(&10)));
sourcepub fn get<'g, Q>(&'g self, key: &Q, guard: &'g Guard) -> Option<&'g V>where
K: Borrow<Q>,
Q: Clone + Ord,
pub fn get<'g, Q>(&'g self, key: &Q, guard: &'g Guard) -> Option<&'g V>where
K: Borrow<Q>,
Q: Clone + Ord,
Get value associated with key.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
let key = "key".to_string();
assert!(tree.insert(key.clone(), 10, &guard));
assert!(matches!(tree.get(&key, &guard), Some(&10)));
sourcepub fn range<'g>(
&'g self,
key_range: impl RangeBounds<K> + 'g + Clone,
guard: &'g Guard
) -> impl DoubleEndedIterator<Item = (&'g K, &'g V)> + 'g
pub fn range<'g>(
&'g self,
key_range: impl RangeBounds<K> + 'g + Clone,
guard: &'g Guard
) -> impl DoubleEndedIterator<Item = (&'g K, &'g V)> + 'g
Create tree range scanner which will return values whose keys is in passed range.
Visibility of changes made in tree during scan, described in BzTree doc.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
let mut scanner = tree.range("key1".to_string()..="key2".to_string(), &guard);
assert!(matches!(scanner.next(), Some((_, &1))));
assert!(matches!(scanner.next(), Some((_, &2))));
assert!(matches!(scanner.next(), None));
sourcepub fn iter<'g>(
&'g self,
guard: &'g Guard
) -> impl DoubleEndedIterator<Item = (&'g K, &'g V)>
pub fn iter<'g>(
&'g self,
guard: &'g Guard
) -> impl DoubleEndedIterator<Item = (&'g K, &'g V)>
Create iterator through all key-values of tree.
Iterator based on tree range scanner and have same changes visibility guarantees.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
let mut scanner = tree.iter(&guard);
assert!(matches!(scanner.next(), Some((_, &1))));
assert!(matches!(scanner.next(), Some((_, &2))));
assert!(matches!(scanner.next(), Some((_, &3))));
assert!(matches!(scanner.next(), None));
sourcepub fn first<'g>(&'g self, guard: &'g Guard) -> Option<(&'g K, &'g V)>
pub fn first<'g>(&'g self, guard: &'g Guard) -> Option<(&'g K, &'g V)>
Return first element of tree according to key ordering.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
assert!(matches!(tree.first(&guard), Some((_, &1))));
sourcepub fn last<'g>(&'g self, guard: &'g Guard) -> Option<(&'g K, &'g V)>
pub fn last<'g>(&'g self, guard: &'g Guard) -> Option<(&'g K, &'g V)>
Return last element of tree according to key ordering.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
assert!(matches!(tree.last(&guard), Some((_, &3))));
sourcepub fn pop_first<'g>(&'g self, guard: &'g Guard) -> Option<(K, &'g V)>
pub fn pop_first<'g>(&'g self, guard: &'g Guard) -> Option<(K, &'g V)>
Remove and return first element of tree according to key ordering.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
assert!(matches!(tree.pop_first(&guard), Some((_, &1))));
assert!(matches!(tree.pop_first(&guard), Some((_, &2))));
assert!(matches!(tree.pop_first(&guard), Some((_, &3))));
assert!(matches!(tree.pop_first(&guard), None));
sourcepub fn pop_last<'g>(&'g self, guard: &'g Guard) -> Option<(K, &'g V)>
pub fn pop_last<'g>(&'g self, guard: &'g Guard) -> Option<(K, &'g V)>
Remove and return last element of tree according to key ordering.
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
tree.insert("key1".to_string(), 1, &guard);
tree.insert("key2".to_string(), 2, &guard);
tree.insert("key3".to_string(), 3, &guard);
assert!(matches!(tree.pop_last(&guard), Some((_, &3))));
assert!(matches!(tree.pop_last(&guard), Some((_, &2))));
assert!(matches!(tree.pop_last(&guard), Some((_, &1))));
assert!(matches!(tree.pop_last(&guard), None));
sourcepub fn compute<'g, Q, F>(&'g self, key: &Q, new_val: F, guard: &'g Guard) -> boolwhere
K: Borrow<Q>,
Q: Ord + Clone,
F: FnMut((&K, &V)) -> Option<V>,
pub fn compute<'g, Q, F>(&'g self, key: &Q, new_val: F, guard: &'g Guard) -> boolwhere
K: Borrow<Q>,
Q: Ord + Clone,
F: FnMut((&K, &V)) -> Option<V>,
Update or delete element with passed key using conditional logic.
Function F
accepts current value of key and based on it, produces new value.
If F
returns Some(V)
then current value will be updated. Otherwise(None
) key will
be removed from tree.
Function F
can be called several times in case of concurrent modification of tree.
Because of this behaviour, function code should not modify global application state or
such code should be carefully designed(understanding consequences of repeated function
calls for same key).
Examples
use bztree::BzTree;
let tree = BzTree::new();
let guard = crossbeam_epoch::pin();
let key = "key".to_string();
tree.insert(key.clone(), 2, &guard);
assert!(tree.compute(&key, |(_, v)| Some(v + 1), &guard));
assert!(matches!(tree.get(&key, &guard), Some(&3)));
assert!(tree.compute(&key, |(_, v)| {
if *v == 3 {
None
} else {
Some(v + 1)
}
}, &guard));
assert!(matches!(tree.get(&key, &guard), None));