Struct scc::tree_index::TreeIndex

pub struct TreeIndex<K, V> where
    K: 'static + Clone + Ord + Send + Sync,
    V: 'static + Clone + Send + Sync,  { /* fields omitted */ }

A 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.

The key features of TreeIndex

• Write-free read: read operations never modify the shared data.
• Near lock-free write: write operations do not block unless a structural change is needed.

The key statistics for TreeIndex

• The maximum number of key-value pairs that a leaf can store: 8.
• The maximum number of leaves or child nodes that a node can point to: 9.
• The size of metadata per key-value pair in a leaf: 3-byte.
• The size of metadata per leaf or node in a node: size_of(K) + 4.

Implementations

impl<K, V> TreeIndex<K, V> where
    K: 'static + Clone + Ord + Send + Sync,
    V: 'static + Clone + Send + Sync, 

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

Creates an empty TreeIndex.

Examples

use scc::TreeIndex;

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

assert!(treeindex.read(&1, |_, v| *v).is_none());

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

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

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

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());
assert!(treeindex.insert(1, 10).is_ok());
assert_eq!(treeindex.read(&1, |k, v| *v).unwrap(), 10);

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::ebr::Barrier;
use scc::TreeIndex;

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

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

let barrier = Barrier::new();
let value_ref = treeindex.read_with(&1, |k, v| v, &barrier).unwrap();
assert_eq!(*value_ref, 10);

pub fn clear(&self)

Clears the TreeIndex.

Examples

use scc::TreeIndex;

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

for key in 0..16_u64 {
    assert!(treeindex.insert(key, 10).is_ok());
}

treeindex.clear();

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

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

for key in 0..16_u64 {
    assert!(treeindex.insert(key, 10).is_ok());
}

assert_eq!(treeindex.len(), 16);

pub fn is_empty(&self) -> bool

Returns true if the TreeIndex is empty.

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!(treeindex.is_empty());

pub fn depth(&self) -> usize

Returns the depth of the TreeIndex.

Examples

use scc::TreeIndex;

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

for key in 0..16_u64 {
    let result = treeindex.insert(key, 10);
    assert!(result.is_ok());
}

assert_eq!(treeindex.depth(), 1);

pub fn iter<'t, 'b>(&'t self, barrier: &'b Barrier) -> Visitor<'t, 'b, K, V>

Returns a Visitor.

The returned Visitor starts scanning from the minimum key-value pair.

Examples

use scc::ebr::Barrier;
use scc::TreeIndex;

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

assert!(treeindex.insert(1, 10).is_ok());
assert!(treeindex.insert(2, 11).is_ok());
assert!(treeindex.insert(3, 13).is_ok());

let barrier = Barrier::new();

let mut visitor = treeindex.iter(&barrier);
assert_eq!(visitor.next().unwrap(), (&1, &10));
assert_eq!(visitor.next().unwrap(), (&2, &11));
assert_eq!(visitor.next().unwrap(), (&3, &13));
assert!(visitor.next().is_none());

pub fn range<'t, 'b, R: RangeBounds<K>>(
    &'t self,
    range: R,
    barrier: &'b Barrier
) -> Range<'t, 'b, K, V, R>

Returns a Range that scans keys in the given range.

Examples

use scc::ebr::Barrier;
use scc::TreeIndex;

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

for i in 0..10 {
    assert!(treeindex.insert(i, 10).is_ok());
}

let barrier = Barrier::new();

assert_eq!(treeindex.range(1..1, &barrier).count(), 0);
assert_eq!(treeindex.range(4..8, &barrier).count(), 4);
assert_eq!(treeindex.range(4..=8, &barrier).count(), 5);

impl<K, V> TreeIndex<K, V> where
    K: 'static + Clone + Display + Ord + Send + Sync,
    V: 'static + Clone + Display + Send + Sync, 

pub fn print<T: Write>(&self, output: &mut T) -> Result<()>

Prints the TreeIndex contents to the given output in the DOT language.

Errors

An io::Error can be returned.

Examples

use scc::TreeIndex;

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

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

treeindex.print(&mut std::io::stdout());

Trait Implementations

impl<K, V> Default for TreeIndex<K, V> where
    K: 'static + Clone + Ord + Send + Sync,
    V: 'static + Clone + Send + Sync, 

fn default() -> Self

Creates a TreeIndex with the default parameters.

Examples

use scc::TreeIndex;

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

assert!(treeindex.read(&1, |_, v| *v).is_none());