Struct rdms::llrb::Llrb

pub struct Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff,  { /* fields omitted */ }

Single threaded, in-memory index using left-leaning-red-black tree.

Methods

impl<K, V> Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

Different ways to construct a new Llrb index.

pub fn new<S: AsRef<str>>(name: S) -> Box<Llrb<K, V>>

Create an empty Llrb index, identified by name. Applications can choose unique names.

pub fn new_lsm<S>(name: S) -> Box<Llrb<K, V>> where
    S: AsRef<str>, 

Create a new Llrb index in lsm mode. In lsm mode, mutations are added as log for each key, instead of over-writing previous mutation. Note that, in case of back-to-back delete, first delete shall be applied and subsequent deletes shall be ignored.

pub fn set_spinlatch(&mut self, spin: bool)

Configure behaviour of spin-latch. If spin is true, calling thread shall spin until a latch is acquired or released, if false calling thread will yield to scheduler.

pub fn set_seqno(&mut self, seqno: u64)

application can set the start sequence number for this index.

pub fn clone(&self) -> Box<Llrb<K, V>>

impl<K, V> Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

Maintanence API.

pub fn is_lsm(&self) -> bool

Return whether this index support lsm mode.

pub fn len(&self) -> usize

Return number of entries in this index.

pub fn to_name(&self) -> String

Identify this index. Applications can choose unique names while creating Llrb indices.

pub fn to_seqno(&self) -> u64

Return current seqno.

pub fn to_stats(&self) -> Stats

Return quickly with basic statisics, only entries() method is valid with this statisics.

impl<K, V> Llrb<K, V> where
    K: Clone + Ord + Debug,
    V: Clone + Diff, 

Deep walk validate of Llrb index.

pub fn validate(&self) -> Result<Stats>

Validate LLRB tree with following rules:

• Root node is always black in color.
• Make sure that the maximum depth do not exceed 100.

Additionally return full statistics on the tree. Refer to [Stats] for more information.

Trait Implementations

impl<K, V> Footprint for Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

fn footprint(&self) -> isize

impl<K, V> Index<K, V> for Llrb<K, V> where
    K: Clone + Ord + Footprint,
    V: Clone + Diff + Footprint, 

type W = LlrbWriter<K, V>

A writer type, that can ingest key-value pairs, associated with this index.

type R = LlrbReader<K, V>

A writer type, that can ingest key-value pairs, associated with this index.

fn make_new(&self) -> Result<Box<Self>>

Make a new empty index of this type, with same configuration.

fn to_reader(&mut self) -> Result<Self::R>

Create a new reader handle, for multi-threading. Llrb uses spin-lock to coordinate between readers and writers.

fn to_writer(&mut self) -> Result<Self::W>

Create a new writer handle, for multi-threading. Llrb uses spin-lock to coordinate between readers and writers.

impl<K, V> Reader<K, V> for Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

Read operations on Llrb index.

fn get<Q: ?Sized>(&self, key: &Q) -> Result<Entry<K, V>> where
    K: Borrow<Q>,
    Q: Ord, 

Get the entry for key.

fn iter(&self) -> Result<IndexIter<K, V>>

Return an iterator over all entries in this index.

fn range<'a, R, Q: ?Sized>(&'a self, range: R) -> Result<IndexIter<K, V>> where
    K: Borrow<Q>,
    R: 'a + RangeBounds<Q>,
    Q: 'a + Ord, 

Range over all entries from low to high.

fn reverse<'a, R, Q: ?Sized>(&'a self, range: R) -> Result<IndexIter<K, V>> where
    K: Borrow<Q>,
    R: 'a + RangeBounds<Q>,
    Q: 'a + Ord, 

Reverse range over all entries from high to low.

fn get_with_versions<Q: ?Sized>(&self, key: &Q) -> Result<Entry<K, V>> where
    K: Borrow<Q>,
    Q: Ord, 

Short circuited to get().

fn iter_with_versions(&self) -> Result<IndexIter<K, V>>

Short circuited to iter().

fn range_with_versions<'a, R, Q: ?Sized>(
    &'a self,
    rng: R
) -> Result<IndexIter<K, V>> where
    K: Borrow<Q>,
    R: 'a + RangeBounds<Q>,
    Q: 'a + Ord, 

Short circuited to range().

fn reverse_with_versions<'a, R, Q: ?Sized>(
    &'a self,
    r: R
) -> Result<IndexIter<K, V>> where
    K: Borrow<Q>,
    R: 'a + RangeBounds<Q>,
    Q: 'a + Ord, 

Short circuited to reverse()

impl<K, V> Writer<K, V> for Llrb<K, V> where
    K: Clone + Ord + Footprint,
    V: Clone + Diff + Footprint, 

Create/Update/Delete operations on Llrb index.

fn set(&mut self, key: K, value: V) -> Result<Option<Entry<K, V>>>

Set {key, value} pair into index. If key is already present, update the value and return the previous entry, else create a new entry.

LSM mode: Add a new version for the key, perserving the old value.

fn set_cas(&mut self, key: K, value: V, cas: u64) -> Result<Option<Entry<K, V>>>

Similar to set, but succeeds only when CAS matches with entry's last seqno. In other words, since seqno is unique to each mutation, we use seqno of the mutation as the CAS value. Use CAS == 0 to enforce a create operation.

LSM mode: Add a new version for the key, perserving the old value.

fn delete<Q: ?Sized>(&mut self, key: &Q) -> Result<Option<Entry<K, V>>> where
    K: Borrow<Q>,
    Q: ToOwned<Owned = K> + Ord, 

Delete the given key. Note that back-to-back delete for the same key shall collapse into a single delete, first delete is ingested while the rest are ignored.

LSM mode: Mark the entry as deleted along with seqno at which it deleted

NOTE: K should be borrowable as &Q and Q must be convertable to owned K. This is require in lsm mode, where owned K must be inserted into the tree.

impl<K, V> Drop for Llrb<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V> AsRef<Llrb<K, V>> for LlrbReader<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

fn as_ref(&self) -> &Llrb<K, V>

Performs the conversion.

impl<K, V> AsMut<Llrb<K, V>> for LlrbWriter<K, V> where
    K: Clone + Ord,
    V: Clone + Diff, 

fn as_mut(&mut self) -> &mut Llrb<K, V>

Performs the conversion.