Akonadi

collectiontreecache.cpp
1 /*
2  SPDX-FileCopyrightText: 2017 Daniel Vr├ítil <[email protected]>
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 
21 using namespace Akonadi::Server;
22 
23 namespace
24 {
25 enum Column {
26  IdColumn,
27  ParentIdColumn,
28  RIDColumn,
29  DisplayPrefColumn,
30  SyncPrefColumn,
31  IndexPrefColumn,
32  EnabledColumn,
33  ReferencedColumn,
34  ResourceNameColumn,
35 };
36 }
37 
38 CollectionTreeCache::Node::Node()
39  : parent(nullptr)
40  , lruCounter(0)
41  , id(-1)
42 {
43 }
44 
45 CollectionTreeCache::Node::Node(const Collection &col)
46  : parent(nullptr)
47  , id(col.id())
48  , collection(col)
49 
50 {
51 }
52 
53 CollectionTreeCache::Node::~Node()
54 {
55  qDeleteAll(children);
56 }
57 
58 void CollectionTreeCache::Node::appendChild(Node *child)
59 {
60  child->parent = this;
61  children.push_back(child);
62 }
63 
64 void CollectionTreeCache::Node::removeChild(Node *child)
65 {
66  child->parent = nullptr;
67  children.removeOne(child);
68 }
69 
70 CollectionTreeCache::CollectionTreeCache()
71  : AkThread(QStringLiteral("CollectionTreeCache"))
72 {
73 }
74 
75 CollectionTreeCache::~CollectionTreeCache()
76 {
77  quitThread();
78 }
79 
80 void 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 
173 void CollectionTreeCache::quit()
174 {
175  delete mRoot;
176 
177  AkThread::quit();
178 }
179 
180 void 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 
195 void 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 
211 void 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 
235 void 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 
251 CollectionTreeCache::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 
271 QVector<Collection> CollectionTreeCache::retrieveCollections(CollectionTreeCache::Node *root, int depth, int ancestorDepth) const
272 {
273  QReadLocker locker(&mLock);
274 
275  QVector<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);
280  parent = parent->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 
304  QVector<Collection> cols;
305  QVector<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 
354 CollectionTreeCache::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 }
bool isEmpty() const const
void push_back(const T &value)
T value(int i) const const
bool isEmpty() const const
QVector< T > result()
Returns the result of this SELECT query.
bool exec()
Executes the query, returns true on success.
Definition: nodetree.h:12
void push(const T &t)
Helper class for creating and executing database SELECT queries.
int size() const const
Represents a WHERE condition tree.
Definition: query.h:61
void addCondition(const Query::Condition &condition, ConditionType type=WhereCondition)
Add a WHERE condition.
void addSortColumn(const QString &column, Query::SortOrder order=Query::Ascending)
Add sort column.
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Sat Jul 2 2022 06:41:47 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.