arena-tree.cpp (2541B)
1 #include <cstddef> 2 #include <utility> 3 #include <span> 4 #include <stdexcept> 5 #include <iostream> 6 #include <iomanip> 7 8 struct arena 9 { 10 std::span<std::byte> buf; 11 unsigned top = 0; 12 13 std::byte* allocate(unsigned n, unsigned align) 14 { 15 auto start = top; 16 if (auto residual = start % align) 17 start += align - residual; 18 19 auto end = start + n; 20 21 if (end > buf.size()) 22 throw std::bad_alloc(); 23 24 top = end; 25 return buf.data() + start; 26 } 27 28 template <typename T, typename... Args> 29 T* construct(Args&&... args) 30 { 31 static_assert(std::is_trivially_destructible_v<T>); 32 return new(allocate(sizeof(T), alignof(T))) T{std::forward<Args>(args)...}; 33 } 34 35 void free() noexcept 36 { 37 top = 0; 38 } 39 40 arena(std::span<std::byte> b) 41 : buf(b) 42 {} 43 arena(arena const&) = delete; 44 arena& operator =(arena const&) = delete; 45 }; 46 47 template <typename T> 48 struct pool 49 { 50 static_assert(std::is_trivially_destructible_v<T>); 51 arena &a; 52 53 struct freenode 54 { 55 freenode *next; 56 } *head = nullptr; 57 58 void free(T* ptr) 59 { 60 ptr->~T(); 61 head = new(ptr) freenode{head}; 62 } 63 64 void* allocate() 65 { 66 if (head) 67 return std::exchange(head, head->next); 68 else 69 return a.allocate(sizeof(T), alignof(T)); 70 } 71 72 template <typename... Args> 73 T* construct(Args&&... args) 74 { 75 return new(allocate()) T{std::forward<Args>(args)...}; 76 } 77 78 pool(arena& aa) 79 : a{aa} 80 {} 81 pool(pool const&) = delete; 82 pool& operator =(pool const&) = delete; 83 }; 84 85 struct treenode 86 { 87 treenode *first_child, *next_sibling; 88 89 treenode(int v) : x{v} {} 90 91 int x; 92 }; 93 94 treenode* make_tree(int v, pool<treenode>& a) 95 { 96 return a.construct(v); 97 } 98 99 treenode* get_last_sibling(treenode* n) 100 { 101 while (auto next = n->next_sibling) 102 n = next; 103 return n; 104 } 105 106 treenode* add_child(int v, treenode* parent, auto& a) 107 { 108 auto node = make_tree(v, a); 109 110 node->next_sibling = std::exchange(parent->first_child, node); 111 112 return node; 113 } 114 115 unsigned count_nodes(treenode const* n) 116 { 117 if (not n) 118 return 0; 119 120 return 1 + count_nodes(n->first_child) + count_nodes(n->next_sibling); 121 } 122 123 unsigned sum_nodes(treenode const* n) 124 { 125 if (not n) 126 return 0; 127 128 return n->x + sum_nodes(n->first_child) + sum_nodes(n->next_sibling); 129 } 130 131 alignas(alignof(std::max_align_t)) std::byte buf[1024*1024]; 132 133 int main() 134 { 135 arena a{buf}; 136 pool<treenode> p{a}; 137 138 auto head = make_tree(100, p); 139 add_child(10, head, p); 140 add_child(10, head, p); 141 add_child(10, head, p); 142 auto leaf = add_child(10, head, p); 143 add_child(1, leaf, p); 144 add_child(1, leaf, p); 145 add_child(10, head, p); 146 add_child(10, head, p); 147 add_child(10, head, p); 148 149 return sum_nodes(head); 150 }