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