monotone

monotone Mtn Source Tree

Root/merkle_tree.hh

1#ifndef __MERKLE_TREE_HH__
2#define __MERKLE_TREE_HH__
3
4// Copyright (C) 2004 Graydon Hoare <graydon@pobox.com>
5//
6// This program is made available under the GNU GPL version 2.0 or
7// greater. See the accompanying file COPYING for details.
8//
9// This program is distributed WITHOUT ANY WARRANTY; without even the
10// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
11// PURPOSE.
12
13#include <map>
14#include <set>
15
16#include <boost/shared_ptr.hpp>
17#include <boost/dynamic_bitset.hpp>
18
19#include "vocab.hh"
20#include "transforms.hh"
21#include "hash_map.hh"
22
23// This file contains data structures and functions for managing merkle
24// trees. A merkle tree is, conceptually, a general recursive construction
25// whereby a range of K data elements is divided up into buckets. Each
26// bucket is then hashed, and the hash values of the buckets at level N of
27// the tree are used as data elements held in buckets at level N-1. At
28// level 0 there is only one bucket.
29//
30// The result is a tree in which each node has J "slots", each of which
31// summarizes (as a hashcode) the entire subtree beneath it. this makes a
32// pair of merkle trees amenable to setwise operations such as union or
33// difference while only inspecting D*log_base_J(K) nodes where D is the
34// number of differences between trees.
35//
36// We build merkle trees over a few collections of objects in our database
37// and use these to synchronize with remote hosts. See netsync.{cc,hh} and
38// refiner.{cc,hh} for more details.
39
40typedef enum
41 {
42 file_item = 2,
43 key_item = 3,
44 revision_item = 4,
45 cert_item = 5,
46 epoch_item = 6
47 }
48netcmd_item_type;
49
50void netcmd_item_type_to_string(netcmd_item_type t, std::string & typestr);
51
52typedef enum
53 {
54 empty_state,
55 leaf_state,
56 subtree_state
57 }
58slot_state;
59
60struct merkle_node
61{
62 size_t level;
63 boost::dynamic_bitset<unsigned char> pref;
64 size_t total_num_leaves;
65 boost::dynamic_bitset<unsigned char> bitmap;
66 std::vector<id> slots;
67 netcmd_item_type type;
68
69 merkle_node();
70 bool operator==(merkle_node const & other) const;
71 void check_invariants() const;
72
73 void get_raw_prefix(prefix & pref) const;
74 void get_hex_prefix(hexenc<prefix> & hpref) const;
75
76 void get_raw_slot(size_t slot, id & val) const;
77 void get_hex_slot(size_t slot, hexenc<id> & val) const;
78
79 void set_raw_slot(size_t slot, id const & val);
80 void set_hex_slot(size_t slot, hexenc<id> const & val);
81
82 void extended_prefix(size_t slot, boost::dynamic_bitset<unsigned char> & extended) const;
83 void extended_raw_prefix(size_t slot, prefix & extended) const;
84 void extended_hex_prefix(size_t slot, hexenc<prefix> & extended) const;
85
86 slot_state get_slot_state(size_t n) const;
87 void set_slot_state(size_t n, slot_state st);
88};
89
90typedef boost::shared_ptr<merkle_node> merkle_ptr;
91
92typedef std::pair<prefix,size_t> merkle_node_id;
93namespace hashmap {
94 template<>
95 struct hash<merkle_node_id>
96 {
97 hash<std::string> sh;
98 size_t operator()(merkle_node_id const & m) const
99 {
100 return sh(m.first()) + m.second;
101 }
102 };
103}
104typedef hashmap::hash_map<merkle_node_id, merkle_ptr> merkle_table;
105
106
107size_t prefix_length_in_bits(size_t level);
108size_t prefix_length_in_bytes(size_t level);
109void write_node(merkle_node const & in, std::string & outbuf);
110void read_node(std::string const & inbuf, size_t & pos, merkle_node & out);
111
112std::string raw_sha1(std::string const & in);
113
114
115bool
116locate_item(merkle_table & table,
117 id const & val,
118 size_t & slotnum,
119 merkle_ptr & mp);
120
121
122void
123pick_slot_and_prefix_for_value(id const & val,
124 size_t level,
125 size_t & slotnum,
126 boost::dynamic_bitset<unsigned char> & pref);
127
128// Collect the items inside a subtree.
129
130void
131collect_items_in_subtree(merkle_table & tab,
132 prefix const & pref,
133 size_t level,
134 std::set<id> & items);
135
136// Insert an item into a tree.
137
138void
139insert_into_merkle_tree(merkle_table & tab,
140 netcmd_item_type type,
141 id const & leaf,
142 size_t level);
143
144inline void
145insert_into_merkle_tree(merkle_table & tab,
146 netcmd_item_type type,
147 hexenc<id> const & hex_leaf,
148 size_t level)
149{
150 id leaf;
151 decode_hexenc(hex_leaf, leaf);
152 insert_into_merkle_tree(tab, type, leaf, level);
153}
154
155// Recalculate the hashes in the given tree. Must be called after
156// insert_into_merkle_tree, and before using tree (but you can batch up
157// multiple calls to insert_into_merkle_tree and then only call this once).
158
159id
160recalculate_merkle_codes(merkle_table & tab,
161 prefix const & pref,
162 size_t level);
163
164// Local Variables:
165// mode: C++
166// fill-column: 76
167// c-file-style: "gnu"
168// indent-tabs-mode: nil
169// End:
170// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
171
172#endif // __MERKLE_TREE_HH__

Archive Download this file

Branches

Tags

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