sync/syncable/parent_child_index.h

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef SYNC_SYNCABLE_PARENT_CHILD_INDEX
   6 #define SYNC_SYNCABLE_PARENT_CHILD_INDEX
   7
   8 #include <map>
   9 #include <set>
  10
  11 #include "base/basictypes.h"
  12 #include "sync/base/sync_export.h"
  13 #include "sync/internal_api/public/base/model_type.h"
  14 #include "sync/syncable/syncable_id.h"
  15
  16 namespace syncer {
  17 namespace syncable {
  18
  19 struct EntryKernel;
  20 class ParentChildIndex;
  21
  22 // A node ordering function.
  23 struct SYNC_EXPORT_PRIVATE ChildComparator {
  24   bool operator() (const EntryKernel* a, const EntryKernel* b) const;
  25 };
  26
  27 // An ordered set of nodes.
  28 typedef std::set<EntryKernel*, ChildComparator> OrderedChildSet;
  29
  30 // Container that tracks parent-child relationships.
  31 // Provides fast lookup of all items under a given parent.
  32 class SYNC_EXPORT_PRIVATE ParentChildIndex {
  33  public:
  34   ParentChildIndex();
  35   ~ParentChildIndex();
  36
  37   // Returns whether or not this entry belongs in the index.
  38   // True for all non-deleted, non-root entries.
  39   static bool ShouldInclude(const EntryKernel* e);
  40
  41   // Inserts a given child into the index.
  42   bool Insert(EntryKernel* e);
  43
  44   // Removes a given child from the index.
  45   void Remove(EntryKernel* e);
  46
  47   // Returns true if this item is in the index as a child.
  48   bool Contains(EntryKernel* e) const;
  49
  50   // Returns all children of the entry with the given Id.  Returns NULL if the
  51   // node has no children or the Id does not identify a valid directory node.
  52   const OrderedChildSet* GetChildren(const Id& id);
  53
  54  private:
  55   friend class ParentChildIndexTest;
  56   typedef std::map<Id, OrderedChildSet*> ParentChildrenMap;
  57
  58   // Determines entry's model type.
  59   static ModelType GetModelType(EntryKernel* e);
  60
  61   // Returns parent ID for the entry which is either its PARENT_ID value
  62   // or derived from its model type.
  63   const Id& GetParentId(EntryKernel* e) const;
  64
  65   // Returns previously cached model type root ID for the given |model_type|.
  66   const Id& GetModelTypeRootId(ModelType model_type) const;
  67
  68   // A map of parent IDs to children.
  69   // Parents with no children are not included in this map.
  70   ParentChildrenMap parent_children_map_;
  71
  72   // This array tracks model type roots IDs.
  73   Id model_type_root_ids_[MODEL_TYPE_COUNT];
  74
  75   DISALLOW_COPY_AND_ASSIGN(ParentChildIndex);
  76 };
  77
  78 }  // namespace syncable
  79 }  // namespace syncer
  80
  81 #endif  // SYNC_SYNCABLE_PARENT_CHILD_INDEX