1 /*******************************************************************************
2
3 Simple pool class template with the following features:
4 * Get and recycle items. Recycled items will be re-used before creating
5 new items.
6 * Fill the free list with a specific number of idle items.
7 * The number of idle items in the free list can be queried.
8
9 A free list does not manage busy items, it only stores a reference to any
10 idle / free items, making them available for re-use.
11
12 TODO:
13 - Free lists could support limiting, simply by counting the number of
14 allocated (i.e. busy) items. A count of allocated items would also allow a
15 length() method (with the same meaning as the method in IPool) to be
16 implemented.
17 - Add idle items iterators (safe & unsafe). These could probably share
18 code with the aggregate pool.
19
20 Copyright:
21 Copyright (c) 2009-2016 dunnhumby Germany GmbH.
22 All rights reserved.
23
24 License:
25 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
26 Alternatively, this file may be distributed under the terms of the Tango
27 3-Clause BSD License (see LICENSE_BSD.txt for details).
28
29 *******************************************************************************/
30
31 module ocean.util.container.pool.FreeList;
32
33
34
35 import ocean.util.container.pool.model.IFreeList;
36
37 import ocean.core.Array : pop;
38
39 import ocean.meta.traits.Basic;
40 import ocean.meta.types.Typedef;
41
42 import ocean.core.Buffer;
43 import ocean.core.TypeConvert;
44
45 version (unittest)
46 import ocean.core.Test;
47
48 /*******************************************************************************
49
50 Template to determine the internal item type of a free list.
51
52 Params:
53 T = item type to be stored in free list
54
55 *******************************************************************************/
56
57 private template ItemType_ ( T )
58 {
59 static if (isTypedef!(T))
60 {
61 alias ItemType_!(TypedefBaseType!(T)) ItemType_;
62 }
63 else static if (
64 isReferenceType!(T)
65 || isArrayType!(T) == ArrayKind.Dynamic
66 || isArrayType!(T) == ArrayKind.Associative)
67 {
68 alias T ItemType_;
69 }
70 else
71 {
72 alias T* ItemType_;
73 }
74 }
75
76
77 /*******************************************************************************
78
79 Free list class template.
80
81 Params:
82 T = item type to be stored in free list
83
84 *******************************************************************************/
85
86 public class FreeList ( T ) : IFreeList!(ItemType_!(T))
87 {
88 import ocean.core.Verify;
89
90 /***************************************************************************
91
92 Free lists of static arrays are not allowed. Likewise a free list of an
93 atomic type (int, float, etc) is not allowed -- this would be rather
94 pointless.
95
96 ***************************************************************************/
97
98 static assert(
99 isArrayType!(T) != ArrayKind.Static,
100 "Cannot use static array type '"
101 ~ T.stringof ~ "' as base type for FreeList"
102 );
103
104 static assert(
105 !isPrimitiveType!(T),
106 "Cannot use primitive type '" ~ T.stringof ~
107 "' as base type for FreeList"
108 );
109
110
111 /***************************************************************************
112
113 Alias for item type to be stored in free list and accepted by public
114 methods.
115
116 Reference types (including dynamic and associative arrays) can be stored
117 directly in the free list. Pointers are stored for other types.
118
119 ***************************************************************************/
120
121 public alias ItemType_!(T) ItemType;
122
123
124 /***************************************************************************
125
126 List of free items.
127
128 ***************************************************************************/
129
130 private ItemType[] free_list;
131
132
133 /***************************************************************************
134
135 Gets an item from the free list.
136
137 Params:
138 new_item = new item, will only be evaluated in the case when no
139 items are available in the free list
140
141 Returns:
142 new item
143
144 ***************************************************************************/
145
146 public ItemType get ( lazy ItemType new_item )
147 {
148 if ( this.free_list.length )
149 {
150 ItemType item;
151 auto popped = this.free_list.pop(item);
152 verify(popped, "Item failed to be popped from non-empty free list");
153 return item;
154 }
155 else
156 {
157 return new_item;
158 }
159 }
160
161
162 /***************************************************************************
163
164 Recycles an item into the free list.
165
166 Params:
167 item = item to be put into the free list
168
169 ***************************************************************************/
170
171 public void recycle ( ItemType item )
172 {
173 this.free_list ~= item;
174 }
175
176
177 /***************************************************************************
178
179 Ensures that the free list contains at least the specified number of
180 (idle) items. Useful to pre-allocate a free list of a certain size.
181
182 Params:
183 num = minimum number of items desired in pool
184 new_item = expression that creates a new instance of T
185
186 Returns:
187 this
188
189 ***************************************************************************/
190
191 public typeof(this) fill ( size_t num, lazy ItemType new_item )
192 out
193 {
194 assert(this.free_list.length >= num);
195 }
196 do
197 {
198 if ( this.free_list.length < num )
199 {
200 auto extra = num - this.free_list.length;
201 for ( size_t i; i < extra; i++ )
202 {
203 this.free_list ~= new_item;
204 }
205 }
206
207 return this;
208 }
209
210
211 /***************************************************************************
212
213 Ensures that the free list contains at most the specified number of
214 (idle) items.
215
216 Params:
217 num = maximum number of idle items desired in free list
218
219 Returns:
220 this
221
222 ***************************************************************************/
223
224 public typeof(this) minimize ( size_t num = 0 )
225 {
226 if ( this.free_list.length > num )
227 {
228 this.free_list.length = num;
229 assumeSafeAppend(this.free_list);
230 }
231
232 return this;
233 }
234
235
236 /***************************************************************************
237
238 Returns:
239 the number of idle (available) items in the free list
240
241 ***************************************************************************/
242
243 public size_t num_idle ( )
244 {
245 return this.free_list.length;
246 }
247 }
248
249
250 /*******************************************************************************
251
252 Unit test.
253
254 Tests:
255 * All methods of IFreeList.
256 * FreeList of strings, structs and classes.
257
258 *******************************************************************************/
259
260 version (unittest)
261 {
262 import ocean.core.Test;
263
264 /***************************************************************************
265
266 String free list tester.
267
268 ***************************************************************************/
269
270 private alias FreeList!(char[]) StringFreeList;
271 private class StringFreeListTester : FreeListTester!(StringFreeList.ItemType)
272 {
273 public this ( ) { super(new StringFreeList); }
274
275 protected override Item newItem ( )
276 {
277 return new char[10];
278 }
279
280 protected override void setItem ( ref Item item, size_t i )
281 {
282 item.length = 1;
283 item[0] = cast(char)(i + 32);
284 }
285
286 protected override void checkItem ( ref Item item, size_t i )
287 {
288 .test!("==")(item.length, 1, "item length wrong");
289 .test!("==")(item[0], cast(char)(i + 32), "item content wrong");
290 }
291 }
292
293
294 /***************************************************************************
295
296 Struct free list tester.
297
298 ***************************************************************************/
299
300 private struct Struct
301 {
302 size_t i;
303 char[] s;
304 }
305
306 private alias FreeList!(Struct) StructFreeList;
307 private class StructFreeListTester : FreeListTester!(StructFreeList.ItemType)
308 {
309 public this ( ) { super(new StructFreeList); }
310
311 protected override Item newItem ( )
312 {
313 return new Struct;
314 }
315
316 protected override void setItem ( ref Item item, size_t i )
317 {
318 item.i = i;
319 item.s.length = 1;
320 item.s[0] = cast(char)(i + 32);
321 }
322
323 protected override void checkItem ( ref Item item, size_t i )
324 {
325 .test!("==")(item.i, i, "item integer wrong");
326 .test!("==")(item.s.length, 1, "item string length wrong");
327 .test!("==")(item.s[0], cast(char)(i + 32), "item string content wrong");
328 }
329 }
330
331 /***************************************************************************
332
333 Buffer free list tester.
334
335 ***************************************************************************/
336
337 private alias FreeList!(Buffer!(void)) BufferFreeList;
338 private class BufferFreeListTester : FreeListTester!(BufferFreeList.ItemType)
339 {
340 public this ( ) { super(new BufferFreeList); }
341
342 protected override Item newItem ( )
343 {
344 return new Buffer!(void);
345 }
346
347 protected override void setItem ( ref Item item, size_t i )
348 {
349 *item ~= 40;
350 *item ~= 41;
351 *item ~= 42;
352 }
353
354 protected override void checkItem ( ref Item item, size_t i )
355 {
356 void[] a = (*item)[];
357 void[] b = arrayOf!(ubyte)(40, 41, 42);
358 .test!("==")(a, b);
359 }
360 }
361
362 /***************************************************************************
363
364 Class free list tester.
365
366 ***************************************************************************/
367
368 private class Class
369 {
370 override equals_t opEquals(Object rhs)
371 {
372 auto crhs = cast(typeof(this)) rhs;
373 return this.i == crhs.i && this.s == crhs.s;
374 }
375
376 size_t i;
377 char[] s;
378 }
379
380 private alias FreeList!(Class) ClassFreeList;
381 private class ClassFreeListTester : FreeListTester!(ClassFreeList.ItemType)
382 {
383 public this ( ) { super(new ClassFreeList); }
384
385 protected override Item newItem ( )
386 {
387 return new Class;
388 }
389
390 protected override void setItem ( ref Item item, size_t i )
391 {
392 item.i = i;
393 item.s.length = 1;
394 item.s[0] = cast(char)(i + 32);
395 }
396
397 protected override void checkItem ( ref Item item, size_t i )
398 {
399 .test!("==")(item.i, i, "item integer wrong");
400 .test!("==")(item.s.length, 1, "item string length wrong");
401 .test!("==")(item.s[0], cast(char)(i + 32), "item string content wrong");
402 }
403 }
404 }
405
406 unittest
407 {
408 // String (arrays) free list test
409 {
410 scope fl = new StringFreeListTester;
411 fl.test();
412 }
413
414 // Struct free list test
415 {
416 scope fl = new StructFreeListTester;
417 fl.test();
418 }
419
420 // Buffer free list test
421 {
422 scope fl = new BufferFreeListTester;
423 fl.test();
424 }
425
426 // Class free list test
427 {
428 scope fl = new ClassFreeListTester;
429 fl.test();
430 }
431 }