data_structures_test.cpp

#include <catch.hpp>

#include <pls/internal/base/system_details.h>

#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>

#include <vector>
#include <mutex>

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

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'};

    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);

    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{};

    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);

    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'};

    stack.push<decltype(data_one)>(data_one);
    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'};

    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);

    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);
  }
}

TEST_CASE("deque stores objects correctly", "[internal/data_structures/deque.h]") {
  class my_item {

  };

  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;

  SECTION("add and remove items form the tail") {
    deque.push_tail(one);
    deque.push_tail(two);
    deque.push_tail(three);

    REQUIRE(*deque.pop_tail() == three);
    REQUIRE(*deque.pop_tail() == two);
    REQUIRE(*deque.pop_tail() == one);
  }

  SECTION("handles getting empty by popping the tail correctly") {
    deque.push_tail(one);
    REQUIRE(*deque.pop_tail() == one);

    deque.push_tail(two);
    REQUIRE(*deque.pop_tail() == two);
  }

  SECTION("remove items form the head") {
    deque.push_tail(one);
    deque.push_tail(two);
    deque.push_tail(three);

    REQUIRE(*deque.pop_head() == one);
    REQUIRE(*deque.pop_head() == two);
    REQUIRE(*deque.pop_head() == three);
  }

  SECTION("handles getting empty by popping the head correctly") {
    deque.push_tail(one);
    REQUIRE(*deque.pop_head() == one);

    deque.push_tail(two);
    REQUIRE(*deque.pop_head() == two);
  }

  SECTION("handles getting empty by popping the head and tail correctly") {
    deque.push_tail(one);
    REQUIRE(*deque.pop_tail() == one);

    deque.push_tail(two);
    REQUIRE(*deque.pop_head() == two);

    deque.push_tail(three);
    REQUIRE(*deque.pop_tail() == three);
  }
}

TEST_CASE("work stealing deque stores objects correctly", "[internal/data_structures/aligned_stack.h]") {
  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") {
    deque.push_tail<int>(one);
    deque.push_tail<int>(two);
    deque.push_tail<int>(three);

    REQUIRE(*deque.pop_tail() == three);
    REQUIRE(*deque.pop_tail() == two);
    REQUIRE(*deque.pop_tail() == one);
  }

  SECTION("handles getting empty by popping the tail correctly") {
    deque.push_tail<int>(one);
    REQUIRE(*deque.pop_tail() == one);

    deque.push_tail<int>(two);
    REQUIRE(*deque.pop_tail() == two);
  }

  SECTION("remove items form the head") {
    deque.push_tail<int>(one);
    deque.push_tail<int>(two);
    deque.push_tail<int>(three);

    REQUIRE(*deque.pop_head() == one);
    REQUIRE(*deque.pop_head() == two);
    REQUIRE(*deque.pop_head() == three);
  }

  SECTION("handles getting empty by popping the head correctly") {
    deque.push_tail<int>(one);
    REQUIRE(*deque.pop_head() == one);

    deque.push_tail<int>(two);
    REQUIRE(*deque.pop_head() == two);
  }

  SECTION("handles getting empty by popping the head and tail correctly") {
    deque.push_tail<int>(one);
    REQUIRE(*deque.pop_tail() == one);

    deque.push_tail<int>(two);
    REQUIRE(*deque.pop_head() == two);

    deque.push_tail<int>(three);
    REQUIRE(*deque.pop_tail() == three);
  }

  SECTION("handles jumps bigger 1 correctly") {
    deque.push_tail<int>(one);
    deque.push_tail<int>(two);
    REQUIRE(*deque.pop_tail() == two);

    deque.push_tail<int>(three);
    deque.push_tail<int>(four);
    REQUIRE(*deque.pop_head() == one);
    REQUIRE(*deque.pop_head() == three);
    REQUIRE(*deque.pop_head() == four);
  }

  SECTION("handles stack reset 1 correctly when emptied by tail") {
    deque.push_tail<int>(one);
    auto state = deque.save_state();
    deque.push_tail<int>(two);
    REQUIRE(*deque.pop_tail() == two);

    deque.release_memory_until(state);
    REQUIRE(*deque.pop_tail() == one);

    deque.push_tail<int>(three);
    deque.push_tail<int>(four);
    REQUIRE(*deque.pop_head() == three);
    REQUIRE(*deque.pop_tail() == four);
  }
}