Improve dependency look-up

Simplify the dependency look-up by moving the dependers directly into
the dependee runnable, each task is then responsible for updating their
dependers and queue them up when they are free to be run.

Change-Id: I96295d47cecd507a864965e1fb65f2ff9af68111
Reviewed-by: Sean Harmer <sean.harmer@kdab.com>

9 files changed, 45 insertions, 342 deletions

diff --git a/src/core/jobs/dependencyhandler.cpp b/src/core/jobs/dependencyhandler.cpp
deleted file mode 100644
index 6a925d037..000000000
--- a/src/core/jobs/dependencyhandler.cpp
+++ /dev/null
@@ -1,157 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the Qt3D module of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:LGPL$
-** Commercial License Usage
-** Licensees holding valid commercial Qt licenses may use this file in
-** accordance with the commercial license agreement provided with the
-** Software or, alternatively, in accordance with the terms contained in
-** a written agreement between you and The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU Lesser General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU Lesser
-** General Public License version 3 as published by the Free Software
-** Foundation and appearing in the file LICENSE.LGPL3 included in the
-** packaging of this file. Please review the following information to
-** ensure the GNU Lesser General Public License version 3 requirements
-** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 2.0 or (at your option) the GNU General
-** Public license version 3 or any later version approved by the KDE Free
-** Qt Foundation. The licenses are as published by the Free Software
-** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-2.0.html and
-** https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
-
-#include "dependencyhandler_p.h"
-
-#include <iterator>
-
-QT_BEGIN_NAMESPACE
-
-namespace Qt3DCore {
-
-namespace {
-    template <template <typename T> class Op>
-    struct ByDepender {
-        typedef bool result_type;
-
-        bool operator()(const RunnableInterface *lhs, const RunnableInterface *rhs) const Q_DECL_NOTHROW
-        { return Op<const RunnableInterface *>()(lhs, rhs); }
-
-        bool operator()(const RunnableInterface *lhs, const Dependency &rhs) const Q_DECL_NOTHROW
-        { return operator()(lhs, rhs.depender); }
-
-        bool operator()(const Dependency &lhs, const RunnableInterface *rhs) const Q_DECL_NOTHROW
-        { return operator()(lhs.depender, rhs); }
-
-        bool operator()(const Dependency &lhs, const Dependency &rhs) const Q_DECL_NOTHROW
-        { return operator()(lhs.depender, rhs.depender); }
-    };
-
-    struct DependeeEquals : std::unary_function<Dependency, bool>
-    {
-        const RunnableInterface *dependee;
-        QVector<RunnableInterface *> *freedList;
-        explicit DependeeEquals(const RunnableInterface *dependee, QVector<RunnableInterface *> *freedList)
-            : dependee(qMove(dependee)), freedList(qMove(freedList)) {}
-        bool operator()(const Dependency &candidate) const
-        {
-            if (dependee == candidate.dependee) {
-                if (!candidate.depender->reserved())
-                    freedList->append(candidate.depender);
-                return true;
-            }
-            return false;
-        }
-    };
-
-    struct DependerEquals : std::unary_function<Dependency, bool>
-    {
-        const RunnableInterface *depender;
-        explicit DependerEquals(const RunnableInterface *depender)
-            : depender(qMove(depender)) {}
-        bool operator()(const Dependency &candidate) const
-        {
-            return depender == candidate.depender;
-        }
-    };
-
-    struct ByDependerThenDependee : std::binary_function<Dependency, Dependency, bool>
-    {
-        // Defines a lexicographical order (depender first).
-        bool operator()(const Dependency &lhs, const Dependency &rhs)
-        {
-            if (lhs.depender < rhs.depender) return true;
-            if (rhs.depender < lhs.depender) return false;
-            return lhs.dependee < rhs.dependee;
-        }
-    };
-}
-
-DependencyHandler::DependencyHandler()
-    : m_mutex()
-{
-}
-
-void DependencyHandler::addDependencies(QVector<Dependency> dependencies)
-{
-    std::sort(dependencies.begin(), dependencies.end(), ByDependerThenDependee());
-
-    const QMutexLocker locker(m_mutex);
-
-    QVector<Dependency> newDependencyMap;
-    newDependencyMap.reserve(dependencies.size() + m_dependencyMap.size());
-    std::set_union(m_dependencyMap.begin(), m_dependencyMap.end(),
-                   dependencies.begin(), dependencies.end(),
-                   std::back_inserter(newDependencyMap), ByDependerThenDependee());
-    m_dependencyMap.swap(newDependencyMap); // commit
-}
-
-bool DependencyHandler::hasDependency(const RunnableInterface *depender)
-{
-    // The caller has to set the mutex, which is QThreadPooler::enqueueTasks
-
-    return std::binary_search(m_dependencyMap.begin(), m_dependencyMap.end(),
-                              depender, ByDepender<std::less>());
-}
-
-/*
- * Removes all the entries on the m_dependencyMap that have given task as a dependee,
- * i.e. entries where the dependency is on the given task.
- */
-QVector<RunnableInterface *> DependencyHandler::freeDependencies(const RunnableInterface *task)
-{
-    // The caller has to set the mutex, which is QThreadPooler::taskFinished
-
-    m_dependencyMap.erase(std::remove_if(m_dependencyMap.begin(),
-                                         m_dependencyMap.end(),
-                                         DependerEquals(task)),
-                          m_dependencyMap.end());
-
-    QVector<RunnableInterface *> freedList;
-    m_dependencyMap.erase(std::remove_if(m_dependencyMap.begin(),
-                                         m_dependencyMap.end(),
-                                         DependeeEquals(task, &freedList)),
-                          m_dependencyMap.end());
-
-    return freedList;
-}
-
-} // namespace Qt3DCore
-
-QT_END_NAMESPACE
diff --git a/src/core/jobs/dependencyhandler_p.h b/src/core/jobs/dependencyhandler_p.h
deleted file mode 100644
index a5a023139..000000000
--- a/src/core/jobs/dependencyhandler_p.h
+++ /dev/null
@@ -1,116 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the Qt3D module of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:LGPL$
-** Commercial License Usage
-** Licensees holding valid commercial Qt licenses may use this file in
-** accordance with the commercial license agreement provided with the
-** Software or, alternatively, in accordance with the terms contained in
-** a written agreement between you and The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU Lesser General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU Lesser
-** General Public License version 3 as published by the Free Software
-** Foundation and appearing in the file LICENSE.LGPL3 included in the
-** packaging of this file. Please review the following information to
-** ensure the GNU Lesser General Public License version 3 requirements
-** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 2.0 or (at your option) the GNU General
-** Public license version 3 or any later version approved by the KDE Free
-** Qt Foundation. The licenses are as published by the Free Software
-** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-2.0.html and
-** https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
-
-#ifndef QT3DCORE_DEPENDENCYHANDLER_P_H
-#define QT3DCORE_DEPENDENCYHANDLER_P_H
-
-//
-//  W A R N I N G
-//  -------------
-//
-// This file is not part of the Qt API.  It exists for the convenience
-// of other Qt classes.  This header file may change from version to
-// version without notice, or even be removed.
-//
-// We mean it.
-//
-
-#include <QtCore/QMutex>
-#include <QtCore/QVector>
-
-#include <Qt3DCore/private/task_p.h>
-
-QT_BEGIN_NAMESPACE
-
-namespace Qt3DCore {
-
-struct Dependency
-{
-    Dependency()
-        : depender(nullptr)
-        , dependee(nullptr)
-    {}
-    Dependency(RunnableInterface *depender, RunnableInterface *dependee)
-        : depender(qMove(depender)),
-          dependee(qMove(dependee)) {}
-
-    RunnableInterface *depender;
-    RunnableInterface *dependee;
-};
-
-} // namespace Qt3DCore
-
-template <>
-class QTypeInfo<Qt3DCore::Dependency> : public QTypeInfoMerger<Qt3DCore::Dependency, Qt3DCore::RunnableInterface *> {};
-
-namespace Qt3DCore {
-
-inline bool operator==(const Dependency &left, const Dependency &right)
-{
-    return left.depender == right.depender && left.dependee == right.dependee;
-}
-
-inline bool operator!=(const Dependency &left, const Dependency &right)
-{
-    return !operator==(left, right);
-}
-
-class DependencyHandler
-{
-public:
-    DependencyHandler();
-
-    void addDependencies(QVector<Dependency> dependencies);
-    bool hasDependency(const RunnableInterface *depender);
-    QVector<RunnableInterface *> freeDependencies(const RunnableInterface *task);
-    void setMutex(QMutex *mutex) { m_mutex = mutex; }
-
-private:
-    Q_DISABLE_COPY(DependencyHandler)
-
-    QVector<Dependency> m_dependencyMap;
-    QMutex *m_mutex;
-};
-
-} // namespace Qt3DCore
-
-QT_END_NAMESPACE
-
-#endif // QT3DCORE_DEPENDENCYHANDLER_P_H
-
diff --git a/src/core/jobs/jobs.pri b/src/core/jobs/jobs.pri
index d12c42237..5d262f5c7 100644
--- a/src/core/jobs/jobs.pri
+++ b/src/core/jobs/jobs.pri
@@ -4,8 +4,7 @@ SOURCES += \
     $$PWD/qaspectjobmanager.cpp \
     $$PWD/qabstractaspectjobmanager.cpp \
     $$PWD/qthreadpooler.cpp \
