Merkle Patricia Tree "Trie": a modifed base-16 Radix tree. More...

#include <TrieDB.h>

Inheritance diagram for dev::GenericTrieDB< _DB >:

Collaboration diagram for dev::GenericTrieDB< _DB >:

Classes
class	iterator

Public Types
using	DB = _DB

Public Member Functions
	GenericTrieDB (DB *_db=nullptr)

	GenericTrieDB (DB *_db, h256 const &_root, Verification _v=Verification::Normal)

	~GenericTrieDB ()

void	open (DB *_db)

void	open (DB *_db, h256 const &_root, Verification _v=Verification::Normal)

void	init ()

void	setRoot (h256 const &_root, Verification _v=Verification::Normal)

bool	isNull () const
	True if the trie is uninitialised (i.e. that the DB doesn't contain the root node). More...

bool	isEmpty () const
	True if the trie is initialised but empty (i.e. that the DB contains the root node which is empty). More...

h256 const &	root () const

std::string	at (bytes const &_key) const

std::string	at (bytesConstRef _key) const

void	insert (bytes const &_key, bytes const &_value)

void	insert (bytesConstRef _key, bytes const &_value)

void	insert (bytes const &_key, bytesConstRef _value)

void	insert (bytesConstRef _key, bytesConstRef _value)

void	remove (bytes const &_key)

void	remove (bytesConstRef _key)

bool	contains (bytes const &_key)

bool	contains (bytesConstRef _key)

iterator	begin () const

iterator	end () const

iterator	lower_bound (bytesConstRef _key) const

void	descendKey (h256 const &_k, h256Hash &_keyMask, bool _wasExt, std::ostream *_out, int _indent=0) const
	Used for debugging, scans the whole trie. More...

void	descendEntry (RLP const &_r, h256Hash &_keyMask, bool _wasExt, std::ostream *_out, int _indent) const
	Used for debugging, scans the whole trie. More...

void	descendList (RLP const &_r, h256Hash &_keyMask, bool _wasExt, std::ostream *_out, int _indent) const
	Used for debugging, scans the whole trie. More...

h256Hash	leftOvers (std::ostream *_out=nullptr) const
	Used for debugging, scans the whole trie. More...

void	debugStructure (std::ostream &_out) const
	Used for debugging, scans the whole trie. More...

bool	check (bool _requireNoLeftOvers) const
	Used for debugging, scans the whole trie. More...

DB const *	db () const
	Get the underlying database. More...

DB *	db ()

Private Member Functions
RLPStream &	streamNode (RLPStream &_s, bytes const &_b)

std::string	atAux (RLP const &_here, NibbleSlice _key) const

void	mergeAtAux (RLPStream &_out, RLP const &_replace, NibbleSlice _key, bytesConstRef _value)

bytes	mergeAt (RLP const &_replace, NibbleSlice _k, bytesConstRef _v, bool _inLine=false)

bytes	mergeAt (RLP const &_replace, h256 const &_replaceHash, NibbleSlice _k, bytesConstRef _v, bool _inLine=false)

bool	deleteAtAux (RLPStream &_out, RLP const &_replace, NibbleSlice _key)

bytes	deleteAt (RLP const &_replace, NibbleSlice _k)

bytes	place (RLP const &_orig, NibbleSlice _k, bytesConstRef _s)

bytes	remove (RLP const &_orig)

bytes	cleve (RLP const &_orig, unsigned _s)

bytes	graft (RLP const &_orig)

bytes	merge (RLP const &_orig, byte _i)

bytes	branch (RLP const &_orig)

bool	isTwoItemNode (RLP const &_n) const

std::string	deref (RLP const &_n) const

std::string	node (h256 const &_h) const

h256	forceInsertNode (bytesConstRef _v)

void	forceInsertNode (h256 const &_h, bytesConstRef _v)

void	forceKillNode (h256 const &_h)

void	killNode (RLP const &_d)

void	killNode (RLP const &_d, h256 const &_h)

Private Attributes
h256	m_root

DB *	m_db = nullptr

Detailed Description

template<class _DB>
class dev::GenericTrieDB< _DB >

Merkle Patricia Tree "Trie": a modifed base-16 Radix tree.

This version uses a database backend. Usage:

GenericTrieDB<MyDB> t(&myDB);
assert(t.isNull());
t.init();
assert(t.isEmpty());
t.insert(x, y);
assert(t.at(x) == y.toString());
t.remove(x);
assert(t.isEmpty());

Definition at line 64 of file TrieDB.h.

Member Typedef Documentation

template<class _DB>

using dev::GenericTrieDB< _DB >::DB = _DB

Definition at line 67 of file TrieDB.h.

Constructor & Destructor Documentation

template<class _DB>

dev::GenericTrieDB< _DB >::GenericTrieDB ( DB * _db = nullptr )

inlineexplicit

Definition at line 69 of file TrieDB.h.

template<class _DB>

dev::GenericTrieDB< _DB >::GenericTrieDB	(	DB *	_db,
		h256 const &	_root,
		Verification	_v = `Verification::Normal`
	)

inline

Definition at line 70 of file TrieDB.h.

template<class _DB>

dev::GenericTrieDB< _DB >::~GenericTrieDB ( )

inline

Definition at line 71 of file TrieDB.h.

Member Function Documentation

template<class _DB>

std::string dev::GenericTrieDB< _DB >::at ( bytes const & _key ) const

inline

Definition at line 101 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

std::string dev::GenericTrieDB< DB >::at ( bytesConstRef _key ) const

Definition at line 796 of file TrieDB.h.

template<class DB >

std::string dev::GenericTrieDB< DB >::atAux	(	RLP const &	_here,
		NibbleSlice	_key
	)		const

private

Definition at line 801 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

iterator dev::GenericTrieDB< _DB >::begin ( ) const

inline

Definition at line 156 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::branch ( RLP const & _orig )

private

Definition at line 1201 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

bool dev::GenericTrieDB< _DB >::check ( bool _requireNoLeftOvers ) const

inline

Used for debugging, scans the whole trie.

Parameters

_requireNoLeftOvers if true, requires that all keys are reachable.

Definition at line 219 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::cleve	(	RLP const &	_orig,
		unsigned	_s
	)

private

Definition at line 1134 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

bool dev::GenericTrieDB< _DB >::contains ( bytes const & _key )

inline

Definition at line 109 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

bool dev::GenericTrieDB< _DB >::contains ( bytesConstRef _key )

inline

Definition at line 110 of file TrieDB.h.

template<class _DB>

DB const* dev::GenericTrieDB< _DB >::db ( ) const

inline

Get the underlying database.

Warning: This can be used to bypass the trie code. Don't use these unless you really know what you're doing.

Definition at line 235 of file TrieDB.h.

template<class _DB>

DB* dev::GenericTrieDB< _DB >::db ( )

inline

Definition at line 236 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::debugStructure ( std::ostream & _out ) const

inline

Used for debugging, scans the whole trie.

Definition at line 212 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::deleteAt	(	RLP const &	_replace,
		NibbleSlice	_k
	)

private

Definition at line 958 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

bool dev::GenericTrieDB< DB >::deleteAtAux	(	RLPStream &	_out,
		RLP const &	_replace,
		NibbleSlice	_key
	)

private

Definition at line 1065 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

std::string dev::GenericTrieDB< DB >::deref ( RLP const & _n ) const

private

Definition at line 953 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::descendEntry	(	RLP const &	_r,
		h256Hash &	_keyMask,
		bool	_wasExt,
		std::ostream *	_out,
		int	_indent
	)		const

inline

Used for debugging, scans the whole trie.

Definition at line 171 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::descendKey	(	h256 const &	_k,
		h256Hash &	_keyMask,
		bool	_wasExt,
		std::ostream *	_out,
		int	_indent = `0`
	)		const

inline

Used for debugging, scans the whole trie.

Definition at line 162 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::descendList	(	RLP const &	_r,
		h256Hash &	_keyMask,
		bool	_wasExt,
		std::ostream *	_out,
		int	_indent
	)		const

inline

Used for debugging, scans the whole trie.

Definition at line 182 of file TrieDB.h.

template<class _DB>

iterator dev::GenericTrieDB< _DB >::end ( ) const

inline

Definition at line 157 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

h256 dev::GenericTrieDB< _DB >::forceInsertNode ( bytesConstRef _v )

inlineprivate

Definition at line 293 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::forceInsertNode	(	h256 const &	_h,
		bytesConstRef	_v
	)

inlineprivate

Definition at line 294 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::forceKillNode ( h256 const & _h )

inlineprivate

Definition at line 295 of file TrieDB.h.

template<class DB >

bytes dev::GenericTrieDB< DB >::graft ( RLP const & _orig )

private

Definition at line 1155 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::init ( )

inline

Definition at line 76 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::insert	(	bytes const &	_key,
		bytes const &	_value
	)

inline

Definition at line 103 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::insert	(	bytesConstRef	_key,
		bytes const &	_value
	)

inline

Definition at line 104 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::insert	(	bytes const &	_key,
		bytesConstRef	_value
	)

inline

Definition at line 105 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

void dev::GenericTrieDB< DB >::insert	(	bytesConstRef	_key,
		bytesConstRef	_value
	)

Definition at line 778 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

bool dev::GenericTrieDB< _DB >::isEmpty ( ) const

inline

True if the trie is initialised but empty (i.e. that the DB contains the root node which is empty).

Definition at line 97 of file TrieDB.h.

template<class _DB>

bool dev::GenericTrieDB< _DB >::isNull ( ) const

inline

True if the trie is uninitialised (i.e. that the DB doesn't contain the root node).

Definition at line 95 of file TrieDB.h.

template<class DB >

bool dev::GenericTrieDB< DB >::isTwoItemNode ( RLP const & _n ) const

private

Definition at line 947 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::killNode ( RLP const & _d )

inlineprivate

Definition at line 301 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::killNode	(	RLP const &	_d,
		h256 const &	_h
	)

inlineprivate

Definition at line 302 of file TrieDB.h.

template<class _DB>

h256Hash dev::GenericTrieDB< _DB >::leftOvers ( std::ostream * _out = nullptr ) const

inline

Used for debugging, scans the whole trie.

Definition at line 204 of file TrieDB.h.

template<class _DB>

iterator dev::GenericTrieDB< _DB >::lower_bound ( bytesConstRef _key ) const

inline

Definition at line 159 of file TrieDB.h.

template<class DB >

bytes dev::GenericTrieDB< DB >::merge	(	RLP const &	_orig,
		byte	_i
	)

private

Definition at line 1182 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::mergeAt	(	RLP const &	_replace,
		NibbleSlice	_k,
		bytesConstRef	_v,
		bool	_inLine = `false`
	)

private

Definition at line 833 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::mergeAt	(	RLP const &	_replace,
		h256 const &	_replaceHash,
		NibbleSlice	_k,
		bytesConstRef	_v,
		bool	_inLine = `false`
	)

private

Definition at line 838 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

void dev::GenericTrieDB< DB >::mergeAtAux	(	RLPStream &	_out,
		RLP const &	_replace,
		NibbleSlice	_key,
		bytesConstRef	_value
	)

private

Definition at line 914 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

std::string dev::GenericTrieDB< _DB >::node ( h256 const & _h ) const

inlineprivate

Definition at line 290 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::open ( DB * _db )

inline

Definition at line 73 of file TrieDB.h.

template<class _DB>

void dev::GenericTrieDB< _DB >::open	(	DB *	_db,
		h256 const &	_root,
		Verification	_v = `Verification::Normal`
	)

inline

Definition at line 74 of file TrieDB.h.

template<class DB >

bytes dev::GenericTrieDB< DB >::place	(	RLP const &	_orig,
		NibbleSlice	_k,
		bytesConstRef	_s
	)

private

Definition at line 1082 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::remove ( bytes const & _key )

inline

Definition at line 107 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

void dev::GenericTrieDB< DB >::remove ( bytesConstRef _key )

Definition at line 931 of file TrieDB.h.

Here is the call graph for this function:

template<class DB >

bytes dev::GenericTrieDB< DB >::remove ( RLP const & _orig )

private

Definition at line 1107 of file TrieDB.h.

Here is the call graph for this function:

template<class _DB>

h256 const& dev::GenericTrieDB< _DB >::root ( ) const

inline

Definition at line 99 of file TrieDB.h.

Here is the caller graph for this function:

template<class _DB>

void dev::GenericTrieDB< _DB >::setRoot	(	h256 const &	_root,
		Verification	_v = `Verification::Normal`
	)

inline

Definition at line 78 of file TrieDB.h.

Here is the caller graph for this function:

template<class DB >

RLPStream & dev::GenericTrieDB< DB >::streamNode	(	RLPStream &	_s,
		bytes const &	_b
	)

private

Definition at line 1125 of file TrieDB.h.

Here is the call graph for this function:

Member Data Documentation

template<class _DB>

DB* dev::GenericTrieDB< _DB >::m_db = nullptr

private

Definition at line 305 of file TrieDB.h.

template<class _DB>

h256 dev::GenericTrieDB< _DB >::m_root

private

Definition at line 304 of file TrieDB.h.

The documentation for this class was generated from the following file:

src/cpp-ethereum/libdevcore/TrieDB.h

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class _DB> class dev::GenericTrieDB< _DB >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class _DB>
class dev::GenericTrieDB< _DB >