| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // | ||
| 2 | // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com) | ||
| 3 | // | ||
| 4 | // Distributed under the Boost Software License, Version 1.0. (See accompanying | ||
| 5 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | ||
| 6 | // | ||
| 7 | // Official repository: https://github.com/boostorg/capy | ||
| 8 | // | ||
| 9 | |||
| 10 | #include "work_allocator.hpp" | ||
| 11 | #include <cstdlib> | ||
| 12 | #include <functional> | ||
| 13 | #include <new> | ||
| 14 | |||
| 15 | namespace boost { | ||
| 16 | namespace capy { | ||
| 17 | |||
| 18 | //------------------------------------------------------------------------------ | ||
| 19 | // | ||
| 20 | // work_allocator::arena | ||
| 21 | // | ||
| 22 | //------------------------------------------------------------------------------ | ||
| 23 | |||
| 24 | 8 | work_allocator::arena:: | |
| 25 | ~arena() | ||
| 26 | { | ||
| 27 | 8 | std::free(base_); | |
| 28 | 8 | } | |
| 29 | |||
| 30 | 8 | work_allocator::arena:: | |
| 31 | 8 | arena(std::size_t capacity) | |
| 32 | 8 | : prev_(nullptr) | |
| 33 | 8 | , next_(nullptr) | |
| 34 | 8 | , base_(std::malloc(capacity)) | |
| 35 | 8 | , capacity_(capacity) | |
| 36 | 8 | , offset_(capacity) | |
| 37 | 8 | , count_(0) | |
| 38 | { | ||
| 39 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(!base_) |
| 40 | ✗ | throw std::bad_alloc(); | |
| 41 | 8 | } | |
| 42 | |||
| 43 | bool | ||
| 44 | 38 | work_allocator::arena:: | |
| 45 | owns(void* p) const noexcept | ||
| 46 | { | ||
| 47 | std::less<char const*> cmp; | ||
| 48 | 38 | auto* cp = static_cast<char const*>(p); | |
| 49 | 38 | auto* base = static_cast<char const*>(base_); | |
| 50 | // cp >= base && cp < base + capacity_ | ||
| 51 |
2/4✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 38 times.
✗ Branch 5 not taken.
|
38 | return !cmp(cp, base) && cmp(cp, base + capacity_); |
| 52 | } | ||
| 53 | |||
| 54 | void* | ||
| 55 | 38 | work_allocator::arena:: | |
| 56 | allocate(std::size_t size, std::size_t align) noexcept | ||
| 57 | { | ||
| 58 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
|
38 | if(offset_ < size) |
| 59 | ✗ | return nullptr; | |
| 60 | |||
| 61 | 38 | std::size_t aligned = (offset_ - size) & ~(align - 1); | |
| 62 | |||
| 63 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
|
38 | if(aligned > offset_) |
| 64 | ✗ | return nullptr; | |
| 65 | |||
| 66 | 38 | offset_ = aligned; | |
| 67 | 38 | ++count_; | |
| 68 | 38 | return static_cast<char*>(base_) + offset_; | |
| 69 | } | ||
| 70 | |||
| 71 | void | ||
| 72 | 38 | work_allocator::arena:: | |
| 73 | deallocate(void* /*p*/, std::size_t /*size*/, std::size_t /*align*/) noexcept | ||
| 74 | { | ||
| 75 | 38 | --count_; | |
| 76 | 38 | } | |
| 77 | |||
| 78 | void | ||
| 79 | ✗ | work_allocator::arena:: | |
| 80 | reset() noexcept | ||
| 81 | { | ||
| 82 | ✗ | offset_ = capacity_; | |
| 83 | ✗ | count_ = 0; | |
| 84 | ✗ | } | |
| 85 | |||
| 86 | //------------------------------------------------------------------------------ | ||
| 87 | // | ||
| 88 | // work_allocator | ||
| 89 | // | ||
| 90 | //------------------------------------------------------------------------------ | ||
| 91 | |||
| 92 | 12 | work_allocator:: | |
| 93 | ~work_allocator() | ||
| 94 | { | ||
| 95 | 12 | arena* a = head_; | |
| 96 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 12 times.
|
20 | while(a) |
| 97 | { | ||
| 98 | 8 | arena* next = a->next_; | |
| 99 |
1/2✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
|
8 | delete a; |
| 100 | 8 | a = next; | |
| 101 | } | ||
| 102 | 12 | } | |
| 103 | |||
| 104 | 12 | work_allocator:: | |
| 105 | work_allocator( | ||
| 106 | std::size_t min_size, | ||
| 107 | std::size_t max_size, | ||
| 108 | 12 | std::size_t keep_empty) | |
| 109 | 12 | : head_(nullptr) | |
| 110 | 12 | , tail_(nullptr) | |
| 111 | 12 | , arena_count_(0) | |
| 112 | 12 | , next_size_(min_size) | |
| 113 | 12 | , min_size_(min_size) | |
| 114 | 12 | , max_size_(max_size) | |
| 115 | 12 | , keep_empty_(keep_empty) | |
| 116 | { | ||
| 117 | 12 | } | |
| 118 | |||
| 119 | void* | ||
| 120 | 38 | work_allocator:: | |
| 121 | allocate(std::size_t size, std::size_t align) | ||
| 122 | { | ||
| 123 | // Always allocate from tail (active arena) | ||
| 124 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8 times.
|
38 | if(tail_) |
| 125 | { | ||
| 126 |
1/2✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
|
30 | if(void* p = tail_->allocate(size, align)) |
| 127 | 30 | return p; | |
| 128 | } | ||
| 129 | |||
| 130 | // Active arena full or none exists. | ||
| 131 | // Try recycling a parked arena to preserve allocation order. | ||
| 132 | 8 | arena* fresh = find_parked(); | |
| 133 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(fresh) |
| 134 | { | ||
| 135 | ✗ | unlink(fresh); | |
| 136 | ✗ | fresh->reset(); | |
| 137 | ✗ | link_at_tail(fresh); | |
| 138 | } | ||
| 139 | else | ||
| 140 | { | ||
| 141 | 8 | std::size_t arena_size = next_size_; | |
| 142 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(arena_size < size + align) |
| 143 | ✗ | arena_size = size + align; | |
| 144 | |||
| 145 |
1/3✓ Branch 2 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
8 | fresh = new arena(arena_size); |
| 146 | 8 | link_at_tail(fresh); | |
| 147 | |||
| 148 |
1/2✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
|
8 | if(next_size_ < max_size_) |
| 149 | { | ||
| 150 | 8 | next_size_ *= 2; | |
| 151 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(next_size_ > max_size_) |
| 152 | ✗ | next_size_ = max_size_; | |
| 153 | } | ||
| 154 | } | ||
| 155 | |||
| 156 | 8 | void* p = tail_->allocate(size, align); | |
| 157 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(!p) |
| 158 | ✗ | throw std::bad_alloc(); | |
| 159 | 8 | return p; | |
| 160 | } | ||
| 161 | |||
| 162 | void | ||
| 163 | 38 | work_allocator:: | |
| 164 | deallocate(void* p, std::size_t size, std::size_t align) noexcept | ||
| 165 | { | ||
| 166 | 38 | arena* a = find_arena(p); | |
| 167 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
|
38 | if(!a) |
| 168 | ✗ | return; | |
| 169 | |||
| 170 | 38 | a->deallocate(p, size, align); | |
| 171 | |||
| 172 | // Prune when a non-active arena empties | ||
| 173 |
4/6✓ Branch 1 taken 9 times.
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 38 times.
|
38 | if(a->empty() && a != tail_) |
| 174 | ✗ | prune(); | |
| 175 | } | ||
| 176 | |||
| 177 | void | ||
| 178 | 8 | work_allocator:: | |
| 179 | link_at_tail(arena* a) noexcept | ||
| 180 | { | ||
| 181 | 8 | a->prev_ = tail_; | |
| 182 | 8 | a->next_ = nullptr; | |
| 183 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
|
8 | if(tail_) |
| 184 | ✗ | tail_->next_ = a; | |
| 185 | else | ||
| 186 | 8 | head_ = a; | |
| 187 | 8 | tail_ = a; | |
| 188 | 8 | ++arena_count_; | |
| 189 | 8 | } | |
| 190 | |||
| 191 | void | ||
| 192 | ✗ | work_allocator:: | |
| 193 | unlink(arena* a) noexcept | ||
| 194 | { | ||
| 195 | ✗ | if(a->prev_) | |
| 196 | ✗ | a->prev_->next_ = a->next_; | |
| 197 | else | ||
| 198 | ✗ | head_ = a->next_; | |
| 199 | |||
| 200 | ✗ | if(a->next_) | |
| 201 | ✗ | a->next_->prev_ = a->prev_; | |
| 202 | else | ||
| 203 | ✗ | tail_ = a->prev_; | |
| 204 | |||
| 205 | ✗ | a->prev_ = nullptr; | |
| 206 | ✗ | a->next_ = nullptr; | |
| 207 | ✗ | --arena_count_; | |
| 208 | ✗ | } | |
| 209 | |||
| 210 | work_allocator::arena* | ||
| 211 | 38 | work_allocator:: | |
| 212 | find_arena(void* p) noexcept | ||
| 213 | { | ||
| 214 |
1/2✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
|
38 | for(arena* a = head_; a; a = a->next_) |
| 215 | { | ||
| 216 |
1/2✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
|
38 | if(a->owns(p)) |
| 217 | 38 | return a; | |
| 218 | } | ||
| 219 | ✗ | return nullptr; | |
| 220 | } | ||
| 221 | |||
| 222 | work_allocator::arena* | ||
| 223 | 8 | work_allocator:: | |
| 224 | find_parked() noexcept | ||
| 225 | { | ||
| 226 | // Search from oldest, skip the active arena (tail) | ||
| 227 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
8 | for(arena* a = head_; a && a != tail_; a = a->next_) |
| 228 | { | ||
| 229 | ✗ | if(a->empty()) | |
| 230 | ✗ | return a; | |
| 231 | } | ||
| 232 | 8 | return nullptr; | |
| 233 | } | ||
| 234 | |||
| 235 | void | ||
| 236 | ✗ | work_allocator:: | |
| 237 | prune() noexcept | ||
| 238 | { | ||
| 239 | // Count parked (empty non-active) arenas | ||
| 240 | ✗ | std::size_t parked_count = 0; | |
| 241 | ✗ | for(arena* a = head_; a && a != tail_; a = a->next_) | |
| 242 | { | ||
| 243 | ✗ | if(a->empty()) | |
| 244 | ✗ | ++parked_count; | |
| 245 | } | ||
| 246 | |||
| 247 | // Delete excess parked arenas from the front | ||
| 248 | ✗ | arena* a = head_; | |
| 249 | ✗ | while(a && a != tail_ && parked_count > keep_empty_) | |
| 250 | { | ||
| 251 | ✗ | arena* next = a->next_; | |
| 252 | ✗ | if(a->empty()) | |
| 253 | { | ||
| 254 | ✗ | unlink(a); | |
| 255 | ✗ | delete a; | |
| 256 | ✗ | --parked_count; | |
| 257 | } | ||
| 258 | ✗ | a = next; | |
| 259 | } | ||
| 260 | |||
| 261 | // Shrink next_size if we're back to minimal state | ||
| 262 | ✗ | if(arena_count_ <= 1) | |
| 263 | ✗ | next_size_ = min_size_; | |
| 264 | ✗ | } | |
| 265 | |||
| 266 | } // capy | ||
| 267 | } // boost | ||
| 268 | |||
| 269 |