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) const;
  53
  54   // Returns all children of the entry.  Returns NULL if the node has no
  55   // children.
  56   const OrderedChildSet* GetChildren(EntryKernel* e) const;
  57
  58   // Returns all siblings of the entry.
  59   const OrderedChildSet* GetSiblings(EntryKernel* e) const;
  60
  61  private:
  62   friend class ParentChildIndexTest;
  63   typedef std::map<Id, OrderedChildSet*> ParentChildrenMap;
  64
  65   // Determines entry's model type.
  66   static ModelType GetModelType(EntryKernel* e);
  67
  68   // Returns parent ID for the entry which is either its PARENT_ID value
  69   // or derived from its model type.
  70   const Id& GetParentId(EntryKernel* e) const;
  71
  72   // Returns previously cached model type root ID for the given |model_type|.
  73   const Id& GetModelTypeRootId(ModelType model_type) const;
  74
  75   // A map of parent IDs to children.
  76   // Parents with no children are not included in this map.
  77   ParentChildrenMap parent_children_map_;
  78
  79   // This array tracks model type roots IDs.
  80   Id model_type_root_ids_[MODEL_TYPE_COUNT];
  81
  82   DISALLOW_COPY_AND_ASSIGN(ParentChildIndex);
  83 };
  84
  85 }  // namespace syncable
  86 }  // namespace syncer
  87
  88 #endif  // SYNC_SYNCABLE_PARENT_CHILD_INDEX