Struct hat_trie::DenseVecTrieNode

pub struct DenseVecTrieNode<K, V> where
    K: AsPrimitive<usize> + Bounded + Copy + Debug + Hash + FromPrimitive + PartialEq + PartialOrd + Sized + Unsigned,
    Box<[K]>: Clone + PartialEq,
    V: Clone + Debug + Default,  { /* fields omitted */ }

A type of Trie that implemented by using Vec index as encoded key.

Care should be taken before using this Trie.

The memory requirement for this Trie is equals to bits of key. For example, if key is of type &u8, each layer of Trie will need at least 2^8 * 4 bytes (1024 bytes) + all other meta such as minimum and maximum length of stored key, threshold for burst/split, etc. If key is of type &u32, each layer will need 2^32 * 4 bytes (16GB).

Implementations

impl<K, V> DenseVecTrieNode<K, V> where
    K: Copy + AsPrimitive<usize> + Bounded + Debug + Hash + FromPrimitive + PartialEq + PartialOrd + Sized + Unsigned,
    Box<[K]>: Clone + PartialEq,
    V: Clone + Debug + Default, 

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

Create new empty DenseVecTrieNode.

It will automatically expand into larger trie by append necesseary child type to maintain it fitness. This method return default configuration for the DenseVecTrieNode.

pub fn with_spec(
    threshold: usize,
    init_bucket_size: usize,
    init_bucket_slots: usize,
    bucket_load_factor: usize
) -> DenseVecTrieNode<K, V>

Create new empty DenseVecTrieNode.

It will automatically expand into larger trie by append necesseary child type to maintain it fitness. This method take specifications which this trie should maintain in order to fit with expected performance.

Parameters

threshold - The number of element in each leaf container which if exceed will cause node burst/split depending on type of node at that moment. init_bucket_size - The initial size of bucket. Bucket is a container used in leaf node. This number shall be large enough to have only few data in each slot in bucket but it shall also be small enough to fit into single page of memory for caching reason. init_bucket_slots - The initial size of each slot which will store actual data. It will grow if there is a lot of hash collision. bucket_load_factor - The number of element in bucket which if reached, will expand the bucket size by 2 times of current size.

Return

A trie instance of type DenseVecTrieNode

Trait Implementations

impl<K: Clone, V: Clone> Clone for DenseVecTrieNode<K, V> where
    K: AsPrimitive<usize> + Bounded + Copy + Debug + Hash + FromPrimitive + PartialEq + PartialOrd + Sized + Unsigned,
    Box<[K]>: Clone + PartialEq,
    V: Clone + Debug + Default, 

fn clone(&self) -> DenseVecTrieNode<K, V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for DenseVecTrieNode<K, V> where
    K: AsPrimitive<usize> + Bounded + Copy + Debug + Hash + FromPrimitive + PartialEq + PartialOrd + Sized + Unsigned,
    Box<[K]>: Clone + PartialEq,
    V: Clone + Debug + Default, 

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<K, V> TrieNode<K, V> for DenseVecTrieNode<K, V> where
    K: AsPrimitive<usize> + Bounded + Copy + Debug + Hash + FromPrimitive + PartialEq + PartialOrd + Sized + Unsigned,
    Box<[K]>: Clone + PartialEq,
    V: Clone + Debug + Default, 

fn new_split(bucket: ArrayHash<XxHash64, Box<[K]>, V>, threshold: usize) -> Self

Construct a new trie node from a bucket of pure node. This happen whenever burst or split threshold reach. It consume a given bucket and return a new Trie node which contains splitted bucket as childs.

fn child<'a>(&'a self, key: &K) -> &'a NodeType<K, Self, V>

Get a child node of given key from current node.

fn value(&self) -> Option<&V>

Retrieve a value of current node.

fn value_mut(&mut self) -> &mut Option<V>

Retrieve a mutable value of current node.

fn put(&mut self, key: &[K], value: V) -> Option<V>

Put value into this trie node.

fn try_put<'a>(&'a mut self, key: &[K], value: V) -> Option<&'a V> where
    K: 'a, 

Try putting value into this trie.

fn max_key_len(&self) -> usize

Utilities function that help shortcut key lookup when caller request key greater than max_key_len, it mean there's no such key in this trie.

fn min_key_len(&self) -> usize

Utilities function that help shortcut key lookup when caller request key less than min_key_len, it mean there's no such key in this trie.

fn get<'a>(&'a self, key: &[K]) -> Option<&'a V> where
    K: 'a, 

Get a value from this trie associated with given key slice.

fn prefix<'a, 'b>(&'a self, key: &'b [K]) -> PrefixIterator<'a, 'b, K, Self, V>

Find all possible prefix in given key that match with this trie node.

fn longest_prefix<'a, 'b>(&'a self, key: &'b [K]) -> Option<(&'b [K], &'a V)> where
    K: 'a, 

Find a longest prefix from given key from this Trie.