OLD | NEW |
| (Empty) |
1 // Copyright 2012 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 "components/sync/core_impl/change_reorder_buffer.h" | |
6 | |
7 #include <limits> | |
8 #include <queue> | |
9 #include <set> | |
10 #include <utility> // for pair<> | |
11 | |
12 #include "components/sync/core/base_node.h" | |
13 #include "components/sync/core/base_transaction.h" | |
14 #include "components/sync/syncable/entry.h" | |
15 #include "components/sync/syncable/syncable_base_transaction.h" | |
16 | |
17 using std::numeric_limits; | |
18 using std::pair; | |
19 using std::queue; | |
20 using std::set; | |
21 | |
22 namespace syncer { | |
23 | |
24 // Traversal provides a way to collect a set of nodes from the syncable | |
25 // directory structure and then traverse them, along with any intermediate | |
26 // nodes, in a top-down fashion, starting from a single common ancestor. A | |
27 // Traversal starts out empty and is grown by means of the ExpandToInclude | |
28 // method. Once constructed, the top(), begin_children(), and end_children() | |
29 // methods can be used to explore the nodes in root-to-leaf order. | |
30 class ChangeReorderBuffer::Traversal { | |
31 public: | |
32 typedef pair<int64_t, int64_t> ParentChildLink; | |
33 typedef set<ParentChildLink> LinkSet; | |
34 | |
35 Traversal() : top_(kInvalidId) {} | |
36 | |
37 // Expand the traversal so that it includes the node indicated by | |
38 // |child_handle|. | |
39 void ExpandToInclude(syncable::BaseTransaction* trans, int64_t 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_t node_to_include = child_handle; | |
47 while (node_to_include != kInvalidId && node_to_include != top_) { | |
48 int64_t node_parent = 0; | |
49 | |
50 syncable::Entry node(trans, syncable::GET_BY_HANDLE, node_to_include); | |
51 CHECK(node.good()); | |
52 if (node.GetId().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.GetMetahandle(); | |
59 } else { | |
60 // Otherwise, get the parent ID so that we can add a ParentChildLink. | |
61 | |
62 // Treat nodes with unset parent ID as if they were linked to the root. | |
63 // That is a valid way to traverse the tree because all hierarchical | |
64 // datatypes must have a valid parent ID and the ones with unset parent | |
65 // ID have flat hierarchy where the order doesn't matter. | |
66 const syncable::Id& parent_id = !node.GetParentId().IsNull() | |
67 ? node.GetParentId() | |
68 : syncable::Id::GetRoot(); | |
69 syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id); | |
70 CHECK(parent.good()); | |
71 node_parent = parent.GetMetahandle(); | |
72 | |
73 ParentChildLink link(node_parent, node_to_include); | |
74 | |
75 // If the link exists in the LinkSet |links_|, we don't need to search | |
76 // any higher; we are done. | |
77 if (links_.find(link) != links_.end()) | |
78 return; | |
79 | |
80 // Otherwise, extend |links_|, and repeat on the parent. | |
81 links_.insert(link); | |
82 node_to_include = node_parent; | |
83 } | |
84 } | |
85 } | |
86 | |
87 // Return the top node of the traversal. Use this as a starting point | |
88 // for walking the tree. | |
89 int64_t top() const { return top_; } | |
90 | |
91 // Return an iterator corresponding to the first child (in the traversal) | |
92 // of the node specified by |parent_id|. Iterate this return value until | |
93 // it is equal to the value returned by end_children(parent_id). The | |
94 // enumeration thus provided is unordered. | |
95 LinkSet::const_iterator begin_children(int64_t parent_id) const { | |
96 return links_.upper_bound( | |
97 ParentChildLink(parent_id, numeric_limits<int64_t>::min())); | |
98 } | |
99 | |
100 // Return an iterator corresponding to the last child in the traversal | |
101 // of the node specified by |parent_id|. | |
102 LinkSet::const_iterator end_children(int64_t parent_id) const { | |
103 return begin_children(parent_id + 1); | |
104 } | |
105 | |
106 private: | |
107 // The topmost point in the directory hierarchy that is in the traversal, | |
108 // and thus the first node to be traversed. If the traversal is empty, | |
109 // this is kInvalidId. If the traversal contains exactly one member, |top_| | |
110 // will be the solitary member, and |links_| will be empty. | |
111 int64_t top_; | |
112 // A set of single-level links that compose the traversal below |top_|. The | |
113 // (parent, child) ordering of values enables efficient lookup of children | |
114 // given the parent handle, which is used for top-down traversal. |links_| | |
115 // is expected to be connected -- every node that appears as a parent in a | |
116 // link must either appear as a child of another link, or else be the | |
117 // topmost node, |top_|. | |
118 LinkSet links_; | |
119 | |
120 DISALLOW_COPY_AND_ASSIGN(Traversal); | |
121 }; | |
122 | |
123 ChangeReorderBuffer::ChangeReorderBuffer() {} | |
124 | |
125 ChangeReorderBuffer::~ChangeReorderBuffer() {} | |
126 | |
127 void ChangeReorderBuffer::PushAddedItem(int64_t id) { | |
128 operations_[id] = ChangeRecord::ACTION_ADD; | |
129 } | |
130 | |
131 void ChangeReorderBuffer::PushDeletedItem(int64_t id) { | |
132 operations_[id] = ChangeRecord::ACTION_DELETE; | |
133 } | |
134 | |
135 void ChangeReorderBuffer::PushUpdatedItem(int64_t id) { | |
136 operations_[id] = ChangeRecord::ACTION_UPDATE; | |
137 } | |
138 | |
139 void ChangeReorderBuffer::SetExtraDataForId( | |
140 int64_t id, | |
141 ExtraPasswordChangeRecordData* extra) { | |
142 extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra); | |
143 } | |
144 | |
145 void ChangeReorderBuffer::SetSpecificsForId( | |
146 int64_t id, | |
147 const sync_pb::EntitySpecifics& specifics) { | |
148 specifics_[id] = specifics; | |
149 } | |
150 | |
151 void ChangeReorderBuffer::Clear() { | |
152 operations_.clear(); | |
153 } | |
154 | |
155 bool ChangeReorderBuffer::IsEmpty() const { | |
156 return operations_.empty(); | |
157 } | |
158 | |
159 bool ChangeReorderBuffer::GetAllChangesInTreeOrder( | |
160 const BaseTransaction* sync_trans, | |
161 ImmutableChangeRecordList* changes) { | |
162 syncable::BaseTransaction* trans = sync_trans->GetWrappedTrans(); | |
163 | |
164 // Step 1: Iterate through the operations, doing three things: | |
165 // (a) Push deleted items straight into the |changelist|. | |
166 // (b) Construct a traversal spanning all non-deleted items. | |
167 // (c) Construct a set of all parent nodes of any position changes. | |
168 Traversal traversal; | |
169 | |
170 ChangeRecordList changelist; | |
171 | |
172 OperationMap::const_iterator i; | |
173 for (i = operations_.begin(); i != operations_.end(); ++i) { | |
174 if (i->second == ChangeRecord::ACTION_DELETE) { | |
175 ChangeRecord record; | |
176 record.id = i->first; | |
177 record.action = i->second; | |
178 if (specifics_.find(record.id) != specifics_.end()) | |
179 record.specifics = specifics_[record.id]; | |
180 if (extra_data_.find(record.id) != extra_data_.end()) | |
181 record.extra = extra_data_[record.id]; | |
182 changelist.push_back(record); | |
183 } else { | |
184 traversal.ExpandToInclude(trans, i->first); | |
185 } | |
186 } | |
187 | |
188 // Step 2: Breadth-first expansion of the traversal. | |
189 queue<int64_t> to_visit; | |
190 to_visit.push(traversal.top()); | |
191 while (!to_visit.empty()) { | |
192 int64_t next = to_visit.front(); | |
193 to_visit.pop(); | |
194 | |
195 // If the node has an associated action, output a change record. | |
196 i = operations_.find(next); | |
197 if (i != operations_.end()) { | |
198 ChangeRecord record; | |
199 record.id = next; | |
200 record.action = i->second; | |
201 if (specifics_.find(record.id) != specifics_.end()) | |
202 record.specifics = specifics_[record.id]; | |
203 if (extra_data_.find(record.id) != extra_data_.end()) | |
204 record.extra = extra_data_[record.id]; | |
205 changelist.push_back(record); | |
206 } | |
207 | |
208 // Now add the children of |next| to |to_visit|. | |
209 Traversal::LinkSet::const_iterator j = traversal.begin_children(next); | |
210 Traversal::LinkSet::const_iterator end = traversal.end_children(next); | |
211 for (; j != end; ++j) { | |
212 CHECK(j->first == next); | |
213 to_visit.push(j->second); | |
214 } | |
215 } | |
216 | |
217 *changes = ImmutableChangeRecordList(&changelist); | |
218 return true; | |
219 } | |
220 | |
221 } // namespace syncer | |
OLD | NEW |