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

Archive Download this file

Branches

Tags

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