/junction

Find file
junction/junction/SingleMap_Leapfrog.h
67553e4 Feb 29, 2016
Raw Blame History
290 lines (259 sloc) 10.9 KB
/*------------------------------------------------------------------------
Junction: Concurrent data structures in C++
Copyright (c) 2016 Jeff Preshing
Distributed under the Simplified BSD License.
Original location: https://github.com/preshing/junction
This software is distributed WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the LICENSE file for more information.
------------------------------------------------------------------------*/
#ifndef JUNCTION_SINGLEMAP_LEAPFROG_H
#define JUNCTION_SINGLEMAP_LEAPFROG_H
#include <junction/Core.h>
#include <junction/MapTraits.h>
#include <turf/Util.h>
#include <turf/Heap.h>
namespace junction {
template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
class SingleMap_Leapfrog {
private:
typedef typename KeyTraits::Hash Hash;
static const ureg InitialSize = 8;
static const ureg LinearSearchLimit = 128;
static const ureg CellsInUseSample = LinearSearchLimit;
TURF_STATIC_ASSERT(LinearSearchLimit > 0 && LinearSearchLimit < 256); // Must fit in CellGroup::links
TURF_STATIC_ASSERT(CellsInUseSample > 0 && CellsInUseSample <= LinearSearchLimit); // Limit sample to failed search chain
struct Cell {
Hash hash;
Value value;
Cell(Hash hash, Value value) : hash(hash), value(value) {
}
};
struct CellGroup {
u8 deltas[8];
Cell cells[4];
};
CellGroup* m_cellGroups;
ureg m_sizeMask;
static CellGroup* createTable(ureg size = InitialSize) {
TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
CellGroup* cellGroups = (CellGroup*) TURF_HEAP.alloc(sizeof(CellGroup) * (size >> 2));
for (ureg i = 0; i < (size >> 2); i++) {
CellGroup* group = cellGroups + i;
ureg j;
for (j = 0; j < 8; j++)
group->deltas[j] = 0;
for (j = 0; j < 4; j++)
new (group->cells + j) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
}
return cellGroups;
}
static void destroyTable(CellGroup* cellGroups, ureg size) {
TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
for (ureg i = 0; i < (size >> 2); i++) {
CellGroup* group = cellGroups + i;
for (ureg j = 0; j < 4; j++)
group->cells[i].~Cell();
}
TURF_HEAP.free(cellGroups);
}
enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
InsertResult insertOrFind(Hash hash, Cell*& cell, ureg& overflowIdx) {
TURF_ASSERT(hash != KeyTraits::NullHash);
ureg idx = ureg(hash);
// Check hashed cell first, though it may not even belong to the bucket.
CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
cell = group->cells + (idx & 3);
if (cell->hash == hash)
return InsertResult_AlreadyFound; // Key found in table.
else if (cell->hash == KeyTraits::NullHash) {
// Reserve the first cell.
cell->hash = hash;
return InsertResult_InsertedNew;
}
// Follow probe chain for our bucket.
ureg maxIdx = idx + m_sizeMask;
u8* prevLink = group->deltas + (idx & 3);
u8 delta = *prevLink;
while (delta) {
idx += delta;
group = m_cellGroups + ((idx & m_sizeMask) >> 2);
cell = group->cells + (idx & 3);
if (cell->hash == hash)
return InsertResult_AlreadyFound; // Key found in table
prevLink = group->deltas + (idx & 3) + 4;
delta = *prevLink;
}
// Reached the end of the link chain for this bucket. Key does not exist in table.
// Switch to linear probing to find a free cell.
ureg prevLinkIdx = idx;
TURF_ASSERT(sreg(maxIdx - idx) >= 0); // Nobody would have linked an idx that's out of range.
ureg linearProbesRemaining = turf::util::min(maxIdx - idx, LinearSearchLimit);
while (linearProbesRemaining-- > 0) {
idx++;
group = m_cellGroups + ((idx & m_sizeMask) >> 2);
cell = group->cells + (idx & 3);
if (cell->hash == KeyTraits::NullHash) {
// It's an empty cell. Reserve it.
cell->hash = hash;
// Link it to previous cell in the same bucket.
*prevLink = idx - prevLinkIdx;
return InsertResult_InsertedNew;
}
// In a single-threaded map, it's impossible for a matching hash to appear outside the probe chain.
TURF_ASSERT(cell->hash != hash);
// Continue linear search...
}
// Table is too full to insert.
overflowIdx = idx + 1;
return InsertResult_Overflow;
}
bool tryMigrateToNewTableWithSize(ureg desiredSize) {
CellGroup* srcCellGroups = m_cellGroups;
ureg srcSize = m_sizeMask + 1;
m_cellGroups = createTable(desiredSize);
m_sizeMask = desiredSize - 1;
for (ureg srcIdx = 0; srcIdx < srcSize; srcIdx++) {
CellGroup* srcGroup = srcCellGroups + (srcIdx >> 2);
Cell* srcCell = srcGroup->cells + (srcIdx & 3);
if (srcCell->value != Value(ValueTraits::NullValue)) {
Cell* dstCell;
ureg overflowIdx;
InsertResult result = insertOrFind(srcCell->hash, dstCell, overflowIdx);
TURF_ASSERT(result != InsertResult_AlreadyFound);
if (result == InsertResult_Overflow) {
// Migration failed; destination table too small
destroyTable(m_cellGroups, m_sizeMask + 1);
m_cellGroups = srcCellGroups;
m_sizeMask = srcSize - 1;
return false;
}
dstCell->value = srcCell->value;
}
}
destroyTable(srcCellGroups, srcSize);
return true;
}
void migrateToNewTable(ureg overflowIdx) {
// Estimate number of cells in use based on a small sample.
ureg idx = overflowIdx - CellsInUseSample;
ureg inUseCells = 0;
for (ureg linearProbesRemaining = CellsInUseSample; linearProbesRemaining > 0; linearProbesRemaining--) {
CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
Cell* cell = group->cells + (idx & 3);
if (cell->value != Value(ValueTraits::NullValue))
inUseCells++;
idx++;
}
float inUseRatio = float(inUseCells) / CellsInUseSample;
float estimatedInUse = (m_sizeMask + 1) * inUseRatio;
#if JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS
// Periodically underestimate the number of cells in use.
// This exercises the code that handles overflow during migration.
static ureg counter = 1;
if ((++counter & 3) == 0) {
estimatedInUse /= 4;
}
#endif
ureg nextTableSize = turf::util::max(InitialSize, turf::util::roundUpPowerOf2(ureg(estimatedInUse * 2)));
for (;;) {
if (tryMigrateToNewTableWithSize(nextTableSize))
break; // Success
// Failed; try a larger table
nextTableSize *= 2;
}
}
public:
SingleMap_Leapfrog(ureg initialSize = 8) : m_cellGroups(createTable(initialSize)), m_sizeMask(initialSize - 1) {
}
~SingleMap_Leapfrog() {
destroyTable(m_cellGroups, m_sizeMask + 1);
}
class Mutator {
private:
friend class SingleMap_Leapfrog;
SingleMap_Leapfrog& m_map;
Cell* m_cell;
// Constructor: Find without insert
Mutator(SingleMap_Leapfrog& map, Key key, bool) : m_map(map) {
Hash hash = KeyTraits::hash(key);
TURF_ASSERT(hash != KeyTraits::NullHash);
// Optimistically check hashed cell even though it might belong to another bucket
ureg idx = ureg(hash);
CellGroup* group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
m_cell = group->cells + (idx & 3);
if (m_cell->hash == hash)
return; // Key found in table.
// Follow probe chain for our bucket.
u8 delta = group->deltas[idx & 3];
while (delta) {
idx += delta;
group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
m_cell = group->cells + (idx & 3);
if (m_cell->hash == hash)
return; // Key found in table
delta = group->deltas[(idx & 3) + 4];
}
// End of probe chain, not found
m_cell = NULL;
return;
}
// Constructor: Find with insert
Mutator(SingleMap_Leapfrog& map, Key key) : m_map(map) {
Hash hash = KeyTraits::hash(key);
for (;;) {
ureg overflowIdx;
if (map.insertOrFind(hash, m_cell, overflowIdx) != InsertResult_Overflow)
return;
// Insert overflow. Migrate and try again.
// On the first iteration of this loop, deleted cells will be purged.
// The second iteration (if any) will always double in size.
// On the third iteration (if any), the insert will succeed.
map.migrateToNewTable(overflowIdx);
}
}
public:
bool isValid() const {
return !!m_cell;
}
Value getValue() const {
TURF_ASSERT(m_cell);
return m_cell->value;
}
Value exchangeValue(Value desired) {
TURF_ASSERT(m_cell);
TURF_ASSERT(desired != NULL); // Use eraseValue()
Value oldValue = m_cell->value;
m_cell->value = desired;
return oldValue;
}
Value erase() {
TURF_ASSERT(m_cell);
// Since this map is single-threaded, we could conceivably shuffle existing cells around to safely fill
// gaps, much like SingleMap_Linear currently does.
// Instead, we'll just leave them as deleted entries and let them get purged on the next migration.
Value oldValue = m_cell->value;
m_cell->value = Value(ValueTraits::NullValue);
return oldValue;
}
};
Mutator insertOrFindKey(const Key& key) {
return Mutator(*this, key);
}
Value get(const Key& key) {
Mutator iter(*this, key, false);
return iter.isValid() ? iter.getValue() : NULL;
}
Value set(const Key& key, Value desired) {
Mutator iter(*this, key);
return iter.exchangeValue(desired);
}
Value erase(const Key& key) {
Mutator iter(*this, key, false);
if (iter.isValid())
return iter.erase();
return NULL;
}
};
} // namespace junction
#endif // JUNCTION_SINGLEMAP_LEAPFROG_H