monotone

monotone Mtn Source Tree

Root/merkle_tree.hh

1#ifndef __MERKLE_TREE_HH__
2#define __MERKLE_TREE_HH__
3// copyright (C) 2004 graydon hoare <graydon@pobox.com>
4// all rights reserved.
5// licensed to the public under the terms of the GNU GPL (>= 2)
6// see the file COPYING for details
7
8#include <map>
9#include <string>
10
11#include <boost/dynamic_bitset.hpp>
12
13#include "app_state.hh"
14#include "numeric_vocab.hh"
15#include "vocab.hh"
16
17// this file contains data structures and functions for managing merkle
18// trees. a merkle tree is a general construction whereby a range of K data
19// elements is divided up into buckets, the buckets are stored on disk,
20// then hashed, and the hash values of the buckets are used as data
21// elements for another iteration of the process. this terminates when you
22// only have 1 bucket left.
23//
24// the result is a tree in which each node has N "slots", each of which
25// summarizes (as a hashcode) the entire subtree beneath it. this makes a
26// pair of merkle trees amenable to setwise operations such as union or
27// difference while only inspecting D*log(K) nodes where D is the number of
28// differences between trees.
29//
30// we build merkle trees over a few collections of objects in our database
31// and use these to synchronize with remote hosts. see netsync.{cc,hh} for
32// more details.
33
34typedef enum
35 {
36 manifest_item = 1,
37 file_item = 2,
38 key_item = 3,
39 revision_item = 4,
40 cert_item = 5,
41 epoch_item = 6,
42 }
43netcmd_item_type;
44
45void netcmd_item_type_to_string(netcmd_item_type t, std::string & typestr);
46
47typedef enum
48 {
49 empty_state,
50 live_leaf_state,
51 dead_leaf_state,
52 subtree_state
53 }
54slot_state;
55
56struct merkle_node
57{
58 size_t level;
59 boost::dynamic_bitset<unsigned char> pref;
60 size_t total_num_leaves;
61 boost::dynamic_bitset<unsigned char> bitmap;
62 std::vector<id> slots;
63 netcmd_item_type type;
64
65 merkle_node();
66 bool operator==(merkle_node const & other) const;
67 void check_invariants() const;
68
69 void get_raw_prefix(prefix & pref) const;
70 void get_hex_prefix(hexenc<prefix> & hpref) const;
71
72 void get_raw_slot(size_t slot, id & val) const;
73 void get_hex_slot(size_t slot, hexenc<id> & val) const;
74
75 void set_raw_slot(size_t slot, id const & val);
76 void set_hex_slot(size_t slot, hexenc<id> const & val);
77
78 void extended_prefix(size_t slot, boost::dynamic_bitset<unsigned char> & extended) const;
79 void extended_raw_prefix(size_t slot, prefix & extended) const;
80 void extended_hex_prefix(size_t slot, hexenc<prefix> & extended) const;
81
82 slot_state get_slot_state(size_t n) const;
83 void set_slot_state(size_t n, slot_state st);
84};
85
86typedef boost::shared_ptr<merkle_node> merkle_ptr;
87typedef std::map<std::pair<prefix,size_t>, merkle_ptr> merkle_table;
88
89size_t prefix_length_in_bits(size_t level);
90size_t prefix_length_in_bytes(size_t level);
91void write_node(merkle_node const & in, std::string & outbuf);
92void read_node(std::string const & inbuf, merkle_node & out);
93
94std::string raw_sha1(std::string const & in);
95
96void pick_slot_and_prefix_for_value(id const & val, size_t level,
97 size_t & slotnum, boost::dynamic_bitset<unsigned char> & pref);
98
99// inserts an item into a tree
100
101void
102insert_into_merkle_tree(merkle_table & tab,
103 netcmd_item_type type,
104 bool live_p,
105 id const & leaf,
106 size_t level);
107
108// recalculates the hashes in the given tree. must be called after
109// insert_into_merkle_tree, and before using tree (but you can batch up
110// multiple calls to insert_into_merkle_tree and then only call this once).
111
112id
113recalculate_merkle_codes(merkle_table & tab,
114 prefix const & pref,
115 size_t level);
116
117#endif // __MERKLE_TREE_HH__

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status