1 /*------------------------------------------------------------------------
2 Junction: Concurrent data structures in C++
3 Copyright (c) 2016 Jeff Preshing
5 Distributed under the Simplified BSD License.
6 Original location: https://github.com/preshing/junction
8 This software is distributed WITHOUT ANY WARRANTY; without even the
9 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 See the LICENSE file for more information.
11 ------------------------------------------------------------------------*/
13 #ifndef JUNCTION_SINGLEMAP_LEAPFROG_H
14 #define JUNCTION_SINGLEMAP_LEAPFROG_H
16 #include <junction/Core.h>
17 #include <junction/MapTraits.h>
18 #include <turf/Util.h>
19 #include <turf/Heap.h>
23 template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
24 class SingleMap_Leapfrog {
26 typedef typename KeyTraits::Hash Hash;
28 static const ureg InitialSize = 8;
29 static const ureg LinearSearchLimit = 128;
30 static const ureg CellsInUseSample = LinearSearchLimit;
31 TURF_STATIC_ASSERT(LinearSearchLimit > 0 && LinearSearchLimit < 256); // Must fit in CellGroup::links
32 TURF_STATIC_ASSERT(CellsInUseSample > 0 && CellsInUseSample <= LinearSearchLimit); // Limit sample to failed search chain
37 Cell(Hash hash, Value value) : hash(hash), value(value) {
46 CellGroup* m_cellGroups;
49 static CellGroup* createTable(ureg size = InitialSize) {
50 TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
51 CellGroup* cellGroups = (CellGroup*) TURF_HEAP.alloc(sizeof(CellGroup) * (size >> 2));
52 for (ureg i = 0; i < (size >> 2); i++) {
53 CellGroup* group = cellGroups + i;
55 for (j = 0; j < 8; j++)
57 for (j = 0; j < 4; j++)
58 new (group->cells + j) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
63 static void destroyTable(CellGroup* cellGroups, ureg size) {
64 TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
65 for (ureg i = 0; i < (size >> 2); i++) {
66 CellGroup* group = cellGroups + i;
67 for (ureg j = 0; j < 4; j++)
68 group->cells[i].~Cell();
70 TURF_HEAP.free(cellGroups);
73 enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
74 InsertResult insertOrFind(Hash hash, Cell*& cell, ureg& overflowIdx) {
75 TURF_ASSERT(hash != KeyTraits::NullHash);
76 ureg idx = ureg(hash);
77 // Check hashed cell first, though it may not even belong to the bucket.
78 CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
79 cell = group->cells + (idx & 3);
80 if (cell->hash == hash)
81 return InsertResult_AlreadyFound; // Key found in table.
82 else if (cell->hash == KeyTraits::NullHash) {
83 // Reserve the first cell.
85 return InsertResult_InsertedNew;
87 // Follow probe chain for our bucket.
88 ureg maxIdx = idx + m_sizeMask;
89 u8* prevLink = group->deltas + (idx & 3);
93 group = m_cellGroups + ((idx & m_sizeMask) >> 2);
94 cell = group->cells + (idx & 3);
95 if (cell->hash == hash)
96 return InsertResult_AlreadyFound; // Key found in table
97 prevLink = group->deltas + (idx & 3) + 4;
100 // Reached the end of the link chain for this bucket. Key does not exist in table.
101 // Switch to linear probing to find a free cell.
102 ureg prevLinkIdx = idx;
103 TURF_ASSERT(sreg(maxIdx - idx) >= 0); // Nobody would have linked an idx that's out of range.
104 ureg linearProbesRemaining = turf::util::min(maxIdx - idx, LinearSearchLimit);
105 while (linearProbesRemaining-- > 0) {
107 group = m_cellGroups + ((idx & m_sizeMask) >> 2);
108 cell = group->cells + (idx & 3);
109 if (cell->hash == KeyTraits::NullHash) {
110 // It's an empty cell. Reserve it.
112 // Link it to previous cell in the same bucket.
113 *prevLink = idx - prevLinkIdx;
114 return InsertResult_InsertedNew;
116 // In a single-threaded map, it's impossible for a matching hash to appear outside the probe chain.
117 TURF_ASSERT(cell->hash != hash);
118 // Continue linear search...
120 // Table is too full to insert.
121 overflowIdx = idx + 1;
122 return InsertResult_Overflow;
125 bool tryMigrateToNewTableWithSize(ureg desiredSize) {
126 CellGroup* srcCellGroups = m_cellGroups;
127 ureg srcSize = m_sizeMask + 1;
128 m_cellGroups = createTable(desiredSize);
129 m_sizeMask = desiredSize - 1;
130 for (ureg srcIdx = 0; srcIdx < srcSize; srcIdx++) {
131 CellGroup* srcGroup = srcCellGroups + (srcIdx >> 2);
132 Cell* srcCell = srcGroup->cells + (srcIdx & 3);
133 if (srcCell->value != Value(ValueTraits::NullValue)) {
136 InsertResult result = insertOrFind(srcCell->hash, dstCell, overflowIdx);
137 TURF_ASSERT(result != InsertResult_AlreadyFound);
138 if (result == InsertResult_Overflow) {
139 // Migration failed; destination table too small
140 destroyTable(m_cellGroups, m_sizeMask + 1);
141 m_cellGroups = srcCellGroups;
142 m_sizeMask = srcSize - 1;
145 dstCell->value = srcCell->value;
148 destroyTable(srcCellGroups, srcSize);
152 void migrateToNewTable(ureg overflowIdx) {
153 // Estimate number of cells in use based on a small sample.
154 ureg idx = overflowIdx - CellsInUseSample;
156 for (ureg linearProbesRemaining = CellsInUseSample; linearProbesRemaining > 0; linearProbesRemaining--) {
157 CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
158 Cell* cell = group->cells + (idx & 3);
159 if (cell->value != Value(ValueTraits::NullValue))
163 float inUseRatio = float(inUseCells) / CellsInUseSample;
164 float estimatedInUse = (m_sizeMask + 1) * inUseRatio;
165 #if JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS
166 // Periodically underestimate the number of cells in use.
167 // This exercises the code that handles overflow during migration.
168 static ureg counter = 1;
169 if ((++counter & 3) == 0) {
173 ureg nextTableSize = turf::util::max(InitialSize, turf::util::roundUpPowerOf2(ureg(estimatedInUse * 2)));
175 if (tryMigrateToNewTableWithSize(nextTableSize))
177 // Failed; try a larger table
183 SingleMap_Leapfrog(ureg initialSize = 8) : m_cellGroups(createTable(initialSize)), m_sizeMask(initialSize - 1) {
186 ~SingleMap_Leapfrog() {
187 destroyTable(m_cellGroups, m_sizeMask + 1);
192 friend class SingleMap_Leapfrog;
193 SingleMap_Leapfrog& m_map;
196 // Constructor: Find without insert
197 Mutator(SingleMap_Leapfrog& map, Key key, bool) : m_map(map) {
198 Hash hash = KeyTraits::hash(key);
199 TURF_ASSERT(hash != KeyTraits::NullHash);
200 // Optimistically check hashed cell even though it might belong to another bucket
201 ureg idx = ureg(hash);
202 CellGroup* group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
203 m_cell = group->cells + (idx & 3);
204 if (m_cell->hash == hash)
205 return; // Key found in table.
206 // Follow probe chain for our bucket.
207 u8 delta = group->deltas[idx & 3];
210 group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
211 m_cell = group->cells + (idx & 3);
212 if (m_cell->hash == hash)
213 return; // Key found in table
214 delta = group->deltas[(idx & 3) + 4];
216 // End of probe chain, not found
221 // Constructor: Find with insert
222 Mutator(SingleMap_Leapfrog& map, Key key) : m_map(map) {
223 Hash hash = KeyTraits::hash(key);
226 if (map.insertOrFind(hash, m_cell, overflowIdx) != InsertResult_Overflow)
228 // Insert overflow. Migrate and try again.
229 // On the first iteration of this loop, deleted cells will be purged.
230 // The second iteration (if any) will always double in size.
231 // On the third iteration (if any), the insert will succeed.
232 map.migrateToNewTable(overflowIdx);
237 bool isValid() const {
241 Value getValue() const {
243 return m_cell->value;
246 Value exchangeValue(Value desired) {
248 TURF_ASSERT(desired != NULL); // Use eraseValue()
249 Value oldValue = m_cell->value;
250 m_cell->value = desired;
256 // Since this map is single-threaded, we could conceivably shuffle existing cells around to safely fill
257 // gaps, much like SingleMap_Linear currently does.
258 // Instead, we'll just leave them as deleted entries and let them get purged on the next migration.
259 Value oldValue = m_cell->value;
260 m_cell->value = Value(ValueTraits::NullValue);
265 Mutator insertOrFindKey(const Key& key) {
266 return Mutator(*this, key);
269 Value get(const Key& key) {
270 Mutator iter(*this, key, false);
271 return iter.isValid() ? iter.getValue() : NULL;
274 Value set(const Key& key, Value desired) {
275 Mutator iter(*this, key);
276 return iter.exchangeValue(desired);
279 Value erase(const Key& key) {
280 Mutator iter(*this, key, false);
287 } // namespace junction
289 #endif // JUNCTION_SINGLEMAP_LEAPFROG_H