-    $$PWD/task.cpp \
-    $$PWD/dependencyhandler.cpp
+    $$PWD/task.cpp
 
 HEADERS += \
     $$PWD/qaspectjob.h \
@@ -13,7 +12,6 @@ HEADERS += \
     $$PWD/qaspectjobproviderinterface_p.h \
     $$PWD/qaspectjobmanager_p.h \
     $$PWD/qabstractaspectjobmanager_p.h \
-    $$PWD/dependencyhandler_p.h \
     $$PWD/task_p.h \
     $$PWD/qthreadpooler_p.h
 
diff --git a/src/core/jobs/qaspectjobmanager.cpp b/src/core/jobs/qaspectjobmanager.cpp
index 468d904b4..702eebfe3 100644
--- a/src/core/jobs/qaspectjobmanager.cpp
+++ b/src/core/jobs/qaspectjobmanager.cpp
@@ -45,7 +45,6 @@
 #include <QtCore/QThread>
 #include <QtCore/QFuture>
 
-#include <Qt3DCore/private/dependencyhandler_p.h>
 #include <Qt3DCore/private/qthreadpooler_p.h>
 #include <Qt3DCore/private/task_p.h>
 
@@ -56,9 +55,7 @@ namespace Qt3DCore {
 QAspectJobManager::QAspectJobManager(QObject *parent)
     : QAbstractAspectJobManager(parent)
     , m_threadPooler(new QThreadPooler(this))
-    , m_dependencyHandler(new DependencyHandler)
 {
-    m_threadPooler->setDependencyHandler(m_dependencyHandler.data());
 }
 
 QAspectJobManager::~QAspectJobManager()
@@ -84,24 +81,23 @@ void QAspectJobManager::enqueueJobs(const QVector<QAspectJobPtr> &jobQueue)
         taskList << task;
     }
 
