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