First-time sync: asymptotic running time improvement

chrome/browser/sync/engine/syncer_util.cc

 // Copyright (c) 2010 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/syncer_util.h"
 
 #include <algorithm>
 #include <set>
 #include <string>
 #include <vector>
@@ skipping 457 matching lines @@
     Entry local_prev(entry->trans(), GET_BY_ID, local_up_to_date_predecessor);
     if (!local_prev.good() || local_prev.Get(IS_DEL))
       return false;
     if (!local_prev.Get(IS_UNAPPLIED_UPDATE) && !local_prev.Get(IS_UNSYNCED))
       break;
     local_up_to_date_predecessor = local_prev.Get(PREV_ID);
   }
 
   // Now find the closest up-to-date sibling in the server order.
   syncable::Id server_up_to_date_predecessor =
-      ComputePrevIdFromServerPosition(entry->trans(), entry,
-                                      entry->Get(SERVER_PARENT_ID));
+      entry->ComputePrevIdFromServerPosition(entry->Get(SERVER_PARENT_ID));
   return server_up_to_date_predecessor == local_up_to_date_predecessor;
 }
 
 // static
 bool SyncerUtil::ServerAndLocalEntriesMatch(syncable::Entry* entry) {
   if (!ClientAndServerTimeMatch(
         entry->Get(CTIME), ClientTimeToServerTime(entry->Get(SERVER_CTIME)))) {
     LOG(WARNING) << "Client and server time mismatch";
     return false;
   }
@@ skipping 66 matching lines @@
   entry->Put(IS_DIR, entry->Get(SERVER_IS_DIR));
   // This strange dance around the IS_DEL flag avoids problems when setting
   // the name.
   // TODO(chron): Is this still an issue? Unit test this codepath.
   if (entry->Get(SERVER_IS_DEL)) {
     entry->Put(IS_DEL, true);
   } else {
     entry->Put(NON_UNIQUE_NAME, entry->Get(SERVER_NON_UNIQUE_NAME));
     entry->Put(PARENT_ID, entry->Get(SERVER_PARENT_ID));
     CHECK(entry->Put(IS_DEL, false));
-    Id new_predecessor = ComputePrevIdFromServerPosition(trans, entry,
-        entry->Get(SERVER_PARENT_ID));
+    Id new_predecessor =
+        entry->ComputePrevIdFromServerPosition(entry->Get(SERVER_PARENT_ID));
     CHECK(entry->PutPredecessor(new_predecessor))
         << " Illegal predecessor after converting from server position.";
   }
 
   entry->Put(CTIME, entry->Get(SERVER_CTIME));
   entry->Put(MTIME, entry->Get(SERVER_MTIME));
   entry->Put(BASE_VERSION, entry->Get(SERVER_VERSION));
   entry->Put(IS_DEL, entry->Get(SERVER_IS_DEL));
   entry->Put(IS_UNAPPLIED_UPDATE, false);
 }
@@ skipping 259 matching lines @@
   }
   if (update.version() < target->Get(SERVER_VERSION)) {
     LOG(WARNING) << "Update older than current server version for "
                  << *target << " Update:"
                  << SyncerProtoUtil::SyncEntityDebugString(update);
     return VERIFY_SUCCESS;  // Expected in new sync protocol.
   }
   return VERIFY_UNDECIDED;
 }
 
-// static
-syncable::Id SyncerUtil::ComputePrevIdFromServerPosition(
-    syncable::BaseTransaction* trans,
-    syncable::Entry* update_item,
-    const syncable::Id& parent_id) {
-  const int64 position_in_parent = update_item->Get(SERVER_POSITION_IN_PARENT);
-
-  // TODO(ncarter): This computation is linear in the number of children, but
-  // we could make it logarithmic if we kept an index on server position.
-  syncable::Id closest_sibling;
-  syncable::Id next_id = trans->directory()->GetFirstChildId(trans, parent_id);
-  while (!next_id.IsRoot()) {
-    syncable::Entry candidate(trans, GET_BY_ID, next_id);
-    if (!candidate.good()) {
-      LOG(WARNING) << "Should not happen";
-      return closest_sibling;
-    }
-    next_id = candidate.Get(NEXT_ID);
-
-    // Defensively prevent self-comparison.
-    if (candidate.Get(META_HANDLE) == update_item->Get(META_HANDLE)) {
-      continue;
-    }
-
-    // Ignore unapplied updates -- they might not even be server-siblings.
-    if (candidate.Get(IS_UNAPPLIED_UPDATE)) {
-      continue;
-    }
-
-    // Unsynced items don't have a valid server position.
-    if (!candidate.Get(IS_UNSYNCED)) {
-      // If |candidate| is after |update_entry| according to the server
-      // ordering, then we're done.  ID is the tiebreaker.
-      if ((candidate.Get(SERVER_POSITION_IN_PARENT) > position_in_parent) ||
-          ((candidate.Get(SERVER_POSITION_IN_PARENT) == position_in_parent) &&
-           (candidate.Get(ID) > update_item->Get(ID)))) {
-          return closest_sibling;
-      }
-    }
-
-    // We can't trust the SERVER_ fields of unsynced items, but they are
-    // potentially legitimate local predecessors.  In the case where
-    // |update_item| and an unsynced item wind up in the same insertion
-    // position, we need to choose how to order them.  The following check puts
-    // the unapplied update first; removing it would put the unsynced item(s)
-    // first.
-    if (candidate.Get(IS_UNSYNCED)) {
-      continue;
-    }
-
-    // |update_entry| is considered to be somewhere after |candidate|, so store
-    // it as the upper bound.
-    closest_sibling = candidate.Get(ID);
-  }
-
-  return closest_sibling;
-}
-
 }  // namespace browser_sync