-    // Resolve dependencies
-    QVector<Dependency> dependencyList;
-
     for (const QSharedPointer<QAspectJob> &job : jobQueue) {
         const QVector<QWeakPointer<QAspectJob> > &deps = job->dependencies();
+        AspectTaskRunnable *taskDepender = tasksMap.value(job.data());
 
+        int dependerCount = 0;
         for (const QWeakPointer<QAspectJob> &dep : deps) {
             AspectTaskRunnable *taskDependee = tasksMap.value(dep.data());
-
+            // The dependencies here are not hard requirements, i.e., the dependencies
+            // not in the jobQueue should already have their data ready.
             if (taskDependee) {
-                AspectTaskRunnable *taskDepender = tasksMap.value(job.data());
-                dependencyList.append(Dependency(taskDepender, taskDependee));
-                taskDepender->setDependencyHandler(m_dependencyHandler.data());
-                taskDependee->setDependencyHandler(m_dependencyHandler.data());
+                taskDependee->m_dependers.append(taskDepender);
+                ++dependerCount;
             }
         }
+
+        taskDepender->m_dependerCount += dependerCount;
     }
-    m_dependencyHandler->addDependencies(qMove(dependencyList));
 #ifdef QT3D_JOBS_RUN_STATS
     QThreadPooler::writeFrameJobLogStats();
 #endif
diff --git a/src/core/jobs/qaspectjobmanager_p.h b/src/core/jobs/qaspectjobmanager_p.h
index 6fbf03d22..fac71f057 100644
--- a/src/core/jobs/qaspectjobmanager_p.h
+++ b/src/core/jobs/qaspectjobmanager_p.h
@@ -81,7 +81,6 @@ public:
 
 private:
     QThreadPooler *m_threadPooler;
-    QScopedPointer<DependencyHandler> m_dependencyHandler;
 };
 
 } // namespace Qt3DCore
diff --git a/src/core/jobs/qthreadpooler.cpp b/src/core/jobs/qthreadpooler.cpp
index 9985e4cee..3c9834418 100644
--- a/src/core/jobs/qthreadpooler.cpp
+++ b/src/core/jobs/qthreadpooler.cpp
@@ -48,8 +48,6 @@
 #include <QtCore/QCoreApplication>
 #endif
 
