Implements a parallelized batch insertion indexed tree Accepts template argument of the type of store backing the tree, the type of store containing the leaves and the hashing policy All public methods are asynchronous unless marked otherwise. More...

#include <content_addressed_indexed_tree.hpp>

Inheritance diagram for bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >:

Classes
struct	HashGenerationResponse

struct	InsertionGenerationResponse

struct	InsertionUpdates

struct	LeafUpdate

struct	SequentialInsertionGenerationResponse

struct	Status

struct	UpdatesCompletionResponse

Public Types
using	StoreType = Store

using	LeafValueType = typename Store::LeafType

using	IndexedLeafValueType = typename Store::IndexedLeafValueType

using	AddCompletionCallbackWithWitness = std::function< void(TypedResponse< AddIndexedDataResponse< LeafValueType > > &)>

using	AddSequentiallyCompletionCallbackWithWitness = std::function< void(TypedResponse< AddIndexedDataSequentiallyResponse< LeafValueType > > &)>

using	AddCompletionCallback = std::function< void(TypedResponse< AddDataResponse > &)>

using	LeafCallback = std::function< void(TypedResponse< GetIndexedLeafResponse< LeafValueType > > &)>

using	FindLowLeafCallback = std::function< void(TypedResponse< GetLowIndexedLeafResponse > &)>

Public Types inherited from bb::crypto::merkle_tree::ContentAddressedAppendOnlyTree< Store, HashingPolicy >
using	StoreType = Store

using	EmptyResponseCallback = std::function< void(Response &)>

using	AppendCompletionCallback = std::function< void(TypedResponse< AddDataResponse > &)>

using	MetaDataCallback = std::function< void(TypedResponse< TreeMetaResponse > &)>

using	HashPathCallback = std::function< void(TypedResponse< GetSiblingPathResponse > &)>

using	FindLeafCallback = std::function< void(TypedResponse< FindLeafIndexResponse > &)>

using	FindSiblingPathCallback = std::function< void(TypedResponse< FindLeafPathResponse > &)>

using	GetLeafCallback = std::function< void(TypedResponse< GetLeafResponse > &)>

using	CommitCallback = std::function< void(TypedResponse< CommitResponse > &)>

using	RollbackCallback = EmptyResponseCallback

using	RemoveHistoricBlockCallback = std::function< void(TypedResponse< RemoveHistoricResponse > &)>

using	UnwindBlockCallback = std::function< void(TypedResponse< UnwindResponse > &)>

using	FinalizeBlockCallback = EmptyResponseCallback

using	GetBlockForIndexCallback = std::function< void(TypedResponse< BlockForIndexResponse > &)>

using	CheckpointCallback = EmptyResponseCallback

using	CheckpointCommitCallback = EmptyResponseCallback

using	CheckpointRevertCallback = EmptyResponseCallback

Public Member Functions
	ContentAddressedIndexedTree (std::unique_ptr< Store > store, std::shared_ptr< ThreadPool > workers, const index_t &initial_size, const std::vector< LeafValueType > &prefilled_values)

	ContentAddressedIndexedTree (std::unique_ptr< Store > store, std::shared_ptr< ThreadPool > workers, const index_t &initial_size)

	ContentAddressedIndexedTree (ContentAddressedIndexedTree const &other)=delete

	ContentAddressedIndexedTree (ContentAddressedIndexedTree &&other)=delete

	~ContentAddressedIndexedTree ()=default

ContentAddressedIndexedTree &	operator= (const ContentAddressedIndexedTree &other)=delete

ContentAddressedIndexedTree &	operator= (ContentAddressedIndexedTree &&other)=delete

void	add_or_update_value (const LeafValueType &value, const AddCompletionCallbackWithWitness &completion)
	Adds or updates a single value in the tree.

void	add_or_update_values (const std::vector< LeafValueType > &values, const AddCompletionCallbackWithWitness &completion)
	Adds or updates the given set of values in the tree using subtree insertion.

void	add_or_update_values (const std::vector< LeafValueType > &values, uint32_t subtree_depth, const AddCompletionCallbackWithWitness &completion)
	Adds or updates the given set of values in the tree using subtree insertion.

