First-time sync: asymptotic running time improvement

chrome/browser/sync/syncable/syncable.h

 // 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.
 
 #ifndef CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_H_
 #define CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_H_
 #pragma once
 
 #include <algorithm>
 #include <bitset>
@@ skipping 398 matching lines @@
     DCHECK(kernel_);
     return kernel_->ref(ID).IsRoot();
   }
 
   Directory* dir() const;
 
   const EntryKernel GetKernelCopy() const {
     return *kernel_;
   }
 
+  // Compute a local predecessor position for |update_item|, based on its
+  // absolute server position.  The returned ID will be a valid predecessor
+  // under SERVER_PARENT_ID that is consistent with the
+  // SERVER_POSITION_IN_PARENT ordering.
+  Id ComputePrevIdFromServerPosition(const Id& parent_id) const;
+
  protected:  // Don't allow creation on heap, except by sync API wrappers.
   friend class sync_api::ReadNode;
   void* operator new(size_t size) { return (::operator new)(size); }
 
   inline Entry(BaseTransaction* trans)
       : basetrans_(trans),
         kernel_(NULL) { }
 
  protected:
 
@@ skipping 166 matching lines @@
 
   // Items are only in this index if they have a non-empty client tag value.
   static bool ShouldInclude(const EntryKernel* a);
 };
 
 // This index contains EntryKernels ordered by parent ID and metahandle.
 // It allows efficient lookup of the children of a given parent.
 struct ParentIdAndHandleIndexer {
   // This index is of the parent ID and metahandle.  We use a custom
   // comparator.
-  class Comparator;
+  class Comparator {
+   public:
+    bool operator() (const syncable::EntryKernel* a,
+                     const syncable::EntryKernel* b) const;
+  };
 
   // This index does not include deleted items.
   static bool ShouldInclude(const EntryKernel* a);
 };
 
 // Given an Indexer providing the semantics of an index, defines the
 // set type used to actually contain the index.
 template <typename Indexer>
 struct Index {
   typedef std::set<EntryKernel*, typename Indexer::Comparator> Set;
@@ skipping 60 matching lines @@
 //   or are public and take a Transaction* argument.
 //
 // All methods which require the kernel lock to be already held take a
 // ScopeKernelLock* argument.
 //
 // To prevent deadlock, the reader writer transaction lock must always
 // be held before acquiring the kernel lock.
 class ScopedKernelLock;
 class IdFilter;
 class DirectoryManager;
-struct PathMatcher;
 
 class Directory {
   friend class BaseTransaction;
   friend class Entry;
   friend class MutableEntry;
   friend class ReadTransaction;
   friend class ReadTransactionWithoutDB;
   friend class ScopedKernelLock;
   friend class ScopedKernelUnlock;
   friend class WriteTransaction;
@@ skipping 161 matching lines @@
     static inline bool IsChannelShutdownEvent(const DirectoryEvent& event) {
       return DIRECTORY_DESTROYED == event;
     }
   };
  public:
   typedef EventChannel<DirectoryEventTraits, base::Lock> Channel;
   typedef std::vector<int64> ChildHandles;
 
   // Returns the child meta handles for given parent id.
   void GetChildHandles(BaseTransaction*, const Id& parent_id,
-      const std::string& path_spec, ChildHandles* result);
-  void GetChildHandles(BaseTransaction*, const Id& parent_id,
       ChildHandles* result);
-  void GetChildHandlesImpl(BaseTransaction* trans, const Id& parent_id,
-                           PathMatcher* matcher, ChildHandles* result);
 
   // Find the first or last child in the positional ordering under a parent,
   // and return its id.  Returns a root Id if parent has no children.
   virtual Id GetFirstChildId(BaseTransaction* trans, const Id& parent_id);
   Id GetLastChildId(BaseTransaction* trans, const Id& parent_id);
 
+  // Compute a local predecessor position for |update_item|.  The position
+  // is determined by the SERVER_POSITION_IN_PARENT value of |update_item|,
+  // as well as the SERVER_POSITION_IN_PARENT values of any up-to-date
+  // children of |parent_id|.
+  Id ComputePrevIdFromServerPosition(
+      const EntryKernel* update_item,
+      const syncable::Id& parent_id);
+
   // SaveChanges works by taking a consistent snapshot of the current Directory
   // state and indices (by deep copy) under a ReadTransaction, passing this
   // snapshot to the backing store under no transaction, and finally cleaning
   // up by either purging entries no longer needed (this part done under a
   // WriteTransaction) or rolling back the dirty bits.  It also uses
   // internal locking to enforce SaveChanges operations are mutually exclusive.
   //
   // WARNING: THIS METHOD PERFORMS SYNCHRONOUS I/O VIA SQLITE.
   bool SaveChanges();
 
@@ skipping 62 matching lines @@
   void HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot);
 
   // For new entry creation only
   void InsertEntry(EntryKernel* entry, ScopedKernelLock* lock);
   void InsertEntry(EntryKernel* entry);
 
   // Used by CheckTreeInvariants
   void GetAllMetaHandles(BaseTransaction* trans, MetahandleSet* result);
   bool SafeToPurgeFromMemory(const EntryKernel* const entry) const;
 
-  // Helper method used to implement GetFirstChildId/GetLastChildId.
-  Id GetChildWithNullIdField(IdField field,
-                             BaseTransaction* trans,
-                             const Id& parent_id);
-
   // Internal setters that do not acquire a lock internally.  These are unsafe
   // on their own; caller must guarantee exclusive access manually by holding
   // a ScopedKernelLock.
   void set_initial_sync_ended_for_type_unsafe(ModelType type, bool x);
   void SetNotificationStateUnsafe(const std::string& notification_state);
 
   Directory& operator = (const Directory&);
 
  public:
   typedef Index<MetahandleIndexer>::Set MetahandlesIndex;
@@ skipping 90 matching lines @@
     base::Lock save_changes_mutex;
 
     // The next metahandle is protected by kernel mutex.
     int64 next_metahandle;
 
     // Keep a history of recently flushed metahandles for debugging
     // purposes.  Protected by the save_changes_mutex.
     DebugQueue<int64, 1000> flushed_metahandles;
   };
 
+  // Helper method used to do searches on |parent_id_child_index|.
+  ParentIdChildIndex::iterator LocateInParentChildIndex(
+      const ScopedKernelLock& lock,
+      const Id& parent_id,
+      int64 position_in_parent,
+      const Id& item_id_for_tiebreaking);
+
+  // Return an iterator to the beginning of the range of the children of
+  // |parent_id| in the kernel's parent_id_child_index.
+  ParentIdChildIndex::iterator GetParentChildIndexLowerBound(
+      const ScopedKernelLock& lock,
+      const Id& parent_id);
+
+  // Return an iterator to just past the end of the range of the
+  // children of |parent_id| in the kernel's parent_id_child_index.
+  ParentIdChildIndex::iterator GetParentChildIndexUpperBound(
+      const ScopedKernelLock& lock,
+      const Id& parent_id);
+
   Kernel* kernel_;
 
   DirectoryBackingStore* store_;
 };
 
 class ScopedKernelLock {
  public:
   explicit ScopedKernelLock(const Directory*);
   ~ScopedKernelLock() {}
 
@@ skipping 86 matching lines @@
 
 // This is not a reset.  It just sets the numeric fields which are not
 // initialized by the constructor to zero.
 void ZeroFields(EntryKernel* entry, int first_field);
 
 }  // namespace syncable
 
 std::ostream& operator <<(std::ostream&, const syncable::Blob&);
 
 #endif  // CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_H_