File indexing completed on 2024-06-09 04:22:25

0001 /*
0002  *  SPDX-FileCopyrightText: 2017 Dmitry Kazakov <dimula73@gmail.com>
0003  *  SPDX-FileCopyrightText: 2018 Andrey Kamakin <a.kamakin@icloud.com>
0004  *
0005  *  SPDX-License-Identifier: GPL-2.0-or-later
0006  */
0007 
0008 #include "KisTiledExtentManager.h"
0009 
0010 #include <QMutex>
0011 #include <QVector>
0012 #include "kis_tile_data_interface.h"
0013 #include "kis_assert.h"
0014 #include "kis_global.h"
0015 #include "kis_debug.h"
0016 
0017 KisTiledExtentManager::Data::Data()
0018     : m_min(qint32_MAX), m_max(qint32_MIN), m_count(0)
0019 {
0020     QWriteLocker lock(&m_migrationLock);
0021     m_capacity = InitialBufferSize;
0022     m_offset = 1;
0023     m_buffer = new QAtomicInt[m_capacity];
0024 }
0025 
0026 KisTiledExtentManager::Data::~Data()
0027 {
0028     QWriteLocker lock(&m_migrationLock);
0029     delete[] m_buffer;
0030 }
0031 
0032 bool KisTiledExtentManager::Data::add(qint32 index)
0033 {
0034     QReadLocker lock(&m_migrationLock);
0035     qint32 currentIndex = m_offset + index;
0036 
0037     if (currentIndex < 0 || currentIndex >= m_capacity) {
0038         lock.unlock();
0039         migrate(index);
0040         lock.relock();
0041         currentIndex = m_offset + index;
0042     }
0043 
0044     KIS_ASSERT_RECOVER_NOOP(m_buffer[currentIndex].loadAcquire() >= 0);
0045     bool needsUpdateExtent = false;
0046 
0047     while (true) {
0048         QReadLocker rl(&m_extentLock);
0049 
0050         int oldValue = m_buffer[currentIndex].loadAcquire();
0051         if (oldValue == 0) {
0052             rl.unlock();
0053             QWriteLocker wl(&m_extentLock);
0054 
0055             if ((oldValue = m_buffer[currentIndex].loadAcquire()) == 0) {
0056 
0057                 if (m_min > index) m_min = index;
0058                 if (m_max < index) m_max = index;
0059 
0060                 ++m_count;
0061                 needsUpdateExtent = true;
0062 
0063                 m_buffer[currentIndex].storeRelease(1);
0064             } else {
0065                 m_buffer[currentIndex].storeRelease(oldValue + 1);
0066             }
0067 
0068             break;
0069         } else if (m_buffer[currentIndex].testAndSetOrdered(oldValue, oldValue + 1)) {
0070             break;
0071         }
0072     }
0073 
0074     return needsUpdateExtent;
0075 }
0076 
0077 bool KisTiledExtentManager::Data::remove(qint32 index)
0078 {
0079     QReadLocker lock(&m_migrationLock);
0080     qint32 currentIndex = m_offset + index;
0081 
0082     bool needsUpdateExtent = false;
0083     QReadLocker rl(&m_extentLock);
0084 
0085     const int oldValue = m_buffer[currentIndex].fetchAndAddAcquire(-1);
0086 
0087     /**
0088      * That is not the droid you're looking for. If you see this assert
0089      * in the backtrace, most probably, the bug is not here. The crash
0090      * happens because two threads are trying to do device->clear(rc)
0091      * concurrently for the overlapping rects. That is, they are trying
0092      * to remove the same tile. Look higher!
0093      */
0094     KIS_SAFE_ASSERT_RECOVER(oldValue > 0) {
0095         m_buffer[currentIndex].store(0);
0096         return false;
0097     }
0098 
0099     if (oldValue == 1) {
0100         rl.unlock();
0101         QWriteLocker wl(&m_extentLock);
0102 
0103         if (m_min == index) updateMin();
0104         if (m_max == index) updateMax();
0105 
0106         --m_count;
0107         needsUpdateExtent = true;
0108     }
0109 
0110     return needsUpdateExtent;
0111 }
0112 
0113 void KisTiledExtentManager::Data::replace(const QVector<qint32> &indexes)
0114 {
0115     QWriteLocker lock(&m_migrationLock);
0116     QWriteLocker l(&m_extentLock);
0117 
0118     for (qint32 i = 0; i < m_capacity; ++i) {
0119         m_buffer[i].store(0);
0120     }
0121 
0122     m_min = qint32_MAX;
0123     m_max = qint32_MIN;
0124     m_count = 0;
0125 
0126     Q_FOREACH (const qint32 index, indexes) {
0127         unsafeAdd(index);
0128     }
0129 }
0130 
0131 void KisTiledExtentManager::Data::clear()
0132 {
0133     QWriteLocker lock(&m_migrationLock);
0134     QWriteLocker l(&m_extentLock);
0135 
0136     for (qint32 i = 0; i < m_capacity; ++i) {
0137         m_buffer[i].store(0);
0138     }
0139 
0140     m_min = qint32_MAX;
0141     m_max = qint32_MIN;
0142     m_count = 0;
0143 }
0144 
0145 bool KisTiledExtentManager::Data::isEmpty()
0146 {
0147     return m_count == 0;
0148 }
0149 
0150 qint32 KisTiledExtentManager::Data::min()
0151 {
0152     return m_min;
0153 }
0154 
0155 qint32 KisTiledExtentManager::Data::max()
0156 {
0157     return m_max;
0158 }
0159 
0160 void KisTiledExtentManager::Data::unsafeAdd(qint32 index)
0161 {
0162     qint32 currentIndex = m_offset + index;
0163 
0164     if (currentIndex < 0 || currentIndex >= m_capacity) {
0165         unsafeMigrate(index);
0166         currentIndex = m_offset + index;
0167     }
0168 
0169     if (!m_buffer[currentIndex].fetchAndAddRelaxed(1)) {
0170         if (m_min > index) m_min = index;
0171         if (m_max < index) m_max = index;
0172         ++m_count;
0173     }
0174 }
0175 
0176 void KisTiledExtentManager::Data::unsafeMigrate(qint32 index)
0177 {
0178     qint32 oldCapacity = m_capacity;
0179     qint32 oldOffset = m_offset;
0180     qint32 currentIndex = m_offset + index;
0181 
0182     while (currentIndex < 0 || currentIndex >= m_capacity) {
0183         m_capacity <<= 1;
0184 
0185         if (currentIndex < 0) {
0186             m_offset <<= 1;
0187             currentIndex = m_offset + index;
0188         }
0189     }
0190 
0191     if (m_capacity != oldCapacity) {
0192         QAtomicInt *newBuffer = new QAtomicInt[m_capacity];
0193         qint32 start = m_offset - oldOffset;
0194 
0195         for (qint32 i = 0; i < oldCapacity; ++i) {
0196             newBuffer[start + i].store(m_buffer[i].load());
0197         }
0198 
0199         delete[] m_buffer;
0200         m_buffer = newBuffer;
0201     }
0202 }
0203 
0204 void KisTiledExtentManager::Data::migrate(qint32 index)
0205 {
0206     QWriteLocker lock(&m_migrationLock);
0207     unsafeMigrate(index);
0208 }
0209 
0210 void KisTiledExtentManager::Data::updateMin()
0211 {
0212     KIS_SAFE_ASSERT_RECOVER_NOOP(m_min != qint32_MAX);
0213 
0214     qint32 start = m_min + m_offset;
0215 
0216     for (qint32 i = start; i < m_capacity; ++i) {
0217         qint32 current = m_buffer[i].load();
0218 
0219         if (current > 0) {
0220             m_min = i - m_offset;
0221             return;
0222         }
0223     }
0224 
0225     m_min = qint32_MAX;
0226 }
0227 
0228 void KisTiledExtentManager::Data::updateMax()
0229 {
0230     KIS_SAFE_ASSERT_RECOVER_NOOP(m_min != qint32_MIN);
0231 
0232     qint32 start = m_max + m_offset;
0233 
0234     for (qint32 i = start; i >= 0; --i) {
0235         qint32 current = m_buffer[i].load();
0236 
0237         if (current > 0) {
0238             m_max = i - m_offset;
0239             return;
0240         }
0241     }
0242 
0243     m_max = qint32_MIN;
0244 }
0245 
0246 KisTiledExtentManager::KisTiledExtentManager()
0247 {
0248     QWriteLocker l(&m_extentLock);
0249     m_currentExtent = QRect();
0250 }
0251 
0252 void KisTiledExtentManager::notifyTileAdded(qint32 col, qint32 row)
0253 {
0254     bool needsUpdateExtent = false;
0255 
0256     needsUpdateExtent |= m_colsData.add(col);
0257     needsUpdateExtent |= m_rowsData.add(row);
0258 
0259     if (needsUpdateExtent) {
0260         updateExtent();
0261     }
0262 }
0263 
0264 void KisTiledExtentManager::notifyTileRemoved(qint32 col, qint32 row)
0265 {
0266     bool needsUpdateExtent = false;
0267 
0268     needsUpdateExtent |= m_colsData.remove(col);
0269     needsUpdateExtent |= m_rowsData.remove(row);
0270 
0271     if (needsUpdateExtent) {
0272         updateExtent();
0273     }
0274 }
0275 
0276 void KisTiledExtentManager::replaceTileStats(const QVector<QPoint> &indexes)
0277 {
0278     QVector<qint32> colsIndexes;
0279     QVector<qint32> rowsIndexes;
0280 
0281     Q_FOREACH (const QPoint &index, indexes) {
0282         colsIndexes.append(index.x());
0283         rowsIndexes.append(index.y());
0284     }
0285 
0286     m_colsData.replace(colsIndexes);
0287     m_rowsData.replace(rowsIndexes);
0288     updateExtent();
0289 }
0290 
0291 void KisTiledExtentManager::clear()
0292 {
0293     m_colsData.clear();
0294     m_rowsData.clear();
0295 
0296     QWriteLocker lock(&m_extentLock);
0297     m_currentExtent = QRect();
0298 }
0299 
0300 QRect KisTiledExtentManager::extent() const
0301 {
0302     QReadLocker lock(&m_extentLock);
0303     return m_currentExtent;
0304 }
0305 
0306 void KisTiledExtentManager::updateExtent()
0307 {
0308     qint32 minX, width, minY, height;
0309 
0310     {
0311         QReadLocker cl(&m_colsData.m_extentLock);
0312 
0313         if (m_colsData.isEmpty()) {
0314             minX = 0;
0315             width = 0;
0316         } else {
0317             minX = m_colsData.min() * KisTileData::WIDTH;
0318             width = (m_colsData.max() + 1) * KisTileData::WIDTH - minX;
0319         }
0320     }
0321 
0322     {
0323         QReadLocker rl(&m_rowsData.m_extentLock);
0324 
0325         if (m_rowsData.isEmpty()) {
0326             minY = 0;
0327             height = 0;
0328         } else {
0329             minY = m_rowsData.min() * KisTileData::HEIGHT;
0330             height = (m_rowsData.max() + 1) * KisTileData::HEIGHT - minY;
0331         }
0332     }
0333 
0334     QWriteLocker lock(&m_extentLock);
0335     m_currentExtent = QRect(minX, minY, width, height);
0336 }