void	add_or_update_value (const LeafValueType &value, const AddCompletionCallback &completion)
	Adds or updates a single values in the tree.

void	add_or_update_values (const std::vector< LeafValueType > &values, const AddCompletionCallback &completion)
	Adds or updates the given set of values in the tree using subtree insertion.

void	add_or_update_values (const std::vector< LeafValueType > &values, uint32_t subtree_depth, const AddCompletionCallback &completion)
	Adds or updates the given set of values in the tree using subtree insertion.

void	add_or_update_values_sequentially (const std::vector< LeafValueType > &values, const AddSequentiallyCompletionCallbackWithWitness &completion)
	Adds or updates the given set of values in the tree one by one, fetching witnesses at every step.

void	add_or_update_values_sequentially (const std::vector< LeafValueType > &values, const AddCompletionCallback &completion)
	Adds or updates the given set of values in the tree one by one.

void	get_leaf (const index_t &index, bool includeUncommitted, const LeafCallback &completion) const

void	find_low_leaf (const fr &leaf_key, bool includeUncommitted, const FindLowLeafCallback &on_completion) const
	Find the leaf with the value immediately lower then the value provided.

void	get_leaf (const index_t &index, const block_number_t &blockNumber, bool includeUncommitted, const LeafCallback &completion) const

void	find_low_leaf (const fr &leaf_key, const block_number_t &blockNumber, bool includeUncommitted, const FindLowLeafCallback &on_completion) const
	Find the leaf with the value immediately lower then the value provided.

Public Member Functions inherited from bb::crypto::merkle_tree::ContentAddressedAppendOnlyTree< Store, HashingPolicy >
	ContentAddressedAppendOnlyTree (std::unique_ptr< Store > store, std::shared_ptr< ThreadPool > workers, const std::vector< fr > &initial_values={}, bool commit_genesis_state=true)

	ContentAddressedAppendOnlyTree (ContentAddressedAppendOnlyTree const &other)=delete

	ContentAddressedAppendOnlyTree (ContentAddressedAppendOnlyTree &&other)=delete

ContentAddressedAppendOnlyTree &	operator= (ContentAddressedAppendOnlyTree const &other)=delete

ContentAddressedAppendOnlyTree &	operator= (ContentAddressedAppendOnlyTree const &&other)=delete

virtual	~ContentAddressedAppendOnlyTree ()=default

virtual void	add_value (const fr &value, const AppendCompletionCallback &on_completion)
	Adds a single value to the end of the tree.

virtual void	add_values (const std::vector< fr > &values, const AppendCompletionCallback &on_completion)
	Adds the given set of values to the end of the tree.

void	get_sibling_path (const index_t &index, const HashPathCallback &on_completion, bool includeUncommitted) const
	Returns the sibling path from the leaf at the given index to the root.

void	get_sibling_path (const index_t &index, const block_number_t &blockNumber, const HashPathCallback &on_completion, bool includeUncommitted) const
	Returns the sibling path from the leaf at the given index to the root.

void	get_subtree_sibling_path (uint32_t subtree_depth, const HashPathCallback &on_completion, bool includeUncommitted) const
	Get the subtree sibling path object.

void	get_subtree_sibling_path (const index_t &leaf_index, uint32_t subtree_depth, const HashPathCallback &on_completion, bool includeUncommitted) const
	Get the subtree sibling path object to a leaf.

void	get_meta_data (bool includeUncommitted, const MetaDataCallback &on_completion) const
	Returns the tree meta data.

void	get_meta_data (const block_number_t &blockNumber, bool includeUncommitted, const MetaDataCallback &on_completion) const
	Returns the tree meta data.

void	get_leaf (const index_t &index, bool includeUncommitted, const GetLeafCallback &completion) const
	Returns the leaf value at the provided index.

void	get_leaf (const index_t &index, const block_number_t &blockNumber, bool includeUncommitted, const GetLeafCallback &completion) const
	Returns the leaf value at the provided index.

void	find_leaf_indices (const std::vector< typename Store::LeafType > &leaves, bool includeUncommitted, const FindLeafCallback &on_completion) const
	Returns the index of the provided leaf in the tree.

