ocean.util.container.map.model.BucketElementFreeList source code

1 /*******************************************************************************
2 
3     Free list of dynamically allocated objects.
4     Implemented as a linked list; a subclass must get and set the next one of
5     a given object.
6 
7     Copyright:
8         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
9         All rights reserved.
10 
11     License:
12         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
13         Alternatively, this file may be distributed under the terms of the Tango
14         3-Clause BSD License (see LICENSE_BSD.txt for details).
15 
16 *******************************************************************************/
17 
18 module ocean.util.container.map.model.BucketElementFreeList;
19 
20 
21 import ocean.util.container.map.model.IAllocator;
22 
23 import ocean.core.Array: clear;
24 
25 /*******************************************************************************
26 
27     Free list of currently unused bucket elements.
28 
29 *******************************************************************************/
30 
31 class BucketElementFreeList ( BucketElement ) : IBucketElementFreeList
32 {
33     static assert(is(BucketElement == struct),
34                   "BucketElement type needs to be a struct, which " ~
35                   BucketElement.stringof ~ " is not");
36 
37     static if(is(typeof(BucketElement.next) Next))
38     {
39         static assert(is(Next == BucketElement*),
40                       BucketElement.stringof ~ ".next needs to be of type " ~
41                       (BucketElement*).stringof ~ ", not " ~ Next.stringof);
42     }
43     else
44     {
45         static assert(false, "need " ~ (BucketElement*).stringof ~ " " ~
46                              BucketElement.stringof ~ ".next");
47     }
48 
49     /***************************************************************************
50 
51         Constructor.
52 
53     ***************************************************************************/
54 
55     public this ( )
56     {
57         super(BucketElement.sizeof);
58     }
59 
60     /**************************************************************************
61 
62         Obtains the next element of element.
63 
64         Params:
65             element = bucket element of which to obtain the next one
66 
67         Returns:
68             the next bucket element (which may be null).
69 
70      **************************************************************************/
71 
72     protected override void* getNext ( void* element )
73     {
74         return (cast(BucketElement*)element).next;
75     }
76 
77     /**************************************************************************
78 
79         Sets the next element of element.
80 
81         Params:
82             element = bucket element to which to set the next one
83             next    = next bucket element for element (nay be null)
84 
85      **************************************************************************/
86 
87     protected override void setNext ( void* element, void* next )
88     {
89         (cast(BucketElement*)element).next = cast(BucketElement*)next;
90     }
91 
92     /**************************************************************************
93 
94         Allocates a bucket element.
95 
96         Returns:
97             a new bucket element.
98 
99      **************************************************************************/
100 
101     protected override void* newElement ( )
102     {
103         return new BucketElement;
104     }
105 }
106 
107 /*******************************************************************************
108 
109     Creates an instance of BucketElementFreeList which is suitable for usage
110     with the Map type passed as a template parameter.
111 
112     Params:
113         Map = the type to create the allocator according to
114 
115     Returns:
116         an instance of type BucketElementFreeList class
117 
118 *******************************************************************************/
119 
120 public BucketElementFreeList!(Map.Bucket.Element) instantiateAllocator ( Map ) ( )
121 {
122     return new BucketElementFreeList!(Map.Bucket.Element);
123 }
124 
125 
126 /*******************************************************************************
127 
128     Type generic BucketElementFreeList base class.
129 
130 *******************************************************************************/
131 
132 abstract class IBucketElementFreeList: IAllocator
133 {
134     import ocean.core.Verify;
135 
136     /**************************************************************************
137 
138         First free element.
139 
140      **************************************************************************/
141 
142     private void* first = null;
143 
144     /**************************************************************************
145 
146         Free list length.
147 
148      **************************************************************************/
149 
150     private size_t n_free = 0;
151 
152     /**************************************************************************
153 
154         True while a ParkingStack instance for this instance exists.
155 
156      **************************************************************************/
157 
158     private bool parking_stack_open = false;
159 
160     /**************************************************************************
161 
162         Consistency check and assertion that at most one ParkingStack instance
163         for this instance exists at a time.
164 
165      **************************************************************************/
166 
167     invariant ( )
168     {
169         if (this.first)
170         {
171             assert (this.n_free);
172         }
173         else
174         {
175             assert (!this.n_free);
176         }
177 
178         assert (!this.parking_stack_open, "attempted to use the outer " ~
179                 typeof (this).stringof ~ " instance of an existing " ~
180                 ParkingStack.stringof ~ " instance");
181     }
182 
183     /***************************************************************************
184 
185         Constructor.
186 
187         Params:
188             bucket_element_sizeof = the amount of memory used by each allocated
189                 element.
190 
191     ***************************************************************************/
192 
193     public this( size_t bucket_element_sizeof )
194     {
195         super(bucket_element_sizeof);
196     }
197 
198     /**************************************************************************
199 
200         Obtains an object either from the free list, if available, or from
201         new_object if the free list is empty.
202 
203         Returns:
204             new object
205 
206         Out:
207             The returned object cannot be null.
208 
209      **************************************************************************/
210 
211     protected override void* allocate ( )
212     out (object)
213     {
214         assert (object !is null);
215     }
216     body
217     {
218         if (this.first)
219         {
220             return this.get_();
221         }
222         else
223         {
224             return this.newElement();
225         }
226     }
227 
228     /**************************************************************************
229 
230         Allocates a new object. Called by get() if the list is empty.
231 
232         Returns:
233             a new object.
234 
235      **************************************************************************/
236 
237     abstract protected void* newElement ( );
238 
239     /**************************************************************************
240 
241         Appends old_object to the free list.
242 
243         Params:
244             old_object = object to recycle
245 
246         In:
247             old_object must not be null.
248 
249      **************************************************************************/
250 
251     protected override void deallocate ( void* old_object )
252     {
253         verify (old_object !is null);
254 
255         scope (success) this.n_free++;
256 
257         this.recycle_(old_object);
258     }
259 
260     /**************************************************************************
261 
262         Returns:
263             the number of objects in the free list.
264 
265      **************************************************************************/
266 
267     public size_t length ( )
268     {
269         return this.n_free;
270     }
271 
272     /**************************************************************************
273 
274         Obtains the next object of object. object is never null but the next
275         object may be.
276 
277         Params:
278             object = object of which to obtain the next object (is never null)
279 
280         Returns:
281             the next object (which may be null).
282 
283      **************************************************************************/
284 
285     abstract protected void* getNext ( void* object );
286 
287     /**************************************************************************
288 
289         Sets the next object of object. object is never null but next may be.
290 
291         Params:
292             object = object to which to set the next object (is never null)
293             next   = next object for object (nay be null)
294 
295      **************************************************************************/
296 
297     abstract protected void setNext ( void* object, void* next );
298 
299     /**************************************************************************
300 
301         Obtains free_list[n] and sets free_list[n] to null.
302 
303         Params:
304             n = free list index
305 
306         Returns:
307             free_list[n]
308 
309      **************************************************************************/
310 
311     private void* get_ ( )
312     {
313         verify (this.first !is null);
314 
315         void* element = this.first;
316 
317         this.first = this.getNext(element);
318         this.n_free--;
319         this.setNext(element, null);
320 
321         return element;
322     }
323 
324     /**************************************************************************
325 
326         Appends object to the free list using n as insertion index. n is
327         expected to refer to the position immediately after the last object in
328         the free list, which may be free_list.length.
329 
330         Params:
331             n = free list insertion index
332 
333         Returns:
334             free_list[n]
335 
336      **************************************************************************/
337 
338     private void* recycle_ ( void* object )
339     {
340         this.setNext(object, this.first);
341 
342         return this.first = object;
343     }
344 
345     /***************************************************************************
346 
347         Calls dg with an IParkingStack instance that is set up to keep n
348         elements.
349 
350         Params:
351             n  = number of elements to park
352             dg = delegate to call with the IParkingStack instance
353 
354     ***************************************************************************/
355 
356     public override void parkElements (size_t n,
357                                        scope void delegate ( IParkingStack park ) dg)
358     {
359         scope parking_stack = this.new ParkingStack(n);
360 
361         dg(parking_stack);
362     }
363 
364     /**************************************************************************
365 
366         Allows using the free list as a stack to park objects without marking
367         them as free. The parked object are appended to the free list after the
368         free objects currently in the list.
369         At most one ParkingStack instance may exist at a time. While a
370         ParkingStack instance exists, no public FreeList method may be used.
371 
372      **************************************************************************/
373 
374     scope class ParkingStack: IParkingStack
375     {
376         /**********************************************************************
377 
378             Constructor.
379 
380             Params:
381                 max_length = maximum number of objects that will be stored
382 
383          **********************************************************************/
384 
385         private this ( size_t max_length )
386         {
387             verify (!this.outer.parking_stack_open);
388 
389             this.outer.parking_stack_open = true;
390             super(max_length);
391         }
392 
393         /**********************************************************************
394 
395             Destructor; removes the remaining stack elements, if any.
396 
397          **********************************************************************/
398 
399         ~this ( )
400         {
401             scope ( exit ) this.outer.parking_stack_open = false;
402             while (this.pop()) { }
403         }
404 
405         /**********************************************************************
406 
407             Pushes an object on the stack.
408 
409             Params:
410                 object = object to push
411                 n      = number of parked objects before object is pushed
412                          (guaranteed to be less than max_length)
413 
414          **********************************************************************/
415 
416         protected override void push_ ( void* object, size_t n )
417         {
418             this.outer.recycle_(object);
419         }
420 
421         /**********************************************************************
422 
423             Pops an object from the stack. This method is never called if the
424             stack is empty.
425 
426             Params:
427                 n = number of parked objects after object is popped (guaranteed
428                     to be less than max_length)
429 
430             Returns:
431                 object popped from the stack or null if the stack is empty.
432 
433          **********************************************************************/
434 
435         protected override void* pop_ ( size_t n )
436         {
437             return this.outer.get_();
438         }
439     }
440 }