Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
171 lines (138 sloc) 4.83 KB
#ifndef __MERKLE_TREE_HH__
#define __MERKLE_TREE_HH__
// Copyright (C) 2004 Graydon Hoare <graydon@pobox.com>
//
// This program is made available under the GNU GPL version 2.0 or
// greater. See the accompanying file COPYING for details.
//
// This program is distributed WITHOUT ANY WARRANTY; without even the
// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE.
#include <map>
#include <set>
#include <boost/shared_ptr.hpp>
#include <boost/dynamic_bitset.hpp>
#include "vector.hh"
#include "vocab.hh"
#include "transforms.hh"
#include "hash_map.hh"
// This file contains data structures and functions for managing merkle
// trees. A merkle tree is, conceptually, a general recursive construction
// whereby a range of K data elements is divided up into buckets. Each
// bucket is then hashed, and the hash values of the buckets at level N of
// the tree are used as data elements held in buckets at level N-1. At
// level 0 there is only one bucket.
//
// The result is a tree in which each node has J "slots", each of which
// summarizes (as a hashcode) the entire subtree beneath it. this makes a
// pair of merkle trees amenable to setwise operations such as union or
// difference while only inspecting D*log_base_J(K) nodes where D is the
// number of differences between trees.
//
// We build merkle trees over a few collections of objects in our database
// and use these to synchronize with remote hosts. See netsync.{cc,hh} and
// refiner.{cc,hh} for more details.
typedef enum
{
file_item = 2,
key_item = 3,
revision_item = 4,
cert_item = 5,
epoch_item = 6
}
netcmd_item_type;
void netcmd_item_type_to_string(netcmd_item_type t, std::string & typestr);
typedef enum
{
empty_state,
leaf_state,
subtree_state
}
slot_state;
struct merkle_node
{
size_t level;
boost::dynamic_bitset<unsigned char> pref;
size_t total_num_leaves;
boost::dynamic_bitset<unsigned char> bitmap;
std::vector<id> slots;
netcmd_item_type type;
merkle_node();
bool operator==(merkle_node const & other) const;
void check_invariants() const;
void get_raw_prefix(prefix & pref) const;
void get_hex_prefix(hexenc<prefix> & hpref) const;
void get_raw_slot(size_t slot, id & val) const;
void set_raw_slot(size_t slot, id const & val);
void extended_prefix(size_t slot, boost::dynamic_bitset<unsigned char> & extended) const;
void extended_raw_prefix(size_t slot, prefix & extended) const;
void extended_hex_prefix(size_t slot, hexenc<prefix> & extended) const;
slot_state get_slot_state(size_t n) const;
void set_slot_state(size_t n, slot_state st);
};
typedef boost::shared_ptr<merkle_node> merkle_ptr;
typedef std::pair<prefix,size_t> merkle_node_id;
namespace hashmap {
template<>
struct hash<merkle_node_id>
{
hash<std::string> sh;
size_t operator()(merkle_node_id const & m) const
{
return sh(m.first()) + m.second;
}
};
}
typedef hashmap::hash_map<merkle_node_id, merkle_ptr> merkle_table;
size_t prefix_length_in_bits(size_t level);
size_t prefix_length_in_bytes(size_t level);
void write_node(merkle_node const & in, std::string & outbuf);
void read_node(std::string const & inbuf, size_t & pos, merkle_node & out);
std::string raw_sha1(std::string const & in);
bool
locate_item(merkle_table & table,
id const & val,
size_t & slotnum,
merkle_ptr & mp);
void
pick_slot_and_prefix_for_value(id const & val,
size_t level,
size_t & slotnum,
boost::dynamic_bitset<unsigned char> & pref);
// Collect the items inside a subtree.
void
collect_items_in_subtree(merkle_table & tab,
prefix const & pref,
size_t level,
std::set<id> & items);
// Insert an item into a tree.
void
insert_into_merkle_tree(merkle_table & tab,
netcmd_item_type type,
id const & leaf,
size_t level);
inline void
insert_into_merkle_tree(merkle_table & tab,
netcmd_item_type type,
hexenc<id> const & hex_leaf,
size_t level)
{
id leaf;
decode_hexenc(hex_leaf, leaf);
insert_into_merkle_tree(tab, type, leaf, level);
}
// Recalculate the hashes in the given tree. Must be called after
// insert_into_merkle_tree, and before using tree (but you can batch up
// multiple calls to insert_into_merkle_tree and then only call this once).
id
recalculate_merkle_codes(merkle_table & tab,
prefix const & pref,
size_t level);
// Local Variables:
// mode: C++
// fill-column: 76
// c-file-style: "gnu"
// indent-tabs-mode: nil
// End:
// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
#endif // __MERKLE_TREE_HH__
You can’t perform that action at this time.