Don't copy CMake scripts to install folder
[junction.git] / samples / MapCorrectnessTests / TestChurn.h
1 /*------------------------------------------------------------------------
2   Junction: Concurrent data structures in C++
3   Copyright (c) 2016 Jeff Preshing
4
5   Distributed under the Simplified BSD License.
6   Original location: https://github.com/preshing/junction
7
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 ------------------------------------------------------------------------*/
12
13 #ifndef SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
14 #define SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
15
16 #include <junction/Core.h>
17 #include "TestEnvironment.h"
18 #include <turf/extra/Random.h>
19 #include <vector>
20 #include <turf/Util.h>
21
22 class TestChurn {
23 public:
24     static const ureg KeysInBlock = 32;
25     static const ureg BlocksToMaintain = 256;
26     static const ureg BlocksToLookup = 4;
27     static const ureg StepsPerIteration = 100;
28
29     enum Phase {
30         Phase_Insert,
31         Phase_Lookup,
32         Phase_Erase,
33         Phase_LookupDeleted,
34     };
35
36     struct ThreadInfo {
37         turf::extra::Random random;
38         u32 rangeLo;
39         u32 rangeHi;
40         u32 insertIndex;
41         u32 eraseIndex;
42         u32 lookupIndex;
43         Phase phase;
44         ureg keysToCheck;
45     };
46
47     TestEnvironment& m_env;
48     MapAdapter::Map m_map;
49     u32 m_rangePerThread;
50     u32 m_relativePrime;
51     std::vector<ThreadInfo> m_threads;
52
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);
58         u32 startIndex = 2;
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;
69         }
70         m_relativePrime = m_threads[0].random.next32() * 2 + 1;
71         m_env.dispatcher.kick(&TestChurn::warmUp, *this);
72     }
73
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);
81             if (key >= 2) {
82                 m_map.insert(key, (void*) uptr(key));
83             }
84             if (++thread.insertIndex >= thread.rangeHi)
85                 thread.insertIndex = thread.rangeLo;
86         }
87     }
88
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) {
94             case Phase_Insert: {
95                 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
96                     u32 key = thread.insertIndex * m_relativePrime;
97                     key = key ^ (key >> 16);
98                     if (key >= 2) {
99                         m_map.insert(key, (void*) uptr(key));
100                     }
101                     if (++thread.insertIndex >= thread.rangeHi)
102                         thread.insertIndex = thread.rangeLo;
103                     TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
104                 }
105                 thread.phase = Phase_Lookup;
106                 thread.lookupIndex = thread.insertIndex;
107                 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
108                 break;
109             }
110             case Phase_Lookup: {
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);
119                     if (key >= 2) {
120                         if (m_map.get(key) != (void*) uptr(key))
121                             TURF_DEBUG_BREAK();
122                     }
123                 }
124                 if (thread.keysToCheck == 0) {
125                     thread.phase = Phase_Erase;
126                 }
127                 break;
128             }
129             case Phase_Erase: {
130                 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
131                     u32 key = thread.eraseIndex * m_relativePrime;
132                     key = key ^ (key >> 16);
133                     if (key >= 2) {
134                         m_map.erase(key);
135                     }
136                     if (++thread.eraseIndex >= thread.rangeHi)
137                         thread.eraseIndex = thread.rangeLo;
138                     TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
139                 }
140                 thread.phase = Phase_LookupDeleted;
141                 thread.lookupIndex = thread.eraseIndex;
142                 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
143                 break;
144             }
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);
154                     if (key >= 2) {
155                         if (m_map.get(key))
156                             TURF_DEBUG_BREAK();
157                     }
158                 }
159                 if (thread.keysToCheck == 0) {
160                     thread.phase = Phase_Insert;
161                 }
162                 break;
163             }
164             }
165         }
166         m_env.threads[threadIndex].update();
167     }
168
169     void run() {
170         m_env.dispatcher.kick(&TestChurn::doChurn, *this);
171     }
172 };
173
174 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H