1 ///
2 module std.experimental.allocator.building_blocks.bucketizer;
3
4 /**
5
6 A $(D Bucketizer) uses distinct allocators for handling allocations of sizes in
7 the intervals $(D [min, min + step - 1]), $(D [min + step, min + 2 * step - 1]),
8 $(D [min + 2 * step, min + 3 * step - 1]), $(D ...), $(D [max - step + 1, max]).
9
10 $(D Bucketizer) holds a fixed-size array of allocators and dispatches calls to
11 them appropriately. The size of the array is $(D (max + 1 - min) / step), which
12 must be an exact division.
13
14 Allocations for sizes smaller than $(D min) or larger than $(D max) are illegal
15 for $(D Bucketizer). To handle them separately, $(D Segregator) may be of use.
16
17 */
Bucketizer(Allocator,size_t min,size_t max,size_t step)18 struct Bucketizer(Allocator, size_t min, size_t max, size_t step)
19 {
20 import common = std.experimental.allocator.common : roundUpToMultipleOf;
21 import std.traits : hasMember;
22 import std.typecons : Ternary;
23
24 static assert((max - (min - 1)) % step == 0,
25 "Invalid limits when instantiating " ~ Bucketizer.stringof);
26
27 // state
28 /**
29 The array of allocators is publicly available for e.g. initialization and
30 inspection.
31 */
32 Allocator[(max + 1 - min) / step] buckets;
33
34 private Allocator* allocatorFor(size_t n)
35 {
36 const i = (n - min) / step;
37 return i < buckets.length ? buckets.ptr + i : null;
38 }
39
40 /**
41 The alignment offered is the same as $(D Allocator.alignment).
42 */
43 enum uint alignment = Allocator.alignment;
44
45 /**
46 Rounds up to the maximum size of the bucket in which $(D bytes) falls.
47 */
48 size_t goodAllocSize(size_t bytes) const
49 {
50 // round up bytes such that bytes - min + 1 is a multiple of step
51 assert(bytes >= min);
52 const min_1 = min - 1;
53 return min_1 + roundUpToMultipleOf(bytes - min_1, step);
54 }
55
56 /**
57 Directs the call to either one of the $(D buckets) allocators.
58 */
59 void[] allocate(size_t bytes)
60 {
61 if (!bytes) return null;
62 if (auto a = allocatorFor(bytes))
63 {
64 const actual = goodAllocSize(bytes);
65 auto result = a.allocate(actual);
66 return result.ptr ? result.ptr[0 .. bytes] : null;
67 }
68 return null;
69 }
70
71 /**
72 Directs the call to either one of the $(D buckets) allocators. Defined only
73 if `Allocator` defines `alignedAllocate`.
74 */
75 static if (hasMember!(Allocator, "alignedAllocate"))
76 void[] alignedAllocate(size_t bytes, uint a)
77 {
78 if (!bytes) return null;
79 if (auto a = allocatorFor(b.length))
80 {
81 const actual = goodAllocSize(bytes);
82 auto result = a.alignedAllocate(actual);
83 return result.ptr ? result.ptr[0 .. bytes] : null;
84 }
85 return null;
86 }
87
88 /**
89 This method allows expansion within the respective bucket range. It succeeds
90 if both $(D b.length) and $(D b.length + delta) fall in a range of the form
91 $(D [min + k * step, min + (k + 1) * step - 1]).
92 */
93 bool expand(ref void[] b, size_t delta)
94 {
95 if (!b.ptr) return delta == 0;
96 assert(b.length >= min && b.length <= max);
97 const available = goodAllocSize(b.length);
98 const desired = b.length + delta;
99 if (available < desired) return false;
100 b = b.ptr[0 .. desired];
101 return true;
102 }
103
104 /**
105 This method allows reallocation within the respective bucket range. If both
106 $(D b.length) and $(D size) fall in a range of the form $(D [min + k *
107 step, min + (k + 1) * step - 1]), then reallocation is in place. Otherwise,
108 reallocation with moving is attempted.
109 */
110 bool reallocate(ref void[] b, size_t size)
111 {
112 if (size == 0)
113 {
114 deallocate(b);
115 b = null;
116 return true;
117 }
118 if (size >= b.length)
119 {
120 return expand(b, size - b.length);
121 }
122 assert(b.length >= min && b.length <= max);
123 if (goodAllocSize(size) == goodAllocSize(b.length))
124 {
125 b = b.ptr[0 .. size];
126 return true;
127 }
128 // Move cross buckets
129 return common.reallocate(this, b, size);
130 }
131
132 /**
133 Similar to `reallocate`, with alignment. Defined only if `Allocator`
134 defines `alignedReallocate`.
135 */
136 static if (hasMember!(Allocator, "alignedReallocate"))
137 bool alignedReallocate(ref void[] b, size_t size, uint a)
138 {
139 if (size == 0)
140 {
141 deallocate(b);
142 b = null;
143 return true;
144 }
145 if (size >= b.length)
146 {
147 return expand(b, size - b.length);
148 }
149 assert(b.length >= min && b.length <= max);
150 if (goodAllocSize(size) == goodAllocSize(b.length))
151 {
152 b = b.ptr[0 .. size];
153 return true;
154 }
155 // Move cross buckets
156 return .alignedReallocate(this, b, size, a);
157 }
158
159 /**
160 Defined only if `Allocator` defines `owns`. Finds the owner of `b` and forwards the call to it.
161 */
162 static if (hasMember!(Allocator, "owns"))
163 Ternary owns(void[] b)
164 {
165 if (!b.ptr) return Ternary.no;
166 if (auto a = allocatorFor(b.length))
167 {
168 const actual = goodAllocSize(b.length);
169 return a.owns(b.ptr[0 .. actual]);
170 }
171 return Ternary.no;
172 }
173
174 /**
175 This method is only defined if $(D Allocator) defines $(D deallocate).
176 */
177 static if (hasMember!(Allocator, "deallocate"))
178 bool deallocate(void[] b)
179 {
180 if (!b.ptr) return true;
181 if (auto a = allocatorFor(b.length))
182 {
183 a.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);
184 }
185 return true;
186 }
187
188 /**
189 This method is only defined if all allocators involved define $(D
190 deallocateAll), and calls it for each bucket in turn. Returns `true` if all
191 allocators could deallocate all.
192 */
193 static if (hasMember!(Allocator, "deallocateAll"))
194 bool deallocateAll()
195 {
196 bool result = true;
197 foreach (ref a; buckets)
198 {
199 if (!a.deallocateAll()) result = false;
200 }
201 return result;
202 }
203
204 /**
205 This method is only defined if all allocators involved define $(D
206 resolveInternalPointer), and tries it for each bucket in turn.
207 */
208 static if (hasMember!(Allocator, "resolveInternalPointer"))
209 Ternary resolveInternalPointer(const void* p, ref void[] result)
210 {
211 foreach (ref a; buckets)
212 {
213 Ternary r = a.resolveInternalPointer(p, result);
214 if (r == Ternary.yes) return r;
215 }
216 return Ternary.no;
217 }
218 }
219
220 ///
221 @system unittest
222 {
223 import std.algorithm.comparison : max;
224 import std.experimental.allocator.building_blocks.allocator_list : AllocatorList;
225 import std.experimental.allocator.building_blocks.free_list : FreeList;
226 import std.experimental.allocator.building_blocks.region : Region;
227 import std.experimental.allocator.common : unbounded;
228 import std.experimental.allocator.mallocator : Mallocator;
229 import std.typecons : Ternary;
230 Bucketizer!(
231 FreeList!(
232 AllocatorList!(
233 (size_t n) => Region!Mallocator(max(n, 1024 * 1024))),
234 0, unbounded),
235 65, 512, 64) a;
236 auto b = a.allocate(400);
237 assert(b.length == 400);
238 assert(a.owns(b) == Ternary.yes);
239 void[] p;
240 a.deallocate(b);
241 }
242