libshit

polymorphic_stack.cpp (5129B)

---

 #include "libshit/container/polymorphic_stack.hpp"
 
 #include "libshit/doctest.hpp"
 #include "libshit/utils.hpp"
 
 #include <tracy/Tracy.hpp>
 
 #include <limits>
 #include <vector>
 
 #if !LIBSHIT_OS_IS_WINDOWS && !LIBSHIT_OS_IS_VITA
 #  include <unistd.h>
 #  include <sys/mman.h>
 #endif
 
 namespace Libshit
 {
   using namespace PolymorphicStackDetail;
   TEST_SUITE_BEGIN("Libshit::PolymorphicStack");
 
   std::pair<void*, std::uint32_t> MallocAllocator::Alloc(
     std::uint32_t size) noexcept
   {
     auto ptr = std::malloc(size);
     TracyAllocS(ptr, size, 5);
     return { ptr, size };
   }
 
   void MallocAllocator::Free(void* ptr, std::uint32_t size) noexcept
   {
     TracyFreeS(ptr, 5);
     std::free(ptr);
   }
 
 #if !LIBSHIT_OS_IS_WINDOWS && !LIBSHIT_OS_IS_VITA
 
   static const std::size_t PAGE_SIZE_M1 = sysconf(_SC_PAGE_SIZE) - 1;
 
   std::pair<void*, std::uint32_t> MmapAllocator::Alloc(
     std::uint32_t size) noexcept
   {
     if (std::numeric_limits<std::uint32_t>::max() - size < PAGE_SIZE_M1)
       return { nullptr, 0 };
 
     size = (size + PAGE_SIZE_M1) & ~PAGE_SIZE_M1;
     auto ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
     if (ptr == MAP_FAILED) return { nullptr, 0 };
 
     TracyAllocS(ptr, size, 5);
     return { ptr, size };
   }
 
   void MmapAllocator::Free(void* ptr, std::uint32_t size) noexcept
   {
     TracyFreeS(ptr, 5);
     munmap(ptr, size);
   }
 
 #endif
 
   static bool disable_mremap [[maybe_unused]] = false;
 #if LIBSHIT_OS_IS_LINUX
   std::uint32_t MmapAllocator::Extend(
     void* ptr, std::uint32_t old_size, std::uint32_t min_size,
     std::uint32_t max_size) noexcept
   {
     LIBSHIT_ASSERT(max_size >= min_size);
     if (disable_mremap) return 0;
     if (std::numeric_limits<std::uint32_t>::max() - max_size < PAGE_SIZE_M1)
       return 0;
 
     max_size = (max_size + PAGE_SIZE_M1) & ~PAGE_SIZE_M1;
     if (mremap(ptr, old_size, max_size, 0) != MAP_FAILED) return max_size;
     min_size = (min_size + PAGE_SIZE_M1) & ~PAGE_SIZE_M1;
     if (mremap(ptr, old_size, min_size, 0) != MAP_FAILED) return min_size;
     return 0;
   }
 #endif
 
   namespace
   {
     struct Base { virtual ~Base() = default; };
     template <std::size_t N>
     struct X : Base { char x[N]; };
   }
 
   TEST_CASE_TEMPLATE_DEFINE("PolymorphicStack", T, polymorphic_stack)
   {
     T stack;
     CHECK(stack.Size() == 0);
     CHECK(stack.Empty());
 
     SUBCASE("simple push/pop")
     {
       auto& x = stack.template Push<Base>();
       CHECK(stack.Size() == 1);
       CHECK(!stack.Empty());
       CHECK(&stack.Back() == &x);
 
       stack.Pop();
       CHECK(stack.Size() == 0);
       CHECK(stack.Empty());
     }
 
     SUBCASE("push multiple")
     {
       auto& a = stack.template Push<Base>();
       auto& b = stack.template Push<X<16>>();
       CHECK(reinterpret_cast<uintptr_t>(&b) ==
             reinterpret_cast<uintptr_t>(&a) + sizeof(Base) + sizeof(Head));
       auto& c = stack.template Push<X<32>>();
       CHECK(reinterpret_cast<uintptr_t>(&c) ==
             reinterpret_cast<uintptr_t>(&b) + sizeof(X<16>) + sizeof(Head));
 
       CHECK(&stack.Back() == &c); CHECK(stack.Size() == 3); stack.Pop();
       CHECK(&stack.Back() == &b); CHECK(stack.Size() == 2); stack.Pop();
       CHECK(&stack.Back() == &a); CHECK(stack.Size() == 1); stack.Pop();
       CHECK(stack.Size() == 0); CHECK(stack.Empty());
     }
 
     SUBCASE("push until overflow")
     {
       disable_mremap = true;
       AtScopeExit x{[]() { disable_mremap = false; }};
 
       auto& first = stack.template Push<X<128>>();
       std::vector<X<128>*> vec{&first};
       do
       {
         REQUIRE(vec.size() < 100'000); // do not eat all of the memory
         vec.push_back(&stack.template Push<X<128>>());
       }
       while (reinterpret_cast<char*>(vec.back()) ==
              reinterpret_cast<char*>(&first) +
                (sizeof(Head) + sizeof(X<128>)) * (vec.size()-1));
       CCAPTURE(vec.size());
 
       std::size_t n = vec.size();
       for (auto it = vec.rbegin(); it != vec.rend(); ++it)
       {
         CHECK(stack.Size() == n);
         CHECK(stack.Empty() == !n);
         --n;
         CHECK(&stack.Back() == *it);
         stack.Pop();
       }
 
       SUBCASE("overflow head")
       {
         auto& foo = stack.template Push<X<65536>>();
         CHECK(&stack.Back() == &foo);
         CHECK(stack.Size() == 1);
       }
       SUBCASE("overflow tail")
       {
         auto& head = stack.template Push<Base>();
         auto& foo = stack.template Push<X<65536>>();
         CHECK(&stack.Back() == &foo);
         CHECK(stack.Size() == 2);
         stack.Pop();
         CHECK(&stack.Back() == &head);
       }
     }
   }
 
   TEST_CASE_TEMPLATE_INVOKE(
     polymorphic_stack, PolymorphicStack<Base, MallocAllocator>);
 #if !LIBSHIT_OS_IS_WINDOWS && !LIBSHIT_OS_IS_VITA
   TEST_CASE_TEMPLATE_INVOKE(
     polymorphic_stack, PolymorphicStack<Base, MmapAllocator>);
 #endif
 
   TEST_SUITE_END();
 }
 
 TYPE_TO_STRING(Libshit::PolymorphicStack<Libshit::Base, Libshit::MallocAllocator>);
 #if !LIBSHIT_OS_IS_WINDOWS && !LIBSHIT_OS_IS_VITA
 TYPE_TO_STRING(Libshit::PolymorphicStack<Libshit::Base, Libshit::MmapAllocator>);
 #endif