void	find_leaf_indices (const std::vector< typename Store::LeafType > &leaves, const block_number_t &blockNumber, bool includeUncommitted, const FindLeafCallback &on_completion) const
	Returns the index of the provided leaf in the tree.

void	find_leaf_sibling_paths (const std::vector< typename Store::LeafType > &leaves, bool includeUncommitted, const FindSiblingPathCallback &on_completion) const
	Returns the sibling paths for the provided leaves in the tree.

void	find_leaf_sibling_paths (const std::vector< typename Store::LeafType > &leaves, const block_number_t &block_number, bool includeUncommitted, const FindSiblingPathCallback &on_completion) const
	Returns the sibling paths for the provided leaves in the tree.

void	find_leaf_indices_from (const std::vector< typename Store::LeafType > &leaves, const index_t &start_index, bool includeUncommitted, const FindLeafCallback &on_completion) const
	Returns the index of the provided leaf in the tree only if it exists after the index value provided.

void	find_leaf_indices_from (const std::vector< typename Store::LeafType > &leaves, const index_t &start_index, const block_number_t &blockNumber, bool includeUncommitted, const FindLeafCallback &on_completion) const
	Returns the index of the provided leaf in the tree only if it exists after the index value provided.

void	find_block_numbers (const std::vector< index_t > &indices, const GetBlockForIndexCallback &on_completion) const
	Returns the block numbers that correspond to the given indices values.

void	find_block_numbers (const std::vector< index_t > &indices, const block_number_t &blockNumber, const GetBlockForIndexCallback &on_completion) const
	Returns the block numbers that correspond to the given indices values, from the perspective of a historical block number.

void	commit (const CommitCallback &on_completion)
	Commit the tree to the backing store.

void	rollback (const RollbackCallback &on_completion)
	Rollback the uncommitted changes.

uint32_t	depth () const
	Synchronous method to retrieve the depth of the tree.

void	remove_historic_block (const block_number_t &blockNumber, const RemoveHistoricBlockCallback &on_completion)

void	unwind_block (const block_number_t &blockNumber, const UnwindBlockCallback &on_completion)

void	finalize_block (const block_number_t &blockNumber, const FinalizeBlockCallback &on_completion)

void	checkpoint (const CheckpointCallback &on_completion)

void	commit_checkpoint (const CheckpointCommitCallback &on_completion)

void	revert_checkpoint (const CheckpointRevertCallback &on_completion)

void	commit_all_checkpoints (const CheckpointCommitCallback &on_completion)

void	revert_all_checkpoints (const CheckpointRevertCallback &on_completion)

Private Types
using	ReadTransaction = typename Store::ReadTransaction

using	ReadTransactionPtr = typename Store::ReadTransactionPtr

using	InsertionGenerationCallback = std::function< void(const TypedResponse< InsertionGenerationResponse > &)>

using	SequentialInsertionGenerationCallback = std::function< void(TypedResponse< SequentialInsertionGenerationResponse > &)>

using	UpdatesCompletionCallback = std::function< void(const TypedResponse< UpdatesCompletionResponse > &)>

using	HashGenerationCallback = std::function< void(const TypedResponse< HashGenerationResponse > &)>

Private Member Functions
void	update_leaf_and_hash_to_root (const index_t &index, const IndexedLeafValueType &leaf, Signal &leader, Signal &follower, fr_sibling_path &previous_sibling_path)

std::pair< bool, fr >	sparse_batch_update (const index_t &start_index, const index_t &num_leaves_to_be_inserted, const uint32_t &root_level, const std::vector< LeafUpdate > &updates)

void	sparse_batch_update (const std::vector< std::pair< index_t, fr > > &hashes_at_level, uint32_t level)

void	add_or_update_values_internal (const std::vector< LeafValueType > &values, uint32_t subtree_depth, const AddCompletionCallbackWithWitness &completion, bool capture_witness)
	Adds or updates the given set of values in the tree.

void	add_or_update_values_sequentially_internal (const std::vector< LeafValueType > &values, const AddSequentiallyCompletionCallbackWithWitness &completion, bool capture_witness)
	Adds or updates the given set of values in the tree, capturing sequential insertion witnesses.

