From 414df42f095ab7188272918cdc727f10e76bd3c2 Mon Sep 17 00:00:00 2001 From: "rlarocque@chromium.org" Date: Tue, 28 May 2013 22:28:54 +0000 Subject: 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 --- sync/syncable/entry.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'sync/syncable/entry.h') 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* result) const; + inline bool ExistsOnClientBecauseNameIsNonEmpty() const { DCHECK(kernel_); return !kernel_->ref(NON_UNIQUE_NAME).empty(); -- cgit v1.1