| 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 |
|---|
Chromium Code Reviews
Issue 2407163004:
[Sync] Move some directory-related things from core/ to syncable/. (Closed)
