data_structures_test.cpp 9.97 KB
Newer Older
1 2
#include <catch.hpp>

3
#include "pls/internal/base/system_details.h"
4

5 6 7
#include "pls/internal/data_structures/aligned_stack.h"
#include "pls/internal/data_structures/locking_deque.h"
#include "pls/internal/data_structures/work_stealing_deque.h"
8 9 10 11 12 13 14

#include <mutex>

using namespace pls::internal::data_structures;
using namespace pls::internal::base;
using namespace std;

15 16 17 18 19 20 21 22 23 24
TEST_CASE("aligned stack stores objects correctly", "[internal/data_structures/aligned_stack.h]") {
  constexpr long data_size = 1024;
  char data[data_size];
  aligned_stack stack{data, data_size};

  SECTION("stack correctly pushes sub linesize objects") {
    std::array<char, 5> small_data_one{'a', 'b', 'c', 'd', 'e'};
    std::array<char, 64> small_data_two{};
    std::array<char, 1> small_data_three{'A'};

25 26 27
    auto pointer_one = stack.push<decltype(small_data_one)>(small_data_one);
    auto pointer_two = stack.push<decltype(small_data_two)>(small_data_two);
    auto pointer_three = stack.push<decltype(small_data_three)>(small_data_three);
28 29 30 31 32 33 34 35 36 37

    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_one) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_two) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_three) % system_details::CACHE_LINE_SIZE == 0);
  }

  SECTION("stack correctly pushes above linesize objects") {
    std::array<char, 5> small_data_one{'a', 'b', 'c', 'd', 'e'};
    std::array<char, system_details::CACHE_LINE_SIZE + 10> big_data_one{};

38 39
    auto big_pointer_one = stack.push<decltype(big_data_one)>(big_data_one);
    auto small_pointer_one = stack.push<decltype(small_data_one)>(small_data_one);
40 41 42 43 44 45 46 47

    REQUIRE(reinterpret_cast<std::uintptr_t>(big_pointer_one) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(small_pointer_one) % system_details::CACHE_LINE_SIZE == 0);
  }

  SECTION("stack correctly stores and retrieves objects") {
    std::array<char, 5> data_one{'a', 'b', 'c', 'd', 'e'};

48
    stack.push<decltype(data_one)>(data_one);
49 50 51 52 53 54 55 56 57 58
    auto retrieved_data = stack.pop<std::array<char, 5>>();

    REQUIRE(retrieved_data == std::array<char, 5>{'a', 'b', 'c', 'd', 'e'});
  }

  SECTION("stack can push and pop multiple times with correct alignment") {
    std::array<char, 5> small_data_one{'a', 'b', 'c', 'd', 'e'};
    std::array<char, 64> small_data_two{};
    std::array<char, 1> small_data_three{'A'};

59 60 61 62 63 64 65
    auto pointer_one = stack.push<decltype(small_data_one)>(small_data_one);
    auto pointer_two = stack.push<decltype(small_data_two)>(small_data_two);
    auto pointer_three = stack.push<decltype(small_data_three)>(small_data_three);
    stack.pop<decltype(small_data_three)>();
    stack.pop<decltype(small_data_two)>();
    auto pointer_four = stack.push<decltype(small_data_two)>(small_data_two);
    auto pointer_five = stack.push<decltype(small_data_three)>(small_data_three);
66 67 68 69 70 71 72 73 74 75

    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_one) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_two) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_three) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_four) % system_details::CACHE_LINE_SIZE == 0);
    REQUIRE(reinterpret_cast<std::uintptr_t>(pointer_five) % system_details::CACHE_LINE_SIZE == 0);

    REQUIRE(pointer_four == pointer_two);
    REQUIRE(pointer_five == pointer_three);
  }
76 77
}

