Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1127)

Unified Diff: sync/internal_api/change_reorder_buffer.cc

Issue 2130453004: [Sync] Move //sync to //components/sync. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Rebase. Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « sync/internal_api/change_reorder_buffer.h ('k') | sync/internal_api/debug_info_event_listener.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: sync/internal_api/change_reorder_buffer.cc
diff --git a/sync/internal_api/change_reorder_buffer.cc b/sync/internal_api/change_reorder_buffer.cc
deleted file mode 100644
index 72af337026f63cdf8b90ae8f22b96ffee7a10bdc..0000000000000000000000000000000000000000
--- a/sync/internal_api/change_reorder_buffer.cc
+++ /dev/null
@@ -1,226 +0,0 @@
-// 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 <stdint.h>
-
-#include <limits>
-#include <queue>
-#include <set>
-#include <utility> // for pair<>
-
-#include "base/macros.h"
-#include "sync/internal_api/public/base_node.h"
-#include "sync/internal_api/public/base_transaction.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_t, int64_t> 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_t child_handle) {
- // If |top_| is invalid, this is the first insertion -- easy.
- if (top_ == kInvalidId) {
- top_ = child_handle;
- return;
- }
-
- int64_t node_to_include = child_handle;
- while (node_to_include != kInvalidId && node_to_include != top_) {
- int64_t node_parent = 0;
-
- syncable::Entry node(trans, syncable::GET_BY_HANDLE, node_to_include);
- CHECK(node.good());
- if (node.GetId().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.GetMetahandle();
- } else {
- // Otherwise, get the parent ID so that we can add a ParentChildLink.
-
- // Treat nodes with unset parent ID as if they were linked to the root.
- // That is a valid way to traverse the tree because all hierarchical
- // datatypes must have a valid parent ID and the ones with unset parent
- // ID have flat hierarchy where the order doesn't matter.
- const syncable::Id& parent_id = !node.GetParentId().IsNull()
- ? node.GetParentId()
- : syncable::Id::GetRoot();
- syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id);
- CHECK(parent.good());
- node_parent = parent.GetMetahandle();
-
- 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_t 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_t parent_id) const {
- return links_.upper_bound(
- ParentChildLink(parent_id, numeric_limits<int64_t>::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_t 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_t 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() {
-}
-
-void ChangeReorderBuffer::PushAddedItem(int64_t id) {
- operations_[id] = ChangeRecord::ACTION_ADD;
-}
-
-void ChangeReorderBuffer::PushDeletedItem(int64_t id) {
- operations_[id] = ChangeRecord::ACTION_DELETE;
-}
-
-void ChangeReorderBuffer::PushUpdatedItem(int64_t id) {
- operations_[id] = ChangeRecord::ACTION_UPDATE;
-}
-
-void ChangeReorderBuffer::SetExtraDataForId(
- int64_t id,
- ExtraPasswordChangeRecordData* extra) {
- extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra);
-}
-
-void ChangeReorderBuffer::SetSpecificsForId(
- int64_t id,
- const sync_pb::EntitySpecifics& specifics) {
- specifics_[id] = specifics;
-}
-
-void ChangeReorderBuffer::Clear() {
- operations_.clear();
-}
-
-bool ChangeReorderBuffer::IsEmpty() const {
- return operations_.empty();
-}
-
-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.
- Traversal traversal;
-
- ChangeRecordList changelist;
-
- OperationMap::const_iterator i;
- for (i = operations_.begin(); i != operations_.end(); ++i) {
- if (i->second == ChangeRecord::ACTION_DELETE) {
- ChangeRecord record;
- record.id = i->first;
- record.action = i->second;
- 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);
- }
- }
-
- // Step 2: Breadth-first expansion of the traversal.
- queue<int64_t> to_visit;
- to_visit.push(traversal.top());
- while (!to_visit.empty()) {
- int64_t 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;
- record.action = i->second;
- 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|.
- 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);
- }
- }
-
- *changes = ImmutableChangeRecordList(&changelist);
- return true;
-}
-
-} // namespace syncer
« no previous file with comments | « sync/internal_api/change_reorder_buffer.h ('k') | sync/internal_api/debug_info_event_listener.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698