KisTileHashTableTraits< T > Class Template Reference

#include <kis_tile_hash_table.h>

Public Types
typedef T	TileType
typedef KisSharedPtr< T >	TileTypeSP
typedef KisWeakSharedPtr< T >	TileTypeWSP

Public Member Functions
void	addTile (TileTypeSP tile)
void	clear ()
void	debugMaxListLength (qint32 &min, qint32 &max)
void	debugPrintInfo ()
KisTileData *	defaultTileData () const
bool	deleteTile (qint32 col, qint32 row)
bool	deleteTile (TileTypeSP tile)
TileTypeSP	getExistingTile (qint32 col, qint32 row)
TileTypeSP	getReadOnlyTileLazy (qint32 col, qint32 row, bool &existingTile)
TileTypeSP	getTileLazy (qint32 col, qint32 row, bool &newTile)
bool	isEmpty ()
	KisTileHashTableTraits (const KisTileHashTableTraits< T > &ht, KisMementoManager *mm)
	KisTileHashTableTraits (KisMementoManager *mm)
qint32	numTiles ()
KisTileData *	refAndFetchDefaultTileData () const
void	setDefaultTileData (KisTileData *defaultTileData)
bool	tileExists (qint32 col, qint32 row)
	~KisTileHashTableTraits ()

Private Member Functions
qint32	debugChainLen (qint32 idx)
void	debugListLengthDistribution ()
KisTileData *	defaultTileDataImp () const
TileTypeSP	getTile (qint32 col, qint32 row, qint32 idx)
TileTypeSP	getTileMinefieldWalk (qint32 col, qint32 row, qint32 idx)
void	linkTile (TileTypeSP tile, qint32 idx)
void	sanityChecksumCheck ()
void	setDefaultTileDataImp (KisTileData *defaultTileData)
bool	unlinkTile (qint32 col, qint32 row, qint32 idx)

Static Private Member Functions
static quint32	calculateHash (qint32 col, qint32 row)

Private Attributes
KisTileData *	m_defaultTileData
TileTypeSP *	m_hashTable
QReadWriteLock	m_lock
KisMementoManager *	m_mementoManager
qint32	m_numTiles

Static Private Attributes
static const qint32	TABLE_SIZE = 1024

Friends
template<class U , class LockerType >
class	KisTileHashTableIteratorTraits

Detailed Description

template<class T>
class KisTileHashTableTraits< T >

This is a template for a hash table that stores tiles (or some other objects resembling tiles). Actually, this object should only have col()/row() methods and be able to answer setNext()/next() requests to be stored here. It is used in KisTiledDataManager and KisMementoManager.

Definition at line 24 of file kis_tile_hash_table.h.

Member Typedef Documentation

TileType

template<class T >

typedef T KisTileHashTableTraits< T >::TileType

Definition at line 27 of file kis_tile_hash_table.h.

TileTypeSP

template<class T >

typedef KisSharedPtr<T> KisTileHashTableTraits< T >::TileTypeSP

Definition at line 28 of file kis_tile_hash_table.h.

TileTypeWSP

template<class T >

typedef KisWeakSharedPtr<T> KisTileHashTableTraits< T >::TileTypeWSP

Definition at line 29 of file kis_tile_hash_table.h.

Constructor & Destructor Documentation

KisTileHashTableTraits() [1/2]

template<class T >

KisTileHashTableTraits< T >::KisTileHashTableTraits

(

KisMementoManager *

mm

)

Definition at line 16 of file kis_tile_hash_table_p.h.

        : m_lock(QReadWriteLock::NonRecursive)
{
    m_hashTable = new TileTypeSP [TABLE_SIZE];
    Q_CHECK_PTR(m_hashTable);
 
    m_numTiles = 0;
    m_defaultTileData = 0;
    m_mementoManager = mm;
}

References KisTileHashTableTraits< T >::m_defaultTileData, KisTileHashTableTraits< T >::m_hashTable, KisTileHashTableTraits< T >::m_mementoManager, KisTileHashTableTraits< T >::m_numTiles, and KisTileHashTableTraits< T >::TABLE_SIZE.

KisTileHashTableTraits() [2/2]

template<class T >

