monotone

monotone Mtn Source Tree

Root/enumerator.cc

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#include "base.hh"
11#include <deque>
12#include <map>
13#include <set>
14#include "vector.hh"
15
16#include "cset.hh"
17#include "enumerator.hh"
18#include "revision.hh"
19#include "vocab.hh"
20#include "app_state.hh"
21
22using std::make_pair;
23using std::map;
24using std::multimap;
25using std::pair;
26using std::set;
27using std::vector;
28
29revision_enumerator::revision_enumerator(enumerator_callbacks & cb,
30 app_state & app,
31 set<revision_id> const & initial,
32 set<revision_id> const & terminal)
33 : cb(cb), app(app), terminal_nodes(terminal)
34{
35 for (set<revision_id>::const_iterator i = initial.begin();
36 i != initial.end(); ++i)
37 revs.push_back(*i);
38 load_graphs();
39}
40
41revision_enumerator::revision_enumerator(enumerator_callbacks & cb,
42 app_state & app)
43 : cb(cb), app(app)
44{
45 revision_id root;
46 revs.push_back(root);
47 load_graphs();
48}
49
50void
51revision_enumerator::load_graphs()
52{
53 app.db.get_revision_ancestry(graph);
54 for (multimap<revision_id, revision_id>::const_iterator i = graph.begin();
55 i != graph.end(); ++i)
56 {
57 inverse_graph.insert(make_pair(i->second, i->first));
58 }
59}
60
61void
62revision_enumerator::get_revision_parents(revision_id const & child,
63 vector<revision_id> & parents)
64{
65 parents.clear();
66 typedef multimap<revision_id, revision_id>::const_iterator ci;
67 pair<ci,ci> range = inverse_graph.equal_range(child);
68 for (ci i = range.first; i != range.second; ++i)
69 {
70 if (i->first == child)
71 {
72 parents.push_back(i->second);
73}
74 }
75}
76
77
78bool
79revision_enumerator::all_parents_enumerated(revision_id const & child)
80{
81 typedef multimap<revision_id, revision_id>::const_iterator ci;
82 pair<ci,ci> range = inverse_graph.equal_range(child);
83 for (ci i = range.first; i != range.second; ++i)
84 {
85 if (i->first == child)
86 {
87 if (enumerated_nodes.find(i->second) == enumerated_nodes.end())
88 return false;
89 }
90 }
91 return true;
92}
93
94bool
95revision_enumerator::done()
96{
97 return revs.empty() && items.empty();
98}
99
100void
101revision_enumerator::files_for_revision(revision_id const & r,
102 set<file_id> & full_files,
103 set<pair<file_id,file_id> > & del_files)
104{
105 // when we're sending a merge, we have to be careful if we
106 // want to send as little data as possible. see bug #15846
107 //
108 // njs's solution: "when sending the files for a revision,
109 // look at both csets. If a given hash is not listed as new
110 // in _both_ csets, throw it out. Now, for everything left
111 // over, if one side says "add" and the other says "delta",
112 // do a delta. If both sides say "add", do a data."
113
114 set<file_id> file_adds;
115 // map<dst, src>. src is arbitrary.
116 map<file_id, file_id> file_deltas;
117 map<file_id, size_t> file_edge_counts;
118
119 revision_t rs;
120 MM(rs);
121 app.db.get_revision(r, rs);
122
123 for (edge_map::const_iterator i = rs.edges.begin();
124 i != rs.edges.end(); ++i)
125 {
126 set<file_id> file_dsts;
127 cset const & cs = edge_changes(i);
128
129 // Queue up all the file-adds
130 for (map<file_path, file_id>::const_iterator fa = cs.files_added.begin();
131 fa != cs.files_added.end(); ++fa)
132 {
133 file_adds.insert(fa->second);
134 file_dsts.insert(fa->second);
135 }
136
137 // Queue up all the file-deltas
138 for (map<file_path, pair<file_id, file_id> >::const_iterator fd
139 = cs.deltas_applied.begin();
140 fd != cs.deltas_applied.end(); ++fd)
141 {
142 file_deltas[fd->second.second] = fd->second.first;
143 file_dsts.insert(fd->second.second);
144 }
145
146 // we don't want to be counting files twice in a single edge
147 for (set<file_id>::const_iterator i = file_dsts.begin();
148 i != file_dsts.end(); i++)
149 file_edge_counts[*i]++;
150 }
151
152 del_files.clear();
153 full_files.clear();
154 size_t num_edges = rs.edges.size();
155
156 for (map<file_id, size_t>::const_iterator i = file_edge_counts.begin();
157 i != file_edge_counts.end(); i++)
158 {
159 MM(i->first);
160 if (i->second < num_edges)
161 continue;
162
163 // first preference is to send as a delta...
164 map<file_id, file_id>::const_iterator fd = file_deltas.find(i->first);
165 if (fd != file_deltas.end())
166 {
167 del_files.insert(make_pair(fd->second, fd->first));
168 continue;
169 }
170
171 // ... otherwise as a full file.
172 set<file_id>::const_iterator f = file_adds.find(i->first);
173 if (f != file_adds.end())
174 {
175 full_files.insert(*f);
176 continue;
177 }
178
179 I(false);
180 }
181}
182
183void
184revision_enumerator::note_cert(revision_id const & rid,
185 hexenc<id> const & cert_hash)
186{
187 revision_certs.insert(make_pair(rid, cert_hash));
188}
189
190
191void
192revision_enumerator::get_revision_certs(revision_id const & rid,
193vector<hexenc<id> > & hashes)
194{
195 hashes.clear();
196 bool found_one = false;
197 typedef multimap<revision_id, hexenc<id> >::const_iterator ci;
198 pair<ci,ci> range = revision_certs.equal_range(rid);
199 for (ci i = range.first; i != range.second; ++i)
200 {
201 found_one = true;
202 if (i->first == rid)
203hashes.push_back(i->second);
204 }
205 if (!found_one)
206 {
207 app.get_project().get_revision_cert_hashes(rid, hashes);
208 }
209}
210
211void
212revision_enumerator::step()
213{
214 while (!done())
215 {
216 if (items.empty() && !revs.empty())
217 {
218 revision_id r = revs.front();
219 revs.pop_front();
220
221 // It's possible we've enumerated this node elsewhere since last
222 // time around. Cull rather than reprocess.
223 if (enumerated_nodes.find(r) != enumerated_nodes.end())
224 continue;
225
226 if (!all_parents_enumerated(r))
227 {
228 revs.push_back(r);
229 continue;
230 }
231
232 if (terminal_nodes.find(r) == terminal_nodes.end())
233 {
234 typedef multimap<revision_id, revision_id>::const_iterator ci;
235 pair<ci,ci> range = graph.equal_range(r);
236 for (ci i = range.first; i != range.second; ++i)
237 {
238 // We push_front here rather than push_back in order
239 // to improve database cache performance. It avoids
240 // skipping back and forth beween parallel lineages.
241 if (i->first == r)
242 if (enumerated_nodes.find(i->first) == enumerated_nodes.end())
243 revs.push_front(i->second);
244 }
245 }
246
247 enumerated_nodes.insert(r);
248
249 if (null_id(r))
250 continue;
251
252 if (cb.process_this_rev(r))
253 {
254 L(FL("revision_enumerator::step expanding "
255 "contents of rev '%d'\n") % r);
256
257 // The rev's files and fdeltas
258 {
259 set<file_id> full_files;
260 set<pair<file_id, file_id> > del_files;
261 files_for_revision(r, full_files, del_files);
262
263 for (set<file_id>::const_iterator f = full_files.begin();
264 f != full_files.end(); f++)
265 {
266 if (cb.queue_this_file(f->inner()))
267 {
268 enumerator_item item;
269 item.tag = enumerator_item::fdata;
270 item.ident_a = f->inner();
271 items.push_back(item);
272 }
273 }
274
275 for (set<pair<file_id, file_id> >::const_iterator fd = del_files.begin();
276 fd != del_files.end(); fd++)
277 {
278 if (cb.queue_this_file(fd->second.inner()))
279 {
280 enumerator_item item;
281 item.tag = enumerator_item::fdelta;
282 item.ident_a = fd->first.inner();
283 item.ident_b = fd->second.inner();
284 items.push_back(item);
285 }
286 }
287 }
288
289 // Queue up the rev itself
290 {
291 enumerator_item item;
292 item.tag = enumerator_item::rev;
293 item.ident_a = r.inner();
294 items.push_back(item);
295 }
296 }
297
298 // Queue up some or all of the rev's certs
299 vector<hexenc<id> > hashes;
300 get_revision_certs(r, hashes);
301 for (vector<hexenc<id> >::const_iterator i = hashes.begin();
302 i != hashes.end(); ++i)
303 {
304 if (cb.queue_this_cert(*i))
305 {
306 enumerator_item item;
307 item.tag = enumerator_item::cert;
308 item.ident_a = *i;
309 items.push_back(item);
310 }
311 }
312 }
313
314 if (!items.empty())
315 {
316 L(FL("revision_enumerator::step extracting item"));
317
318 enumerator_item i = items.front();
319 items.pop_front();
320 I(!null_id(i.ident_a));
321
322 switch (i.tag)
323 {
324 case enumerator_item::fdata:
325 cb.note_file_data(file_id(i.ident_a));
326 break;
327
328 case enumerator_item::fdelta:
329 I(!null_id(i.ident_b));
330 cb.note_file_delta(file_id(i.ident_a),
331 file_id(i.ident_b));
332 break;
333
334 case enumerator_item::rev:
335 cb.note_rev(revision_id(i.ident_a));
336 break;
337
338 case enumerator_item::cert:
339 cb.note_cert(i.ident_a);
340 break;
341 }
342 break;
343 }
344 }
345}
346
347// Local Variables:
348// mode: C++
349// fill-column: 76
350// c-file-style: "gnu"
351// indent-tabs-mode: nil
352// End:
353// 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