void	generate_insertions (const std::shared_ptr< std::vector< std::pair< LeafValueType, index_t > > > &values_to_be_sorted, const InsertionGenerationCallback &completion)

void	generate_sequential_insertions (const std::vector< LeafValueType > &values, const SequentialInsertionGenerationCallback &completion)

void	perform_updates (size_t total_leaves, std::shared_ptr< std::vector< LeafUpdate > > updates, const UpdatesCompletionCallback &completion)

void	perform_updates_without_witness (const index_t &highest_index, std::shared_ptr< std::vector< LeafUpdate > > updates, const UpdatesCompletionCallback &completion)

void	generate_hashes_for_appending (std::shared_ptr< std::vector< IndexedLeafValueType > > leaves_to_hash, const HashGenerationCallback &completion)

Additional Inherited Members
Protected Types inherited from bb::crypto::merkle_tree::ContentAddressedAppendOnlyTree< Store, HashingPolicy >
using	ReadTransaction = typename Store::ReadTransaction

using	ReadTransactionPtr = typename Store::ReadTransactionPtr

using	OptionalSiblingPath = std::vector< std::optional< fr > >

Protected Member Functions inherited from bb::crypto::merkle_tree::ContentAddressedAppendOnlyTree< Store, HashingPolicy >
fr_sibling_path	optional_sibling_path_to_full_sibling_path (const OptionalSiblingPath &optionalPath) const

void	add_values_internal (std::shared_ptr< std::vector< fr > > values, fr &new_root, index_t &new_size, bool update_index)

void	add_values_internal (const std::vector< fr > &values, const AppendCompletionCallback &on_completion, bool update_index)

OptionalSiblingPath	get_subtree_sibling_path_internal (const index_t &leaf_index, uint32_t subtree_depth, const RequestContext &requestContext, ReadTransaction &tx) const

std::optional< fr >	find_leaf_hash (const index_t &leaf_index, const RequestContext &requestContext, ReadTransaction &tx, bool updateNodesByIndexCache=false) const

index_t	get_batch_insertion_size (const index_t &treeSize, const index_t &remainingAppendSize)

void	add_batch_internal (std::vector< fr > &values, fr &new_root, index_t &new_size, bool update_index, ReadTransaction &tx)

Protected Attributes inherited from bb::crypto::merkle_tree::ContentAddressedAppendOnlyTree< Store, HashingPolicy >
std::unique_ptr< Store >	store_

uint32_t	depth_

uint64_t	max_size_

std::vector< fr >	zero_hashes_

std::shared_ptr< ThreadPool >	workers_

Detailed Description

template<typename Store, typename HashingPolicy>
class bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >

Implements a parallelized batch insertion indexed tree Accepts template argument of the type of store backing the tree, the type of store containing the leaves and the hashing policy All public methods are asynchronous unless marked otherwise.

Definition at line 52 of file content_addressed_indexed_tree.hpp.

Member Typedef Documentation

◆ AddCompletionCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::AddCompletionCallback = std::function<void(TypedResponse<AddDataResponse>&)>

Definition at line 62 of file content_addressed_indexed_tree.hpp.

◆ AddCompletionCallbackWithWitness

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::AddCompletionCallbackWithWitness = std::function<void(TypedResponse<AddIndexedDataResponse<LeafValueType> >&)>

Definition at line 59 of file content_addressed_indexed_tree.hpp.

◆ AddSequentiallyCompletionCallbackWithWitness

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::AddSequentiallyCompletionCallbackWithWitness = std::function<void(TypedResponse<AddIndexedDataSequentiallyResponse<LeafValueType> >&)>

Definition at line 60 of file content_addressed_indexed_tree.hpp.

◆ FindLowLeafCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::FindLowLeafCallback = std::function<void(TypedResponse<GetLowIndexedLeafResponse>&)>

Definition at line 65 of file content_addressed_indexed_tree.hpp.

◆ HashGenerationCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::HashGenerationCallback = std::function<void(const TypedResponse<HashGenerationResponse>&)>

private

Definition at line 265 of file content_addressed_indexed_tree.hpp.

◆ IndexedLeafValueType

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::IndexedLeafValueType = typename Store::IndexedLeafValueType

