-
-
Notifications
You must be signed in to change notification settings - Fork 701
/
bucketizer.d
335 lines (305 loc) · 10.6 KB
/
bucketizer.d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
// Written in the D programming language.
/**
Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/bucketizer.d)
*/
module std.experimental.allocator.building_blocks.bucketizer;
/**
A `Bucketizer` uses distinct allocators for handling allocations of sizes in
the intervals $(D [min, min + step - 1]), $(D [min + step, min + 2 * step - 1]),
$(D [min + 2 * step, min + 3 * step - 1]), `...`, $(D [max - step + 1, max]).
`Bucketizer` holds a fixed-size array of allocators and dispatches calls to
them appropriately. The size of the array is $(D (max + 1 - min) / step), which
must be an exact division.
Allocations for sizes smaller than `min` or larger than `max` are illegal
for `Bucketizer`. To handle them separately, `Segregator` may be of use.
*/
struct Bucketizer(Allocator, size_t min, size_t max, size_t step)
{
import common = std.experimental.allocator.common : roundUpToMultipleOf,
alignedAt;
import std.traits : hasMember;
import std.typecons : Ternary;
static assert((max - (min - 1)) % step == 0,
"Invalid limits when instantiating " ~ Bucketizer.stringof);
// state
/**
The array of allocators is publicly available for e.g. initialization and
inspection.
*/
Allocator[(max + 1 - min) / step] buckets;
pure nothrow @safe @nogc
private Allocator* allocatorFor(size_t n)
{
const i = (n - min) / step;
return i < buckets.length ? &buckets[i] : null;
}
/**
The alignment offered is the same as `Allocator.alignment`.
*/
enum uint alignment = Allocator.alignment;
/**
Rounds up to the maximum size of the bucket in which `bytes` falls.
*/
pure nothrow @safe @nogc
size_t goodAllocSize(size_t bytes) const
{
// round up bytes such that bytes - min + 1 is a multiple of step
assert(bytes >= min);
const min_1 = min - 1;
return min_1 + roundUpToMultipleOf(bytes - min_1, step);
}
/**
Directs the call to either one of the `buckets` allocators.
*/
void[] allocate(size_t bytes)
{
if (!bytes) return null;
if (auto a = allocatorFor(bytes))
{
const actual = goodAllocSize(bytes);
auto result = a.allocate(actual);
return result.ptr ? result.ptr[0 .. bytes] : null;
}
return null;
}
/**
Allocates the requested `bytes` of memory with specified `alignment`.
Directs the call to either one of the `buckets` allocators. Defined only
if `Allocator` defines `alignedAllocate`.
*/
static if (hasMember!(Allocator, "alignedAllocate"))
void[] alignedAllocate(size_t bytes, uint alignment)
{
if (!bytes) return null;
if (auto a = allocatorFor(bytes))
{
const actual = goodAllocSize(bytes);
auto result = a.alignedAllocate(actual, alignment);
return result !is null ? (() @trusted => (&result[0])[0 .. bytes])() : null;
}
return null;
}
/**
This method allows expansion within the respective bucket range. It succeeds
if both `b.length` and $(D b.length + delta) fall in a range of the form
$(D [min + k * step, min + (k + 1) * step - 1]).
*/
bool expand(ref void[] b, size_t delta)
{
if (!b || delta == 0) return delta == 0;
assert(b.length >= min && b.length <= max);
const available = goodAllocSize(b.length);
const desired = b.length + delta;
if (available < desired) return false;
b = (() @trusted => b.ptr[0 .. desired])();
return true;
}
/**
This method allows reallocation within the respective bucket range. If both
`b.length` and `size` fall in a range of the form $(D [min + k *
step, min + (k + 1) * step - 1]), then reallocation is in place. Otherwise,
reallocation with moving is attempted.
*/
bool reallocate(ref void[] b, size_t size)
{
if (size == 0)
{
deallocate(b);
b = null;
return true;
}
if (size >= b.length && expand(b, size - b.length))
{
return true;
}
assert(b.length >= min && b.length <= max);
if (goodAllocSize(size) == goodAllocSize(b.length))
{
b = b.ptr[0 .. size];
return true;
}
// Move cross buckets
return common.reallocate(this, b, size);
}
/**
Similar to `reallocate`, with alignment. Defined only if `Allocator`
defines `alignedReallocate`.
*/
static if (hasMember!(Allocator, "alignedReallocate"))
bool alignedReallocate(ref void[] b, size_t size, uint a)
{
if (size == 0)
{
deallocate(b);
b = null;
return true;
}
if (size >= b.length && b.ptr.alignedAt(a) && expand(b, size - b.length))
{
return true;
}
assert(b.length >= min && b.length <= max);
if (goodAllocSize(size) == goodAllocSize(b.length) && b.ptr.alignedAt(a))
{
b = b.ptr[0 .. size];
return true;
}
// Move cross buckets
return common.alignedReallocate(this, b, size, a);
}
/**
Defined only if `Allocator` defines `owns`. Finds the owner of `b` and forwards the call to it.
*/
static if (hasMember!(Allocator, "owns"))
Ternary owns(void[] b)
{
if (!b.ptr) return Ternary.no;
if (auto a = allocatorFor(b.length))
{
const actual = goodAllocSize(b.length);
return a.owns(b.ptr[0 .. actual]);
}
return Ternary.no;
}
/**
This method is only defined if `Allocator` defines `deallocate`.
*/
static if (hasMember!(Allocator, "deallocate"))
bool deallocate(void[] b)
{
if (!b.ptr) return true;
if (auto a = allocatorFor(b.length))
{
a.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);
}
return true;
}
/**
This method is only defined if all allocators involved define $(D
deallocateAll), and calls it for each bucket in turn. Returns `true` if all
allocators could deallocate all.
*/
static if (hasMember!(Allocator, "deallocateAll"))
bool deallocateAll()
{
bool result = true;
foreach (ref a; buckets)
{
if (!a.deallocateAll()) result = false;
}
return result;
}
/**
This method is only defined if all allocators involved define $(D
resolveInternalPointer), and tries it for each bucket in turn.
*/
static if (hasMember!(Allocator, "resolveInternalPointer"))
Ternary resolveInternalPointer(const void* p, ref void[] result)
{
foreach (ref a; buckets)
{
Ternary r = a.resolveInternalPointer(p, result);
if (r == Ternary.yes) return r;
}
return Ternary.no;
}
}
///
@system unittest
{
import std.algorithm.comparison : max;
import std.experimental.allocator.building_blocks.allocator_list : AllocatorList;
import std.experimental.allocator.building_blocks.free_list : FreeList;
import std.experimental.allocator.building_blocks.region : Region;
import std.experimental.allocator.common : unbounded;
import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Ternary;
Bucketizer!(
FreeList!(
AllocatorList!(
(size_t n) => Region!Mallocator(max(n, 1024 * 1024))),
0, unbounded),
65, 512, 64) a;
auto b = a.allocate(400);
assert(b.length == 400);
assert(a.owns(b) == Ternary.yes);
a.deallocate(b);
}
@system unittest
{
import std.algorithm.comparison : max;
import std.experimental.allocator.building_blocks.allocator_list : AllocatorList;
import std.experimental.allocator.building_blocks.free_list : FreeList;
import std.experimental.allocator.building_blocks.region : Region;
import std.experimental.allocator.common : unbounded;
import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Ternary;
Bucketizer!(
FreeList!(
AllocatorList!(
(size_t n) => Region!Mallocator(max(n, 1024 * 1024)), Mallocator),
0, unbounded),
65, 512, 64) a;
assert((() pure nothrow @safe @nogc => a.goodAllocSize(65))() == 128);
auto b = a.allocate(100);
assert(b.length == 100);
// Make reallocate use extend
assert((() nothrow @nogc => a.reallocate(b, 101))());
assert(b.length == 101);
// Move cross buckets
assert((() nothrow @nogc => a.reallocate(b, 200))());
assert(b.length == 200);
// Free through realloc
assert((() nothrow @nogc => a.reallocate(b, 0))());
assert(b is null);
// Ensure deallocate inherits from parent allocators
assert((() nothrow @nogc => a.deallocate(b))());
assert((() nothrow @nogc => a.deallocateAll())());
}
// Test alignedAllocate
@system unittest
{
import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
import std.experimental.allocator.gc_allocator : GCAllocator;
Bucketizer!(BitmappedBlock!(64, 8, GCAllocator), 65, 512, 64) a;
foreach (ref bucket; a.buckets)
{
bucket = BitmappedBlock!(64, 8, GCAllocator)(new ubyte[1024]);
}
auto b = a.alignedAllocate(100, 16);
assert(b.length == 100);
assert(a.alignedAllocate(42, 16) is null);
assert(a.alignedAllocate(0, 16) is null);
assert((() pure nothrow @safe @nogc => a.expand(b, 0))());
assert(b.length == 100);
assert((() pure nothrow @safe @nogc => a.expand(b, 28))());
assert(b.length == 128);
assert((() pure nothrow @safe @nogc => !a.expand(b, 1))());
}
@system unittest
{
import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
import std.experimental.allocator.gc_allocator : GCAllocator;
Bucketizer!(BitmappedBlock!(64, 8, GCAllocator), 1, 512, 64) a;
foreach (ref bucket; a.buckets)
{
bucket = BitmappedBlock!(64, 8, GCAllocator)(new ubyte[1024]);
}
auto b = a.alignedAllocate(1, 4);
assert(b.length == 1);
// Make reallocate use extend
assert(a.alignedReallocate(b, 11, 4));
assert(b.length == 11);
// Make reallocate use use realloc because of alignment change
assert(a.alignedReallocate(b, 21, 16));
assert(b.length == 21);
// Make reallocate use extend
assert(a.alignedReallocate(b, 22, 16));
assert(b.length == 22);
// Move cross buckets
assert(a.alignedReallocate(b, 101, 16));
assert(b.length == 101);
// Free through realloc
assert(a.alignedReallocate(b, 0, 16));
assert(b is null);
}