polymorphic_stack.hpp (8013B)
1 #ifndef GUARD_THRUOUT_CHANCE_FACE_BLINDNESS_MESSES_UP_1276 2 #define GUARD_THRUOUT_CHANCE_FACE_BLINDNESS_MESSES_UP_1276 3 #pragma once 4 5 #include "libshit/asan.hpp" 6 #include "libshit/assert.hpp" 7 #include "libshit/except.hpp" 8 #include "libshit/platform.hpp" 9 10 #include <algorithm> 11 #include <cstdint> 12 #include <cstdlib> 13 #include <new> 14 #include <type_traits> 15 #include <utility> 16 17 namespace Libshit 18 { 19 20 namespace PolymorphicStackDetail 21 { 22 struct MallocAllocator 23 { 24 static std::pair<void*, std::uint32_t> Alloc(std::uint32_t size) noexcept; 25 static void Free(void* ptr, std::uint32_t size) noexcept; 26 static constexpr bool EXTEND_SUPPORTED = false; 27 }; 28 29 #if !LIBSHIT_OS_IS_WINDOWS && !LIBSHIT_OS_IS_VITA 30 struct MmapAllocator 31 { 32 static std::pair<void*, std::uint32_t> Alloc(std::uint32_t size) noexcept; 33 static void Free(void* ptr, std::uint32_t size) noexcept; 34 static constexpr bool EXTEND_SUPPORTED = LIBSHIT_OS_IS_LINUX; 35 static std::uint32_t Extend( 36 void* ptr, std::uint32_t old_size, std::uint32_t min_size, 37 std::uint32_t max_size) noexcept; 38 }; 39 40 using Allocator = MmapAllocator; 41 #else 42 using Allocator = MallocAllocator; 43 #endif 44 45 struct Chunk 46 { 47 Chunk* prev; // nullptr when none 48 Chunk* next; 49 std::uint32_t size, current; 50 51 template <typename T> 52 T& Get(std::size_t offs) noexcept 53 { return *reinterpret_cast<T*>(reinterpret_cast<char*>(this) + offs); } 54 }; 55 56 union Builtin 57 { 58 void* ptr; 59 std::uint64_t u64; 60 double d; 61 }; 62 63 struct alignas(Builtin) Head 64 { 65 // prev is 0 on the first head 66 // next points to where the next header *would* start on the last header 67 std::uint32_t prev, next; 68 }; 69 } 70 71 template <typename Base, typename Allocator = PolymorphicStackDetail::Allocator> 72 class PolymorphicStack 73 { 74 public: 75 static_assert( 76 std::has_virtual_destructor_v<Base>, "Base needs a virtual dtor"); 77 78 PolymorphicStack() = default; 79 PolymorphicStack(PolymorphicStack&& o) noexcept 80 : head{o.head}, tail{o.tail} 81 { 82 o.head = nullptr; 83 o.tail = nullptr; 84 } 85 86 PolymorphicStack& operator=(PolymorphicStack o) noexcept 87 { 88 swap(o); 89 return *this; 90 } 91 92 ~PolymorphicStack() noexcept 93 { 94 Clear(); 95 FreeList(head); 96 } 97 98 99 template <typename T, typename... Args, typename = std::enable_if_t< 100 std::is_constructible_v<T, Args...>>> 101 T& Push(Args&&... args) 102 { 103 static_assert(std::is_base_of_v<Base, T>); 104 static_assert(alignof(T) <= ALIGN); 105 static_assert(sizeof(T) < 0xffffff00 - sizeof(Chunk)); // prevent some overflows 106 static constexpr const auto NEED_SPACE = sizeof(Head) + sizeof(T); 107 108 auto [chunk, offs] = PushGeneric(NEED_SPACE); 109 110 Asan::Undefined(reinterpret_cast<char*>(chunk) + offs, NEED_SPACE); 111 T* ret; 112 try 113 { 114 ret = new (&chunk->template Get<T>(offs + sizeof(Head))) 115 T(std::forward<Args>(args)...); 116 } 117 catch (...) 118 { 119 Asan::Poison(reinterpret_cast<char*>(chunk) + offs, NEED_SPACE); 120 throw; 121 } 122 123 tail = chunk; 124 auto& nhead = tail->Get<Head>(offs); 125 nhead.prev = tail->current; 126 nhead.next = offs + NEED_SPACE; 127 tail->current = offs; 128 return *ret; 129 } 130 131 void Pop() 132 { 133 Back().~Base(); 134 auto new_current = tail->Get<Head>(tail->current).prev; 135 Asan::Poison(reinterpret_cast<char*>(tail) + tail->current, 136 tail->Get<Head>(tail->current).next - tail->current); 137 tail->current = new_current; 138 if (tail->current == 0 && tail != head) 139 tail = tail->prev; 140 } 141 142 Base& Back() noexcept { return BackImpl(); } 143 const Base& Back() const noexcept { return BackImpl(); } 144 145 146 bool Empty() const noexcept 147 { return !head || (head == tail && head->current == 0); } 148 149 // warning: O(n)! 150 std::size_t Size() const noexcept 151 { 152 if (!head) return 0; 153 std::size_t n = 0; 154 for (Chunk* c = head; c; c = c->next) 155 { 156 if (c->current == 0) break; 157 auto last = &c->Get<Head>(c->current); 158 for (auto h = &c->Get<Head>(START_OFFSET); h <= last; 159 h = &c->Get<Head>(h->next)) ++n; 160 } 161 return n; 162 } 163 164 void Clear() noexcept 165 { while (!Empty()) Pop(); } 166 167 void swap(PolymorphicStack& o) noexcept 168 { 169 std::swap(head, o.head); 170 std::swap(tail, o.tail); 171 } 172 173 private: 174 using Chunk = PolymorphicStackDetail::Chunk; 175 using Head = PolymorphicStackDetail::Head; 176 177 static constexpr std::size_t ALIGN = std::max(alignof(Head), alignof(Base)); 178 static constexpr std::size_t Align(std::size_t s) noexcept 179 { return (s + (ALIGN-1)) & ~(ALIGN-1); } 180 181 static constexpr std::size_t START_OFFSET = Align(sizeof(Chunk)); 182 // head points to the beginning of the linked list. tail to the last used 183 // chunk (so tail->next is not neccessarily nullptr) 184 // when empty, head == tail is true 185 Chunk* head = nullptr; 186 Chunk* tail = nullptr; 187 188 Base& BackImpl() const noexcept 189 { 190 LIBSHIT_ASSERT(!Empty()); 191 return tail->Get<Base>(tail->current + sizeof(Head)); 192 } 193 194 std::uint32_t SuggestSize(std::uint32_t last, std::uint32_t min) 195 { 196 if (last < 0x7fffffff) last *= 2; 197 return std::max(last, min); 198 } 199 200 std::pair<Chunk*, std::uint32_t> PushGeneric(std::size_t need_space) 201 { 202 if (tail) 203 { 204 auto next = 205 tail->current ? tail->Get<Head>(tail->current).next : START_OFFSET; 206 if constexpr (Allocator::EXTEND_SUPPORTED) 207 // try to extend the last chunk 208 if (!tail->next && (tail->size - next) < need_space && 209 0xffffffff - next >= need_space) 210 { 211 auto min_size = next + need_space; 212 auto suggest = SuggestSize(tail->size, min_size); 213 if (auto s = Allocator::Extend(tail, tail->size, min_size, suggest)) 214 tail->size = s; 215 } 216 217 // check the current chunk has enough space 218 if ((tail->size - next) >= need_space) 219 return { tail, next }; 220 221 if (tail->current == 0) 222 { 223 // We can't have empty chunks between used chunks! This shouldn't 224 // happen in practice though (we should not allocate chunks this big), 225 // so just get rid of the remaining chunks and fall back to the "no 226 // more chunks" logic below. 227 auto prev = tail->prev; 228 if (prev) prev->next = nullptr; 229 FreeList(tail); 230 tail = prev; 231 if (!prev) head = nullptr; 232 } 233 else if (tail->next) 234 { 235 LIBSHIT_ASSERT(tail->next->current == 0); 236 if ((tail->next->size - START_OFFSET) < need_space) 237 { 238 // Next is unusuable 239 FreeList(tail->next); 240 tail->next = nullptr; 241 } 242 else 243 return { tail->next, START_OFFSET }; 244 } 245 } 246 247 // no more chunks 248 auto s = SuggestSize(tail ? tail->size : 64, START_OFFSET + need_space); 249 auto [chunk_, new_s] = Allocator::Alloc(s); 250 auto chunk = static_cast<Chunk*>(chunk_); 251 if (!chunk) LIBSHIT_THROW(std::bad_alloc, {}); 252 253 chunk->prev = tail; 254 chunk->next = nullptr; 255 chunk->size = new_s; 256 chunk->current = 0; 257 Asan::Poison( 258 reinterpret_cast<char*>(chunk) + START_OFFSET, new_s - START_OFFSET); 259 if (head) 260 tail->next = chunk; 261 else 262 head = tail = chunk; 263 264 return { chunk, START_OFFSET }; 265 } 266 267 void FreeList(Chunk* c) 268 { 269 while (c) 270 { 271 auto n = c->next; 272 auto size = c->size; 273 Asan::Undefined(c, size); 274 Allocator::Free(c, size); 275 c = n; 276 } 277 } 278 }; 279 280 template <typename Base, typename Allocator> 281 inline void swap(PolymorphicStack<Base, Allocator>& a, 282 PolymorphicStack<Base, Allocator>& b) noexcept 283 { a.swap(b); } 284 285 } 286 287 #endif