KisTileHashTableTraits< T >::KisTileHashTableTraits	(	const KisTileHashTableTraits< T > &	ht,
		KisMementoManager *	mm )

Definition at line 28 of file kis_tile_hash_table_p.h.

        : m_lock(QReadWriteLock::NonRecursive)
{
    QReadLocker locker(&ht.m_lock);
 
    m_mementoManager = mm;
    m_defaultTileData = 0;
    setDefaultTileDataImp(ht.m_defaultTileData);
 
    m_hashTable = new TileTypeSP [TABLE_SIZE];
    Q_CHECK_PTR(m_hashTable);
 
 
    TileTypeSP foreignTile;
    TileTypeSP nativeTile;
    TileTypeSP nativeTileHead;
    for (qint32 i = 0; i < TABLE_SIZE; i++) {
        nativeTileHead = 0;
 
        foreignTile = ht.m_hashTable[i];
        while (foreignTile) {
            nativeTile = TileTypeSP(new TileType(*foreignTile, m_mementoManager));
            nativeTile->setNext(nativeTileHead);
            nativeTileHead = nativeTile;
 
            foreignTile = foreignTile->next();
        }
 
        m_hashTable[i] = nativeTileHead;
    }
    m_numTiles = ht.m_numTiles;
}

~KisTileHashTableTraits()

template<class T >

KisTileHashTableTraits< T >::~KisTileHashTableTraits

(

)

Definition at line 63 of file kis_tile_hash_table_p.h.

{
    clear();
    delete[] m_hashTable;
    setDefaultTileDataImp(0);
}

Member Function Documentation

addTile()

template<class T >

void KisTileHashTableTraits< T >::addTile

(

TileTypeSP

tile

)

Definition at line 267 of file kis_tile_hash_table_p.h.

{
    const qint32 idx = calculateHash(tile->col(), tile->row());
 
    QWriteLocker locker(&m_lock);
    linkTile(tile, idx);
}

calculateHash()

template<class T >

quint32 KisTileHashTableTraits< T >::calculateHash ( qint32 col, qint32 row )

inlinestaticprivate

Definition at line 71 of file kis_tile_hash_table_p.h.

{
    return ((row << 5) + (col & 0x1F)) & 0x3FF;
}

clear()

template<class T >

void KisTileHashTableTraits< T >::clear

(

)

About disconnection of tiles see a comment in unlinkTile()

Definition at line 291 of file kis_tile_hash_table_p.h.

{
    QWriteLocker locker(&m_lock);
    TileTypeSP tile = TileTypeSP();
    qint32 i;
 
    for (i = 0; i < TABLE_SIZE; i++) {
        tile = m_hashTable[i];
 
        while (tile) {
            TileTypeSP tmp = tile;
            tile = tile->next();
 
            tmp->setNext(TileTypeSP());
            tmp->notifyDetachedFromDataManager();
            tmp = 0;
 
            m_numTiles--;
        }
 
        m_hashTable[i] = 0;
    }
 
    Q_ASSERT(!m_numTiles);
}

debugChainLen()

template<class T >

qint32 KisTileHashTableTraits< T >::debugChainLen ( qint32 idx )

inlineprivate

Definition at line 361 of file kis_tile_hash_table_p.h.

{
    qint32 len = 0;
    for (TileTypeSP it = m_hashTable[idx]; it; it = it->next(), len++) ;
    return len;
}

debugListLengthDistribution()

template<class T >

void KisTileHashTableTraits< T >::debugListLengthDistribution ( )

private

Definition at line 389 of file kis_tile_hash_table_p.h.

{
    qint32 min, max;
    qint32 arraySize;
    qint32 tmp;
 
    debugMaxListLength(min, max);
    arraySize = max - min + 1;
 
    qint32 *array = new qint32[arraySize];
    memset(array, 0, sizeof(qint32)*arraySize);
 
    for (qint32 i = 0; i < TABLE_SIZE; i++) {
        tmp = debugChainLen(i);
        array[tmp-min]++;
    }
 
    qInfo() << QString("   minChain: %1\n").arg(min);
    qInfo() << QString("   maxChain: %1\n").arg(max);
 
    qInfo() << "   Chain size distribution:";
    for (qint32 i = 0; i < arraySize; i++)
        qInfo() << QString("      %1: %2").arg(i + min).arg(array[i]);
 
    delete[] array;
}