Definition at line 58 of file content_addressed_indexed_tree.hpp.

◆ InsertionGenerationCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::InsertionGenerationCallback = std::function<void(const TypedResponse<InsertionGenerationResponse>&)>

private

Definition at line 227 of file content_addressed_indexed_tree.hpp.

◆ LeafCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::LeafCallback = std::function<void(TypedResponse<GetIndexedLeafResponse<LeafValueType> >&)>

Definition at line 64 of file content_addressed_indexed_tree.hpp.

◆ LeafValueType

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::LeafValueType = typename Store::LeafType

Definition at line 57 of file content_addressed_indexed_tree.hpp.

◆ ReadTransaction

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ReadTransaction = typename Store::ReadTransaction

private

Definition at line 166 of file content_addressed_indexed_tree.hpp.

◆ ReadTransactionPtr

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ReadTransactionPtr = typename Store::ReadTransactionPtr

private

Definition at line 167 of file content_addressed_indexed_tree.hpp.

◆ SequentialInsertionGenerationCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::SequentialInsertionGenerationCallback = std::function<void(TypedResponse<SequentialInsertionGenerationResponse>&)>

private

Definition at line 244 of file content_addressed_indexed_tree.hpp.

◆ StoreType

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::StoreType = Store

Definition at line 54 of file content_addressed_indexed_tree.hpp.

◆ UpdatesCompletionCallback

template<typename Store , typename HashingPolicy >

using bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::UpdatesCompletionCallback = std::function<void(const TypedResponse<UpdatesCompletionResponse>&)>

private

Definition at line 253 of file content_addressed_indexed_tree.hpp.

Constructor & Destructor Documentation

◆ ContentAddressedIndexedTree() [1/4]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ContentAddressedIndexedTree	(	std::unique_ptr< Store >	store,
		std::shared_ptr< ThreadPool >	workers,
		const index_t &	initial_size,
		const std::vector< LeafValueType > &	prefilled_values
	)

Definition at line 282 of file content_addressed_indexed_tree.hpp.

◆ ContentAddressedIndexedTree() [2/4]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ContentAddressedIndexedTree	(	std::unique_ptr< Store >	store,
		std::shared_ptr< ThreadPool >	workers,
		const index_t &	initial_size
	)

inline

Definition at line 71 of file content_addressed_indexed_tree.hpp.

◆ ContentAddressedIndexedTree() [3/4]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ContentAddressedIndexedTree ( ContentAddressedIndexedTree< Store, HashingPolicy > const & other )

delete

◆ ContentAddressedIndexedTree() [4/4]

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::ContentAddressedIndexedTree ( ContentAddressedIndexedTree< Store, HashingPolicy > && other )

delete

◆ ~ContentAddressedIndexedTree()

template<typename Store , typename HashingPolicy >

bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::~ContentAddressedIndexedTree ( )

default

Member Function Documentation

