Struct RaxMap 

pub struct RaxMap<K: RaxKey, V> {
    pub rax: *mut rax,
    /* private fields */
}

Redis has a beautiful Radix Tree implementation in ANSI C. This brings it to Rust and creates a safe Map like wrapper for it. This is very similar in utility to a BTreeMap, but RAX is likely much faster and more efficient. Naive testing showed a 2x-4x improvement for all common operations. The only disadvantage to BTreeMap is that BTree’s allow much more flexibility in regards to comparing keys. Radix trees are lexicographically only. Composite keys where the non-last member is variable length could be something BTrees could handle much easier.

Internal RAX Node Layout

uint32_t iskey:1; /* Does this node contain a key? / uint32_t isnull:1; / Associated value is NULL (don’t store it). / uint32_t iscompr:1; / Node is compressed. / uint32_t size:29; / Number of children, or compressed string len. */

+––+—+––––+––––+––––+––––+ |HDR |xyz| x-ptr | y-ptr | z-ptr |dataptr | +––+—+––––+––––+––––+––––+

As is evident above, there is no storage penalty for NULL values.

Keys are represented in compressed form therefore, there is no need to pump in Boxed keys or any sort of heap allocated chunk of memory. Stack or heap keys may be used from rust. Values can either be a sizeof size integer or it’s a data pointer to a heap allocated / Boxed value.

Iterators were designed to be fast and attempt to only use stack allocated memory. RaxMap provides a model to take full advantage of stack allocated iterators through wrapping in a closure.

#Examples

use rax::RaxMap;
let mut r = RaxMap::new();
r.insert(1, Box::new("my heap allocation".to_string()));
r.insert(2, Box::new("my other heap allocation".to_string()));

r.iter(|r, iter| {
    // Place iterator at the first entry.
    if !iter.seek_min() {
        // EOF
        return;
    }

    // Can test EOF at any time.
    if iter.eof() {
        // EOF
        return;
    }

    while iter.forward() {
        iter.key();
        iter.value();
    }
    // In reverse
    // Place iterator at the end.
    if !iter.seek_max() {
        // EOF
        return;
    }
    while iter.back() {
        iter.key();
        iter.value();
    }

    // Seek
    if !iter.seek(">=", 2) {
        // EOF
    }
    while iter.forward() {
        iter.key();
        iter.value();
    }
});

Fields

rax: *mut rax

Implementations

impl<K: RaxKey, V> RaxMap<K, V>

Implementation of RaxMap

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

pub fn try_new() -> Result<RaxMap<K, V>, RaxError>

Fallible constructor. Returns Err(OutOfMemory) when raxNew() returns NULL.

pub fn len(&self) -> u64

The number of entries in the RAX

pub fn size(&self) -> u64

The number of entries in the RAX

pub fn is_empty(&self) -> bool

Returns true if the RAX is empty.

pub fn show(&self)

Prints the Rax as ASCII art to stdout.

pub fn insert_null(&mut self, key: K) -> Result<Option<Box<V>>, RaxError>

Insert or replace existing key with a NULL value.

pub fn try_insert( &mut self, key: K, data: Box<V>, ) -> Result<Option<Box<V>>, RaxError>

Insert a new entry into the RAX if an existing one does not exist.

pub unsafe fn try_insert_ptr( &mut self, key: K, value: *mut u8, ) -> Result<Option<*mut u8>, RaxError>

Try to insert a raw pointer value into the RAX.

Safety

value must be a valid pointer or null.

pub fn insert( &mut self, key: K, data: Box<V>, ) -> Result<Option<Box<V>>, RaxError>

Insert a new entry into the RAX replacing and returning the existing entry for the supplied key.

pub unsafe fn insert_ptr( &mut self, key: K, value: *mut u8, ) -> Result<Option<*mut u8>, RaxError>

Insert a raw pointer value into the RAX.

Safety

value must be a valid pointer or null.

pub fn remove(&mut self, key: K) -> (bool, Option<Box<V>>)

Remove an entry from the RAX and return the associated value.

pub fn find_exists(&self, key: K) -> (bool, Option<&V>)

Find a key and return whether it exists along with its value.

pub fn find(&self, key: K) -> Option<&V>

Same as get but added for semantics parity.

pub fn get(&self, key: K) -> Option<&V>

Get the value associated with the key.

pub fn exists(&self, key: K) -> bool

Determines if the supplied key exists in the Rax.

pub fn seek_min<F>(&mut self, f: F)

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>),

Seek to the minimum key and execute the closure.

pub fn seek_min_result<R, F>(&mut self, f: F) -> Result<R, RaxError>

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>) -> Result<R, RaxError>,

Seek to the minimum key and execute the closure, returning a result.

pub fn seek_max<F>(&mut self, f: F)

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>),

Seek to the maximum key and execute the closure.

pub fn seek_max_result<R, F>(&mut self, f: F) -> Result<R, RaxError>

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>) -> Result<R, RaxError>,

Seek to the maximum key and execute the closure, returning a result.

pub fn seek<F>(&mut self, op: &str, key: K, f: F)

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>),

Seek to the given key using the specified operator and execute the closure.

pub fn seek_result<R, F>( &mut self, op: &str, key: K, f: F, ) -> Result<R, RaxError>

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>) -> Result<R, RaxError>,

Seek to the given key using the specified operator and execute the closure, returning a result.

pub fn iter<F>(&mut self, f: F)

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>),

Create an iterator and execute the closure.

pub fn iter_result<F, R>(&mut self, f: F) -> Result<R, RaxError>

where F: Fn(&mut RaxMap<K, V>, &mut RaxIterator<K, V>) -> Result<R, RaxError>,

Create an iterator and execute the closure, returning a result.

Trait Implementations

impl<K: RaxKey, V> Default for RaxMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: RaxKey, V> Drop for RaxMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.