Akonadi

collectiontreecache.cpp
1/*
2 SPDX-FileCopyrightText: 2017 Daniel Vrátil <dvratil@kde.org>
3
4 SPDX-License-Identifier: LGPL-2.0-or-later
5*/
6
7#include "collectiontreecache.h"
8#include "akonadiserver_debug.h"
9#include "commandcontext.h"
10#include "selectquerybuilder.h"
11
12#include "private/scope_p.h"
13
14#include <QStack>
15
16#include <algorithm>
17#include <iterator>
18#include <map>
19#include <tuple>
20
21using namespace Akonadi::Server;
22
23namespace
24{
25enum Column {
26 IdColumn,
27 ParentIdColumn,
28 RIDColumn,
29 DisplayPrefColumn,
30 SyncPrefColumn,
31 IndexPrefColumn,
32 EnabledColumn,
33 ReferencedColumn,
34 ResourceNameColumn,
35};
36}
37
38CollectionTreeCache::Node::Node()
39 : parent(nullptr)
40 , lruCounter(0)
41 , id(-1)
42{
43}
44
45CollectionTreeCache::Node::Node(const Collection &col)
46 : parent(nullptr)
47 , id(col.id())
48 , collection(col)
49
50{
51}
52
53CollectionTreeCache::Node::~Node()
54{
55 qDeleteAll(children);
56}
57
58void CollectionTreeCache::Node::appendChild(Node *child)
59{
60 child->parent = this;
61 children.push_back(child);
62}
63
64void CollectionTreeCache::Node::removeChild(Node *child)
65{
66 child->parent = nullptr;
67 children.removeOne(child);
68}
69
70CollectionTreeCache::CollectionTreeCache()
71 : AkThread(QStringLiteral("CollectionTreeCache"))
72{
73}
74
75CollectionTreeCache::~CollectionTreeCache()
76{
77 quitThread();
78}
79
80void CollectionTreeCache::init()
81{
82 AkThread::init();
83
84 QWriteLocker locker(&mLock);
85
86 mRoot = new Node;
87 mRoot->id = 0;
88 mRoot->parent = nullptr;
89 mNodeLookup.insert(0, mRoot);
90
92 qb.addSortColumn(Collection::idFullColumnName(), Query::Ascending);
93
94 if (!qb.exec()) {
95 qCCritical(AKONADISERVER_LOG) << "Failed to initialize Collection tree cache!";
96 return;
97 }
98
99 // std's reverse iterators makes processing pendingNodes much easier.
100 std::multimap<qint64 /* parentID */, Node *> pendingNodes;
101 const auto collections = qb.result();
102 for (const auto &col : collections) {
103 auto parent = mNodeLookup.value(col.parentId(), nullptr);
104
105 auto node = new Node(col);
106
107 if (parent) {
108 parent->appendChild(node);
109 mNodeLookup.insert(node->id, node);
110 } else {
111 pendingNodes.insert({col.parentId(), node});
112 }
113 }
114
115 if (!pendingNodes.empty()) {
116 int inserts = 0;
117
118 // Thanks to the SQL results being ordered by ID we already inserted most
119 // of the nodes in the loop above and here we only handle the rare cases
120 // when child has ID lower than its parent, i.e. moved collections.
121 //
122 // In theory we may need multiple passes to insert all nodes, but we can
123 // optimize by iterating the ordered map in reverse order. This way we find
124 // the parents with higher IDs first and their children later, thus needing
125 // fewer passes to process all the nodes.
126 auto it = pendingNodes.rbegin();
127 while (!pendingNodes.empty()) {
128 auto parent = mNodeLookup.value(it->first, nullptr);
129 if (!parent) {
130 // Parent of this node is still somewhere in pendingNodes, let's skip
131 // this one for now and try again in the next iteration
132 ++it;
133 } else {
134 auto node = it->second;
135 parent->appendChild(node);
136 mNodeLookup.insert(node->id, node);
137 pendingNodes.erase((++it).base());
138 ++inserts;
139 }
140
141 if (it == pendingNodes.rend()) {
142 if (Q_UNLIKELY(inserts == 0)) {
143 // This means we iterated through the entire pendingNodes but did
144 // not manage to insert any collection to the node tree. That
145 // means that there is an unreferenced collection in the database
146 // that points to an invalid parent (or has a parent which points
147 // to an invalid parent etc.). This should not happen
148 // anymore with DB constraints, but who knows...
149 qCWarning(AKONADISERVER_LOG) << "Found unreferenced Collections!";
150 auto unref = pendingNodes.begin();
151 while (unref != pendingNodes.end()) {
152 qCWarning(AKONADISERVER_LOG) << "\tCollection" << unref->second->id << "references an invalid parent" << it->first;
153 // Remove the unreferenced collection from the map
154 delete unref->second;
155 unref = pendingNodes.erase(unref);
156 }
157 qCWarning(AKONADISERVER_LOG) << "Please run \"akonadictl fsck\" to correct the inconsistencies!";
158 // pendingNodes should be empty now so break the loop here
159 break;
160 }
161
162 it = pendingNodes.rbegin();
163 inserts = 0;
164 }
165 }
166 }
167
168 Q_ASSERT(pendingNodes.empty());
169 Q_ASSERT(mNodeLookup.size() == collections.count() + 1 /* root */);
170 // Now we should have a complete tree built, yay!
171}
172
173void CollectionTreeCache::quit()
174{
175 delete mRoot;
176
177 AkThread::quit();
178}
179
180void CollectionTreeCache::collectionAdded(const Collection &col)
181{
182 QWriteLocker locker(&mLock);
183
184 auto parent = mNodeLookup.value(col.parentId(), nullptr);
185 if (!parent) {
186 qCWarning(AKONADISERVER_LOG) << "Received a new collection (" << col.id() << ") with unknown parent (" << col.parentId() << ")";
187 return;
188 }
189
190 auto node = new Node(col);
191 parent->appendChild(node);
192 mNodeLookup.insert(node->id, node);
193}
194
195void CollectionTreeCache::collectionChanged(const Collection &col)
196{
197 QWriteLocker locker(&mLock);
198
199 auto node = mNodeLookup.value(col.id(), nullptr);
200 if (!node) {
201 qCWarning(AKONADISERVER_LOG) << "Received an unknown changed collection (" << col.id() << ")";
202 return;
203 }
204
205 // Only update non-expired nodes
206 if (node->collection.isValid()) {
207 node->collection = col;
208 }
209}
210
211void CollectionTreeCache::collectionMoved(const Collection &col)
212{
213 QWriteLocker locker(&mLock);
214
215 auto node = mNodeLookup.value(col.id(), nullptr);
216 if (!node) {
217 qCWarning(AKONADISERVER_LOG) << "Received an unknown moved collection (" << col.id() << ")";
218 return;
219 }
220 auto oldParent = node->parent;
221
222 auto newParent = mNodeLookup.value(col.parentId(), nullptr);
223 if (!newParent) {
224 qCWarning(AKONADISERVER_LOG) << "Received a moved collection (" << col.id() << ") with an unknown move destination (" << col.parentId() << ")";
225 return;
226 }
227
228 oldParent->removeChild(node);
229 newParent->appendChild(node);
230 if (node->collection.isValid()) {
231 node->collection = col;
232 }
233}
234
235void CollectionTreeCache::collectionRemoved(const Collection &col)
236{
237 QWriteLocker locker(&mLock);
238
239 auto node = mNodeLookup.value(col.id(), nullptr);
240 if (!node) {
241 qCWarning(AKONADISERVER_LOG) << "Received unknown removed collection (" << col.id() << ")";
242 return;
243 }
244
245 auto parent = node->parent;
246 parent->removeChild(node);
247 mNodeLookup.remove(node->id);
248 delete node;
249}
250
251CollectionTreeCache::Node *CollectionTreeCache::findNode(const QString &rid, const QString &resource) const
252{
253 QReadLocker locker(&mLock);
254
255 // Find a subtree that belongs to the respective resource
256 auto root = std::find_if(mRoot->children.cbegin(), mRoot->children.cend(), [resource](Node *node) {
257 // resource().name() may seem expensive, but really
258 // there are only few resources and they are all cached
259 // in memory.
260 return node->collection.resource().name() == resource;
261 });
262 if (root == mRoot->children.cend()) {
263 return nullptr;
264 }
265
266 return findNode((*root), [rid](Node *node) {
267 return node->collection.remoteId() == rid;
268 });
269}
270
271QList<Collection> CollectionTreeCache::retrieveCollections(CollectionTreeCache::Node *root, int depth, int ancestorDepth) const
272{
273 QReadLocker locker(&mLock);
274
275 QList<Node *> nodes;
276 // Get all ancestors for root
277 Node *parent = root->parent;
278 for (int i = 0; i < ancestorDepth && parent != nullptr; ++i) {
279 nodes.push_back(parent);
281 }
282
283 struct StackTuple {
284 Node *node;
285 int depth;
286 };
287 QStack<StackTuple> stack;
288 stack.push({root, 0});
289 while (!stack.isEmpty()) {
290 auto c = stack.pop();
291 if (c.depth > depth) {
292 break;
293 }
294
295 if (c.node->id > 0) { // skip root
296 nodes.push_back(c.node);
297 }
298
299 for (auto child : std::as_const(c.node->children)) {
300 stack.push({child, c.depth + 1});
301 }
302 }
303
305 QList<Node *> missing;
306 for (auto node : nodes) {
307 if (node->collection.isValid()) {
308 cols.push_back(node->collection);
309 } else {
310 missing.push_back(node);
311 }
312 }
313
314 if (!missing.isEmpty()) {
315 // TODO: Check if no-one else is currently retrieving the same collections
317 Query::Condition cond(Query::Or);
318 for (auto node : std::as_const(missing)) {
319 cond.addValueCondition(Collection::idFullColumnName(), Query::Equals, node->id);
320 }
321 qb.addCondition(cond);
322 if (!qb.exec()) {
323 qCWarning(AKONADISERVER_LOG) << "Failed to retrieve collections from the database";
324 return {};
325 }
326
327 const auto results = qb.result();
328 if (results.size() != missing.size()) {
329 qCWarning(AKONADISERVER_LOG) << "Could not obtain all missing collections! Node tree refers to a non-existent collection";
330 }
331
332 cols += results;
333
334 // Relock for write
335 // TODO: Needs a better lock-upgrade mechanism
336 locker.unlock();
337 QWriteLocker wLocker(&mLock);
338 for (auto node : std::as_const(missing)) {
339 auto it = std::find_if(results.cbegin(), results.cend(), [node](const Collection &col) {
340 return node->id == col.id();
341 });
342 if (Q_UNLIKELY(it == results.cend())) {
343 continue;
344 }
345
346 node->collection = *it;
347 }
348 }
349
350 return cols;
351}
352
354CollectionTreeCache::retrieveCollections(const Scope &scope, int depth, int ancestorDepth, const QString &resource, CommandContext *context) const
355{
356 if (scope.isEmpty()) {
357 return retrieveCollections(mRoot, depth, ancestorDepth);
358 } else if (scope.scope() == Scope::Rid) {
359 // Caller must ensure!
360 Q_ASSERT(!resource.isEmpty() || (context && context->resource().isValid()));
361
362 Node *node = nullptr;
363 if (!resource.isEmpty()) {
364 node = findNode(scope.rid(), resource);
365 } else if (context && context->resource().isValid()) {
366 node = findNode(scope.rid(), context->resource().name());
367 } else {
368 return {};
369 }
370
371 if (Q_LIKELY(node)) {
372 return retrieveCollections(node, depth, ancestorDepth);
373 }
374 } else if (scope.scope() == Scope::Uid) {
375 Node *node = mNodeLookup.value(scope.uid());
376 if (Q_LIKELY(node)) {
377 return retrieveCollections(node, depth, ancestorDepth);
378 }
379 }
380
381 return {};
382}
383
384#include "moc_collectiontreecache.cpp"
Represents a collection of PIM items.
Definition collection.h:62
void addSortColumn(const QString &column, Query::SortOrder order=Query::Ascending)
Add sort column.
bool exec()
Executes the query, returns true on success.
void addCondition(const Query::Condition &condition, ConditionType type=WhereCondition)
Add a WHERE condition.
Represents a WHERE condition tree.
Definition query.h:62
Helper class for creating and executing database SELECT queries.
QList< T > result()
Returns the result of this SELECT query.
QString name() const
iterator insert(const Key &key, const T &value)
bool remove(const Key &key)
qsizetype size() const const
T value(const Key &key) const const
const_iterator cbegin() const const
const_iterator cend() const const
bool isEmpty() const const
void push_back(parameter_type value)
qsizetype size() const const
const QObjectList & children() const const
QObject * parent() const const
void push(const T &t)
bool isEmpty() const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Fri Nov 29 2024 11:49:12 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.