debugMaxListLength()

template<class T >

void KisTileHashTableTraits< T >::debugMaxListLength	(	qint32 &	min,
		qint32 &	max )

Definition at line 369 of file kis_tile_hash_table_p.h.

{
    TileTypeSP tile;
    qint32 maxLen = 0;
    qint32 minLen = m_numTiles;
    qint32 tmp = 0;
 
    for (qint32 i = 0; i < TABLE_SIZE; i++) {
        tmp = debugChainLen(i);
        if (tmp > maxLen)
            maxLen = tmp;
        if (tmp < minLen)
            minLen = tmp;
    }
 
    min = minLen;
    max = maxLen;
}

debugPrintInfo()

template<class T >

void KisTileHashTableTraits< T >::debugPrintInfo

(

)

Definition at line 348 of file kis_tile_hash_table_p.h.

{
    if (!m_numTiles) return;
 
    qInfo() << "==========================\n"
             << "TileHashTable:"
             << "\n   def. data:\t\t" << m_defaultTileData
             << "\n   numTiles:\t\t" << m_numTiles;
    debugListLengthDistribution();
    qInfo() << "==========================\n";
}

defaultTileData()

template<class T >

KisTileData * KisTileHashTableTraits< T >::defaultTileData

(

)

const

Definition at line 329 of file kis_tile_hash_table_p.h.

{
    QWriteLocker locker(&m_lock);
    return defaultTileDataImp();
}

defaultTileDataImp()

template<class T >

KisTileData * KisTileHashTableTraits< T >::defaultTileDataImp ( ) const

inlineprivate

Definition at line 192 of file kis_tile_hash_table_p.h.

{
    return m_defaultTileData;
}

deleteTile() [1/2]

template<class T >

bool KisTileHashTableTraits< T >::deleteTile	(	qint32	col,
		qint32	row )

Definition at line 276 of file kis_tile_hash_table_p.h.

{
    const qint32 idx = calculateHash(col, row);
 
    QWriteLocker locker(&m_lock);
    return unlinkTile(col, row, idx);
}

deleteTile() [2/2]

template<class T >

bool KisTileHashTableTraits< T >::deleteTile

(

TileTypeSP

tile

)

Definition at line 285 of file kis_tile_hash_table_p.h.

{
    return deleteTile(tile->col(), tile->row());
}

getExistingTile()

template<class T >

KisTileHashTableTraits< T >::TileTypeSP KisTileHashTableTraits< T >::getExistingTile	(	qint32	col,
		qint32	row )

Returns a tile in position (col,row). If no tile exists, returns null.

Parameters

col	column of the tile
row	row of the tile

Definition at line 206 of file kis_tile_hash_table_p.h.

{
    const qint32 idx = calculateHash(col, row);
 
    // NOTE: minefield walk is disabled due to supposed unsafety,
    //       see bug 391270
 
    QReadLocker locker(&m_lock);
    return getTile(col, row, idx);
}

getReadOnlyTileLazy()

template<class T >

KisTileHashTableTraits< T >::TileTypeSP KisTileHashTableTraits< T >::getReadOnlyTileLazy	(	qint32	col,
		qint32	row,
		bool &	existingTile )

Returns a tile in position (col,row). If no tile exists, creates nothing, but returns shared default tile object of the table. Be careful, this object has column and row parameters set to (qint32_MIN, qint32_MIN).

Parameters

col	column of the tile
row	row of the tile
existingTile	returns true if the tile actually exists in the table and it is not a lazily created default wrapper tile

Definition at line 247 of file kis_tile_hash_table_p.h.

{
    const qint32 idx = calculateHash(col, row);
 
    // NOTE: minefield walk is disabled due to supposed unsafety,
    //       see bug 391270
 
    QReadLocker locker(&m_lock);
 
    TileTypeSP tile = getTile(col, row, idx);
    existingTile = tile;
 
    if (!existingTile) {
        tile = new TileType(col, row, m_defaultTileData, 0);
    }
 
    return tile;
}

getTile()

template<class T >

KisTileHashTableTraits< T >::TileTypeSP KisTileHashTableTraits< T >::getTile ( qint32 col, qint32 row, qint32 idx )

private

