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