df21e29fa2be51e9f1cb3dfdbb4977f2fd6cdfe1
[junction.git] / samples / MapCorrectnessTests / TestInsertDifferentKeys.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_TESTINSERTDIFFERENTKEYS_H
14 #define SAMPLES_MAPCORRECTNESSTESTS_TESTINSERTDIFFERENTKEYS_H
15
16 #include <junction/Core.h>
17 #include "TestEnvironment.h"
18 #include <turf/extra/Random.h>
19
20 class TestInsertDifferentKeys {
21 public:
22     static const ureg KeysToInsert = 2048;
23     TestEnvironment& m_env;
24     MapAdapter::Map *m_map;
25     turf::extra::Random m_random;
26     u32 m_startIndex;
27     u32 m_relativePrime;
28
29     TestInsertDifferentKeys(TestEnvironment& env) : m_env(env), m_map(NULL), m_startIndex(0), m_relativePrime(0) {
30     }
31
32     void insertKeys(ureg threadIndex) {
33         u32 index = m_startIndex + threadIndex * (KeysToInsert + 2);
34         sreg keysRemaining = KeysToInsert;
35         while (keysRemaining > 0) {
36             u32 key = index * m_relativePrime;
37             key = key ^ (key >> 16);
38             if (key >= 2) {         // Don't insert 0 or 1
39                 m_map->insert(key, (void*) uptr(key));
40                 keysRemaining--;
41             }
42             index++;
43         }
44         m_env.threads[threadIndex].update();
45     }
46
47     void eraseKeys(ureg threadIndex) {
48         u32 index = m_startIndex + threadIndex * (KeysToInsert + 2);
49         sreg keysRemaining = KeysToInsert;
50         while (keysRemaining > 0) {
51             u32 key = index * m_relativePrime;
52             key = key ^ (key >> 16);
53             if (key >= 2) {         // Don't insert 0 or 1
54                 m_map->erase(key);
55                 keysRemaining--;
56             }
57             index++;
58         }
59         m_env.threads[threadIndex].update();
60     }
61
62     void checkMapContents() {
63 #if TEST_CHECK_MAP_CONTENTS
64         ureg iterCount = 0;
65         ureg iterChecksum = 0;
66         for (MapAdapter::Map::Iterator iter(*m_map); iter.isValid(); iter.next()) {
67             iterCount++;
68             u32 key = iter.getKey();
69             iterChecksum += key;
70             if (iter.getValue() != (void*) uptr(key))
71                 TURF_DEBUG_BREAK();
72         }
73
74         ureg actualChecksum = 0;
75         for (ureg i = 0; i < m_env.numThreads; i++) {
76             u32 index = m_startIndex + i * (KeysToInsert + 2);
77             sreg leftToCheck = KeysToInsert;
78             while (leftToCheck > 0) {
79                 u32 key = index * m_relativePrime;
80                 key = key ^ (key >> 16);
81                 if (key >= 2) {         // Don't insert 0 or 1
82                     if (m_map->get(key) != (void*) uptr(key))
83                         TURF_DEBUG_BREAK();
84                     actualChecksum += key;
85                     leftToCheck--;
86                 }
87                 index++;
88             }
89         }
90
91         if (iterCount != KeysToInsert * m_env.numThreads)
92             TURF_DEBUG_BREAK();
93         if (iterChecksum != actualChecksum)
94             TURF_DEBUG_BREAK();
95 #endif
96     }
97
98     void checkMapEmpty() {
99 #if TEST_CHECK_MAP_CONTENTS
100         for (MapAdapter::Map::Iterator iter(*m_map); iter.isValid(); iter.next()) {
101             TURF_DEBUG_BREAK();
102         }
103         
104         for (ureg i = 0; i < m_env.numThreads; i++) {
105             u32 index = m_startIndex + i * (KeysToInsert + 2);
106             sreg leftToCheck = KeysToInsert;
107             while (leftToCheck > 0) {
108                 u32 key = index * m_relativePrime;
109                 key = key ^ (key >> 16);
110                 if (key >= 2) {         // Don't insert 0 or 1
111                     if (m_map->get(key))
112                         TURF_DEBUG_BREAK();
113                     leftToCheck--;
114                 }
115                 index++;
116             }
117         }
118 #endif // TEST_CHECK_MAP_CONTENTS
119     }
120
121     void run() {
122         m_map = new MapAdapter::Map(MapAdapter::getInitialCapacity(KeysToInsert));
123         m_startIndex = m_random.next32();
124         m_relativePrime = m_random.next32() * 2 + 1;
125         m_env.dispatcher.kick(&TestInsertDifferentKeys::insertKeys, *this);
126         checkMapContents();
127         m_env.dispatcher.kick(&TestInsertDifferentKeys::eraseKeys, *this);
128         checkMapEmpty();
129         delete m_map;
130         m_map = NULL;
131     }
132 };
133
134 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTINSERTDIFFERENTKEYS_H