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 SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
14 #define SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
16 #include <junction/Core.h>
17 #include "TestEnvironment.h"
18 #include <turf/extra/Random.h>
20 #include <turf/Util.h>
24 static const ureg KeysInBlock = 32;
25 static const ureg BlocksToMaintain = 256;
26 static const ureg BlocksToLookup = 4;
27 static const ureg StepsPerIteration = 100;
37 turf::extra::Random random;
47 TestEnvironment& m_env;
48 MapAdapter::Map m_map;
51 std::vector<ThreadInfo> m_threads;
53 TestChurn(TestEnvironment& env)
54 : m_env(env), m_map(MapAdapter::getInitialCapacity(KeysInBlock * BlocksToMaintain * env.numThreads)) {
55 m_threads.resize(m_env.numThreads);
56 m_rangePerThread = u32(-3) / m_env.numThreads; // from 2 to 0xffffffff inclusive
57 TURF_ASSERT(KeysInBlock * (BlocksToMaintain + BlocksToLookup + 1) < m_rangePerThread);
59 for (ureg i = 0; i < m_env.numThreads; i++) {
60 ThreadInfo& thread = m_threads[i];
61 thread.rangeLo = startIndex;
62 startIndex += m_rangePerThread;
63 thread.rangeHi = startIndex;
64 thread.insertIndex = thread.rangeLo + thread.random.next32() % m_rangePerThread;
65 thread.eraseIndex = thread.insertIndex;
66 thread.lookupIndex = 0;
67 thread.phase = Phase_Insert;
68 thread.keysToCheck = 0;
70 m_relativePrime = m_threads[0].random.next32() * 2 + 1;
71 m_env.dispatcher.kick(&TestChurn::warmUp, *this);
74 void warmUp(ureg threadIndex) {
75 ThreadInfo& thread = m_threads[threadIndex];
76 TURF_ASSERT(thread.phase == Phase_Insert);
77 TURF_ASSERT(thread.insertIndex == thread.eraseIndex);
78 for (sreg keysRemaining = KeysInBlock * BlocksToMaintain; keysRemaining > 0; keysRemaining--) {
79 u32 key = thread.insertIndex * m_relativePrime;
80 key = key ^ (key >> 16);
82 m_map.set(key, (void*) uptr(key));
84 if (++thread.insertIndex >= thread.rangeHi)
85 thread.insertIndex = thread.rangeLo;
89 void doChurn(ureg threadIndex) {
90 ThreadInfo& thread = m_threads[threadIndex];
91 TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
92 for (sreg stepsRemaining = StepsPerIteration; stepsRemaining > 0; stepsRemaining--) {
93 switch (thread.phase) {
95 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
96 u32 key = thread.insertIndex * m_relativePrime;
97 key = key ^ (key >> 16);
99 m_map.set(key, (void*) uptr(key));
101 if (++thread.insertIndex >= thread.rangeHi)
102 thread.insertIndex = thread.rangeLo;
103 TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
105 thread.phase = Phase_Lookup;
106 thread.lookupIndex = thread.insertIndex;
107 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
111 sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
112 thread.keysToCheck -= keysRemaining;
113 for (; keysRemaining > 0; keysRemaining--) {
114 if (thread.lookupIndex == thread.rangeLo)
115 thread.lookupIndex = thread.rangeHi;
116 thread.lookupIndex--;
117 u32 key = thread.lookupIndex * m_relativePrime;
118 key = key ^ (key >> 16);
120 if (m_map.get(key) != (void*) uptr(key))
124 if (thread.keysToCheck == 0) {
125 thread.phase = Phase_Erase;
130 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
131 u32 key = thread.eraseIndex * m_relativePrime;
132 key = key ^ (key >> 16);
136 if (++thread.eraseIndex >= thread.rangeHi)
137 thread.eraseIndex = thread.rangeLo;
138 TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
140 thread.phase = Phase_LookupDeleted;
141 thread.lookupIndex = thread.eraseIndex;
142 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
145 case Phase_LookupDeleted: {
146 sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
147 thread.keysToCheck -= keysRemaining;
148 for (; keysRemaining > 0; keysRemaining--) {
149 if (thread.lookupIndex == thread.rangeLo)
150 thread.lookupIndex = thread.rangeHi;
151 thread.lookupIndex--;
152 u32 key = thread.lookupIndex * m_relativePrime;
153 key = key ^ (key >> 16);
159 if (thread.keysToCheck == 0) {
160 thread.phase = Phase_Insert;
166 m_env.threads[threadIndex].update();
170 m_env.dispatcher.kick(&TestChurn::doChurn, *this);
174 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H