Leapfrog< Map > Struct Template Reference

#include <leapfrog.h>

Classes
struct	Cell
struct	CellGroup
struct	Table
class	TableMigration

Public Types
typedef Map::Hash	Hash
enum	InsertResult { InsertResult_AlreadyFound , InsertResult_InsertedNew , InsertResult_Overflow }
typedef Map::KeyTraits	KeyTraits
typedef Map::Value	Value
typedef Map::ValueTraits	ValueTraits

Public Member Functions
	Q_STATIC_ASSERT (CellsInUseSample > 0 &&CellsInUseSample<=LinearSearchLimit)
	Q_STATIC_ASSERT (LinearSearchLimit > 0 &&LinearSearchLimit< 256)

Static Public Member Functions
static void	beginTableMigration (Map &map, Table *table, quint64 overflowIdx)
static void	beginTableMigrationToSize (Map &map, Table *table, quint64 nextTableSize)
static Cell *	find (Hash hash, Table *table)
static InsertResult	insertOrFind (Hash hash, Table *table, Cell *&cell, quint64 &overflowIdx)

Static Public Attributes
static const quint64	CellsInUseSample = LinearSearchLimit
static const quint64	InitialSize = 8
static const quint64	LinearSearchLimit = 128
static const quint64	TableMigrationUnitSize = 32

Detailed Description

template<class Map>
struct Leapfrog< Map >

Definition at line 21 of file leapfrog.h.

Member Typedef Documentation

Hash

template<class Map >

typedef Map::Hash Leapfrog< Map >::Hash

Definition at line 22 of file leapfrog.h.

KeyTraits

template<class Map >

typedef Map::KeyTraits Leapfrog< Map >::KeyTraits

Definition at line 24 of file leapfrog.h.

Value

template<class Map >

typedef Map::Value Leapfrog< Map >::Value

Definition at line 23 of file leapfrog.h.

ValueTraits

template<class Map >

typedef Map::ValueTraits Leapfrog< Map >::ValueTraits

Definition at line 25 of file leapfrog.h.

Member Enumeration Documentation

InsertResult

template<class Map >

enum Leapfrog::InsertResult

Enumerator
InsertResult_AlreadyFound
InsertResult_InsertedNew
InsertResult_Overflow

Definition at line 194 of file leapfrog.h.

{ InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };

Member Function Documentation

beginTableMigration()

template<class Map >

static void Leapfrog< Map >::beginTableMigration ( Map & map, Table * table, quint64 overflowIdx )

inlinestatic

Definition at line 332 of file leapfrog.h.

    {
        // Estimate number of cells in use based on a small sample.
        quint64 sizeMask = table->sizeMask;
        quint64 idx = overflowIdx - CellsInUseSample;
        quint64 inUseCells = 0;
        for (quint64 linearProbesRemaining = CellsInUseSample; linearProbesRemaining > 0; linearProbesRemaining--) {
            CellGroup* group = table->getCellGroups() + ((idx & sizeMask) >> 2);
            Cell* cell = group->cells + (idx & 3);
            Value value = cell->value.load(Relaxed);
            if (value == Value(ValueTraits::Redirect)) {
                // Another thread kicked off the jobCoordinator. The caller will participate upon return.
                return;
            }
            if (value != Value(ValueTraits::NullValue))
                inUseCells++;
            idx++;
        }
        float inUseRatio = float(inUseCells) / CellsInUseSample;
        float estimatedInUse = (sizeMask + 1) * inUseRatio;
        quint64 nextTableSize = qMax(quint64(InitialSize), roundUpPowerOf2(quint64(estimatedInUse * 2)));
        beginTableMigrationToSize(map, table, nextTableSize);
    }

References Leapfrog< Map >::beginTableMigrationToSize(), Leapfrog< Map >::CellGroup::cells, Leapfrog< Map >::CellsInUseSample, Leapfrog< Map >::Table::getCellGroups(), Leapfrog< Map >::InitialSize, Atomic< T >::load(), Relaxed, roundUpPowerOf2(), Leapfrog< Map >::Table::sizeMask, Leapfrog< Map >::Cell::value, and value().

beginTableMigrationToSize()

template<class Map >

static void Leapfrog< Map >::beginTableMigrationToSize ( Map & map, Table * table, quint64 nextTableSize )

inlinestatic

Definition at line 307 of file leapfrog.h.

    {
        // Create new migration by DCLI.
        SimpleJobCoordinator::Job* job = table->jobCoordinator.loadConsume();
        if (job) {
            // new migration already exists
        } else {
            QMutexLocker guard(&table->mutex);
            job = table->jobCoordinator.loadConsume(); // Non-atomic would be sufficient, but that's OK.
 
            if (job) {
                // new migration already exists (double-checked)
            } else {
                // Create new migration.
                TableMigration* migration = TableMigration::create(map, 1);
                migration->m_unitsRemaining.storeNonatomic(table->getNumMigrationUnits());
                migration->getSources()[0].table = table;
                migration->getSources()[0].sourceIndex.storeNonatomic(0);
                migration->m_destination = Table::create(nextTableSize);
                // Publish the new migration.
                table->jobCoordinator.storeRelease(migration);
            }
        }
    }

