WIP: The Bookmark Position Megapatch

sync/syncable/directory.h

 // Copyright 2012 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 SYNC_SYNCABLE_DIRECTORY_H_
 #define SYNC_SYNCABLE_DIRECTORY_H_
 
 #include <set>
 #include <string>
 #include <vector>
 
 #include "base/file_util.h"
 #include "base/gtest_prod_util.h"
 #include "sync/base/sync_export.h"
 #include "sync/internal_api/public/util/report_unrecoverable_error_function.h"
 #include "sync/internal_api/public/util/weak_handle.h"
 #include "sync/syncable/dir_open_result.h"
 #include "sync/syncable/entry_kernel.h"
 #include "sync/syncable/metahandle_set.h"
+#include "sync/syncable/parent_child_index.h"
 #include "sync/syncable/scoped_kernel_lock.h"
 
+// TODO: Check this file for useless members.
+
 namespace syncer {
 
 class Cryptographer;
 class UnrecoverableErrorHandler;
 
 namespace syncable {
 
 class BaseTransaction;
 class DirectoryChangeDelegate;
 class DirectoryBackingStore;
@@ skipping 45 matching lines @@
 
 // Traits type for unique client tag index.
 struct ClientTagIndexer {
   // This index is of the client-tag values.
   typedef LessField<StringField, UNIQUE_CLIENT_TAG> Comparator;
 
   // 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 {
-   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;
 };
 
+
+
 // Reason for unlinking.
 enum UnlinkReason {
   NODE_MANIPULATION, // To be used by any operation manipulating the linked
                      // list.
   DATA_TYPE_PURGE    // To be used when purging a dataype.
 };
 
 class EntryKernelLessByMetaHandle {
  public:
   inline bool operator()(const EntryKernel& a,
@@ skipping 113 matching lines @@
   DirOpenResult Open(const std::string& name,
                      DirectoryChangeDelegate* delegate,
                      const WeakHandle<TransactionObserver>&
                          transaction_observer);
 
   // Stops sending events to the delegate and the transaction
   // observer.
   void Close();
 
   int64 NextMetahandle();
-  // Always returns a negative id.  Positive client ids are generated
-  // by the server only.
-  Id NextId();
+  // Returns a negative integer unique to this client.
+  syncable::Id NextId();
 
   bool good() const { return NULL != kernel_; }
 
   // The download progress is an opaque token provided by the sync server
   // to indicate the continuation state of the next GetUpdates operation.
   void GetDownloadProgress(
       ModelType type,
       sync_pb::DataTypeProgressMarker* value_out) const;
   void GetDownloadProgressAsString(
       ModelType type,
@@ skipping 65 matching lines @@
   virtual EntryKernel* GetEntryById(const Id& id);
   EntryKernel* GetEntryByServerTag(const std::string& tag);
   virtual EntryKernel* GetEntryByClientTag(const std::string& tag);
   EntryKernel* GetRootEntry();
   bool ReindexId(WriteTransaction* trans, EntryKernel* const entry,
                  const Id& new_id);
   bool ReindexParentId(WriteTransaction* trans, EntryKernel* const entry,
                        const Id& new_parent_id);
   void ClearDirtyMetahandles();
 
-  // These don't do semantic checking.
-  // The semantic checking is implemented higher up.
-  bool UnlinkEntryFromOrder(EntryKernel* entry,
-                            WriteTransaction* trans,
-                            ScopedKernelLock* lock,
-                            UnlinkReason unlink_reason);
-
   DirOpenResult OpenImpl(
       const std::string& name,
       DirectoryChangeDelegate* delegate,
       const WeakHandle<TransactionObserver>& transaction_observer);
 
  private:
   // These private versions expect the kernel lock to already be held
   // before calling.
   EntryKernel* GetEntryById(const Id& id, ScopedKernelLock* const lock);
 
@@ skipping 14 matching lines @@
   bool GetChildHandlesByHandle(BaseTransaction*, int64 handle,
       ChildHandles* result);
 
   // Returns true iff |id| has children.
   bool HasChildren(BaseTransaction* trans, const Id& id);
 
   // Find the first child in the positional ordering under a parent,
   // and fill in |*first_child_id| with its id.  Fills in a root Id if
   // parent has no children.  Returns true if the first child was
   // successfully found, or false if an error was encountered.
-  bool GetFirstChildId(BaseTransaction* trans, const Id& parent_id,
-                       Id* first_child_id) WARN_UNUSED_RESULT;
+  Id GetFirstChildId(BaseTransaction* trans, const EntryKernel* parent);
 
-  // Find the last child in the positional ordering under a parent,
-  // and fill in |*first_child_id| with its id.  Fills in a root Id if
-  // parent has no children.  Returns true if the first child was
-  // successfully found, or false if an error was encountered.
-  bool GetLastChildIdForTest(BaseTransaction* trans, const Id& parent_id,
-                             Id* last_child_id) WARN_UNUSED_RESULT;
+  // These functions allow one to fetch the next or previous item under
+  // the same folder.  Returns the "root" ID if there is no predecessor
+  // or successor.
+  //
+  // TODO(rlarocque): These functions are used mainly for tree traversal.  We
+  // should replace these with an iterator API.
+  syncable::Id GetPredecessorId(EntryKernel*);
+  syncable::Id GetSuccessorId(EntryKernel*);
 
-  // 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);
+  // Places |e| as a successor to |predecessor|.  If |predecessor| is NULL,
+  // |e| will be placed as the left-most item in its folder.
+  //
+  // Both |e| and |predecessor| must be valid entries under the same parent.
+  //
+  // TODO(rlarocque): This function includes limited support for placing items
+  // with valid positions (ie. Bookmarks) as siblings of items that have no set
+  // ordering (ie. Autofill items).  This support is required only for tests,
+  // and should be removed.
+  void PutPredecessor(EntryKernel* e, EntryKernel* predecessor);
 
   // 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 89 matching lines @@
                              const EntryKernel* const entry) const;
 
   // 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 SetNotificationStateUnsafe(const std::string& notification_state);
 
   Directory& operator = (const Directory&);
 
  public:
+  // These contain all items, including IS_DEL items.
   typedef Index<MetahandleIndexer>::Set MetahandlesIndex;
   typedef Index<IdIndexer>::Set IdsIndex;
-  // All entries in memory must be in both the MetahandlesIndex and
-  // the IdsIndex, but only non-deleted entries will be the
-  // ParentIdChildIndex.
-  typedef Index<ParentIdAndHandleIndexer>::Set ParentIdChildIndex;
 
   // Contains both deleted and existing entries with tags.
   // We can't store only existing tags because the client would create
   // items that had a duplicated ID in the end, resulting in a DB key
   // violation. ID reassociation would fail after an attempted commit.
   typedef Index<ClientTagIndexer>::Set ClientTagIndex;
 
  protected:
   // Used by tests. |delegate| must not be NULL.
   // |transaction_observer| must be initialized.
@@ skipping 26 matching lines @@
     // entries themselves.  So once a pointer to an entry is pulled
     // from the index, the mutex can be unlocked and entry read or written.
     //
     // Never hold the mutex and do anything with the database or any
     // other buffered IO.  Violating this rule will result in deadlock.
     base::Lock mutex;
     // Entries indexed by metahandle
     MetahandlesIndex* metahandles_index;
     // Entries indexed by id
     IdsIndex* ids_index;
-    ParentIdChildIndex* parent_id_child_index;
+
+    // Contains non-deleted items, indexed according to parent and position
+    // within parent.  Protected by the ScopedKernelLock.
+    ParentChildIndex* parent_child_index;
+
     ClientTagIndex* client_tag_index;
     // So we don't have to create an EntryKernel every time we want to
     // look something up in an index.  Needle in haystack metaphor.
     EntryKernel needle;
 
     // 3 in-memory indices on bits used extremely frequently by the syncer.
     // |unapplied_update_metahandles| is keyed by the server model type.
     MetahandleSet unapplied_update_metahandles[MODEL_TYPE_COUNT];
     MetahandleSet* const unsynced_metahandles;
     // Contains metahandles that are most likely dirty (though not
@@ skipping 24 matching lines @@
     // The next metahandle is protected by kernel mutex.
     int64 next_metahandle;
 
     // The delegate for directory change events.  Must not be NULL.
     DirectoryChangeDelegate* const delegate;
 
     // The transaction observer.
     const WeakHandle<TransactionObserver> transaction_observer;
   };
 
-  // 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);
-
   // Append the handles of the children of |parent_id| to |result|.
   void AppendChildHandles(
       const ScopedKernelLock& lock,
       const Id& parent_id, Directory::ChildHandles* result);
 
-  // Return a pointer to what is probably (but not certainly) the
-  // first child of |parent_id|, or NULL if |parent_id| definitely has
-  // no children.
-  EntryKernel* GetPossibleFirstChild(
-      const ScopedKernelLock& lock, const Id& parent_id);
-
   Kernel* kernel_;
 
   scoped_ptr<DirectoryBackingStore> store_;
 
   UnrecoverableErrorHandler* const unrecoverable_error_handler_;
   const ReportUnrecoverableErrorFunction report_unrecoverable_error_function_;
   bool unrecoverable_error_set_;
 
   // Not owned.
   NigoriHandler* const nigori_handler_;
   Cryptographer* const cryptographer_;
 
   InvariantCheckLevel invariant_check_level_;
 };
 
 }  // namespace syncable
 }  // namespace syncer
 
 #endif // SYNC_SYNCABLE_DIRECTORY_H_