78
TEST_CASE("work_stealing_deque functions correctly", "[internal/data_structures/work_stealing_deque.h]") {
79
  SECTION("add and remove items form the tail") {
80 81 82 83 84 85 86 87
    constexpr long data_size = 2 << 14;
    char data[data_size];
    aligned_stack stack{data, data_size};
    work_stealing_deque<int> deque{&stack};

    int one = 1, two = 2, three = 3, four = 4;

    SECTION("add and remove items form the tail") {
88 89 90 91 92 93 94 95 96 97
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      deque.push_task<int>(three);
      deque.publish_last_task();

      REQUIRE(*deque.pop_local_task() == three);
      REQUIRE(*deque.pop_local_task() == two);
      REQUIRE(*deque.pop_local_task() == one);
98 99 100
    }

    SECTION("handles getting empty by popping the tail correctly") {
101 102 103
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == one);
104

105 106 107
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);
108 109 110
    }

    SECTION("remove items form the head") {
111 112 113 114 115 116 117 118 119 120
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      deque.push_task<int>(three);
      deque.publish_last_task();

      REQUIRE(*deque.pop_external_task() == one);
      REQUIRE(*deque.pop_external_task() == two);
      REQUIRE(*deque.pop_external_task() == three);
121 122 123
    }

    SECTION("handles getting empty by popping the head correctly") {
124 125 126
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == one);
127

128 129 130
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);
131 132 133
    }

    SECTION("handles getting empty by popping the head and tail correctly") {
134 135 136
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == one);
137

138 139 140
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);
141

142 143 144
      deque.push_task<int>(three);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == three);
145 146 147
    }

    SECTION("handles jumps bigger 1 correctly") {
148 149 150 151 152 153 154 155 156 157 158 159 160
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);

      deque.push_task<int>(three);
      deque.publish_last_task();
      deque.push_task<int>(four);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == one);
      REQUIRE(*deque.pop_external_task() == three);
      REQUIRE(*deque.pop_external_task() == four);
161 162 163
    }

    SECTION("handles stack reset 1 correctly when emptied by tail") {
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
      deque.push_task<int>(one);
      deque.publish_last_task();
      auto state = deque.save_offset();
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);

      deque.reset_offset(state);
      REQUIRE(*deque.pop_local_task() == one);

      deque.push_task<int>(three);
      deque.publish_last_task();
      deque.push_task<int>(four);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == three);
      REQUIRE(*deque.pop_local_task() == four);
180
    }
181
  }
182
}
183

184
TEST_CASE("locking_deque functions correctly", "[internal/data_structures/locking_deque.h]") {
185
  SECTION("add and remove items form the tail") {
186 187 188 189 190 191 192 193
    constexpr long data_size = 2 << 14;
    char data[data_size];
    aligned_stack stack{data, data_size};
    locking_deque<int> deque{&stack};

    int one = 1, two = 2, three = 3, four = 4;

    SECTION("add and remove items form the tail") {
194 195 196 197 198 199
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      deque.push_task<int>(three);
      deque.publish_last_task();
200

201 202 203
      REQUIRE(*deque.pop_local_task() == three);
      REQUIRE(*deque.pop_local_task() == two);
      REQUIRE(*deque.pop_local_task() == one);
204 205 206
    }

    SECTION("handles getting empty by popping the tail correctly") {
207 208 209
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == one);
210

211 212 213
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);
214 215 216
    }

    SECTION("remove items form the head") {
217 218 219 220 221 222
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      deque.push_task<int>(three);
      deque.publish_last_task();
223

224 225 226
      REQUIRE(*deque.pop_external_task() == one);
      REQUIRE(*deque.pop_external_task() == two);
      REQUIRE(*deque.pop_external_task() == three);
227 228 229
    }

    SECTION("handles getting empty by popping the head correctly") {
230 231 232
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == one);
233

234 235 236
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);
237 238 239
    }

    SECTION("handles getting empty by popping the head and tail correctly") {
240 241 242
      deque.push_task<int>(one);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == one);
243

244 245 246
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);
247

248 249 250
      deque.push_task<int>(three);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == three);
251 252 253
    }

    SECTION("handles jumps bigger 1 correctly") {
254 255 256 257 258 259 260 261 262 263 264 265 266
      deque.push_task<int>(one);
      deque.publish_last_task();
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);

      deque.push_task<int>(three);
      deque.publish_last_task();
      deque.push_task<int>(four);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == one);
      REQUIRE(*deque.pop_external_task() == three);
      REQUIRE(*deque.pop_external_task() == four);
267 268 269
    }

    SECTION("handles stack reset 1 correctly when emptied by tail") {
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
      deque.push_task<int>(one);
      deque.publish_last_task();
      auto state = deque.save_offset();
      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);

      deque.reset_offset(state);
      REQUIRE(*deque.pop_local_task() == one);

      deque.push_task<int>(three);
      deque.publish_last_task();
      deque.push_task<int>(four);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == three);
      REQUIRE(*deque.pop_local_task() == four);
286
    }
287 288
  }
}