OLD | NEW |
| (Empty) |
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 <memory> | |
8 | |
9 #include "base/stl_util.h" | |
10 #include "sync/syncable/entry_kernel.h" | |
11 #include "sync/syncable/syncable_id.h" | |
12 | |
13 namespace syncer { | |
14 namespace syncable { | |
15 | |
16 bool ChildComparator::operator()(const EntryKernel* a, | |
17 const EntryKernel* b) const { | |
18 const UniquePosition& a_pos = a->ref(UNIQUE_POSITION); | |
19 const UniquePosition& b_pos = b->ref(UNIQUE_POSITION); | |
20 | |
21 if (a_pos.IsValid() && b_pos.IsValid()) { | |
22 // Position is important to this type. | |
23 return a_pos.LessThan(b_pos); | |
24 } else if (a_pos.IsValid() && !b_pos.IsValid()) { | |
25 // TODO(rlarocque): Remove this case. | |
26 // An item with valid position as sibling of one with invalid position. | |
27 // We should not support this, but the tests rely on it. For now, just | |
28 // move all invalid position items to the right. | |
29 return true; | |
30 } else if (!a_pos.IsValid() && b_pos.IsValid()) { | |
31 // TODO(rlarocque): Remove this case. | |
32 // Mirror of the above case. | |
33 return false; | |
34 } else { | |
35 // Position doesn't matter. | |
36 DCHECK(!a->ref(UNIQUE_POSITION).IsValid()); | |
37 DCHECK(!b->ref(UNIQUE_POSITION).IsValid()); | |
38 // Sort by META_HANDLE to ensure consistent order for testing. | |
39 return a->ref(META_HANDLE) < b->ref(META_HANDLE); | |
40 } | |
41 } | |
42 | |
43 ParentChildIndex::ParentChildIndex() { | |
44 // Pre-allocate these two vectors to the number of model types. | |
45 model_type_root_ids_.resize(MODEL_TYPE_COUNT); | |
46 type_root_child_sets_.resize(MODEL_TYPE_COUNT); | |
47 } | |
48 | |
49 ParentChildIndex::~ParentChildIndex() {} | |
50 | |
51 bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) { | |
52 // This index excludes deleted items and the root item. The root | |
53 // item is excluded so that it doesn't show up as a child of itself. | |
54 return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot(); | |
55 } | |
56 | |
57 bool ParentChildIndex::Insert(EntryKernel* entry) { | |
58 DCHECK(ShouldInclude(entry)); | |
59 | |
60 OrderedChildSetRef siblings = nullptr; | |
61 const Id& parent_id = entry->ref(PARENT_ID); | |
62 ModelType model_type = entry->GetModelType(); | |
63 | |
64 if (ShouldUseParentId(parent_id, model_type)) { | |
65 // Hierarchical type, lookup child set in the map. | |
66 DCHECK(!parent_id.IsNull()); | |
67 ParentChildrenMap::iterator it = parent_children_map_.find(parent_id); | |
68 if (it != parent_children_map_.end()) { | |
69 siblings = it->second; | |
70 } else { | |
71 siblings = OrderedChildSetRef(new OrderedChildSet()); | |
72 parent_children_map_.insert(std::make_pair(parent_id, siblings)); | |
73 } | |
74 } else { | |
75 // Non-hierarchical type, return a pre-defined collection by type. | |
76 siblings = GetOrCreateModelTypeChildSet(model_type); | |
77 } | |
78 | |
79 // If this is one of type root folder for a non-hierarchical type, associate | |
80 // its ID with the model type and the type's pre-defined child set with the | |
81 // type root ID. | |
82 // TODO(stanisc): crbug/438313: Just TypeSupportsHierarchy condition should | |
83 // theoretically be sufficient but in practice many tests don't properly | |
84 // initialize entries so TypeSupportsHierarchy ends up failing. Consider | |
85 // tweaking TypeSupportsHierarchy and fixing all related test code. | |
86 if (parent_id.IsRoot() && entry->ref(IS_DIR) && | |
87 syncer::IsRealDataType(model_type) && | |
88 !TypeSupportsHierarchy(model_type)) { | |
89 const Id& type_root_id = entry->ref(ID); | |
90 | |
91 // If the entry exists in the map it must already have the same | |
92 // model type specific child set. It's possible another type root exists | |
93 // in parent_children_map_, but that's okay as the new type root will | |
94 // point to the same OrderedChildSet. As such, we just blindly store the | |
95 // new type root ID and associate it to the (possibly existing) child set. | |
96 model_type_root_ids_[model_type] = type_root_id; | |
97 parent_children_map_.insert(std::make_pair( | |
98 type_root_id, GetOrCreateModelTypeChildSet(model_type))); | |
99 } | |
100 | |
101 // Finally, insert the entry in the child set. | |
102 return siblings->insert(entry).second; | |
103 } | |
104 | |
105 // Like the other containers used to help support the syncable::Directory, this | |
106 // one does not own any EntryKernels. This function removes references to the | |
107 // given EntryKernel but does not delete it. | |
108 void ParentChildIndex::Remove(EntryKernel* e) { | |
109 OrderedChildSetRef siblings = nullptr; | |
110 ModelType model_type = e->GetModelType(); | |
111 const Id& parent_id = e->ref(PARENT_ID); | |
112 bool should_erase = false; | |
113 ParentChildrenMap::iterator sibling_iterator; | |
114 | |
115 if (ShouldUseParentId(parent_id, model_type)) { | |
116 // Hierarchical type, lookup child set in the map. | |
117 DCHECK(!parent_id.IsNull()); | |
118 sibling_iterator = parent_children_map_.find(parent_id); | |
119 DCHECK(sibling_iterator != parent_children_map_.end()); | |
120 siblings = sibling_iterator->second; | |
121 should_erase = true; | |
122 } else { | |
123 // Non-hierarchical type, return a pre-defined child set by type. | |
124 siblings = type_root_child_sets_[model_type]; | |
125 } | |
126 | |
127 OrderedChildSet::iterator j = siblings->find(e); | |
128 DCHECK(j != siblings->end()); | |
129 | |
130 // Erase the entry from the child set. | |
131 siblings->erase(j); | |
132 // If the set is now empty and isn't shareable with |type_root_child_sets_|, | |
133 // erase it from the map. | |
134 if (siblings->empty() && should_erase) { | |
135 parent_children_map_.erase(sibling_iterator); | |
136 } | |
137 } | |
138 | |
139 bool ParentChildIndex::Contains(EntryKernel *e) const { | |
140 const OrderedChildSetRef siblings = GetChildSet(e); | |
141 return siblings && siblings->count(e) > 0; | |
142 } | |
143 | |
144 const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const { | |
145 DCHECK(!id.IsNull()); | |
146 | |
147 ParentChildrenMap::const_iterator parent = parent_children_map_.find(id); | |
148 if (parent == parent_children_map_.end()) { | |
149 return nullptr; | |
150 } | |
151 | |
152 OrderedChildSetRef children = parent->second; | |
153 // The expectation is that the function returns nullptr instead of an empty | |
154 // child set | |
155 if (children && children->empty()) | |
156 children = nullptr; | |
157 return children.get(); | |
158 } | |
159 | |
160 const OrderedChildSet* ParentChildIndex::GetChildren(EntryKernel* e) const { | |
161 return GetChildren(e->ref(ID)); | |
162 } | |
163 | |
164 const OrderedChildSet* ParentChildIndex::GetSiblings(EntryKernel* e) const { | |
165 // This implies the entry is in the index. | |
166 DCHECK(Contains(e)); | |
167 const OrderedChildSetRef siblings = GetChildSet(e); | |
168 DCHECK(siblings && !siblings->empty()); | |
169 return siblings.get(); | |
170 } | |
171 | |
172 /* static */ | |
173 bool ParentChildIndex::ShouldUseParentId(const Id& parent_id, | |
174 ModelType model_type) { | |
175 // For compatibility with legacy unit tests, in addition to hierarchical | |
176 // entries, this returns true any entries directly under root and for entries | |
177 // of UNSPECIFIED model type. | |
178 return parent_id.IsRoot() || TypeSupportsHierarchy(model_type) || | |
179 !syncer::IsRealDataType(model_type); | |
180 } | |
181 | |
182 const OrderedChildSetRef ParentChildIndex::GetChildSet(EntryKernel* e) const { | |
183 ModelType model_type = e->GetModelType(); | |
184 | |
185 const Id& parent_id = e->ref(PARENT_ID); | |
186 if (ShouldUseParentId(parent_id, model_type)) { | |
187 // Hierarchical type, lookup child set in the map. | |
188 ParentChildrenMap::const_iterator it = parent_children_map_.find(parent_id); | |
189 if (it == parent_children_map_.end()) | |
190 return nullptr; | |
191 return it->second; | |
192 } | |
193 | |
194 // Non-hierarchical type, return a collection indexed by type. | |
195 return GetModelTypeChildSet(model_type); | |
196 } | |
197 | |
198 const OrderedChildSetRef ParentChildIndex::GetModelTypeChildSet( | |
199 ModelType model_type) const { | |
200 return type_root_child_sets_[model_type]; | |
201 } | |
202 | |
203 OrderedChildSetRef ParentChildIndex::GetOrCreateModelTypeChildSet( | |
204 ModelType model_type) { | |
205 if (!type_root_child_sets_[model_type]) | |
206 type_root_child_sets_[model_type] = | |
207 OrderedChildSetRef(new OrderedChildSet()); | |
208 return type_root_child_sets_[model_type]; | |
209 } | |
210 | |
211 const Id& ParentChildIndex::GetModelTypeRootId(ModelType model_type) const { | |
212 return model_type_root_ids_[model_type]; | |
213 } | |
214 | |
215 } // namespace syncable | |
216 } // namespace syncer | |
OLD | NEW |