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.
5 #include "sync/syncable/parent_child_index.h"
7 #include "base/stl_util.h"
9 #include "sync/syncable/entry_kernel.h"
10 #include "sync/syncable/syncable_id.h"
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
);
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.
29 } else if (!a_pos
.IsValid() && b_pos
.IsValid()) {
30 // TODO(rlarocque): Remove this case.
31 // Mirror of the above case.
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
);
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
);
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;
60 STLDeleteContainerPairSecondPointers(parent_children_map_
.begin(),
61 parent_children_map_
.end());
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 return !entry
->ref(IS_DEL
) && !entry
->ref(ID
).IsRoot();
70 bool ParentChildIndex::Insert(EntryKernel
* entry
) {
71 DCHECK(ShouldInclude(entry
));
73 OrderedChildSet
* siblings
= nullptr;
74 const Id
& parent_id
= entry
->ref(PARENT_ID
);
75 ModelType model_type
= entry
->GetModelType();
77 if (ShouldUseParentId(parent_id
, model_type
)) {
78 // Hierarchical type, lookup child set in the map.
79 DCHECK(!parent_id
.IsNull());
80 ParentChildrenMap::iterator it
= parent_children_map_
.find(parent_id
);
81 if (it
!= parent_children_map_
.end()) {
82 siblings
= it
->second
;
84 siblings
= new OrderedChildSet();
85 parent_children_map_
.insert(std::make_pair(parent_id
, siblings
));
88 // Non-hierarchical type, return a pre-defined collection by type.
89 siblings
= GetOrCreateModelTypeChildSet(model_type
);
92 // If this is one of type root folder for a non-hierarchical type, associate
93 // its ID with the model type and the type's pre-defined child set with the
95 // TODO(stanisc): crbug/438313: Just TypeSupportsHierarchy condition should
96 // theoretically be sufficient but in practice many tests don't properly
97 // initialize entries so TypeSupportsHierarchy ends up failing. Consider
98 // tweaking TypeSupportsHierarchy and fixing all related test code.
99 if (parent_id
.IsRoot() && entry
->ref(IS_DIR
) &&
100 syncer::IsRealDataType(model_type
) &&
101 !TypeSupportsHierarchy(model_type
)) {
102 const Id
& type_root_id
= entry
->ref(ID
);
103 // Disassociate the type root child set with the previous ID if any.
104 const Id
& prev_type_root_id
= model_type_root_ids_
[model_type
];
105 if (!prev_type_root_id
.IsNull()) {
106 ParentChildrenMap::iterator it
=
107 parent_children_map_
.find(prev_type_root_id
);
108 if (it
!= parent_children_map_
.end()) {
109 // If the entry exists in the map it must already have the same
110 // model type specific child set. This child set will be re-inserted
111 // in the map under the new ID below so it is safe to simply erase
113 DCHECK_EQ(it
->second
, GetModelTypeChildSet(model_type
));
114 parent_children_map_
.erase(it
);
117 // Store the new type root ID and associate the child set.
118 // Note that the child set isn't owned by the map in this case.
119 model_type_root_ids_
[model_type
] = type_root_id
;
120 parent_children_map_
.insert(
121 std::make_pair(type_root_id
, GetOrCreateModelTypeChildSet(model_type
)));
124 // Finally, insert the entry in the child set.
125 return siblings
->insert(entry
).second
;
128 // Like the other containers used to help support the syncable::Directory, this
129 // one does not own any EntryKernels. This function removes references to the
130 // given EntryKernel but does not delete it.
131 void ParentChildIndex::Remove(EntryKernel
* e
) {
132 OrderedChildSet
* siblings
= nullptr;
133 ModelType model_type
= e
->GetModelType();
134 const Id
& parent_id
= e
->ref(PARENT_ID
);
135 bool should_erase
= false;
136 ParentChildrenMap::iterator it
;
138 if (ShouldUseParentId(parent_id
, model_type
)) {
139 // Hierarchical type, lookup child set in the map.
140 DCHECK(!parent_id
.IsNull());
141 it
= parent_children_map_
.find(parent_id
);
142 DCHECK(it
!= parent_children_map_
.end());
143 siblings
= it
->second
;
146 // Non-hierarchical type, return a pre-defined child set by type.
147 siblings
= type_root_child_sets_
[model_type
];
150 OrderedChildSet::iterator j
= siblings
->find(e
);
151 DCHECK(j
!= siblings
->end());
153 // Erase the entry from the child set.
155 // If the set is now empty and isn't shareable with |type_root_child_sets_|,
156 // erase it from the map.
157 if (siblings
->empty() && should_erase
) {
159 parent_children_map_
.erase(it
);
163 bool ParentChildIndex::Contains(EntryKernel
*e
) const {
164 const OrderedChildSet
* siblings
= GetChildSet(e
);
165 return siblings
&& siblings
->count(e
) > 0;
168 const OrderedChildSet
* ParentChildIndex::GetChildren(const Id
& id
) const {
169 DCHECK(!id
.IsNull());
171 ParentChildrenMap::const_iterator parent
= parent_children_map_
.find(id
);
172 if (parent
== parent_children_map_
.end()) {
176 OrderedChildSet
* children
= parent
->second
;
177 // The expectation is that the function returns nullptr instead of an empty
179 if (children
&& children
->empty())
184 const OrderedChildSet
* ParentChildIndex::GetChildren(EntryKernel
* e
) const {
185 return GetChildren(e
->ref(ID
));
188 const OrderedChildSet
* ParentChildIndex::GetSiblings(EntryKernel
* e
) const {
189 // This implies the entry is in the index.
191 const OrderedChildSet
* siblings
= GetChildSet(e
);
192 DCHECK(siblings
&& !siblings
->empty());
197 bool ParentChildIndex::ShouldUseParentId(const Id
& parent_id
,
198 ModelType model_type
) {
199 // For compatibility with legacy unit tests, in addition to hierarchical
200 // entries, this returns true any entries directly under root and for entries
201 // of UNSPECIFIED model type.
202 return parent_id
.IsRoot() || TypeSupportsHierarchy(model_type
) ||
203 !syncer::IsRealDataType(model_type
);
206 const OrderedChildSet
* ParentChildIndex::GetChildSet(EntryKernel
* e
) const {
207 ModelType model_type
= e
->GetModelType();
209 const Id
& parent_id
= e
->ref(PARENT_ID
);
210 if (ShouldUseParentId(parent_id
, model_type
)) {
211 // Hierarchical type, lookup child set in the map.
212 ParentChildrenMap::const_iterator it
= parent_children_map_
.find(parent_id
);
213 if (it
== parent_children_map_
.end())
218 // Non-hierarchical type, return a collection indexed by type.
219 return GetModelTypeChildSet(model_type
);
222 const OrderedChildSet
* ParentChildIndex::GetModelTypeChildSet(
223 ModelType model_type
) const {
224 return type_root_child_sets_
[model_type
];
227 OrderedChildSet
* ParentChildIndex::GetOrCreateModelTypeChildSet(
228 ModelType model_type
) {
229 if (!type_root_child_sets_
[model_type
])
230 type_root_child_sets_
[model_type
] = new OrderedChildSet();
231 return type_root_child_sets_
[model_type
];
234 const Id
& ParentChildIndex::GetModelTypeRootId(ModelType model_type
) const {
235 return model_type_root_ids_
[model_type
];
238 } // namespace syncable
239 } // namespace syncer