monotone

monotone Mtn Source Tree

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