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 <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("work_stealing_deque functions correctly", "[internal/data_structures/work_stealing_deque.h]") {
  SECTION("add and remove items form the tail") {
    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_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);
    }

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

      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == two);
    }

    SECTION("remove items form the head") {
      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);
    }

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

      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);
    }

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

      deque.push_task<int>(two);
      deque.publish_last_task();
      REQUIRE(*deque.pop_external_task() == two);

      deque.push_task<int>(three);
      deque.publish_last_task();
      REQUIRE(*deque.pop_local_task() == three);
    }

    SECTION("handles jumps bigger 1 correctly") {
      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);
    }

    SECTION("handles stack reset 1 correctly when emptied by tail") {
      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);
    }
  }
}

TEST_CASE("locking_deque functions correctly", "[internal/data_structures/locking_deque.h]") {
  SECTION("add and remove items form the tail") {
    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") {
      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);
    }
  }
}