monotone

monotone Mtn Source Tree

Root/src/refiner.hh

1// Copyright (C) 2005 Graydon Hoare <graydon@pobox.com>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#ifndef __REFINER_HH__
11#define __REFINER_HH__
12
13#include <set>
14
15#include "vocab.hh"
16#include "merkle_tree.hh"
17#include "netcmd.hh"
18
19// This file defines the "refiner" class, which is a helper encapsulating
20// the main tricky part of the netsync algorithm. You must construct a
21// refiner for every merkle trie you wish to refine, and pass it a
22// reference to a refiner_callbacks object, such as the netsync session
23// object. Refinement proceeds in stages.
24//
25// 1. Add local items.
26//
27// 2. Call reindex_local_items to index the merkle table.
28//
29// 3. Call begin_refinement, and process the queue_refine_cmd callback
30// this will generate.
31//
32// 4. Call process_peer_node repeatedly as nodes arrive from your peer,
33// processing the callbacks each such call generates.
34//
35// 5. When done, stop refining and examine the sets of local and peer
36// items you've determined the existence of during refinement.
37
38struct
39refiner_callbacks
40{
41 virtual void queue_refine_cmd(refinement_type ty,
42 merkle_node const & our_node) = 0;
43 virtual void queue_done_cmd(netcmd_item_type ty,
44 size_t n_items) = 0;
45 virtual ~refiner_callbacks() {}
46};
47
48class
49refiner
50{
51 netcmd_item_type type;
52 protocol_voice voice;
53 refiner_callbacks & cb;
54
55 bool sent_initial_query;
56 size_t queries_in_flight;
57 bool calculated_items_to_send;
58
59 std::set<id> local_items;
60 std::set<id> peer_items;
61 merkle_table table;
62
63 void note_subtree_shared_with_peer(merkle_node const & our_node, size_t slot);
64 void send_subquery(merkle_node const & our_node, size_t slot);
65 void send_synthetic_subquery(merkle_node const & our_node, size_t slot);
66 void note_item_in_peer(merkle_node const & their_node, size_t slot);
67 void load_merkle_node(size_t level, prefix const & pref,
68 merkle_ptr & node);
69 bool merkle_node_exists(size_t level, prefix const & pref);
70 void calculate_items_to_send();
71 std::string voicestr()
72 {
73 return voice == server_voice ? "server" : "client";
74 }
75
76public:
77
78 refiner(netcmd_item_type type, protocol_voice voice, refiner_callbacks & cb);
79 void note_local_item(id const & item);
80 void reindex_local_items();
81 void begin_refinement();
82 void process_done_command(size_t n_items);
83 void process_refinement_command(refinement_type ty, merkle_node const & their_node);
84 bool local_item_exists(id const & ident)
85 {
86 return local_items.find(ident) != local_items.end();
87 }
88
89 std::set<id> const & get_local_items() const { return local_items; }
90 std::set<id> const & get_peer_items() const { return peer_items; }
91
92 // These are populated as the 'done' packets arrive.
93 bool done;
94 std::set<id> items_to_send;
95 size_t items_to_receive;
96
97 // Estimate of what items_to_receive will be.
98 size_t min_items_to_receive;
99 bool may_receive_more_than_min;
100};
101
102
103#endif // __REFINER_H__
104
105// Local Variables:
106// mode: C++
107// fill-column: 76
108// c-file-style: "gnu"
109// indent-tabs-mode: nil
110// End:
111// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

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