Line data Source code
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 5 : if(!base_)
40 0 : 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 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 84 : if(offset_ < size)
59 1 : return nullptr;
60 :
61 83 : std::size_t aligned = (offset_ - size) & ~(align - 1);
62 :
63 83 : if(aligned > offset_)
64 0 : 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 0 : work_allocator::arena::
80 : reset() noexcept
81 : {
82 0 : offset_ = capacity_;
83 0 : count_ = 0;
84 0 : }
85 :
86 : //------------------------------------------------------------------------------
87 : //
88 : // work_allocator
89 : //
90 : //------------------------------------------------------------------------------
91 :
92 14 : work_allocator::
93 : ~work_allocator()
94 : {
95 14 : arena* a = head_;
96 19 : while(a)
97 : {
98 5 : arena* next = a->next_;
99 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 83 : if(tail_)
125 : {
126 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 5 : if(fresh)
134 : {
135 0 : unlink(fresh);
136 0 : fresh->reset();
137 0 : link_at_tail(fresh);
138 : }
139 : else
140 : {
141 5 : std::size_t arena_size = next_size_;
142 5 : if(arena_size < size + align)
143 0 : arena_size = size + align;
144 :
145 5 : fresh = new arena(arena_size);
146 5 : link_at_tail(fresh);
147 :
148 5 : if(next_size_ < max_size_)
149 : {
150 5 : next_size_ *= 2;
151 5 : if(next_size_ > max_size_)
152 0 : next_size_ = max_size_;
153 : }
154 : }
155 :
156 5 : void* p = tail_->allocate(size, align);
157 5 : if(!p)
158 0 : 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 83 : if(!a)
168 0 : return;
169 :
170 83 : a->deallocate(p, size, align);
171 :
172 : // Prune when a non-active arena empties
173 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 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 0 : work_allocator::
193 : unlink(arena* a) noexcept
194 : {
195 0 : if(a->prev_)
196 0 : a->prev_->next_ = a->next_;
197 : else
198 0 : head_ = a->next_;
199 :
200 0 : if(a->next_)
201 0 : a->next_->prev_ = a->prev_;
202 : else
203 0 : tail_ = a->prev_;
204 :
205 0 : a->prev_ = nullptr;
206 0 : a->next_ = nullptr;
207 0 : --arena_count_;
208 0 : }
209 :
210 : work_allocator::arena*
211 83 : work_allocator::
212 : find_arena(void* p) noexcept
213 : {
214 90 : for(arena* a = head_; a; a = a->next_)
215 : {
216 90 : if(a->owns(p))
217 83 : return a;
218 : }
219 0 : 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 5 : for(arena* a = head_; a && a != tail_; a = a->next_)
228 : {
229 0 : if(a->empty())
230 0 : 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 2 : for(arena* a = head_; a && a != tail_; a = a->next_)
242 : {
243 1 : if(a->empty())
244 1 : ++parked_count;
245 : }
246 :
247 : // Delete excess parked arenas from the front
248 1 : arena* a = head_;
249 1 : while(a && a != tail_ && parked_count > keep_empty_)
250 : {
251 0 : arena* next = a->next_;
252 0 : if(a->empty())
253 : {
254 0 : unlink(a);
255 0 : delete a;
256 0 : --parked_count;
257 : }
258 0 : a = next;
259 : }
260 :
261 : // Shrink next_size if we're back to minimal state
262 1 : if(arena_count_ <= 1)
263 0 : next_size_ = min_size_;
264 1 : }
265 :
266 : } // capy
267 : } // boost
268 :
|
