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 "base/memory/scoped_vector.h"
  13 #include "sync/base/sync_export.h"
  14 #include "sync/internal_api/public/base/model_type.h"
  15 #include "sync/syncable/syncable_id.h"
  16
  17 namespace syncer {
  18 namespace syncable {
  19
  20 struct EntryKernel;
  21 class ParentChildIndex;
  22
  23 // A node ordering function.
  24 struct SYNC_EXPORT_PRIVATE ChildComparator {
  25   bool operator() (const EntryKernel* a, const EntryKernel* b) const;
  26 };
  27
  28 // An ordered set of nodes.
  29 typedef std::set<EntryKernel*, ChildComparator> OrderedChildSet;
  30
  31 // Container that tracks parent-child relationships.
  32 // Provides fast lookup of all items under a given parent.
  33 class SYNC_EXPORT_PRIVATE ParentChildIndex {
  34  public:
  35   ParentChildIndex();
  36   ~ParentChildIndex();
  37
  38   // Returns whether or not this entry belongs in the index.
  39   // True for all non-deleted, non-root entries.
  40   static bool ShouldInclude(const EntryKernel* e);
  41
  42   // Inserts a given child into the index.
  43   bool Insert(EntryKernel* e);
  44
  45   // Removes a given child from the index.
  46   void Remove(EntryKernel* e);
  47
  48   // Returns true if this item is in the index as a child.
  49   bool Contains(EntryKernel* e) const;
  50
  51   // Returns all children of the entry with the given Id.  Returns NULL if the
  52   // node has no children or the Id does not identify a valid directory node.
  53   const OrderedChildSet* GetChildren(const Id& id) const;
  54
  55   // Returns all children of the entry.  Returns NULL if the node has no
  56   // children.
  57   const OrderedChildSet* GetChildren(EntryKernel* e) const;
  58
  59   // Returns all siblings of the entry.
  60   const OrderedChildSet* GetSiblings(EntryKernel* e) const;
  61
  62  private:
  63   friend class ParentChildIndexTest;
  64
  65   typedef std::map<Id, OrderedChildSet*> ParentChildrenMap;
  66   typedef std::vector<Id> TypeRootIds;
  67   typedef ScopedVector<OrderedChildSet> TypeRootChildSets;
  68
  69   static bool ShouldUseParentId(const Id& parent_id, ModelType model_type);
  70
  71   // Returns OrderedChildSet that should contain the specified entry
  72   // based on the entry's Parent ID or model type.
  73   const OrderedChildSet* GetChildSet(EntryKernel* e) const;
  74
  75   // Returns OrderedChildSet that contain entries of the |model_type| type.
  76   const OrderedChildSet* GetModelTypeChildSet(ModelType model_type) const;
  77
  78   // Returns mutable OrderedChildSet that contain entries of the |model_type|
  79   // type. Create one as necessary.
  80   OrderedChildSet* GetOrCreateModelTypeChildSet(ModelType model_type);
  81
  82   // Returns previously cached model type root ID for the given |model_type|.
  83   const Id& GetModelTypeRootId(ModelType model_type) const;
  84
  85   // A map of parent IDs to children.
  86   // Parents with no children are not included in this map.
  87   ParentChildrenMap parent_children_map_;
  88
  89   // This array tracks model type roots IDs.
  90   TypeRootIds model_type_root_ids_;
  91
  92   // This array contains pre-defined child sets for
  93   // non-hierarchical types (types with flat hierarchy) that support entries
  94   // with implicit parent.
  95   TypeRootChildSets type_root_child_sets_;
  96
  97   DISALLOW_COPY_AND_ASSIGN(ParentChildIndex);
  98 };
  99
 100 }  // namespace syncable
 101 }  // namespace syncer
 102
 103 #endif  // SYNC_SYNCABLE_PARENT_CHILD_INDEX