| 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 | 5 | work_allocator::arena:: | |
| 25 | ~arena() | ||
| 26 | { | ||
| 27 | 5 | std::free(base_); | |
| 28 | 5 | } | |
| 29 | |||
| 30 | 5 | work_allocator::arena:: | |
| 31 | 5 | arena(std::size_t capacity) | |
| 32 | 5 | : prev_(nullptr) | |
| 33 | 5 | , next_(nullptr) | |
| 34 | 5 | , base_(std::malloc(capacity)) | |
| 35 | 5 | , capacity_(capacity) | |
| 36 | 5 | , offset_(capacity) | |
| 37 | 5 | , count_(0) | |
| 38 | { | ||
| 39 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if(!base_) |
| 40 | ✗ | throw std::bad_alloc(); | |
| 41 | 5 | } | |
| 42 | |||
| 43 | bool | ||
| 44 | 90 | work_allocator::arena:: | |
| 45 | owns(void* p) const noexcept | ||
| 46 | { | ||
| 47 | std::less<char const*> cmp; | ||
| 48 | 90 | auto* cp = static_cast<char const*>(p); | |
| 49 | 90 | auto* base = static_cast<char const*>(base_); | |
| 50 | // cp >= base && cp < base + capacity_ | ||
| 51 |
3/4✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 83 times.
✓ Branch 5 taken 7 times.
|
90 | return !cmp(cp, base) && cmp(cp, base + capacity_); |
| 52 | } | ||
| 53 | |||
| 54 | void* | ||
| 55 | 84 | work_allocator::arena:: | |
| 56 | allocate(std::size_t size, std::size_t align) noexcept | ||
| 57 | { | ||
| 58 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 83 times.
|
84 | if(offset_ < size) |
| 59 | 1 | return nullptr; | |
| 60 | |||
| 61 | 83 | std::size_t aligned = (offset_ - size) & ~(align - 1); | |
| 62 | |||
| 63 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 83 times.
|
83 | if(aligned > offset_) |
| 64 | ✗ | return nullptr; | |
| 65 | |||
| 66 | 83 | offset_ = aligned; | |
| 67 | 83 | ++count_; | |
| 68 | 83 | return static_cast<char*>(base_) + offset_; | |
| 69 | } | ||
| 70 | |||
| 71 | void | ||
| 72 | 83 | work_allocator::arena:: | |
| 73 | deallocate(void* /*p*/, std::size_t /*size*/, std::size_t /*align*/) noexcept | ||
| 74 | { | ||
| 75 | 83 | --count_; | |
| 76 | 83 | } | |
| 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 | 14 | work_allocator:: | |
| 93 | ~work_allocator() | ||
| 94 | { | ||
| 95 | 14 | arena* a = head_; | |
| 96 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 14 times.
|
19 | while(a) |
| 97 | { | ||
| 98 | 5 | arena* next = a->next_; | |
| 99 |
1/2✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
|
5 | delete a; |
| 100 | 5 | a = next; | |
| 101 | } | ||
| 102 | 14 | } | |
| 103 | |||
| 104 | 14 | work_allocator:: | |
| 105 | work_allocator( | ||
| 106 | std::size_t min_size, | ||
| 107 | std::size_t max_size, | ||
| 108 | 14 | std::size_t keep_empty) | |
| 109 | 14 | : head_(nullptr) | |
| 110 | 14 | , tail_(nullptr) | |
| 111 | 14 | , arena_count_(0) | |
| 112 | 14 | , next_size_(min_size) | |
| 113 | 14 | , min_size_(min_size) | |
| 114 | 14 | , max_size_(max_size) | |
| 115 | 14 | , keep_empty_(keep_empty) | |
| 116 | { | ||
| 117 | 14 | } | |
| 118 | |||
| 119 | void* | ||
| 120 | 83 | 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 79 times.
✓ Branch 1 taken 4 times.
|
83 | if(tail_) |
| 125 | { | ||
| 126 |
2/2✓ Branch 1 taken 78 times.
✓ Branch 2 taken 1 times.
|
79 | if(void* p = tail_->allocate(size, align)) |
| 127 | 78 | return p; | |
| 128 | } | ||
| 129 | |||
| 130 | // Active arena full or none exists. | ||
| 131 | // Try recycling a parked arena to preserve allocation order. | ||
| 132 | 5 | arena* fresh = find_parked(); | |
| 133 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if(fresh) |
| 134 | { | ||
| 135 | ✗ | unlink(fresh); | |
| 136 | ✗ | fresh->reset(); | |
| 137 | ✗ | link_at_tail(fresh); | |
| 138 | } | ||
| 139 | else | ||
| 140 | { | ||
| 141 | 5 | std::size_t arena_size = next_size_; | |
| 142 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if(arena_size < size + align) |
| 143 | ✗ | arena_size = size + align; | |
| 144 | |||
| 145 |
1/3✓ Branch 2 taken 5 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
5 | fresh = new arena(arena_size); |
| 146 | 5 | link_at_tail(fresh); | |
| 147 | |||
| 148 |
1/2✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
|
5 | if(next_size_ < max_size_) |
| 149 | { | ||
| 150 | 5 | next_size_ *= 2; | |
| 151 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if(next_size_ > max_size_) |
| 152 | ✗ | next_size_ = max_size_; | |
| 153 | } | ||
| 154 | } | ||
| 155 | |||
| 156 | 5 | void* p = tail_->allocate(size, align); | |
| 157 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if(!p) |
| 158 | ✗ | throw std::bad_alloc(); | |
| 159 | 5 | return p; | |
| 160 | } | ||
| 161 | |||
| 162 | void | ||
| 163 | 83 | work_allocator:: | |
| 164 | deallocate(void* p, std::size_t size, std::size_t align) noexcept | ||
| 165 | { | ||
| 166 | 83 | arena* a = find_arena(p); | |
| 167 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 83 times.
|
83 | if(!a) |
| 168 | ✗ | return; | |
| 169 | |||
| 170 | 83 | a->deallocate(p, size, align); | |
| 171 | |||
| 172 | // Prune when a non-active arena empties | ||
| 173 |
6/6✓ Branch 1 taken 13 times.
✓ Branch 2 taken 70 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 12 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 82 times.
|
83 | if(a->empty() && a != tail_) |
| 174 | 1 | prune(); | |
| 175 | } | ||
| 176 | |||
| 177 | void | ||
| 178 | 5 | work_allocator:: | |
| 179 | link_at_tail(arena* a) noexcept | ||
| 180 | { | ||
| 181 | 5 | a->prev_ = tail_; | |
| 182 | 5 | a->next_ = nullptr; | |
| 183 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
|
5 | if(tail_) |
| 184 | 1 | tail_->next_ = a; | |
| 185 | else | ||
| 186 | 4 | head_ = a; | |
| 187 | 5 | tail_ = a; | |
| 188 | 5 | ++arena_count_; | |
| 189 | 5 | } | |
| 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 | 83 | work_allocator:: | |
| 212 | find_arena(void* p) noexcept | ||
| 213 | { | ||
| 214 |
1/2✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
|
90 | for(arena* a = head_; a; a = a->next_) |
| 215 | { | ||
| 216 |
2/2✓ Branch 1 taken 83 times.
✓ Branch 2 taken 7 times.
|
90 | if(a->owns(p)) |
| 217 | 83 | return a; | |
| 218 | } | ||
| 219 | ✗ | return nullptr; | |
| 220 | } | ||
| 221 | |||
| 222 | work_allocator::arena* | ||
| 223 | 5 | work_allocator:: | |
| 224 | find_parked() noexcept | ||
| 225 | { | ||
| 226 | // Search from oldest, skip the active arena (tail) | ||
| 227 |
3/4✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
|
5 | for(arena* a = head_; a && a != tail_; a = a->next_) |
| 228 | { | ||
| 229 | ✗ | if(a->empty()) | |
| 230 | ✗ | return a; | |
| 231 | } | ||
| 232 | 5 | return nullptr; | |
| 233 | } | ||
| 234 | |||
| 235 | void | ||
| 236 | 1 | work_allocator:: | |
| 237 | prune() noexcept | ||
| 238 | { | ||
| 239 | // Count parked (empty non-active) arenas | ||
| 240 | 1 | std::size_t parked_count = 0; | |
| 241 |
3/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
|
2 | for(arena* a = head_; a && a != tail_; a = a->next_) |
| 242 | { | ||
| 243 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | if(a->empty()) |
| 244 | 1 | ++parked_count; | |
| 245 | } | ||
| 246 | |||
| 247 | // Delete excess parked arenas from the front | ||
| 248 | 1 | arena* a = head_; | |
| 249 |
3/6✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
|
1 | 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 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | if(arena_count_ <= 1) |
| 263 | ✗ | next_size_ = min_size_; | |
| 264 | 1 | } | |
| 265 | |||
| 266 | } // capy | ||
| 267 | } // boost | ||
| 268 | |||
| 269 |