References Leapfrog< Map >::TableMigration::create(), Leapfrog< Map >::Table::create(), Leapfrog< Map >::Table::getNumMigrationUnits(), Leapfrog< Map >::TableMigration::getSources(), Leapfrog< Map >::Table::jobCoordinator, SimpleJobCoordinator::loadConsume(), Leapfrog< Map >::TableMigration::m_destination, Leapfrog< Map >::TableMigration::m_unitsRemaining, Leapfrog< Map >::Table::mutex, Leapfrog< Map >::TableMigration::Source::sourceIndex, Atomic< T >::storeNonatomic(), SimpleJobCoordinator::storeRelease(), and Leapfrog< Map >::TableMigration::Source::table.

find()

template<class Map >

static Cell * Leapfrog< Map >::find ( Hash hash, Table * table )

inlinestatic

Definition at line 157 of file leapfrog.h.

    {
#ifdef SANITY_CHECK
        KIS_ASSERT_RECOVER_NOOP(table);
        KIS_ASSERT_RECOVER_NOOP(hash != KeyTraits::NullHash);
#endif // SANITY_CHECK
        quint64 sizeMask = table->sizeMask;
        // Optimistically check hashed cell even though it might belong to another bucket
        quint64 idx = hash & sizeMask;
        CellGroup* group = table->getCellGroups() + (idx >> 2);
        Cell* cell = group->cells + (idx & 3);
        Hash probeHash = cell->hash.load(Relaxed);
 
        if (probeHash == hash) {
            return cell;
        } else if (probeHash == KeyTraits::NullHash) {
            return cell = NULL;
        }
        // Follow probe chain for our bucket
        quint8 delta = group->deltas[idx & 3].load(Relaxed);
        while (delta) {
            idx = (idx + delta) & sizeMask;
            group = table->getCellGroups() + (idx >> 2);
            cell = group->cells + (idx & 3);
            Hash probeHash = cell->hash.load(Relaxed);
            // Note: probeHash might actually be NULL due to memory reordering of a concurrent insert,
            // but we don't check for it. We just follow the probe chain.
            if (probeHash == hash) {
                return cell;
            }
            delta = group->deltas[(idx & 3) + 4].load(Relaxed);
        }
        // End of probe chain, not found
        return NULL;
    }

References Leapfrog< Map >::CellGroup::cells, Leapfrog< Map >::CellGroup::deltas, Leapfrog< Map >::Table::getCellGroups(), Leapfrog< Map >::Cell::hash, KIS_ASSERT_RECOVER_NOOP, Atomic< T >::load(), Relaxed, and Leapfrog< Map >::Table::sizeMask.

insertOrFind()

template<class Map >

static InsertResult Leapfrog< Map >::insertOrFind ( Hash hash, Table * table, Cell *& cell, quint64 & overflowIdx )

inlinestatic

