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

Archive Download this file

Branches

Tags

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