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