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