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