ocean.util.container.pool.model.IFreeList source code

1 /*******************************************************************************
2 
3     Interfaces to manage and get information about a free list.
4 
5     Copyright:
6         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
7         All rights reserved.
8 
9     License:
10         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
11         Alternatively, this file may be distributed under the terms of the Tango
12         3-Clause BSD License (see LICENSE_BSD.txt for details).
13 
14 *******************************************************************************/
15 
16 module ocean.util.container.pool.model.IFreeList;
17 
18 import ocean.meta.types.Qualifiers;
19 
20 /*******************************************************************************
21 
22     Informational interface to a free list.
23 
24 *******************************************************************************/
25 
26 public interface IFreeListInfo
27 {
28     /***************************************************************************
29 
30         Returns the number of idle items in pool.
31 
32         Returns:
33             the number of idle items in pool
34 
35     ***************************************************************************/
36 
37     size_t num_idle ( );
38 }
39 
40 
41 /*******************************************************************************
42 
43     Management interface to a free list.
44 
45 *******************************************************************************/
46 
47 public interface IFreeList ( T ) : IFreeListInfo
48 {
49     /***************************************************************************
50 
51         Gets an item from the free list.
52 
53         Params:
54             new_item = new item, will only be evaluated in the case when no
55                 items are available in the free list
56 
57         Returns:
58             new item (either popped from free list or new_item)
59 
60     ***************************************************************************/
61 
62     T get ( lazy T new_item );
63 
64 
65     /***************************************************************************
66 
67         Ensures that the free list contains at least the specified number of
68         (idle) items. Useful to pre-allocate a free list of a certain size.
69 
70         Params:
71             num = minimum number of idle items desired in free list
72             new_item = expression that creates a new instance of T
73 
74         Returns:
75             this
76 
77     ***************************************************************************/
78 
79     typeof(this) fill ( size_t num, lazy T new_item );
80 
81 
82     /***************************************************************************
83 
84         Recycles an item into the free list.
85 
86         Params:
87             item = item to be put into the free list
88 
89     ***************************************************************************/
90 
91     void recycle ( T item );
92 
93 
94     /***************************************************************************
95 
96         Ensures that the free list contains at most the specified number of
97         items.
98 
99         Params:
100             num = maximum number of items desired in free list
101 
102         Returns:
103             this
104 
105     ***************************************************************************/
106 
107     typeof(this) minimize ( size_t num = 0 );
108 }
109 
110 
111 
112 version (unittest)
113 {
114     import ocean.core.Test;
115     import ocean.core.Array : pop;
116 
117 
118     /***************************************************************************
119 
120         Free list tester base class. Tests all methods of IFreeList.
121 
122         Params:
123             I = type of item stored in free list
124 
125     ***************************************************************************/
126 
127     abstract class FreeListTester ( I )
128     {
129         /***********************************************************************
130 
131             Free list being tested.
132 
133         ***********************************************************************/
134 
135         private alias IFreeList!(I) FL;
136 
137         private FL fl;
138 
139 
140         /***********************************************************************
141 
142             Alias for type of item stored in free list.
143 
144         ***********************************************************************/
145 
146         protected alias I Item;
147 
148 
149         /***********************************************************************
150 
151             Number of items to use in tests.
152 
153         ***********************************************************************/
154 
155         protected static immutable num_items = 10;
156 
157 
158         /***********************************************************************
159 
160             Constructor.
161 
162             Params:
163                 fl = free list to test
164 
165         ***********************************************************************/
166 
167         public this ( FL fl )
168         {
169             this.fl = fl;
170         }
171 
172 
173         /***********************************************************************
174 
175             Unittest for internal free list.
176 
177         ***********************************************************************/
178 
179         public void test ( )
180         {
181             Item[] busy_items;
182             size_t idle_count;
183 
184             // Get some items (initial creation)
185             for ( int i; i < this.num_items; i++ )
186             {
187                 busy_items ~= this.fl.get(this.newItem());
188                 this.lengthCheck(busy_items.length, idle_count);
189             }
190             .test!("==")(idle_count, 0, "idle count mismatch");
191 
192             // Recycle them
193             this.recycle(busy_items, idle_count);
194             .test!("==")(idle_count, this.num_items);
195 
196             // Get some items and store something in them
197             for ( int i; i < this.num_items; i++ )
198             {
199                 auto item = this.fl.get(this.newItem());
200 
201                 this.setItem(item, i);
202                 busy_items ~= item;
203 
204                 this.lengthCheck(busy_items.length, --idle_count);
205             }
206             .test!("==")(idle_count, 0, "idle count mismatch");
207 
208             // Recycle them
209             this.recycle(busy_items, idle_count);
210             .test!("==")(idle_count, this.num_items, "idle count mismatch");
211 
212             // Get them again and check the contents are as expected
213             for ( int i; i < this.num_items; i++ )
214             {
215                 auto item = this.fl.get(this.newItem());
216 
217                 this.checkItem(item, i);
218                 busy_items ~= item;
219 
220                 this.lengthCheck(busy_items.length, --idle_count);
221             }
222             .test!("==")(idle_count, 0, "idle count mismatch");
223 
224             // Recycle them
225             this.recycle(busy_items, idle_count);
226             .test!("==")(idle_count, this.num_items, "idle count mismatch");
227 
228             // Fill
229             this.fl.fill(this.num_items * 2, this.newItem());
230             this.lengthCheck(busy_items.length, this.num_items * 2);
231 
232             // Minimize
233             this.fl.minimize(this.num_items);
234             this.lengthCheck(busy_items.length, this.num_items);
235 
236             this.fl.minimize();
237             this.lengthCheck(busy_items.length, 0);
238         }
239 
240 
241         /***********************************************************************
242 
243             Checks that the contents of the free list match the expected values.
244             Derived classes can add additional checks by overriding.
245 
246             Params:
247                 expected_busy = expected number of busy items
248                 expected_idle = expected number of idle items
249 
250         ***********************************************************************/
251 
252         protected void lengthCheck ( size_t expected_busy, size_t expected_idle )
253         {
254             .test!("==")(this.fl.num_idle, expected_idle, "FreeList idle items wrong");
255         }
256 
257 
258         /***********************************************************************
259 
260             Returns:
261                 a new item of the type stored in the free list.
262 
263         ***********************************************************************/
264 
265         protected abstract Item newItem ( );
266 
267 
268         /***********************************************************************
269 
270             Sets the value of the passed item, using the passed integer to
271             deterministically decide its contents.
272 
273             Params:
274                 item = item to set value of
275                 i = integer to determine contents of item
276 
277         ***********************************************************************/
278 
279         protected abstract void setItem ( ref Item item, size_t i );
280 
281 
282         /***********************************************************************
283 
284             Checks the value of the passed item against the value which can be
285             deterministically derived from the passed integer. The method should
286             throw TestException on failure.
287 
288             Params:
289                 item = item to check value of
290                 i = integer to determine contents of item
291 
292         ***********************************************************************/
293 
294         protected abstract void checkItem ( ref Item item, size_t i );
295 
296 
297         /***********************************************************************
298 
299             Recycles all of the passed items into the free list, checking
300             consistency along the way.
301 
302             Params:
303                 busy_items = items to recycle
304                 idle_count = count of idle items
305 
306         ***********************************************************************/
307 
308         private void recycle ( ref Item[] busy_items, ref size_t idle_count )
309         {
310             while ( busy_items.length )
311             {
312                 Item item;
313                 auto popped = busy_items.pop(item);
314                 .test(popped, "pop from list of busy items failed");
315 
316                 this.fl.recycle(item);
317                 this.lengthCheck(busy_items.length, ++idle_count);
318             }
319 
320             assumeSafeAppend(busy_items);
321         }
322     }
323 }