CITA-Trie

Rust implementation of the Modified Patricia Tree (aka Trie),

The implementation is strongly inspired by go-ethereum trie

Features

• Implementation of the Modified Patricia Tree
• Custom decoder (RLP is provided by default)
• Custom storage interface

Interfaces

DB

```rust pub trait DB: Send + Sync { type Error: Error;

fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error>;
fn insert(&self, key: &[u8], value: &[u8]) -> Result<(), Self::Error>;
fn contains(&self, key: &[u8]) -> Result<bool, Self::Error>;
fn remove(&self, key: &[u8]) -> Result<(), Self::Error>;

} ```

Decoder

```rust pub trait NodeCodec: Sized + Clone { type Error: ::std::error::Error;

const HASH_LENGTH: usize;

type Hash: AsRef<[u8]>
    + AsMut<[u8]>
    + Default
    + PartialEq
    + Eq
    + hash::Hash
    + Send
    + Sync
    + Clone;

fn decode<F, T>(&self, data: &[u8], f: F) -> Result<T, Self::Error>
where
    F: Fn(DataType) -> Result<T, Self::Error>;

fn encode_empty(&self) -> Vec<u8>;
fn encode_pair(&self, key: &[u8], value: &[u8]) -> Vec<u8>;
fn encode_values(&self, values: &[Vec<u8>]) -> Vec<u8>;
fn encode_raw(&self, raw: &[u8]) -> Vec<u8>;

fn decode_hash(&self, data: &[u8], is_hash: bool) -> Self::Hash;

} ```

Example

Use the RLP decoder

```rust use std::sync::Arc; use citatrie::codec::RLPNodeCodec; use citatrie::db::MemoryDB; use cita_trie::trie::{PatriciaTrie, Trie};

fn main() { let memdb = Arc::new(MemoryDB::new(true)); let key = "test-key".asbytes(); let value = "test-value".asbytes();

let root = {
    let mut trie = PatriciaTrie::new(Arc::clone(&memdb), RLPNodeCodec::default());
    trie.insert(key, value).unwrap();

    let v = trie.get(key).unwrap();
    assert_eq!(Some(value.to_vec()), v);
    trie.root().unwrap()
};

let mut trie = PatriciaTrie::from(Arc::clone(memdb), RLPNodeCodec::default(), &root).unwrap();
let exists = trie.contains(key).unwrap();
assert_eq!(exists, true);
let removed = trie.remove(key).unwrap();
assert_eq!(removed, true);
let new_root = trie.root().unwrap();
println!("new root = {:?}", new_root);

}

```

Custom decoder

Refer to RLPCodec in src/codec.rs

Why not use parity/trie

Because the parity/trie code is too difficult to understand, and the user needs to know the details of the trie to implement the decoder.

CITA-trie is more user-friendly, users can easily implement custom decoders without paying attention to trie implementation details, and provide an implementation of RLP by default.

However, this project is currently not perfect, stability and performance testing has not been done, it is not recommended to use in production environments