Definition at line 195 of file leapfrog.h.

    {
#ifdef SANITY_CHECK
        KIS_ASSERT_RECOVER_NOOP(table);
        KIS_ASSERT_RECOVER_NOOP(hash != KeyTraits::NullHash);
#endif // SANITY_CHECK
        quint64 sizeMask = table->sizeMask;
        quint64 idx = quint64(hash);
 
        // Check hashed cell first, though it may not even belong to the bucket.
        CellGroup* group = table->getCellGroups() + ((idx & sizeMask) >> 2);
        cell = group->cells + (idx & 3);
        Hash probeHash = cell->hash.load(Relaxed);
 
        if (probeHash == KeyTraits::NullHash) {
            if (cell->hash.compareExchangeStrong(probeHash, hash, Relaxed)) {
                // There are no links to set. We're done.
                return InsertResult_InsertedNew;
            } else {
                // Fall through to check if it was the same hash...
            }
        }
 
        if (probeHash == hash) {
            return InsertResult_AlreadyFound;
        }
 
        // Follow the link chain for this bucket.
        quint64 maxIdx = idx + sizeMask;
        quint64 linkLevel = 0;
        Atomic<quint8>* prevLink;
        for (;;) {
        followLink:
            prevLink = group->deltas + ((idx & 3) + linkLevel);
            linkLevel = 4;
            quint8 probeDelta = prevLink->load(Relaxed);
 
            if (probeDelta) {
                idx += probeDelta;
                // Check the hash for this cell.
                group = table->getCellGroups() + ((idx & sizeMask) >> 2);
                cell = group->cells + (idx & 3);
                probeHash = cell->hash.load(Relaxed);
 
                if (probeHash == KeyTraits::NullHash) {
                    // Cell was linked, but hash is not visible yet.
                    // We could avoid this case (and guarantee it's visible) using acquire & release, but instead,
                    // just poll until it becomes visible.
                    do {
                        probeHash = cell->hash.load(Acquire);
                    } while (probeHash == KeyTraits::NullHash);
                }
 
#ifdef SANITY_CHECK
                KIS_ASSERT_RECOVER_NOOP(((probeHash ^ hash) & sizeMask) == 0); // Only hashes in same bucket can be linked
#endif // SANITY_CHECK
                if (probeHash == hash) {
                    return InsertResult_AlreadyFound;
                }
            } else {
                // Reached the end of the link chain for this bucket.
                // Switch to linear probing until we reserve a new cell or find a late-arriving cell in the same bucket.
                quint64 prevLinkIdx = idx;
#ifdef SANITY_CHECK
                KIS_ASSERT_RECOVER_NOOP(qint64(maxIdx - idx) >= 0); // Nobody would have linked an idx that's out of range.
#endif // SANITY_CHECK
                quint64 linearProbesRemaining = qMin(maxIdx - idx, quint64(LinearSearchLimit));
 
                while (linearProbesRemaining-- > 0) {
                    idx++;
                    group = table->getCellGroups() + ((idx & sizeMask) >> 2);
                    cell = group->cells + (idx & 3);
                    probeHash = cell->hash.load(Relaxed);
 
                    if (probeHash == KeyTraits::NullHash) {
                        // It's an empty cell. Try to reserve it.
                        if (cell->hash.compareExchangeStrong(probeHash, hash, Relaxed)) {
                            // Success. We've reserved the cell. Link it to previous cell in same bucket.
#ifdef SANITY_CHECK
                            KIS_ASSERT_RECOVER_NOOP(probeDelta == 0);
#endif // SANITY_CHECK
                            quint8 desiredDelta = idx - prevLinkIdx;
                            prevLink->store(desiredDelta, Relaxed);
                            return InsertResult_InsertedNew;
                        } else {
                            // Fall through to check if it's the same hash...
                        }
                    }
                    Hash x = (probeHash ^ hash);
                    // Check for same hash.
                    if (!x) {
                        return InsertResult_AlreadyFound;
                    }
                    // Check for same bucket.
                    if ((x & sizeMask) == 0) {
                        // Attempt to set the link on behalf of the late-arriving cell.
                        // This is usually redundant, but if we don't attempt to set the late-arriving cell's link here,
                        // there's no guarantee that our own link chain will be well-formed by the time this function returns.
                        // (Indeed, subsequent lookups sometimes failed during testing, for this exact reason.)
                        quint8 desiredDelta = idx - prevLinkIdx;
                        prevLink->store(desiredDelta, Relaxed);
                        goto followLink; // Try to follow link chain for the bucket again.
                    }
                    // Continue linear search...
                }
                // Table is too full to insert.
                overflowIdx = idx + 1;
                return InsertResult_Overflow;
            }
        }
    }

References Acquire, Leapfrog< Map >::CellGroup::cells, Atomic< T >::compareExchangeStrong(), Leapfrog< Map >::CellGroup::deltas, Leapfrog< Map >::Table::getCellGroups(), Leapfrog< Map >::Cell::hash, Leapfrog< Map >::InsertResult_AlreadyFound, Leapfrog< Map >::InsertResult_InsertedNew, Leapfrog< Map >::InsertResult_Overflow, KIS_ASSERT_RECOVER_NOOP, Leapfrog< Map >::LinearSearchLimit, Atomic< T >::load(), Relaxed, Leapfrog< Map >::Table::sizeMask, and Atomic< T >::store().

Q_STATIC_ASSERT() [1/2]

template<class Map >

Leapfrog< Map >::Q_STATIC_ASSERT	(	CellsInUseSample	,
		0 &&CellsInUseSample<=	LinearSearchLimit )

Q_STATIC_ASSERT() [2/2]

template<class Map >

Leapfrog< Map >::Q_STATIC_ASSERT

(

LinearSearchLimit

)

Member Data Documentation

CellsInUseSample

template<class Map >

const quint64 Leapfrog< Map >::CellsInUseSample = LinearSearchLimit

static

Definition at line 30 of file leapfrog.h.

InitialSize

template<class Map >

const quint64 Leapfrog< Map >::InitialSize = 8

static

Definition at line 27 of file leapfrog.h.

LinearSearchLimit

template<class Map >

const quint64 Leapfrog< Map >::LinearSearchLimit = 128

static

Definition at line 29 of file leapfrog.h.

TableMigrationUnitSize

template<class Map >

const quint64 Leapfrog< Map >::TableMigrationUnitSize = 32

static

Definition at line 28 of file leapfrog.h.

---

The documentation for this struct was generated from the following file:

• libs/image/3rdparty/lock_free_map/leapfrog.h