sync: Better iteration in GenericChangeProcessor

This change introduces a new function for fetching the handles of all
children of a sync node, then puts it to use in optimizing the
GenericChangeProcessor's GetSyncDataForType() function.

Prior to the UniquePosition changes, it was simple and cheap to fetch
the ID of a successor or predecessor item.  After the change, it
requires a few expensive map lookups.  In other words, GetSuccessorId()
has gone from being O(1) to O(lg(n)).  This is a especially a problem in
code paths where we use GetSuccessorId() to iterate over all nodes in a
folder.

The UniquePosition change also makes it pretty easy to fetch all child
nodes under a given parent.  We could easily return all the EntryKernels
under a given folder.  Unfortunately, the APIs don't make it easy to
expose that functionality.  Instead, we do something less efficient, but
still much better than the status quo: return the IDs of all the
children.  The caller will need to look up each entry at O(lg(n)) cost,
but at least it didn't have to do two lookups to fetch each ID.

This change should lead to a slight performance improvement in the
ModelAssociation time of types that use the GenericChangeProcessor.

BUG=178275, 241813

Review URL: https://chromiumcodereview.appspot.com/14667013

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@202673 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 19 insertions, 0 deletions

diff --git a/sync/internal_api/base_node.cc b/sync/internal_api/base_node.cc
index 88dec8c..f9bf79b 100644
--- a/sync/internal_api/base_node.cc
+++ b/sync/internal_api/base_node.cc
@@ -215,6 +215,10 @@ int64 BaseNode::GetFirstChildId() const {
   return IdToMetahandle(GetTransaction()->GetWrappedTrans(), id_string);
 }
 
+void BaseNode::GetChildIds(std::vector<int64>* result) const {
+  GetEntry()->GetChildHandles(result);
+}
+
 int BaseNode::GetTotalNodeCount() const {
   syncable::BaseTransaction* trans = GetTransaction()->GetWrappedTrans();
 
diff --git a/sync/internal_api/public/base_node.h b/sync/internal_api/public/base_node.h
index 3c56b5e..6c54ce2 100644
--- a/sync/internal_api/public/base_node.h
+++ b/sync/internal_api/public/base_node.h
@@ -195,6 +195,11 @@ class SYNC_EXPORT BaseNode {
   // children, return 0.
   int64 GetFirstChildId() const;
 
+  // Returns the IDs of the children of this node.
+  // If this type supports user-defined positions the returned IDs will be in
+  // the correct order.
+  void GetChildIds(std::vector<int64>* result) const;
+
   // Returns the total number of nodes including and beneath this node.
   // Recursively iterates through all children.
   int GetTotalNodeCount() const;
diff --git a/sync/syncable/entry.cc b/sync/syncable/entry.cc
index 2d98c6f..ac62448 100644
--- a/sync/syncable/entry.cc
+++ b/sync/syncable/entry.cc
@@ -104,6 +104,10 @@ Id Entry::GetFirstChildId() const {
   return dir()->GetFirstChildId(basetrans_, kernel_);
 }
 
+void Entry::GetChildHandles(std::vector<int64>* result) const {
+  dir()->GetChildHandlesById(basetrans_, Get(ID), result);
+}
+
 bool Entry::ShouldMaintainPosition() const {
   return kernel_->ShouldMaintainPosition();
 }
diff --git a/sync/syncable/entry.h b/sync/syncable/entry.h
index f9d3f90..26ccc0a 100644
--- a/sync/syncable/entry.h
+++ b/sync/syncable/entry.h
@@ -109,6 +109,12 @@ class SYNC_EXPORT Entry {
   Id GetSuccessorId() const;
   Id GetFirstChildId() const;
 
+  // Returns a vector of this node's children's handles.
+  // Clears |result| if there are no children.  If this node is of a type that
+  // supports user-defined ordering then the resulting vector will be in the
+  // proper order.
+  void GetChildHandles(std::vector<int64>* result) const;
+
   inline bool ExistsOnClientBecauseNameIsNonEmpty() const {
     DCHECK(kernel_);
     return !kernel_->ref(NON_UNIQUE_NAME).empty();