samples/MapCorrectnessTests/TestInsertSameKeys.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_TESTINSERTSAMEKEYS_H
  14 #define SAMPLES_MAPCORRECTNESSTESTS_TESTINSERTSAMEKEYS_H
  15
  16 #include <junction/Core.h>
  17 #include "TestEnvironment.h"
  18 #include <turf/extra/Random.h>
  19
  20 class TestInsertSameKeys {
  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     TestInsertSameKeys(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;
  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;
  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         u32 index = m_startIndex;
  76         sreg leftToCheck = KeysToInsert;
  77         while (leftToCheck > 0) {
  78             u32 key = index * m_relativePrime;
  79             key = key ^ (key >> 16);
  80             if (key >= 2) {         // Don't insert 0 or 1
  81                 if (m_map->get(key) != (void*) uptr(key))
  82                     TURF_DEBUG_BREAK();
  83                 actualChecksum += key;
  84                 leftToCheck--;
  85             }
  86             index++;
  87         }
  88
  89         if (iterCount != KeysToInsert)
  90             TURF_DEBUG_BREAK();
  91         if (iterChecksum != actualChecksum)
  92             TURF_DEBUG_BREAK();
  93 #endif // TEST_CHECK_MAP_CONTENTS
  94     }
  95
  96     void checkMapEmpty() {
  97 #if TEST_CHECK_MAP_CONTENTS
  98         for (MapAdapter::Map::Iterator iter(*m_map); iter.isValid(); iter.next()) {
  99             TURF_DEBUG_BREAK();
 100         }
 101
 102         u32 index = m_startIndex;
 103         sreg leftToCheck = KeysToInsert;
 104         while (leftToCheck > 0) {
 105             u32 key = index * m_relativePrime;
 106             key = key ^ (key >> 16);
 107             if (key >= 2) {         // Don't insert 0 or 1
 108                 if (m_map->get(key))
 109                     TURF_DEBUG_BREAK();
 110                 leftToCheck--;
 111             }
 112             index++;
 113         }
 114 #endif // TEST_CHECK_MAP_CONTENTS
 115     }
 116
 117     void run() {
 118         m_map = new MapAdapter::Map(MapAdapter::getInitialCapacity(KeysToInsert));
 119         m_startIndex = m_random.next32();
 120         m_relativePrime = m_random.next32() * 2 + 1;
 121         m_env.dispatcher.kick(&TestInsertSameKeys::insertKeys, *this);
 122         checkMapContents();
 123         m_env.dispatcher.kick(&TestInsertSameKeys::eraseKeys, *this);
 124         checkMapEmpty();
 125         delete m_map;
 126         m_map = NULL;
 127     }
 128 };
 129
 130 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTINSERTSAMEKEYS_H