Initial commit of sync engine code to browser/sync....

chrome/browser/sync/engine/change_reorder_buffer.cc

+// Copyright (c) 2006-2009 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 "chrome/browser/sync/engine/change_reorder_buffer.h"
+
+#include <limits>
+#include <queue>
+#include <set>
+#include <utility>  // for pair<>
+#include <vector>
+
+#include "chrome/browser/sync/syncable/syncable.h"
+
+using std::numeric_limits;
+using std::pair;
+using std::queue;
+using std::set;
+using std::vector;
+
+namespace sync_api {
+
+// 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.Get(syncable::ID).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.Get(syncable::META_HANDLE);
+      } else {
+        // Otherwise, get the parent ID so that we can add a ParentChildLink.
+        syncable::Entry parent(trans, syncable::GET_BY_ID,
+                             node.Get(syncable::PARENT_ID));
+        CHECK(parent.good());
+        node_parent = parent.Get(syncable::META_HANDLE);
+
+        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);
+};
+
+void ChangeReorderBuffer::GetAllChangesInTreeOrder(
+    const BaseTransaction* sync_trans,
+    vector<ChangeRecord>* changelist) {
+  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.
+  set<int64> parents_of_position_changes;
+  Traversal traversal;
+
+  OperationMap::const_iterator i;
+  for (i = operations_.begin(); i != operations_.end(); ++i) {
+    if (i->second == OP_DELETE) {
+      ChangeRecord record;
+      record.id = i->first;
+      record.action = ChangeRecord::ACTION_DELETE;
+      changelist->push_back(record);
+    } else {
+      traversal.ExpandToInclude(trans, i->first);
+      if (i->second == OP_ADD ||
+          i->second == OP_UPDATE_POSITION_AND_PROPERTIES) {
+        ReadNode node(sync_trans);
+        CHECK(node.InitByIdLookup(i->first));
+        parents_of_position_changes.insert(node.GetParentId());
+      }
+    }
+  }
+
+  // Step 2: Breadth-first expansion of the traversal, enumerating children in
+  // the syncable sibling order if there were any position updates.
+  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;
+      if (i->second == OP_ADD)
+        record.action = ChangeRecord::ACTION_ADD;
+      else
+        record.action = ChangeRecord::ACTION_UPDATE;
+      changelist->push_back(record);
+    }
+
+    // Now add the children of |next| to |to_visit|.
+    if (parents_of_position_changes.find(next) ==
+        parents_of_position_changes.end()) {
+        // No order changes on this parent -- traverse only the nodes listed
+        // in the traversal (and not in sibling order).
+        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);
+        }
+    } else {
+      // There were ordering changes on the children of this parent, so
+      // enumerate all the children in the sibling order.
+      syncable::Entry parent(trans, syncable::GET_BY_HANDLE, next);
+      syncable::Id id = trans->directory()->
+          GetFirstChildId(trans, parent.Get(syncable::ID));
+      while (!id.IsRoot()) {
+        syncable::Entry child(trans, syncable::GET_BY_ID, id);
+        CHECK(child.good());
+        int64 handle = child.Get(syncable::META_HANDLE);
+        to_visit.push(handle);
+        // If there is no operation on this child node, record it as as an
+        // update, so that the listener gets notified of all nodes in the new
+        // ordering.
+        if (operations_.find(handle) == operations_.end())
+          operations_[handle] = OP_UPDATE_POSITION_AND_PROPERTIES;
+        id = child.Get(syncable::NEXT_ID);
+      }
+    }
+  }
+}
+
+}  // namespace sync_api