◆ add_or_update_value() [1/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_value	(	const LeafValueType &	value,
		const AddCompletionCallback &	completion
	)

Adds or updates a single values in the tree.

Definition at line 500 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_value() [2/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_value	(	const LeafValueType &	value,
		const AddCompletionCallbackWithWitness &	completion
	)

Adds or updates a single value in the tree.

Definition at line 493 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values() [1/4]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values	(	const std::vector< LeafValueType > &	values,
		const AddCompletionCallback &	completion
	)

Adds or updates the given set of values in the tree using subtree insertion.

Parameters

values	The values to be added or updated
completion	The callback to be triggered once the values have been added

Definition at line 514 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values() [2/4]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values	(	const std::vector< LeafValueType > &	values,
		const AddCompletionCallbackWithWitness &	completion
	)

Adds or updates the given set of values in the tree using subtree insertion.

Parameters

values	The values to be added or updated
completion	The callback to be triggered once the values have been added

Definition at line 507 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values() [3/4]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values	(	const std::vector< LeafValueType > &	values,
		uint32_t	subtree_depth,
		const AddCompletionCallback &	completion
	)

Adds or updates the given set of values in the tree using subtree insertion.

Parameters

values	The values to be added or updated
subtree_depth	The height of the subtree to be inserted.
completion	The callback to be triggered once the values have been added

Definition at line 530 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values() [4/4]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values	(	const std::vector< LeafValueType > &	values,
		uint32_t	subtree_depth,
		const AddCompletionCallbackWithWitness &	completion
	)

Adds or updates the given set of values in the tree using subtree insertion.

Parameters

values	The values to be added or updated
subtree_depth	The height of the subtree to be inserted.
completion	The callback to be triggered once the values have been added

Definition at line 521 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values_internal()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values_internal	(	const std::vector< LeafValueType > &	values,
		uint32_t	subtree_depth,
		const AddCompletionCallbackWithWitness &	completion,
		bool	capture_witness
	)

private

Adds or updates the given set of values in the tree.

Parameters

values	The values to be added or updated
subtree_depth	The height of the subtree to be inserted.
completion	The callback to be triggered once the values have been added
capture_witness	Whether or not we should capture the low-leaf witnesses

Definition at line 548 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values_sequentially() [1/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values_sequentially	(	const std::vector< LeafValueType > &	values,
		const AddCompletionCallback &	completion
	)

Adds or updates the given set of values in the tree one by one.

Parameters

values	The values to be added or updated
completion	The callback to be triggered once the values have been added

Definition at line 1305 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values_sequentially() [2/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values_sequentially	(	const std::vector< LeafValueType > &	values,
		const AddSequentiallyCompletionCallbackWithWitness &	completion
	)

Adds or updates the given set of values in the tree one by one, fetching witnesses at every step.

Parameters

values	The values to be added or updated
completion	The callback to be triggered once the values have been added

Definition at line 1298 of file content_addressed_indexed_tree.hpp.

◆ add_or_update_values_sequentially_internal()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::add_or_update_values_sequentially_internal	(	const std::vector< LeafValueType > &	values,
		const AddSequentiallyCompletionCallbackWithWitness &	completion,
		bool	capture_witness
	)

private

Adds or updates the given set of values in the tree, capturing sequential insertion witnesses.

Parameters

values	The values to be added or updated
completion	The callback to be triggered once the values have been added
capture_witness	Whether or not we should capture the witnesses

Definition at line 1323 of file content_addressed_indexed_tree.hpp.

◆ find_low_leaf() [1/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::find_low_leaf	(	const fr &	leaf_key,
		bool	includeUncommitted,
		const FindLowLeafCallback &	on_completion
	)		const

Find the leaf with the value immediately lower then the value provided.

Definition at line 438 of file content_addressed_indexed_tree.hpp.

◆ find_low_leaf() [2/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::find_low_leaf	(	const fr &	leaf_key,
		const block_number_t &	blockNumber,
		bool	includeUncommitted,
		const FindLowLeafCallback &	on_completion
	)		const

Find the leaf with the value immediately lower then the value provided.

Definition at line 460 of file content_addressed_indexed_tree.hpp.

◆ generate_hashes_for_appending()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::generate_hashes_for_appending	(	std::shared_ptr< std::vector< IndexedLeafValueType > >	leaves_to_hash,
		const HashGenerationCallback &	completion
	)

private

Definition at line 894 of file content_addressed_indexed_tree.hpp.

◆ generate_insertions()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::generate_insertions	(	const std::shared_ptr< std::vector< std::pair< LeafValueType, index_t > > > &	values_to_be_sorted,
		const InsertionGenerationCallback &	completion
	)

private

Definition at line 912 of file content_addressed_indexed_tree.hpp.

◆ generate_sequential_insertions()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::generate_sequential_insertions	(	const std::vector< LeafValueType > &	values,
		const SequentialInsertionGenerationCallback &	completion
	)

private

Definition at line 1439 of file content_addressed_indexed_tree.hpp.

◆ get_leaf() [1/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::get_leaf	(	const index_t &	index,
		bool	includeUncommitted,
		const LeafCallback &	completion
	)		const

Definition at line 359 of file content_addressed_indexed_tree.hpp.

◆ get_leaf() [2/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::get_leaf	(	const index_t &	index,
		const block_number_t &	blockNumber,
		bool	includeUncommitted,
		const LeafCallback &	completion
	)		const

Definition at line 392 of file content_addressed_indexed_tree.hpp.

◆ operator=() [1/2]

template<typename Store , typename HashingPolicy >

ContentAddressedIndexedTree & bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::operator= ( const ContentAddressedIndexedTree< Store, HashingPolicy > & other )

delete

◆ operator=() [2/2]

template<typename Store , typename HashingPolicy >

ContentAddressedIndexedTree & bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::operator= ( ContentAddressedIndexedTree< Store, HashingPolicy > && other )

delete

◆ perform_updates()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::perform_updates	(	size_t	total_leaves,
		std::shared_ptr< std::vector< LeafUpdate > >	updates,
		const UpdatesCompletionCallback &	completion
	)

private

Definition at line 701 of file content_addressed_indexed_tree.hpp.

◆ perform_updates_without_witness()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::perform_updates_without_witness	(	const index_t &	highest_index,
		std::shared_ptr< std::vector< LeafUpdate > >	updates,
		const UpdatesCompletionCallback &	completion
	)

private

Definition at line 817 of file content_addressed_indexed_tree.hpp.

◆ sparse_batch_update() [1/2]

template<typename Store , typename HashingPolicy >

std::pair< bool, fr > bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::sparse_batch_update	(	const index_t &	start_index,
		const index_t &	num_leaves_to_be_inserted,
		const uint32_t &	root_level,
		const std::vector< LeafUpdate > &	updates
	)

private

Definition at line 1211 of file content_addressed_indexed_tree.hpp.

◆ sparse_batch_update() [2/2]

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::sparse_batch_update	(	const std::vector< std::pair< index_t, fr > > &	hashes_at_level,
		uint32_t	level
	)

private

Definition at line 1159 of file content_addressed_indexed_tree.hpp.

◆ update_leaf_and_hash_to_root()

template<typename Store , typename HashingPolicy >

void bb::crypto::merkle_tree::ContentAddressedIndexedTree< Store, HashingPolicy >::update_leaf_and_hash_to_root	(	const index_t &	index,
		const IndexedLeafValueType &	leaf,
		Signal &	leader,
		Signal &	follower,
		fr_sibling_path &	previous_sibling_path
	)

private

Definition at line 1083 of file content_addressed_indexed_tree.hpp.

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

src/barretenberg/crypto/merkle_tree/indexed_tree/content_addressed_indexed_tree.hpp

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ AddCompletionCallback

◆ AddCompletionCallbackWithWitness

◆ AddSequentiallyCompletionCallbackWithWitness

◆ FindLowLeafCallback

◆ HashGenerationCallback

◆ IndexedLeafValueType

◆ InsertionGenerationCallback

◆ LeafCallback

◆ LeafValueType

◆ ReadTransaction

◆ ReadTransactionPtr

◆ SequentialInsertionGenerationCallback

◆ StoreType

◆ UpdatesCompletionCallback

Constructor & Destructor Documentation

◆ ContentAddressedIndexedTree() [1/4]

◆ ContentAddressedIndexedTree() [2/4]

◆ ContentAddressedIndexedTree() [3/4]

◆ ContentAddressedIndexedTree() [4/4]

◆ ~ContentAddressedIndexedTree()

Member Function Documentation

◆ add_or_update_value() [1/2]

◆ add_or_update_value() [2/2]

◆ add_or_update_values() [1/4]

◆ add_or_update_values() [2/4]

◆ add_or_update_values() [3/4]

◆ add_or_update_values() [4/4]

◆ add_or_update_values_internal()

◆ add_or_update_values_sequentially() [1/2]

◆ add_or_update_values_sequentially() [2/2]

◆ add_or_update_values_sequentially_internal()

◆ find_low_leaf() [1/2]

◆ find_low_leaf() [2/2]

◆ generate_hashes_for_appending()

◆ generate_insertions()

◆ generate_sequential_insertions()

◆ get_leaf() [1/2]

◆ get_leaf() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ perform_updates()

◆ perform_updates_without_witness()

◆ sparse_batch_update() [1/2]

◆ sparse_batch_update() [2/2]

◆ update_leaf_and_hash_to_root()