-#include <Qt3DCore/private/dependencyhandler_p.h>
-
 QT_BEGIN_NAMESPACE
 
 namespace Qt3DCore {
@@ -62,7 +60,6 @@ QThreadPooler::QThreadPooler(QObject *parent)
     : QObject(parent)
     , m_futureInterface(nullptr)
     , m_mutex()
-    , m_dependencyHandler(nullptr)
     , m_taskCount(0)
 {
     // Ensures that threads will never be recycled
@@ -79,12 +76,6 @@ QThreadPooler::~QThreadPooler()
     locker.unlock();
 }
 
-void QThreadPooler::setDependencyHandler(DependencyHandler *handler)
-{
-    m_dependencyHandler = handler;
-    m_dependencyHandler->setMutex(&m_mutex);
-}
-
 void QThreadPooler::enqueueTasks(const QVector<RunnableInterface *> &tasks)
 {
     // The caller have to set the mutex
@@ -92,7 +83,14 @@ void QThreadPooler::enqueueTasks(const QVector<RunnableInterface *> &tasks)
 
     for (QVector<RunnableInterface *>::const_iterator it = tasks.cbegin();
          it != end; ++it) {
-        if (!m_dependencyHandler->hasDependency((*it)) && !(*it)->reserved()) {
+
+        // Only AspectTaskRunnables are checked for dependencies.
+        static const auto hasDependencies = [](RunnableInterface *task) -> bool {
+            return (task->type() == RunnableInterface::RunnableType::AspectTask)
+                    && (static_cast<AspectTaskRunnable *>(task)->m_dependerCount > 0);
+        };
+
+        if (!hasDependencies(*it) && !(*it)->reserved()) {
             (*it)->setReserved(true);
             (*it)->setPooler(this);
             m_threadPool.start((*it));
@@ -106,10 +104,19 @@ void QThreadPooler::taskFinished(RunnableInterface *task)
 
     release();
 
-    if (task->dependencyHandler()) {
-        const QVector<RunnableInterface *> freedTasks = m_dependencyHandler->freeDependencies(task);
-        if (!freedTasks.empty())
-            enqueueTasks(freedTasks);
+    if (task->type() == RunnableInterface::RunnableType::AspectTask) {
+        AspectTaskRunnable *aspectTask = static_cast<AspectTaskRunnable *>(task);
+        const auto &dependers = aspectTask->m_dependers;
+        for (auto it = dependers.begin(); it != dependers.end(); ++it) {
+            aspectTask = static_cast<AspectTaskRunnable *>(*it);
+            if (--aspectTask->m_dependerCount == 0) {
+                if (!aspectTask->reserved()) {
+                    aspectTask->setReserved(true);
+                    aspectTask->setPooler(this);
+                    m_threadPool.start(aspectTask);
+                }
+            }
+        }
     }
 
     if (currentCount() == 0) {
diff --git a/src/core/jobs/qthreadpooler_p.h b/src/core/jobs/qthreadpooler_p.h
index 9d632a696..d03e55624 100644
--- a/src/core/jobs/qthreadpooler_p.h
+++ b/src/core/jobs/qthreadpooler_p.h
@@ -57,7 +57,6 @@
 #include <QtCore/QSharedPointer>
 #include <QtCore/QThreadPool>
 
-#include <Qt3DCore/private/dependencyhandler_p.h>
 #include <Qt3DCore/private/qaspectjob_p.h>
 #include <Qt3DCore/private/task_p.h>
 
@@ -81,8 +80,6 @@ public:
     void taskFinished(RunnableInterface *task);
     QFuture<void> future();
 
-    void setDependencyHandler(DependencyHandler *handler);
-
     int maxThreadCount() const;
 #ifdef QT3D_JOBS_RUN_STATS
     static QElapsedTimer m_jobsStatTimer;
@@ -105,7 +102,6 @@ private:
 private:
     QFutureInterface<void> *m_futureInterface;
     QMutex m_mutex;
-    DependencyHandler *m_dependencyHandler;
     QAtomicInt m_taskCount;
     QThreadPool m_threadPool;
 };
diff --git a/src/core/jobs/task.cpp b/src/core/jobs/task.cpp
index ca3c8b65a..6e053eb73 100644
--- a/src/core/jobs/task.cpp
+++ b/src/core/jobs/task.cpp
@@ -43,7 +43,6 @@
 #include <QtCore/QElapsedTimer>
 #include <QtCore/QMutexLocker>
 
-#include <Qt3DCore/private/dependencyhandler_p.h>
 #include <Qt3DCore/private/qthreadpooler_p.h>
 
 QT_BEGIN_NAMESPACE
@@ -57,8 +56,7 @@ RunnableInterface::~RunnableInterface()
 // Aspect task
 
 AspectTaskRunnable::AspectTaskRunnable()
-    : m_dependencyHandler(nullptr)
-    , m_pooler(nullptr)
+    : m_pooler(nullptr)
     , m_reserved(false)
 {
 }
@@ -94,16 +92,6 @@ void AspectTaskRunnable::run()
         m_pooler->taskFinished(this);
 }
 
-void AspectTaskRunnable::setDependencyHandler(DependencyHandler *handler)
-{
-    m_dependencyHandler = handler;
-}
-
-DependencyHandler *AspectTaskRunnable::dependencyHandler()
-{
-    return m_dependencyHandler;
-}
-
 // Synchronized task
 
 SyncTaskRunnable::SyncTaskRunnable(QAbstractAspectJobManager::JobFunction func,
@@ -137,16 +125,6 @@ void SyncTaskRunnable::run()
         m_pooler->taskFinished(this);
 }
 
-void SyncTaskRunnable::setDependencyHandler(DependencyHandler *handler)
-{
-    Q_UNUSED(handler);
-}
-
-DependencyHandler *SyncTaskRunnable::dependencyHandler()
-{
-    return nullptr;
-}
-
 } // namespace Qt3DCore {
 
 QT_END_NAMESPACE
diff --git a/src/core/jobs/task_p.h b/src/core/jobs/task_p.h
index 8193abaf6..91e3f5f3d 100644
--- a/src/core/jobs/task_p.h
+++ b/src/core/jobs/task_p.h
@@ -69,13 +69,15 @@ class QThreadPooler;
 class RunnableInterface : public QRunnable
 {
 public:
+    enum class RunnableType {
+        AspectTask,
+        SyncTask
+    };
+
     virtual ~RunnableInterface();
 
     virtual void run() = 0;
 
-    virtual void setDependencyHandler(DependencyHandler *) = 0;
-    virtual DependencyHandler *dependencyHandler() = 0;
-
     virtual int id() = 0;
     virtual void setId(int id) = 0;
 
@@ -83,6 +85,8 @@ public:
     virtual bool reserved() = 0;
 
     virtual void setPooler(QThreadPooler *pooler) = 0;
+
+    virtual RunnableType type() const = 0;
 };
 
 class AspectTaskRunnable : public RunnableInterface
@@ -93,9 +97,6 @@ public:
 
     void run() Q_DECL_OVERRIDE;
 
-    void setDependencyHandler(DependencyHandler *handler) Q_DECL_OVERRIDE;
-    DependencyHandler *dependencyHandler() Q_DECL_OVERRIDE;
-
     void setPooler(QThreadPooler *pooler) Q_DECL_OVERRIDE { m_pooler = pooler; }
 
     void setReserved(bool reserved) Q_DECL_OVERRIDE { m_reserved = reserved; }
@@ -104,15 +105,17 @@ public:
     int id() Q_DECL_OVERRIDE { return m_id; }
     void setId(int id) Q_DECL_OVERRIDE { m_id = id; }
 
+    RunnableType type() const Q_DECL_OVERRIDE { return RunnableType::AspectTask; }
+
 public:
     QSharedPointer<QAspectJob> m_job;
+    QVector<AspectTaskRunnable *> m_dependers;
+    int m_dependerCount = 0;
 
 private:
-    DependencyHandler *m_dependencyHandler;
     QThreadPooler *m_pooler;
-    bool m_reserved;
-
     int m_id; // For testing purposes for now
+    bool m_reserved;
 };
 
 class SyncTaskRunnable : public RunnableInterface
@@ -124,9 +127,6 @@ public:
 
     void run() Q_DECL_OVERRIDE;
 
-    void setDependencyHandler(DependencyHandler *handler) Q_DECL_OVERRIDE;
-    DependencyHandler *dependencyHandler() Q_DECL_OVERRIDE;
-
     void setPooler(QThreadPooler *pooler) Q_DECL_OVERRIDE { m_pooler = pooler; }
 
     void setReserved(bool reserved) Q_DECL_OVERRIDE { m_reserved = reserved; }
@@ -135,6 +135,8 @@ public:
     int id() Q_DECL_OVERRIDE { return m_id; }
     void setId(int id) Q_DECL_OVERRIDE { m_id = id; }
 
+    RunnableType type() const Q_DECL_OVERRIDE { return RunnableType::SyncTask; }
+
 private:
     QAbstractAspectJobManager::JobFunction m_func;
     void *m_arg;