diff options
Diffstat (limited to 'chromium/sync/internal_api/change_reorder_buffer.cc')
-rw-r--r-- | chromium/sync/internal_api/change_reorder_buffer.cc | 217 |
1 files changed, 0 insertions, 217 deletions
diff --git a/chromium/sync/internal_api/change_reorder_buffer.cc b/chromium/sync/internal_api/change_reorder_buffer.cc deleted file mode 100644 index 572f56dc11f..00000000000 --- a/chromium/sync/internal_api/change_reorder_buffer.cc +++ /dev/null @@ -1,217 +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 <limits> -#include <queue> -#include <set> -#include <utility> // for pair<> - -#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, int64> 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 child_handle) { - // If |top_| is invalid, this is the first insertion -- easy. - if (top_ == kInvalidId) { - top_ = child_handle; - return; - } - - int64 node_to_include = child_handle; - while (node_to_include != kInvalidId && node_to_include != top_) { - int64 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. - syncable::Entry parent(trans, syncable::GET_BY_ID, - node.GetParentId()); - 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 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 parent_id) const { - return links_.upper_bound( - ParentChildLink(parent_id, numeric_limits<int64>::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 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 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 id) { - operations_[id] = ChangeRecord::ACTION_ADD; -} - -void ChangeReorderBuffer::PushDeletedItem(int64 id) { - operations_[id] = ChangeRecord::ACTION_DELETE; -} - -void ChangeReorderBuffer::PushUpdatedItem(int64 id) { - operations_[id] = ChangeRecord::ACTION_UPDATE; -} - -void ChangeReorderBuffer::SetExtraDataForId( - int64 id, - ExtraPasswordChangeRecordData* extra) { - extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra); -} - -void ChangeReorderBuffer::SetSpecificsForId( - int64 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> to_visit; - to_visit.push(traversal.top()); - while (!to_visit.empty()) { - int64 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 |