Definition at line 113 of file kis_tile_hash_table_p.h.

{
    TileTypeSP tile = m_hashTable[idx];
 
    for (; tile; tile = tile->next()) {
        if (tile->col() == col &&
                tile->row() == row) {
 
            return tile;
        }
    }
 
    return TileTypeSP();
}

getTileLazy()

template<class T >

KisTileHashTableTraits< T >::TileTypeSP KisTileHashTableTraits< T >::getTileLazy	(	qint32	col,
		qint32	row,
		bool &	newTile )

Returns a tile in position (col,row). If no tile exists, creates a new one, attaches it to the list and returns.

Parameters

col	column of the tile
row	row of the tile
newTile	out-parameter, returns true if a new tile was created

Definition at line 219 of file kis_tile_hash_table_p.h.

{
    const qint32 idx = calculateHash(col, row);
 
    // NOTE: minefield walk is disabled due to supposed unsafety,
    //       see bug 391270
 
    newTile = false;
    TileTypeSP tile;
 
    {
        QReadLocker locker(&m_lock);
        tile = getTile(col, row, idx);
    }
 
    if (!tile) {
        QWriteLocker locker(&m_lock);
        tile = new TileType(col, row, m_defaultTileData, m_mementoManager);
        linkTile(tile, idx);
        newTile = true;
    }
 
    return tile;
}

References newTile().

getTileMinefieldWalk()

template<class T >

KisTileHashTableTraits< T >::TileTypeSP KisTileHashTableTraits< T >::getTileMinefieldWalk ( qint32 col, qint32 row, qint32 idx )

private

This is a special method for dangerous and unsafe access to the tiles table. Thanks to the fact that our shared pointers are thread safe, we can iterate through the linked list without having any locks help. In the worst case, we will miss the needed tile. In that case, the higher level code will do the proper locking and do the second try with all the needed locks held.

Definition at line 78 of file kis_tile_hash_table_p.h.

{
    // WARNING: this function is here only for educational purposes! Don't
    //          use it! It causes race condition in a shared pointer copy-ctor
    //          when accessing m_hashTable!
 
    TileTypeSP headTile = m_hashTable[idx];
    TileTypeSP tile = headTile;
 
    for (; tile; tile = tile->next()) {
        if (tile->col() == col &&
            tile->row() == row) {
 
            if (m_hashTable[idx] != headTile) {
                tile.clear();
            }
 
            break;
        }
    }
 
    return tile;
}

isEmpty()

template<class T >

bool KisTileHashTableTraits< T >::isEmpty ( )

inline

Definition at line 38 of file kis_tile_hash_table.h.

                   {
        return !m_numTiles;
    }

References KisTileHashTableTraits< T >::m_numTiles.

linkTile()

template<class T >

void KisTileHashTableTraits< T >::linkTile ( TileTypeSP tile, qint32 idx )

private

Definition at line 129 of file kis_tile_hash_table_p.h.

{
    TileTypeSP firstTile = m_hashTable[idx];
 
#ifdef SHARED_TILES_SANITY_CHECK
    Q_ASSERT_X(!tile->next(), "KisTileHashTableTraits<T>::linkTile",
               "A tile can't be shared by several hash tables, sorry.");
#endif
 
    tile->setNext(firstTile);
    m_hashTable[idx] = tile;
    m_numTiles++;
}

numTiles()

template<class T >

qint32 KisTileHashTableTraits< T >::numTiles ( )

inline

Definition at line 83 of file kis_tile_hash_table.h.

                      {
        return m_numTiles;
    }

References KisTileHashTableTraits< T >::m_numTiles.

refAndFetchDefaultTileData()

template<class T >

KisTileData * KisTileHashTableTraits< T >::refAndFetchDefaultTileData ( ) const

inline

Definition at line 336 of file kis_tile_hash_table_p.h.

{
    QWriteLocker locker(&m_lock);
    KisTileData *result = defaultTileDataImp();
    result->ref();
    return result;
}

References KisTileData::ref().

sanityChecksumCheck()

template<class T >

void KisTileHashTableTraits< T >::sanityChecksumCheck ( )

private

We assume that the lock should have already been taken by the code that was going to change the table

Definition at line 417 of file kis_tile_hash_table_p.h.

