sync/syncable/parent_child_index.cc

   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 #include "sync/syncable/parent_child_index.h"
   6
   7 #include "base/stl_util.h"
   8
   9 #include "sync/syncable/entry_kernel.h"
  10 #include "sync/syncable/syncable_id.h"
  11
  12 namespace syncer {
  13 namespace syncable {
  14
  15 bool ChildComparator::operator()(const EntryKernel* a,
  16                                  const EntryKernel* b) const {
  17   const UniquePosition& a_pos = a->ref(UNIQUE_POSITION);
  18   const UniquePosition& b_pos = b->ref(UNIQUE_POSITION);
  19
  20   if (a_pos.IsValid() && b_pos.IsValid()) {
  21     // Position is important to this type.
  22     return a_pos.LessThan(b_pos);
  23   } else if (a_pos.IsValid() && !b_pos.IsValid()) {
  24     // TODO(rlarocque): Remove this case.
  25     // An item with valid position as sibling of one with invalid position.
  26     // We should not support this, but the tests rely on it.  For now, just
  27     // move all invalid position items to the right.
  28     return true;
  29   } else if (!a_pos.IsValid() && b_pos.IsValid()) {
  30     // TODO(rlarocque): Remove this case.
  31     // Mirror of the above case.
  32     return false;
  33   } else {
  34     // Position doesn't matter.
  35     DCHECK(!a->ref(UNIQUE_POSITION).IsValid());
  36     DCHECK(!b->ref(UNIQUE_POSITION).IsValid());
  37     return a->ref(ID) < b->ref(ID);
  38   }
  39 }
  40
  41 ParentChildIndex::ParentChildIndex() {
  42 }
  43
  44 ParentChildIndex::~ParentChildIndex() {
  45   STLDeleteContainerPairSecondPointers(
  46       parent_children_map_.begin(), parent_children_map_.end());
  47 }
  48
  49 bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) {
  50   // This index excludes deleted items and the root item.  The root
  51   // item is excluded so that it doesn't show up as a child of itself.
  52   return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot();
  53 }
  54
  55 bool ParentChildIndex::Insert(EntryKernel* entry) {
  56   DCHECK(ShouldInclude(entry));
  57
  58   const Id& parent_id = GetParentId(entry);
  59   // Store type root ID when inserting a type root entry.
  60   if (parent_id.IsRoot()) {
  61     ModelType model_type = GetModelType(entry);
  62     // TODO(stanisc): there are some unit tests that create entries
  63     // at the root and don't bother initializing specifics which
  64     // produces TOP_LEVEL_FOLDER type here.
  65     if (syncer::IsRealDataType(model_type)) {
  66       model_type_root_ids_[model_type] = entry->ref(ID);
  67     }
  68   }
  69
  70   OrderedChildSet* children = NULL;
  71   ParentChildrenMap::iterator i = parent_children_map_.find(parent_id);
  72   if (i != parent_children_map_.end()) {
  73     children = i->second;
  74   } else {
  75     children = new OrderedChildSet();
  76     parent_children_map_.insert(std::make_pair(parent_id, children));
  77   }
  78
  79   return children->insert(entry).second;
  80 }
  81
  82 // Like the other containers used to help support the syncable::Directory, this
  83 // one does not own any EntryKernels.  This function removes references to the
  84 // given EntryKernel but does not delete it.
  85 void ParentChildIndex::Remove(EntryKernel* e) {
  86   const Id& parent_id = GetParentId(e);
  87   // Clear type root ID when removing a type root entry.
  88   if (parent_id.IsRoot()) {
  89     ModelType model_type = GetModelType(e);
  90     // TODO(stanisc): the check is needed to work around some tests.
  91     // See TODO above.
  92     if (model_type_root_ids_[model_type] == e->ref(ID)) {
  93       model_type_root_ids_[model_type] = Id();
  94     }
  95   }
  96
  97   ParentChildrenMap::iterator parent = parent_children_map_.find(parent_id);
  98   DCHECK(parent != parent_children_map_.end());
  99
 100   OrderedChildSet* children = parent->second;
 101   OrderedChildSet::iterator j = children->find(e);
 102   DCHECK(j != children->end());
 103
 104   children->erase(j);
 105   if (children->empty()) {
 106     delete children;
 107     parent_children_map_.erase(parent);
 108   }
 109 }
 110
 111 bool ParentChildIndex::Contains(EntryKernel *e) const {
 112   const Id& parent_id = GetParentId(e);
 113   ParentChildrenMap::const_iterator parent =
 114       parent_children_map_.find(parent_id);
 115   if (parent == parent_children_map_.end()) {
 116     return false;
 117   }
 118   const OrderedChildSet* children = parent->second;
 119   DCHECK(children && !children->empty());
 120   return children->count(e) > 0;
 121 }
 122
 123 const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const {
 124   DCHECK(!id.IsNull());
 125
 126   ParentChildrenMap::const_iterator parent = parent_children_map_.find(id);
 127   if (parent == parent_children_map_.end()) {
 128     return NULL;
 129   }
 130
 131   // A successful lookup implies at least some children exist.
 132   DCHECK(!parent->second->empty());
 133   return parent->second;
 134 }
 135
 136 const OrderedChildSet* ParentChildIndex::GetChildren(EntryKernel* e) const {
 137   return GetChildren(e->ref(ID));
 138 }
 139
 140 const OrderedChildSet* ParentChildIndex::GetSiblings(EntryKernel* e) const {
 141   DCHECK(Contains(e));
 142   const OrderedChildSet* siblings = GetChildren(GetParentId(e));
 143   DCHECK(siblings && !siblings->empty());
 144   return siblings;
 145 }
 146
 147 const Id& ParentChildIndex::GetParentId(EntryKernel* e) const {
 148   const Id& parent_id = e->ref(PARENT_ID);
 149   if (!parent_id.IsNull()) {
 150     return parent_id;
 151   }
 152   return GetModelTypeRootId(GetModelType(e));
 153 }
 154
 155 ModelType ParentChildIndex::GetModelType(EntryKernel* e) {
 156   // TODO(stanisc): is there a more effective way to find out model type?
 157   ModelType model_type = e->GetModelType();
 158   if (!syncer::IsRealDataType(model_type)) {
 159     model_type = e->GetServerModelType();
 160   }
 161   return model_type;
 162 }
 163
 164 const Id& ParentChildIndex::GetModelTypeRootId(ModelType model_type) const {
 165   // TODO(stanisc): Review whether this approach is reliable enough.
 166   // Should this method simply enumerate children of root node ("r") instead?
 167   return model_type_root_ids_[model_type];
 168 }
 169
 170 }  // namespace syncable
 171 }  // namespace syncer