diff --git a/libs/image/kis_simple_update_queue.cpp b/libs/image/kis_simple_update_queue.cpp index 4b183d8e15..2c8bbc74be 100644 --- a/libs/image/kis_simple_update_queue.cpp +++ b/libs/image/kis_simple_update_queue.cpp @@ -1,393 +1,396 @@ /* * Copyright (c) 2010 Dmitry Kazakov * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "kis_simple_update_queue.h" #include #include #include "kis_image_config.h" #include "kis_full_refresh_walker.h" #include "kis_spontaneous_job.h" //#define ENABLE_DEBUG_JOIN //#define ENABLE_ACCUMULATOR #ifdef ENABLE_DEBUG_JOIN #define DEBUG_JOIN(baseRect, newRect, alpha) \ dbgKrita << "Two rects were joined:\t" \ << (baseRect) << "+" << (newRect) << "->" \ << ((baseRect) | (newRect)) << "(" << alpha << ")" #else #define DEBUG_JOIN(baseRect, newRect, alpha) #endif /* ENABLE_DEBUG_JOIN */ #ifdef ENABLE_ACCUMULATOR #define DECLARE_ACCUMULATOR() static qreal _baseAmount=0, _newAmount=0 #define ACCUMULATOR_ADD(baseAmount, newAmount) \ do {_baseAmount += baseAmount; _newAmount += newAmount;} while (0) #define ACCUMULATOR_DEBUG() \ dbgKrita << "Accumulated alpha:" << _newAmount / _baseAmount #else #define DECLARE_ACCUMULATOR() #define ACCUMULATOR_ADD(baseAmount, newAmount) #define ACCUMULATOR_DEBUG() #endif /* ENABLE_ACCUMULATOR */ KisSimpleUpdateQueue::KisSimpleUpdateQueue() : m_overrideLevelOfDetail(-1) { updateSettings(); } KisSimpleUpdateQueue::~KisSimpleUpdateQueue() { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); while (!m_spontaneousJobsList.isEmpty()) { delete m_spontaneousJobsList.takeLast(); } } void KisSimpleUpdateQueue::updateSettings() { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); KisImageConfig config(true); m_patchWidth = config.updatePatchWidth(); m_patchHeight = config.updatePatchHeight(); m_maxCollectAlpha = config.maxCollectAlpha(); m_maxMergeAlpha = config.maxMergeAlpha(); m_maxMergeCollectAlpha = config.maxMergeCollectAlpha(); } int KisSimpleUpdateQueue::overrideLevelOfDetail() const { return m_overrideLevelOfDetail; } void KisSimpleUpdateQueue::processQueue(KisUpdaterContext &updaterContext) { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); while (updaterContext.hasSpareThread() && processOneJob(updaterContext)); } bool KisSimpleUpdateQueue::processOneJob(KisUpdaterContext &updaterContext) { KisBaseRectsWalkerSP item; - KisMutableWalkersListIterator iter(m_updatesList); + KisMutableWalkersListIterator iter(m_updatesList, true); bool jobAdded = false; int currentLevelOfDetail = updaterContext.currentLevelOfDetail(); while(iter.hasNext()) { item = iter.next(); if ((currentLevelOfDetail < 0 || currentLevelOfDetail == item->levelOfDetail()) && !item->checksumValid()) { m_overrideLevelOfDetail = item->levelOfDetail(); item->recalculate(item->requestedRect()); m_overrideLevelOfDetail = -1; } if ((currentLevelOfDetail < 0 || currentLevelOfDetail == item->levelOfDetail()) && updaterContext.isJobAllowed(item)) { jobAdded = updaterContext.addMergeJob(item); if (!jobAdded) continue; - iter.remove(); + iter.remove(item); break; } } + iter.unlock(); if (jobAdded) return true; if (!m_spontaneousJobsList.isEmpty()) { /** * WARNING: Please note that this still doesn't guarantee that * the spontaneous jobs are exclusive, since updates and/or * strokes can be added after them. The only thing it * guarantees that two spontaneous jobs will not be executed * in parallel. * * Right now it works as it is. Probably will need to be fixed * in the future. */ qint32 numMergeJobs; qint32 numStrokeJobs; updaterContext.getJobsSnapshot(numMergeJobs, numStrokeJobs); if (!numMergeJobs && !numStrokeJobs) { KisSpontaneousJob *job = m_spontaneousJobsList.first(); jobAdded = updaterContext.addSpontaneousJob(job); - if (jobAdded) m_spontaneousJobsList.pop_front(); + if (jobAdded) m_spontaneousJobsList.takeFirst(); } } return jobAdded; } void KisSimpleUpdateQueue::addUpdateJob(KisNodeSP node, const QVector &rects, const QRect& cropRect, int levelOfDetail) { addJob(node, rects, cropRect, levelOfDetail, KisBaseRectsWalker::UPDATE); } void KisSimpleUpdateQueue::addUpdateJob(KisNodeSP node, const QRect &rc, const QRect& cropRect, int levelOfDetail) { addJob(node, {rc}, cropRect, levelOfDetail, KisBaseRectsWalker::UPDATE); } void KisSimpleUpdateQueue::addUpdateNoFilthyJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail) { addJob(node, {rc}, cropRect, levelOfDetail, KisBaseRectsWalker::UPDATE_NO_FILTHY); } void KisSimpleUpdateQueue::addFullRefreshJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail) { addJob(node, {rc}, cropRect, levelOfDetail, KisBaseRectsWalker::FULL_REFRESH); } void KisSimpleUpdateQueue::addJob(KisNodeSP node, const QVector &rects, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type) { QList walkers; Q_FOREACH (const QRect &rc, rects) { if (rc.isEmpty()) continue; KisBaseRectsWalkerSP walker; if(trySplitJob(node, rc, cropRect, levelOfDetail, type)) continue; if(tryMergeJob(node, rc, cropRect, levelOfDetail, type)) continue; if (type == KisBaseRectsWalker::UPDATE) { walker = new KisMergeWalker(cropRect, KisMergeWalker::DEFAULT); } else if (type == KisBaseRectsWalker::FULL_REFRESH) { walker = new KisFullRefreshWalker(cropRect); } else if (type == KisBaseRectsWalker::UPDATE_NO_FILTHY) { walker = new KisMergeWalker(cropRect, KisMergeWalker::NO_FILTHY); } /* else if(type == KisBaseRectsWalker::UNSUPPORTED) fatalKrita; */ walker->collectRects(node, rc); walkers.append(walker); } if (!walkers.isEmpty()) { - m_mutex.lock(); +// m_mutex.lock(); m_updatesList.append(walkers); - m_mutex.unlock(); +// m_mutex.unlock(); } } void KisSimpleUpdateQueue::addSpontaneousJob(KisSpontaneousJob *spontaneousJob) { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); KisSpontaneousJob *item; - KisMutableSpontaneousJobsListIterator iter(m_spontaneousJobsList); + KisMutableSpontaneousJobsListIterator iter(m_spontaneousJobsList, true); iter.toBack(); while(iter.hasPrevious()) { item = iter.previous(); if (spontaneousJob->overrides(item)) { - iter.remove(); - delete item; + if (iter.remove(item)) delete item; } } + iter.unlock(); m_spontaneousJobsList.append(spontaneousJob); } bool KisSimpleUpdateQueue::isEmpty() const { return m_updatesList.isEmpty() && m_spontaneousJobsList.isEmpty(); } qint32 KisSimpleUpdateQueue::sizeMetric() const { return m_updatesList.size() + m_spontaneousJobsList.size(); } bool KisSimpleUpdateQueue::trySplitJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type) { if(rc.width() <= m_patchWidth || rc.height() <= m_patchHeight) return false; // a bit of recursive splitting... qint32 firstCol = rc.x() / m_patchWidth; qint32 firstRow = rc.y() / m_patchHeight; qint32 lastCol = (rc.x() + rc.width()) / m_patchWidth; qint32 lastRow = (rc.y() + rc.height()) / m_patchHeight; QVector splitRects; for(qint32 i = firstRow; i <= lastRow; i++) { for(qint32 j = firstCol; j <= lastCol; j++) { QRect maxPatchRect(j * m_patchWidth, i * m_patchHeight, m_patchWidth, m_patchHeight); QRect patchRect = rc & maxPatchRect; splitRects.append(patchRect); } } KIS_SAFE_ASSERT_RECOVER_NOOP(!splitRects.isEmpty()); addJob(node, splitRects, cropRect, levelOfDetail, type); return true; } bool KisSimpleUpdateQueue::tryMergeJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type) { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); QRect baseRect = rc; KisBaseRectsWalkerSP goodCandidate; KisBaseRectsWalkerSP item; KisWalkersListIterator iter(m_updatesList); /** * We add new jobs to the tail of the list, * so it's more probable to find a good candidate here. */ iter.toBack(); while(iter.hasPrevious()) { item = iter.previous(); if(item->startNode() != node) continue; if(item->type() != type) continue; if(item->cropRect() != cropRect) continue; if(item->levelOfDetail() != levelOfDetail) continue; if(joinRects(baseRect, item->requestedRect(), m_maxMergeAlpha)) { goodCandidate = item; break; } } + iter.unlock(); if(goodCandidate) collectJobs(goodCandidate, baseRect, m_maxMergeCollectAlpha); return (bool)goodCandidate; } void KisSimpleUpdateQueue::optimize() { - QMutexLocker locker(&m_mutex); +// QMutexLocker locker(&m_mutex); if(m_updatesList.size() <= 1) { return; } KisBaseRectsWalkerSP baseWalker = m_updatesList.first(); QRect baseRect = baseWalker->requestedRect(); collectJobs(baseWalker, baseRect, m_maxCollectAlpha); } void KisSimpleUpdateQueue::collectJobs(KisBaseRectsWalkerSP &baseWalker, QRect baseRect, const qreal maxAlpha) { KisBaseRectsWalkerSP item; - KisMutableWalkersListIterator iter(m_updatesList); + KisMutableWalkersListIterator iter(m_updatesList, true); while(iter.hasNext()) { item = iter.next(); if(item == baseWalker) continue; if(item->type() != baseWalker->type()) continue; if(item->startNode() != baseWalker->startNode()) continue; if(item->cropRect() != baseWalker->cropRect()) continue; if(item->levelOfDetail() != baseWalker->levelOfDetail()) continue; if(joinRects(baseRect, item->requestedRect(), maxAlpha)) { - iter.remove(); + iter.remove(item); } } + iter.unlock(); if(baseWalker->requestedRect() != baseRect) { baseWalker->collectRects(baseWalker->startNode(), baseRect); } } bool KisSimpleUpdateQueue::joinRects(QRect& baseRect, const QRect& newRect, qreal maxAlpha) { QRect unitedRect = baseRect | newRect; if(unitedRect.width() > m_patchWidth || unitedRect.height() > m_patchHeight) return false; bool result = false; qint64 baseWork = baseRect.width() * baseRect.height() + newRect.width() * newRect.height(); qint64 newWork = unitedRect.width() * unitedRect.height(); qreal alpha = qreal(newWork) / baseWork; if(alpha < maxAlpha) { DEBUG_JOIN(baseRect, newRect, alpha); DECLARE_ACCUMULATOR(); ACCUMULATOR_ADD(baseWork, newWork); ACCUMULATOR_DEBUG(); baseRect = unitedRect; result = true; } return result; } KisWalkersList& KisTestableSimpleUpdateQueue::getWalkersList() { return m_updatesList; } KisSpontaneousJobsList& KisTestableSimpleUpdateQueue::getSpontaneousJobsList() { return m_spontaneousJobsList; } diff --git a/libs/image/kis_simple_update_queue.h b/libs/image/kis_simple_update_queue.h index 6314a098ce..488674522e 100644 --- a/libs/image/kis_simple_update_queue.h +++ b/libs/image/kis_simple_update_queue.h @@ -1,116 +1,261 @@ /* * Copyright (c) 2010 Dmitry Kazakov * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef __KIS_SIMPLE_UPDATE_QUEUE_H #define __KIS_SIMPLE_UPDATE_QUEUE_H #include #include "kis_updater_context.h" -typedef QList KisWalkersList; -typedef QListIterator KisWalkersListIterator; -typedef QMutableListIterator KisMutableWalkersListIterator; +//typedef QList KisWalkersList; +//typedef QListIterator KisWalkersListIterator; +//typedef QMutableListIterator KisMutableWalkersListIterator; -typedef QList KisSpontaneousJobsList; -typedef QListIterator KisSpontaneousJobsListIterator; -typedef QMutableListIterator KisMutableSpontaneousJobsListIterator; +//typedef QList KisSpontaneousJobsList; +//typedef QListIterator KisSpontaneousJobsListIterator; +//typedef QMutableListIterator KisMutableSpontaneousJobsListIterator; +template +class ConcurrentListIterator; + +template +class ConcurrentList +{ +public: + void append(T &item) + { + QWriteLocker locker(&m_rwLock); + m_list.append(item); + } + + void append(QList &list) + { + QWriteLocker locker(&m_rwLock); + m_list.append(list); + } + + T &first() + { + QReadLocker locker(&m_rwLock); + return m_list.first(); + } + + int size() const + { + QReadLocker locker(&m_rwLock); + return m_list.size(); + } + + bool isEmpty() const + { + QReadLocker locker(&m_rwLock); + return m_list.isEmpty(); + } + + T takeFirst() + { + QWriteLocker locker(&m_rwLock); + return m_list.takeFirst(); + } + + T takeLast() + { + QWriteLocker locker(&m_rwLock); + return m_list.takeLast(); + } + + T &operator[](int i) + { + return m_list[i]; + } + + ConcurrentList &operator=(const ConcurrentList &l) + { + m_list = l.m_list; + return *this; + } + + friend class ConcurrentListIterator; + +private: + QList m_list; + mutable QReadWriteLock m_rwLock; +}; + +template +class ConcurrentListIterator +{ +public: + ConcurrentListIterator(ConcurrentList &list, bool writeLock = false) : + m_pos(0), m_reversed(false), m_writeLock(writeLock), m_list(list) + { + if (m_writeLock) { + m_list.m_rwLock.lockForWrite(); + } else { + m_list.m_rwLock.lockForRead(); + } + } + + void unlock() + { + m_list.m_rwLock.unlock(); + } + + bool hasNext() const + { + return m_pos < m_list.m_list.size(); + } + + bool hasPrevious() const + { + return m_pos > -1; + } + + T &next() + { + return m_list.m_list[m_pos++]; + } + + T &previous() + { + return m_list.m_list[m_pos--]; + } + + void toBack() + { + m_pos = m_list.m_list.size() - 1; + } + + bool remove(T &item) + { + bool result = true; + + if (m_writeLock) { + if (!m_reversed) { + if (m_list.m_list[m_pos - 1] == item) { + m_list.m_list.removeAt(--m_pos); + result = true; + } + } else { + if (m_list.m_list[m_pos + 1] == item) { + m_list.m_list.removeAt(m_pos + 1); + result = true; + } + } + } + + return result; + } + +private: + int m_pos; + bool m_reversed; + bool m_writeLock; + ConcurrentList &m_list; +}; + +typedef ConcurrentList KisWalkersList; +typedef ConcurrentListIterator KisWalkersListIterator; +typedef ConcurrentListIterator KisMutableWalkersListIterator; + +typedef ConcurrentList KisSpontaneousJobsList; +typedef ConcurrentListIterator KisMutableSpontaneousJobsListIterator; class KRITAIMAGE_EXPORT KisSimpleUpdateQueue { public: KisSimpleUpdateQueue(); virtual ~KisSimpleUpdateQueue(); void processQueue(KisUpdaterContext &updaterContext); void addUpdateJob(KisNodeSP node, const QVector &rects, const QRect& cropRect, int levelOfDetail); void addUpdateJob(KisNodeSP node, const QRect &rc, const QRect& cropRect, int levelOfDetail); void addUpdateNoFilthyJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail); void addFullRefreshJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail); void addSpontaneousJob(KisSpontaneousJob *spontaneousJob); void optimize(); bool isEmpty() const; qint32 sizeMetric() const; void updateSettings(); int overrideLevelOfDetail() const; protected: void addJob(KisNodeSP node, const QVector &rects, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type); bool processOneJob(KisUpdaterContext &updaterContext); bool trySplitJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type); bool tryMergeJob(KisNodeSP node, const QRect& rc, const QRect& cropRect, int levelOfDetail, KisBaseRectsWalker::UpdateType type); void collectJobs(KisBaseRectsWalkerSP &baseWalker, QRect baseRect, const qreal maxAlpha); bool joinRects(QRect& baseRect, const QRect& newRect, qreal maxAlpha); protected: - mutable QMutex m_mutex; +// mutable QMutex m_mutex; KisWalkersList m_updatesList; KisSpontaneousJobsList m_spontaneousJobsList; /** * Parameters of optimization * (loaded from a configuration file) */ /** * Big update areas are split into a set of smaller * ones, m_patchWidth and m_patchHeight represent the * size of these areas. */ qint32 m_patchWidth; qint32 m_patchHeight; /** * Maximum coefficient of work while regular optimization() */ qreal m_maxCollectAlpha; /** * Maximum coefficient of work when to rects are considered * similar and are merged in tryMergeJob() */ qreal m_maxMergeAlpha; /** * The coefficient of work used while collecting phase of tryToMerge() */ qreal m_maxMergeCollectAlpha; int m_overrideLevelOfDetail; }; class KRITAIMAGE_EXPORT KisTestableSimpleUpdateQueue : public KisSimpleUpdateQueue { public: KisWalkersList& getWalkersList(); KisSpontaneousJobsList& getSpontaneousJobsList(); }; #endif /* __KIS_SIMPLE_UPDATE_QUEUE_H */