{
    Q_ASSERT(!m_lock.tryLockForWrite());
 
    TileTypeSP tile = 0;
    qint32 exactNumTiles = 0;
 
    for (qint32 i = 0; i < TABLE_SIZE; i++) {
        tile = m_hashTable[i];
        while (tile) {
            exactNumTiles++;
            tile = tile->next();
        }
    }
 
    if (exactNumTiles != m_numTiles) {
        dbgKrita << "Sanity check failed!";
        dbgKrita << ppVar(exactNumTiles);
        dbgKrita << ppVar(m_numTiles);
        dbgKrita << "Wrong tiles checksum!";
        Q_ASSERT(0); // not fatalKrita for a backtrace support
    }
}

References dbgKrita, and ppVar.

setDefaultTileData()

template<class T >

void KisTileHashTableTraits< T >::setDefaultTileData

(

KisTileData *

defaultTileData

)

Definition at line 322 of file kis_tile_hash_table_p.h.

{
    QWriteLocker locker(&m_lock);
    setDefaultTileDataImp(defaultTileData);
}

setDefaultTileDataImp()

template<class T >

void KisTileHashTableTraits< T >::setDefaultTileDataImp ( KisTileData * defaultTileData )

inlineprivate

Definition at line 178 of file kis_tile_hash_table_p.h.

{
    if (m_defaultTileData) {
        m_defaultTileData->release();
        m_defaultTileData = 0;
    }
 
    if (defaultTileData) {
        defaultTileData->acquire();
        m_defaultTileData = defaultTileData;
    }
}

References KisTileData::acquire().

tileExists()

template<class T >

bool KisTileHashTableTraits< T >::tileExists	(	qint32	col,
		qint32	row )

Definition at line 199 of file kis_tile_hash_table_p.h.

{
    return this->getExistingTile(col, row);
}

unlinkTile()

template<class T >

bool KisTileHashTableTraits< T >::unlinkTile ( qint32 col, qint32 row, qint32 idx )

private

The shared pointer may still be accessed by someone, so we need to disconnects the tile from memento manager explicitly

Definition at line 144 of file kis_tile_hash_table_p.h.

{
    TileTypeSP tile = m_hashTable[idx];
    TileTypeSP prevTile;
 
    for (; tile; tile = tile->next()) {
        if (tile->col() == col &&
                tile->row() == row) {
 
            if (prevTile)
                prevTile->setNext(tile->next());
            else
                /* optimize here*/
                m_hashTable[idx] = tile->next();
 
            tile->setNext(TileTypeSP());
            tile->notifyDetachedFromDataManager();
            tile.clear();
 
            m_numTiles--;
            return true;
        }
        prevTile = tile;
    }
 
    return false;
}

References KisSharedPtr< T >::clear().

Friends And Related Symbol Documentation

KisTileHashTableIteratorTraits

template<class T >

template<class U , class LockerType >

friend class KisTileHashTableIteratorTraits

friend

Definition at line 106 of file kis_tile_hash_table.h.

Member Data Documentation

m_defaultTileData

template<class T >

KisTileData* KisTileHashTableTraits< T >::m_defaultTileData

private

Definition at line 112 of file kis_tile_hash_table.h.

m_hashTable

template<class T >

TileTypeSP* KisTileHashTableTraits< T >::m_hashTable

private

Definition at line 109 of file kis_tile_hash_table.h.

m_lock

template<class T >

QReadWriteLock KisTileHashTableTraits< T >::m_lock

mutableprivate

Definition at line 115 of file kis_tile_hash_table.h.

m_mementoManager

template<class T >

KisMementoManager* KisTileHashTableTraits< T >::m_mementoManager

private

Definition at line 113 of file kis_tile_hash_table.h.

m_numTiles

template<class T >

qint32 KisTileHashTableTraits< T >::m_numTiles

private

Definition at line 110 of file kis_tile_hash_table.h.

TABLE_SIZE

template<class T >

const qint32 KisTileHashTableTraits< T >::TABLE_SIZE = 1024

staticprivate

Definition at line 108 of file kis_tile_hash_table.h.

---

The documentation for this class was generated from the following files:

• libs/image/tiles3/kis_tile_hash_table.h
• libs/image/tiles3/kis_tile_hash_table_p.h