blob: 72af337026f63cdf8b90ae8f22b96ffee7a10bdc [file] [log] [blame]
// 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 {
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;
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);
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);
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())
// Otherwise, extend |links_|, and repeat on the parent.
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);
// 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_;
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() {
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; = i->first;
record.action = i->second;
if (specifics_.find( != specifics_.end())
record.specifics = specifics_[];
if (extra_data_.find( != extra_data_.end())
record.extra = extra_data_[];
} else {
traversal.ExpandToInclude(trans, i->first);
// Step 2: Breadth-first expansion of the traversal.
queue<int64_t> to_visit;
while (!to_visit.empty()) {
int64_t next = to_visit.front();
// If the node has an associated action, output a change record.
i = operations_.find(next);
if (i != operations_.end()) {
ChangeRecord record; = next;
record.action = i->second;
if (specifics_.find( != specifics_.end())
record.specifics = specifics_[];
if (extra_data_.find( != extra_data_.end())
record.extra = extra_data_[];
// 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);
*changes = ImmutableChangeRecordList(&changelist);
return true;
} // namespace syncer