Akonadi

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

KDE's Doxygen guidelines are available online.