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     // Sort by META_HANDLE to ensure consistent order for testing.
  38     return a->ref(META_HANDLE) < b->ref(META_HANDLE);
  39   }
  40 }
  41
  42 ParentChildIndex::ParentChildIndex() {
  43   // Pre-allocate these two vectors to the number of model types.
  44   model_type_root_ids_.resize(MODEL_TYPE_COUNT);
  45   type_root_child_sets_.resize(MODEL_TYPE_COUNT);
  46 }
  47
  48 ParentChildIndex::~ParentChildIndex() {
  49   for (int i = 0; i < MODEL_TYPE_COUNT; i++) {
  50     // Normally all OrderedChildSet instances in |type_root_child_sets_|
  51     // are shared with |parent_children_map_|. Null out shared instances and
  52     // ScopedVector will take care of the ones that are not shared (if any).
  53     if (!model_type_root_ids_[i].IsNull()) {
  54       DCHECK_EQ(type_root_child_sets_[i],
  55                 parent_children_map_.find(model_type_root_ids_[i])->second);
  56       type_root_child_sets_[i] = nullptr;
  57     }
  58   }
  59
  60   STLDeleteContainerPairSecondPointers(parent_children_map_.begin(),
  61                                        parent_children_map_.end());
  62 }
  63
  64 bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) {
  65   // This index excludes deleted items and the root item.  The root
  66   // item is excluded so that it doesn't show up as a child of itself.
  67   // The index also excludes items without client data e.g. the items that
  68   // don't have client SPECIFICS or PARENT_ID. There is no need to include
  69   // server-only entries because they shouldn't show up on the client until
  70   // they're applied.
  71   return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot() &&
  72          (entry->GetModelType() != UNSPECIFIED ||
  73           !entry->ref(PARENT_ID).IsNull());
  74 }
  75
  76 bool ParentChildIndex::Insert(EntryKernel* entry) {
  77   DCHECK(ShouldInclude(entry));
  78
  79   OrderedChildSet* siblings = nullptr;
  80   const Id& parent_id = entry->ref(PARENT_ID);
  81   ModelType model_type = entry->GetModelType();
  82
  83   if (ShouldUseParentId(parent_id, model_type)) {
  84     // Hierarchical type, lookup child set in the map.
  85     DCHECK(!parent_id.IsNull());
  86     ParentChildrenMap::iterator it = parent_children_map_.find(parent_id);
  87     if (it != parent_children_map_.end()) {
  88       siblings = it->second;
  89     } else {
  90       siblings = new OrderedChildSet();
  91       parent_children_map_.insert(std::make_pair(parent_id, siblings));
  92     }
  93   } else {
  94     // Non-hierarchical type, return a pre-defined collection by type.
  95     siblings = GetOrCreateModelTypeChildSet(model_type);
  96   }
  97
  98   // If this is one of type root folder for a non-hierarchical type, associate
  99   // its ID with the model type and the type's pre-defined child set with the
 100   // type root ID.
 101   // TODO(stanisc): crbug/438313: Just TypeSupportsHierarchy condition should
 102   // theoretically be sufficient but in practice many tests don't properly
 103   // initialize entries so TypeSupportsHierarchy ends up failing. Consider
 104   // tweaking TypeSupportsHierarchy and fixing all related test code.
 105   if (parent_id.IsRoot() && entry->ref(IS_DIR) &&
 106       syncer::IsRealDataType(model_type) &&
 107       !TypeSupportsHierarchy(model_type)) {
 108     const Id& type_root_id = entry->ref(ID);
 109     // Disassociate the type root child set with the previous ID if any.
 110     const Id& prev_type_root_id = model_type_root_ids_[model_type];
 111     if (!prev_type_root_id.IsNull()) {
 112       ParentChildrenMap::iterator it =
 113           parent_children_map_.find(prev_type_root_id);
 114       if (it != parent_children_map_.end()) {
 115         // If the entry exists in the map it must already have the same
 116         // model type specific child set. This child set will be re-inserted
 117         // in the map under the new ID below so it is safe to simply erase
 118         // the entry here.
 119         DCHECK_EQ(it->second, GetModelTypeChildSet(model_type));
 120         parent_children_map_.erase(it);
 121       }
 122     }
 123     // Store the new type root ID and associate the child set.
 124     // Note that the child set isn't owned by the map in this case.
 125     model_type_root_ids_[model_type] = type_root_id;
 126     parent_children_map_.insert(
 127         std::make_pair(type_root_id, GetOrCreateModelTypeChildSet(model_type)));
 128   }
 129
 130   // Finally, insert the entry in the child set.
 131   return siblings->insert(entry).second;
 132 }
 133
 134 // Like the other containers used to help support the syncable::Directory, this
 135 // one does not own any EntryKernels.  This function removes references to the
 136 // given EntryKernel but does not delete it.
 137 void ParentChildIndex::Remove(EntryKernel* e) {
 138   OrderedChildSet* siblings = nullptr;
 139   ModelType model_type = e->GetModelType();
 140   const Id& parent_id = e->ref(PARENT_ID);
 141   bool should_erase = false;
 142   ParentChildrenMap::iterator it;
 143
 144   if (ShouldUseParentId(parent_id, model_type)) {
 145     // Hierarchical type, lookup child set in the map.
 146     DCHECK(!parent_id.IsNull());
 147     it = parent_children_map_.find(parent_id);
 148     DCHECK(it != parent_children_map_.end());
 149     siblings = it->second;
 150     should_erase = true;
 151   } else {
 152     // Non-hierarchical type, return a pre-defined child set by type.
 153     siblings = type_root_child_sets_[model_type];
 154   }
 155
 156   OrderedChildSet::iterator j = siblings->find(e);
 157   DCHECK(j != siblings->end());
 158
 159   // Erase the entry from the child set.
 160   siblings->erase(j);
 161   // If the set is now empty and isn't shareable with |type_root_child_sets_|,
 162   // erase it from the map.
 163   if (siblings->empty() && should_erase) {
 164     delete siblings;
 165     parent_children_map_.erase(it);
 166   }
 167 }
 168
 169 bool ParentChildIndex::Contains(EntryKernel *e) const {
 170   const OrderedChildSet* siblings = GetChildSet(e);
 171   return siblings && siblings->count(e) > 0;
 172 }
 173
 174 const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const {
 175   DCHECK(!id.IsNull());
 176
 177   ParentChildrenMap::const_iterator parent = parent_children_map_.find(id);
 178   if (parent == parent_children_map_.end()) {
 179     return nullptr;
 180   }
 181
 182   OrderedChildSet* children = parent->second;
 183   // The expectation is that the function returns nullptr instead of an empty
 184   // child set
 185   if (children && children->empty())
 186     children = nullptr;
 187   return children;
 188 }
 189
 190 const OrderedChildSet* ParentChildIndex::GetChildren(EntryKernel* e) const {
 191   return GetChildren(e->ref(ID));
 192 }
 193
 194 const OrderedChildSet* ParentChildIndex::GetSiblings(EntryKernel* e) const {
 195   // This implies the entry is in the index.
 196   DCHECK(Contains(e));
 197   const OrderedChildSet* siblings = GetChildSet(e);
 198   DCHECK(siblings && !siblings->empty());
 199   return siblings;
 200 }
 201
 202 /* static */
 203 bool ParentChildIndex::ShouldUseParentId(const Id& parent_id,
 204                                          ModelType model_type) {
 205   // For compatibility with legacy unit tests, in addition to hierarchical
 206   // entries, this returns true any entries directly under root and for entries
 207   // of UNSPECIFIED model type.
 208   return parent_id.IsRoot() || TypeSupportsHierarchy(model_type) ||
 209          !syncer::IsRealDataType(model_type);
 210 }
 211
 212 const OrderedChildSet* ParentChildIndex::GetChildSet(EntryKernel* e) const {
 213   ModelType model_type = e->GetModelType();
 214
 215   const Id& parent_id = e->ref(PARENT_ID);
 216   if (ShouldUseParentId(parent_id, model_type)) {
 217     // Hierarchical type, lookup child set in the map.
 218     ParentChildrenMap::const_iterator it = parent_children_map_.find(parent_id);
 219     if (it == parent_children_map_.end())
 220       return nullptr;
 221     return it->second;
 222   }
 223
 224   // Non-hierarchical type, return a collection indexed by type.
 225   return GetModelTypeChildSet(model_type);
 226 }
 227
 228 const OrderedChildSet* ParentChildIndex::GetModelTypeChildSet(
 229     ModelType model_type) const {
 230   return type_root_child_sets_[model_type];
 231 }
 232
 233 OrderedChildSet* ParentChildIndex::GetOrCreateModelTypeChildSet(
 234     ModelType model_type) {
 235   if (!type_root_child_sets_[model_type])
 236     type_root_child_sets_[model_type] = new OrderedChildSet();
 237   return type_root_child_sets_[model_type];
 238 }
 239
 240 const Id& ParentChildIndex::GetModelTypeRootId(ModelType model_type) const {
 241   return model_type_root_ids_[model_type];
 242 }
 243
 244 }  // namespace syncable
 245 }  // namespace syncer