1 // Copyright (c) 2006-2009 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "chrome/browser/sync/engine/change_reorder_buffer.h"
6
7 #include <limits>
8 #include <queue>
9 #include <set>
10 #include <utility> // for pair<>
11 #include <vector>
12
13 #include "chrome/browser/sync/syncable/syncable.h"
14
15 using std::numeric_limits;
16 using std::pair;
17 using std::queue;
18 using std::set;
19 using std::vector;
20
21 namespace sync_api {
22
23 // Traversal provides a way to collect a set of nodes from the syncable
24 // directory structure and then traverse them, along with any intermediate
25 // nodes, in a top-down fashion, starting from a single common ancestor. A
26 // Traversal starts out empty and is grown by means of the ExpandToInclude
27 // method. Once constructed, the top(), begin_children(), and end_children()
28 // methods can be used to explore the nodes in root-to-leaf order.
29 class ChangeReorderBuffer::Traversal {
30 public:
31 typedef pair<int64, int64> ParentChildLink;
32 typedef set<ParentChildLink> LinkSet;
33
Traversal()34 Traversal() : top_(kInvalidId) { }
35
36 // Expand the traversal so that it includes the node indicated by
37 // |child_handle|.
ExpandToInclude(syncable::BaseTransaction * trans,int64 child_handle)38 void ExpandToInclude(syncable::BaseTransaction* trans,
39 int64 child_handle) {
40 // If |top_| is invalid, this is the first insertion -- easy.
41 if (top_ == kInvalidId) {
42 top_ = child_handle;
43 return;
44 }
45
46 int64 node_to_include = child_handle;
47 while (node_to_include != kInvalidId && node_to_include != top_) {
48 int64 node_parent = 0;
49
50 syncable::Entry node(trans, syncable::GET_BY_HANDLE, node_to_include);
51 CHECK(node.good());
52 if (node.Get(syncable::ID).IsRoot()) {
53 // If we've hit the root, and the root isn't already in the tree
54 // (it would have to be |top_| if it were), start a new expansion
55 // upwards from |top_| to unite the original traversal with the
56 // path we just added that goes from |child_handle| to the root.
57 node_to_include = top_;
58 top_ = node.Get(syncable::META_HANDLE);
59 } else {
60 // Otherwise, get the parent ID so that we can add a ParentChildLink.
61 syncable::Entry parent(trans, syncable::GET_BY_ID,
62 node.Get(syncable::PARENT_ID));
63 CHECK(parent.good());
64 node_parent = parent.Get(syncable::META_HANDLE);
65
66 ParentChildLink link(node_parent, node_to_include);
67
68 // If the link exists in the LinkSet |links_|, we don't need to search
69 // any higher; we are done.
70 if (links_.find(link) != links_.end())
71 return;
72
73 // Otherwise, extend |links_|, and repeat on the parent.
74 links_.insert(link);
75 node_to_include = node_parent;
76 }
77 }
78 }
79
80 // Return the top node of the traversal. Use this as a starting point
81 // for walking the tree.
top() const82 int64 top() const { return top_; }
83
84 // Return an iterator corresponding to the first child (in the traversal)
85 // of the node specified by |parent_id|. Iterate this return value until
86 // it is equal to the value returned by end_children(parent_id). The
87 // enumeration thus provided is unordered.
begin_children(int64 parent_id) const88 LinkSet::const_iterator begin_children(int64 parent_id) const {
89 return links_.upper_bound(
90 ParentChildLink(parent_id, numeric_limits<int64>::min()));
91 }
92
93 // Return an iterator corresponding to the last child in the traversal
94 // of the node specified by |parent_id|.
end_children(int64 parent_id) const95 LinkSet::const_iterator end_children(int64 parent_id) const {
96 return begin_children(parent_id + 1);
97 }
98
99 private:
100 // The topmost point in the directory hierarchy that is in the traversal,
101 // and thus the first node to be traversed. If the traversal is empty,
102 // this is kInvalidId. If the traversal contains exactly one member, |top_|
103 // will be the solitary member, and |links_| will be empty.
104 int64 top_;
105 // A set of single-level links that compose the traversal below |top_|. The
106 // (parent, child) ordering of values enables efficient lookup of children
107 // given the parent handle, which is used for top-down traversal. |links_|
108 // is expected to be connected -- every node that appears as a parent in a
109 // link must either appear as a child of another link, or else be the
110 // topmost node, |top_|.
111 LinkSet links_;
112
113 DISALLOW_COPY_AND_ASSIGN(Traversal);
114 };
115
ChangeReorderBuffer()116 ChangeReorderBuffer::ChangeReorderBuffer() {
117 }
118
~ChangeReorderBuffer()119 ChangeReorderBuffer::~ChangeReorderBuffer() {
120 }
121
GetAllChangesInTreeOrder(const BaseTransaction * sync_trans,vector<ChangeRecord> * changelist)122 void ChangeReorderBuffer::GetAllChangesInTreeOrder(
123 const BaseTransaction* sync_trans,
124 vector<ChangeRecord>* changelist) {
125 syncable::BaseTransaction* trans = sync_trans->GetWrappedTrans();
126
127 // Step 1: Iterate through the operations, doing three things:
128 // (a) Push deleted items straight into the |changelist|.
129 // (b) Construct a traversal spanning all non-deleted items.
130 // (c) Construct a set of all parent nodes of any position changes.
131 set<int64> parents_of_position_changes;
132 Traversal traversal;
133
134 OperationMap::const_iterator i;
135 for (i = operations_.begin(); i != operations_.end(); ++i) {
136 if (i->second == OP_DELETE) {
137 ChangeRecord record;
138 record.id = i->first;
139 record.action = ChangeRecord::ACTION_DELETE;
140 if (specifics_.find(record.id) != specifics_.end())
141 record.specifics = specifics_[record.id];
142 if (extra_data_.find(record.id) != extra_data_.end())
143 record.extra = extra_data_[record.id];
144 changelist->push_back(record);
145 } else {
146 traversal.ExpandToInclude(trans, i->first);
147 if (i->second == OP_ADD ||
148 i->second == OP_UPDATE_POSITION_AND_PROPERTIES) {
149 ReadNode node(sync_trans);
150 CHECK(node.InitByIdLookup(i->first));
151
152 // We only care about parents of entry's with position-sensitive models.
153 if (node.GetEntry()->ShouldMaintainPosition())
154 parents_of_position_changes.insert(node.GetParentId());
155 }
156 }
157 }
158
159 // Step 2: Breadth-first expansion of the traversal, enumerating children in
160 // the syncable sibling order if there were any position updates.
161 queue<int64> to_visit;
162 to_visit.push(traversal.top());
163 while (!to_visit.empty()) {
164 int64 next = to_visit.front();
165 to_visit.pop();
166
167 // If the node has an associated action, output a change record.
168 i = operations_.find(next);
169 if (i != operations_.end()) {
170 ChangeRecord record;
171 record.id = next;
172 if (i->second == OP_ADD)
173 record.action = ChangeRecord::ACTION_ADD;
174 else
175 record.action = ChangeRecord::ACTION_UPDATE;
176 if (specifics_.find(record.id) != specifics_.end())
177 record.specifics = specifics_[record.id];
178 if (extra_data_.find(record.id) != extra_data_.end())
179 record.extra = extra_data_[record.id];
180 changelist->push_back(record);
181 }
182
183 // Now add the children of |next| to |to_visit|.
184 if (parents_of_position_changes.find(next) ==
185 parents_of_position_changes.end()) {
186 // No order changes on this parent -- traverse only the nodes listed
187 // in the traversal (and not in sibling order).
188 Traversal::LinkSet::const_iterator j = traversal.begin_children(next);
189 Traversal::LinkSet::const_iterator end = traversal.end_children(next);
190 for (; j != end; ++j) {
191 CHECK(j->first == next);
192 to_visit.push(j->second);
193 }
194 } else {
195 // There were ordering changes on the children of this parent, so
196 // enumerate all the children in the sibling order.
197 syncable::Entry parent(trans, syncable::GET_BY_HANDLE, next);
198 syncable::Id id = trans->directory()->
199 GetFirstChildId(trans, parent.Get(syncable::ID));
200 while (!id.IsRoot()) {
201 syncable::Entry child(trans, syncable::GET_BY_ID, id);
202 CHECK(child.good());
203 int64 handle = child.Get(syncable::META_HANDLE);
204 to_visit.push(handle);
205 // If there is no operation on this child node, record it as as an
206 // update, so that the listener gets notified of all nodes in the new
207 // ordering.
208 if (operations_.find(handle) == operations_.end())
209 operations_[handle] = OP_UPDATE_POSITION_AND_PROPERTIES;
210 id = child.Get(syncable::NEXT_ID);
211 }
212 }
213 }
214 }
215
216 } // namespace sync_api
217