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