Struct bztree::BzTree

pub struct BzTree<K: Ord, V> { /* fields omitted */ }

BzTree data structure.

Key-value trait bounds

Keys should implement Ord and Hash, values should be 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] 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

impl<K, V> BzTree<K, V> where
    K: Clone + Ord,
    V: Clone + Send + Sync, 

pub fn new() -> BzTree<K, V>

Create new tree with default node size.

pub fn with_node_size(node_size: u16) -> BzTree<K, V>

Create new tree with passed node size.

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));

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)));

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)));

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)));

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));

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));

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))));

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))));

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));

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));

pub fn compute<'g, Q, F>(
    &'g self,
    key: &Q,
    new_val: F,
    guard: &'g Guard
) -> bool where
    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));

Trait Implementations

impl<K, V> Default for BzTree<K, V> where
    K: Clone + Ord,
    V: Clone + Send + Sync, 

fn default() -> Self

Returns the “default value” for a type.

impl<K: Ord, V> Send for BzTree<K, V>

impl<K: Ord, V> Sync for BzTree<K, V>