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 mcert_item = 3,
39 fcert_item = 4,
40 key_item = 5
41 }
42netcmd_item_type;
43
44void netcmd_item_type_to_string(netcmd_item_type t, std::string & typestr);
45
46typedef enum
47 {
48 empty_state,
49 live_leaf_state,
50 dead_leaf_state,
51 subtree_state
52 }
53slot_state;
54
55struct merkle_node
56{
57 size_t level;
58 boost::dynamic_bitset<char> pref;
59 size_t total_num_leaves;
60 boost::dynamic_bitset<char> bitmap;
61 std::vector<id> slots;
62 netcmd_item_type type;
63
64 merkle_node();
65 bool operator==(merkle_node const & other) const;
66 void check_invariants() const;
67
68 void get_raw_prefix(prefix & pref) const;
69 void get_hex_prefix(hexenc<prefix> & hpref) const;
70
71 void get_raw_slot(size_t slot, id & val) const;
72 void get_hex_slot(size_t slot, hexenc<id> & val) const;
73
74 void set_raw_slot(size_t slot, id const & val);
75 void set_hex_slot(size_t slot, hexenc<id> const & val);
76
77 void extended_prefix(size_t slot, boost::dynamic_bitset<char> & extended) const;
78 void extended_raw_prefix(size_t slot, prefix & extended) const;
79 void extended_hex_prefix(size_t slot, hexenc<prefix> & extended) const;
80
81 slot_state get_slot_state(size_t n) const;
82 void set_slot_state(size_t n, slot_state st);
83};
84
85size_t prefix_length_in_bits(size_t level);
86size_t prefix_length_in_bytes(size_t level);
87void write_node(merkle_node const & in, std::string & outbuf);
88void read_node(std::string const & inbuf, merkle_node & out);
89
90std::string raw_sha1(std::string const & in);
91
92// these operate against the database
93
94void load_merkle_node(app_state & app,
95 netcmd_item_type type,
96 utf8 const & collection,
97 size_t level,
98 hexenc<prefix> const & hpref,
99 merkle_node & node);
100
101// returns the first hashsz bytes of the serialized node, which is
102// the hash of its contents.
103
104id store_merkle_node(app_state & app,
105 utf8 const & collection,
106 merkle_node const & node);
107
108void pick_slot_and_prefix_for_value(id const & val, size_t level,
109 size_t & slotnum, boost::dynamic_bitset<char> & pref);
110
111// this inserts a leaf into the appropriate position in a merkle
112// tree, writing it to the db and updating any other nodes in the
113// tree which are affected by the insertion.
114
115id insert_into_merkle_tree(app_state & app,
116 bool live_p,
117 netcmd_item_type type,
118 utf8 const & collection,
119 id const & leaf,
120 size_t level);
121
122#endif // __MERKLE_TREE_HH__

Archive Download this file

Branches

Tags

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