ocean.util.container.ConcatBuffer source code

1 /*******************************************************************************
2 
3     Class templates for reusable buffers with minimal memory allocation.
4 
5     Each class has its own detailed description and usage example below.
6 
7     The difference between this and AppendBuffer is that AppendBuffer basically
8     wraps a dynamic array and keeps track of the length, while this class
9     provides a way to store multiple arrays by appending them into a single
10     buffer. The basic ConcatBuffer class returns the slices to the appended
11     arrays from its 'add' method. The extended SliceBuffer class internally
12     keeps track of the appended slices, and offers opIndex and opApply methods
13     over them.
14 
15     Copyright:
16         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
17         All rights reserved.
18 
19     License:
20         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
21         Alternatively, this file may be distributed under the terms of the Tango
22         3-Clause BSD License (see LICENSE_BSD.txt for details).
23 
24 *******************************************************************************/
25 
26 module ocean.util.container.ConcatBuffer;
27 
28 
29 
30 
31 import ocean.meta.types.Qualifiers;
32 
33 import ocean.core.Array : removeShift;
34 
35 
36 
37 /*******************************************************************************
38 
39     Concat buffer class template.
40 
41     Params:
42         T = element type of buffer
43 
44     This template is useful for situations where you want to be able to
45     repeatedly fill and empty a buffer of type T[] without recurring memory
46     allocation. The buffer will grow over time to the required maximum size, and
47     then will no longer allocate memory.
48 
49     ConcatBuffer classes also avoid modifying the .length property of the
50     internal buffer, which has been observed to be costly, even when extending
51     an array's length to <= its previous length.
52 
53     Internally the class stores a single buffer. If an item is added which does
54     not fit in the currently allocated buffer, then a new expanded buffer is
55     newed and replaces the old buffer. This means that the old buffer still
56     exists in memory, and will not be garbage collected until there are no more
57     references to it. As a result of this behaviour, any slices remaining to the
58     previous buffer may still safely be used. Only at the point where all these
59     slices no longer reference the old buffer will it be garbage collected.
60 
61     Usage example:
62     ---
63 
64         import ocean.util.container.ConcatBuffer;
65 
66         // Create a concat buffer
67         auto buff = new ConcatBuffer!(char);
68 
69         // Repeatedly...
70         while ( application_running )
71         {
72             // Empty the buffer
73             buff.clear();
74 
75             // Add stuff to the buffer
76             buff.add("hello");
77             buff.add("world");
78         }
79 
80     ---
81 
82 *******************************************************************************/
83 
84 public class ConcatBuffer ( T )
85 {
86     /***************************************************************************
87 
88         Data buffer.
89 
90     ***************************************************************************/
91 
92     private T[] buffer;
93 
94 
95     /***************************************************************************
96 
97         Current write position in the buffer.
98 
99     ***************************************************************************/
100 
101     private size_t write_pos;
102 
103 
104     /***************************************************************************
105 
106         Constructor.
107 
108         Params:
109             len = initial buffer length
110 
111     ***************************************************************************/
112 
113     public this ( size_t len = 0 )
114     {
115         this.buffer.length = len;
116     }
117 
118 
119     /***************************************************************************
120 
121         Appends a new piece of data to the end of the buffer.
122 
123         Params:
124             data = data to append to buffer
125 
126         Returns:
127             in-place slice to the location in the buffer where the new item was
128             appended
129 
130     ***************************************************************************/
131 
132     public T[] add ( const(T)[] data )
133     {
134         return this.add(data.length)[] = data[];
135     }
136 
137 
138     /***************************************************************************
139 
140         Reserves a new piece of data at the end of the buffer.
141 
142         Params:
143             length = amount of bytes to reserve
144 
145         Returns:
146             in-place slice to the reserved data in the buffer
147 
148     ***************************************************************************/
149 
150     public T[] add ( size_t length )
151     {
152         if ( this.write_pos + length > this.buffer.length )
153         {
154             this.buffer = new T[this.buffer.length + length];
155             this.write_pos = 0;
156         }
157 
158         auto start = this.write_pos;
159         auto end = start + length;
160 
161         this.write_pos = end;
162 
163         return this.buffer[start .. end];
164     }
165 
166 
167     /***************************************************************************
168 
169         Returns:
170             the number of elements which the currently allocated buffer can
171             contain
172 
173     ***************************************************************************/
174 
175     public size_t dimension ( )
176     {
177         return this.buffer.length;
178     }
179 
180 
181     /***************************************************************************
182 
183         Empties the buffer.
184 
185     ***************************************************************************/
186 
187     public void clear ( )
188     {
189         this.write_pos = 0;
190     }
191 }
192 
193 
194 
195 /*******************************************************************************
196 
197     Slice buffer class template. Extends ConcatBuffer, encapsulating a buffer
198     with a list of slices to the concatenated items.
199 
200     Params:
201         T = element type of buffer
202 
203     This template is useful for situations where you need to build up a list of
204     arrays of type T[], and be able to repeatedly fill and empty the list
205     without recurring memory allocation. Note that once an item is added to the
206     buffer, it is *not* possible to modify its length, as each item is only
207     stored as a slice (though it is possible to modify the contents of a slice).
208     (For situations where you want to be able to modify the lengths of the
209     individual arrays after adding them to the collection, a Pool of structs
210     containing arrays would be a suitable solution -- see
211     ocean.core.ObjectPool.)
212 
213     Usage example:
214 
215     ---
216 
217         import ocean.util.container.ConcatBuffer;
218 
219         // Create a slice buffer
220         auto buff = new SliceBuffer!(char);
221 
222         // Repeatedly...
223         while ( application_running )
224         {
225             // Empty the buffer
226             buff.clear();
227 
228             // Add stuff to the buffer
229             buff.add("hello");
230             buff.add("world");
231 
232             // Iterate over the items in the buffer
233             foreach ( index, item; buff )
234             {
235             }
236         }
237 
238     ---
239 
240 *******************************************************************************/
241 
242 public class SliceBuffer ( T ) : ConcatBuffer!(T)
243 {
244     /***************************************************************************
245 
246         List of slices into the buffer content. A slice is added to the list
247         each time an item is added to the buffer.
248 
249     ***************************************************************************/
250 
251     private T[][] slices;
252 
253 
254     /***************************************************************************
255 
256         Constructor.
257 
258         Params:
259             len = initial buffer length
260 
261     ***************************************************************************/
262 
263     public this ( size_t len = 0 )
264     {
265         super(len);
266     }
267 
268 
269     /***************************************************************************
270 
271         Appends a new piece of data to the end of the buffer. The item is also
272         added to the slices list.
273 
274         Params:
275             data = data to append to buffer
276 
277         Returns:
278             in-place slice to the location in the buffer where the new item was
279             appended
280 
281     ***************************************************************************/
282 
283     override public T[] add ( const(T)[] data )
284     {
285         auto slice = super.add(data);
286         this.slices ~= slice;
287         return slice;
288     }
289 
290 
291     /***************************************************************************
292 
293         Removes an indexed item in the items list, maintaining the order of the
294         list.
295 
296         Note that the item's content in the buffer is *not* removed, the item is
297         simply removed from the list of slices.
298 
299         Beware that this removal involves a call to memmove.
300 
301         Params:
302             index = index of item to remove
303 
304         Returns:
305             indexed item
306 
307         Throws:
308             out of bounds exception if index is > the number of items added to
309             the buffer
310 
311     ***************************************************************************/
312 
313     public T[] removeSlice ( size_t index )
314     {
315         auto slice = this.slices[index];
316         this.slices.removeShift(index);
317 
318         return slice;
319     }
320 
321 
322     /***************************************************************************
323 
324         Empties the buffer.
325 
326     ***************************************************************************/
327 
328     override public void clear ( )
329     {
330         super.clear;
331         this.slices.length = 0;
332         assumeSafeAppend(this.slices);
333     }
334 
335 
336     /***************************************************************************
337 
338         Returns:
339             the number of items added to the buffer
340 
341     ***************************************************************************/
342 
343     public size_t length ( )
344     {
345         return this.slices.length;
346     }
347 
348 
349     /***************************************************************************
350 
351         Gets an indexed item in the items list.
352 
353         Params:
354             index = index of item to get
355 
356         Returns:
357             indexed item
358 
359         Throws:
360             out of bounds exception if index is > the number of items added to
361             the buffer
362 
363     ***************************************************************************/
364 
365     public T[] opIndex ( size_t index )
366     {
367         return this.slices[index];
368     }
369 
370 
371     /***************************************************************************
372 
373         Get the stored slices.
374 
375         Returns:
376             The currently stored slices.
377 
378     ***************************************************************************/
379 
380     public T[][] opSlice ( )
381     {
382         return this.slices;
383     }
384 
385 
386     /***************************************************************************
387 
388         foreach iterator over the items which have been added to the buffer.
389 
390     ***************************************************************************/
391 
392     public int opApply ( scope int delegate ( ref T[] ) dg )
393     {
394         int res;
395 
396         foreach ( slice; this.slices )
397         {
398             res = dg(slice);
399 
400             if ( res ) break;
401         }
402 
403         return res;
404     }
405 
406 
407     /***************************************************************************
408 
409         foreach iterator over the items which have been added to the buffer and
410         their indices.
411 
412     ***************************************************************************/
413 
414     public int opApply ( scope int delegate ( ref size_t, ref T[] ) dg )
415     {
416         int res;
417 
418         foreach ( i, slice; this.slices )
419         {
420             res = dg(i, slice);
421 
422             if ( res ) break;
423         }
424 
425         return res;
426     }
427 }
428 
429