1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 /**
6 * This module contains buffers designed for C-style input/output APIs.
7 *
8 * Copyright: Eugene Wissner 2016-2020.
9 * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
10 * Mozilla Public License, v. 2.0).
11 * Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
12 * Source: $(LINK2 https://github.com/caraus-ecms/tanya/blob/master/source/tanya/container/buffer.d,
13 * tanya/container/buffer.d)
14 */
15 module tanya.container.buffer;
16
17 import tanya.memory.allocator;
18 import tanya.meta.trait;
19
20 version (unittest)
21 {
22 private int fillBuffer(ubyte[] buffer,
23 int start = 0,
24 int end = 10) @nogc pure nothrow
25 in
26 {
27 assert(start < end);
28 }
29 do
30 {
31 auto numberRead = end - start;
32 for (ubyte i; i < numberRead; ++i)
33 {
34 buffer[i] = cast(ubyte) (start + i);
35 }
36 return numberRead;
37 }
38 }
39
40 /**
41 * Self-expanding buffer, that can be used with functions returning the number
42 * of the read bytes.
43 *
44 * This buffer supports asynchronous reading. It means you can pass a new chunk
45 * to an asynchronous read function during you are working with already
46 * available data. But only one asynchronous call at a time is supported. Be
47 * sure to call $(D_PSYMBOL ReadBuffer.clear()) before you append the result
48 * of the pended asynchronous call.
49 *
50 * Params:
51 * T = Buffer type.
52 */
53 struct ReadBuffer(T = ubyte)
54 if (isScalarType!T)
55 {
56 /// Internal buffer.
57 private T[] buffer_;
58
59 /// Filled buffer length.
60 private size_t length_;
61
62 /// Start of available data.
63 private size_t start;
64
65 /// Last position returned with $(D_KEYWORD []).
66 private size_t ring;
67
68 /// Available space.
69 private size_t minAvailable = 1024;
70
71 /// Size by which the buffer will grow.
72 private size_t blockSize = 8192;
73
74 invariant
75 {
76 assert(this.length_ <= this.buffer_.length);
77 assert(this.blockSize > 0);
78 assert(this.minAvailable > 0);
79 }
80
81 /**
82 * Creates a new read buffer.
83 *
84 * Params:
85 * size = Initial buffer size and the size by which the buffer
86 * will grow.
87 * minAvailable = minimal size should be always available to fill.
88 * So it will reallocate if $(D_INLINECODE
89 * $(D_PSYMBOL free) < $(D_PARAM minAvailable)).
90 * allocator = Allocator.
91 */
92 this(size_t size,
93 size_t minAvailable = 1024,
94 shared Allocator allocator = defaultAllocator) @trusted
95 {
96 this(allocator);
97 this.minAvailable = minAvailable;
98 this.blockSize = size;
99 this.buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
100 }
101
102 /// ditto
103 this(shared Allocator allocator)
104 in
105 {
106 assert(allocator_ is null);
107 }
108 do
109 {
110 allocator_ = allocator;
111 }
112
113 /**
114 * Deallocates the internal buffer.
115 */
116 ~this() @trusted
117 {
118 allocator.deallocate(this.buffer_);
119 }
120
121 ///
122 @nogc nothrow pure @safe unittest
123 {
124 ReadBuffer!ubyte b;
125 assert(b.capacity == 0);
126 assert(b.length == 0);
127 }
128
129 /**
130 * Returns: The size of the internal buffer.
131 */
132 @property size_t capacity() const
133 {
134 return this.buffer_.length;
135 }
136
137 /**
138 * Returns: Data size.
139 */
140 @property size_t length() const
141 {
142 return this.length_ - start;
143 }
144
145 /// ditto
146 alias opDollar = length;
147
148 /**
149 * Clears the buffer.
150 *
151 * Returns: $(D_KEYWORD this).
152 */
153 void clear()
154 {
155 start = this.length_ = ring;
156 }
157
158 /**
159 * Returns: Available space.
160 */
161 @property size_t free() const
162 {
163 return length > ring ? capacity - length : capacity - ring;
164 }
165
166 ///
167 @nogc nothrow pure @system unittest
168 {
169 ReadBuffer!ubyte b;
170 size_t numberRead;
171
172 assert(b.free == 0);
173
174 // Fills the buffer with values 0..10
175 numberRead = fillBuffer(b[], 0, 10);
176 b += numberRead;
177 assert(b.free == b.blockSize - numberRead);
178 b.clear();
179 assert(b.free == b.blockSize);
180 }
181
182 /**
183 * Appends some data to the buffer.
184 *
185 * Params:
186 * length = Number of the bytes read.
187 *
188 * Returns: $(D_KEYWORD this).
189 */
190 ref ReadBuffer opOpAssign(string op)(size_t length)
191 if (op == "+")
192 {
193 this.length_ += length;
194 ring = start;
195 return this;
196 }
197
198 ///
199 @nogc nothrow pure @system unittest
200 {
201 ReadBuffer!ubyte b;
202 size_t numberRead;
203 ubyte[] result;
204
205 // Fills the buffer with values 0..10
206 numberRead = fillBuffer(b[], 0, 10);
207 b += numberRead;
208
209 result = b[0 .. $];
210 assert(result[0] == 0);
211 assert(result[1] == 1);
212 assert(result[9] == 9);
213 b.clear();
214
215 // It shouldn't overwrite, but append another 5 bytes to the buffer
216 numberRead = fillBuffer(b[], 0, 10);
217 b += numberRead;
218
219 numberRead = fillBuffer(b[], 20, 25);
220 b += numberRead;
221
222 result = b[0..$];
223 assert(result[0] == 0);
224 assert(result[1] == 1);
225 assert(result[9] == 9);
226 assert(result[10] == 20);
227 assert(result[14] == 24);
228 }
229
230 /**
231 * Params:
232 * start = Start position.
233 * end = End position.
234 *
235 * Returns: Array between $(D_PARAM start) and $(D_PARAM end).
236 */
237 T[] opSlice(size_t start, size_t end)
238 {
239 return this.buffer_[this.start + start .. this.start + end];
240 }
241
242 /**
243 * Returns a free chunk of the buffer.
244 *
245 * Add ($(D_KEYWORD +=)) the number of the read bytes after using it.
246 *
247 * Returns: A free chunk of the buffer.
248 */
249 T[] opIndex()
250 {
251 if (start > 0)
252 {
253 auto ret = this.buffer_[0 .. start];
254 ring = 0;
255 return ret;
256 }
257 else
258 {
259 if (capacity - length < this.minAvailable)
260 {
261 void[] buf = this.buffer_;
262 const cap = capacity;
263 () @trusted {
264 allocator.reallocate(buf,
265 (cap + this.blockSize) * T.sizeof);
266 this.buffer_ = cast(T[]) buf;
267 }();
268 }
269 ring = this.length_;
270 return this.buffer_[this.length_ .. $];
271 }
272 }
273
274 ///
275 @nogc nothrow pure @system unittest
276 {
277 ReadBuffer!ubyte b;
278 size_t numberRead;
279 ubyte[] result;
280
281 // Fills the buffer with values 0..10
282 numberRead = fillBuffer(b[], 0, 10);
283 b += numberRead;
284
285 assert(b.length == 10);
286 result = b[0 .. $];
287 assert(result[0] == 0);
288 assert(result[9] == 9);
289 b.clear();
290 assert(b.length == 0);
291 }
292
293 mixin DefaultAllocator;
294 }
295
296 /**
297 * Circular, self-expanding buffer with overflow support. Can be used with
298 * functions returning the number of the transferred bytes.
299 *
300 * The buffer is optimized for situations where you read all the data from it
301 * at once (without writing to it occasionally). It can become ineffective if
302 * you permanently keep some data in the buffer and alternate writing and
303 * reading, because it may allocate and move elements.
304 *
305 * Params:
306 * T = Buffer type.
307 */
308 struct WriteBuffer(T = ubyte)
309 if (isScalarType!T)
310 {
311 /// Internal buffer.
312 private T[] buffer_;
313
314 /// Buffer start position.
315 private size_t start;
316
317 /// Buffer ring area size. After this position begins buffer overflow area.
318 private size_t ring;
319
320 /// Size by which the buffer will grow.
321 private const size_t blockSize;
322
323 /// The position of the free area in the buffer.
324 private size_t position;
325
326 invariant
327 {
328 assert(this.blockSize > 0);
329 // Position can refer to an element outside the buffer if the buffer is
330 // full.
331 assert(this.position <= this.buffer_.length);
332 }
333
334 /**
335 * Params:
336 * size = Initial buffer size and the size by which the buffer will
337 * grow.
338 * allocator = Allocator.
339 *
340 * Precondition: $(D_INLINECODE size > 0 && allocator !is null)
341 */
342 this(size_t size, shared Allocator allocator = defaultAllocator) @trusted
343 in
344 {
345 assert(size > 0);
346 assert(allocator !is null);
347 }
348 do
349 {
350 this.blockSize = size;
351 ring = size - 1;
352 allocator_ = allocator;
353 this.buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
354 }
355
356 @disable this();
357
358 /**
359 * Deallocates the internal buffer.
360 */
361 ~this()
362 {
363 allocator.deallocate(this.buffer_);
364 }
365
366 /**
367 * Returns: The size of the internal buffer.
368 */
369 @property size_t capacity() const
370 {
371 return this.buffer_.length;
372 }
373
374 /**
375 * Note that $(D_PSYMBOL length) doesn't return the real length of the data,
376 * but only the array length that will be returned with $(D_PSYMBOL opIndex)
377 * next time. Be sure to call $(D_PSYMBOL opIndex) and set $(D_KEYWORD +=)
378 * until $(D_PSYMBOL length) returns 0.
379 *
380 * Returns: Data size.
381 */
382 @property size_t length() const
383 {
384 if (this.position > ring || this.position < start) // Buffer overflowed
385 {
386 return ring - start + 1;
387 }
388 else
389 {
390 return this.position - start;
391 }
392 }
393
394 /// ditto
395 alias opDollar = length;
396
397 ///
398 @nogc nothrow pure @system unittest
399 {
400 auto b = WriteBuffer!ubyte(4);
401 ubyte[3] buf = [48, 23, 255];
402
403 b ~= buf;
404 assert(b.length == 3);
405 b += 2;
406 assert(b.length == 1);
407
408 b ~= buf;
409 assert(b.length == 2);
410 b += 2;
411 assert(b.length == 2);
412
413 b ~= buf;
414 assert(b.length == 5);
415 b += b.length;
416 assert(b.length == 0);
417 }
418
419 /**
420 * Returns: Available space.
421 */
422 @property size_t free() const
423 {
424 return capacity - length;
425 }
426
427 /**
428 * Appends data to the buffer.
429 *
430 * Params:
431 * buffer = Buffer chunk got with $(D_PSYMBOL opIndex).
432 */
433 ref WriteBuffer opOpAssign(string op)(const T[] buffer)
434 if (op == "~")
435 {
436 size_t end, start;
437
438 if (this.position >= this.start && this.position <= ring)
439 {
440 auto afterRing = ring + 1;
441
442 end = this.position + buffer.length;
443 if (end > afterRing)
444 {
445 end = afterRing;
446 }
447 start = end - this.position;
448 this.buffer_[this.position .. end] = buffer[0 .. start];
449 if (end == afterRing)
450 {
451 this.position = this.start == 0 ? afterRing : 0;
452 }
453 else
454 {
455 this.position = end;
456 }
457 }
458
459 // Check if we have some free space at the beginning
460 if (start < buffer.length && this.position < this.start)
461 {
462 end = this.position + buffer.length - start;
463 if (end > this.start)
464 {
465 end = this.start;
466 }
467 auto areaEnd = end - this.position + start;
468 this.buffer_[this.position .. end] = buffer[start .. areaEnd];
469 this.position = end == this.start ? ring + 1 : end - this.position;
470 start = areaEnd;
471 }
472
473 // And if we still haven't found any place, save the rest in the overflow area
474 if (start < buffer.length)
475 {
476 end = this.position + buffer.length - start;
477 if (end > capacity)
478 {
479 const newSize = end / this.blockSize * this.blockSize
480 + this.blockSize;
481 () @trusted {
482 void[] buf = this.buffer_;
483 allocator.reallocate(buf, newSize * T.sizeof);
484 this.buffer_ = cast(T[]) buf;
485 }();
486 }
487 this.buffer_[this.position .. end] = buffer[start .. $];
488 this.position = end;
489 if (this.start == 0)
490 {
491 ring = capacity - 1;
492 }
493 }
494
495 return this;
496 }
497
498 /**
499 * Sets how many bytes were written. It will shrink the buffer
500 * appropriately. Always call it after $(D_PSYMBOL opIndex).
501 *
502 * Params:
503 * length = Length of the written data.
504 *
505 * Returns: $(D_KEYWORD this).
506 */
507 ref WriteBuffer opOpAssign(string op)(size_t length)
508 if (op == "+")
509 in
510 {
511 assert(length <= this.length);
512 }
513 do
514 {
515 auto afterRing = ring + 1;
516 auto oldStart = start;
517
518 if (length <= 0)
519 {
520 return this;
521 }
522 else if (this.position <= afterRing)
523 {
524 start += length;
525 if (start > 0 && this.position == afterRing)
526 {
527 this.position = oldStart;
528 }
529 }
530 else
531 {
532 auto overflow = this.position - afterRing;
533
534 if (overflow > length)
535 {
536 const afterLength = afterRing + length;
537 this.buffer_[start .. start + length] = this.buffer_[afterRing .. afterLength];
538 this.buffer_[afterRing .. afterLength] = this.buffer_[afterLength .. this.position];
539 this.position -= length;
540 }
541 else if (overflow == length)
542 {
543 this.buffer_[start .. start + overflow] = this.buffer_[afterRing .. this.position];
544 this.position -= overflow;
545 }
546 else
547 {
548 this.buffer_[start .. start + overflow] = this.buffer_[afterRing .. this.position];
549 this.position = overflow;
550 }
551 start += length;
552
553 if (start == this.position)
554 {
555 if (this.position != afterRing)
556 {
557 this.position = 0;
558 }
559 start = 0;
560 ring = capacity - 1;
561 }
562 }
563 if (start > ring)
564 {
565 start = 0;
566 }
567 return this;
568 }
569
570 ///
571 @nogc nothrow pure @system unittest
572 {
573 auto b = WriteBuffer!ubyte(6);
574 ubyte[6] buf = [23, 23, 255, 128, 127, 9];
575
576 b ~= buf;
577 assert(b.length == 6);
578 b += 2;
579 assert(b.length == 4);
580 b += 4;
581 assert(b.length == 0);
582 }
583
584 /**
585 * Returns a chunk with data.
586 *
587 * After calling it, set $(D_KEYWORD +=) to the length could be
588 * written.
589 *
590 * $(D_PSYMBOL opIndex) may return only part of the data. You may need
591 * to call it and set $(D_KEYWORD +=) several times until
592 * $(D_PSYMBOL length) is 0. If all the data can be written,
593 * maximally 3 calls are required.
594 *
595 * Returns: A chunk of data buffer.
596 */
597 T[] opSlice(size_t start, size_t end)
598 {
599 if (this.position > ring || this.position < start) // Buffer overflowed
600 {
601 return this.buffer_[this.start .. ring + 1 - length + end];
602 }
603 else
604 {
605 return this.buffer_[this.start .. this.start + end];
606 }
607 }
608
609 ///
610 @nogc nothrow pure @system unittest
611 {
612 auto b = WriteBuffer!ubyte(6);
613 ubyte[6] buf = [23, 23, 255, 128, 127, 9];
614
615 b ~= buf;
616 assert(b[0 .. $] == buf[0 .. 6]);
617 b += 2;
618
619 assert(b[0 .. $] == buf[2 .. 6]);
620
621 b ~= buf;
622 assert(b[0 .. $] == buf[2 .. 6]);
623 b += b.length;
624
625 assert(b[0 .. $] == buf[0 .. 6]);
626 b += b.length;
627 }
628
629 /**
630 * After calling it, set $(D_KEYWORD +=) to the length could be
631 * written.
632 *
633 * $(D_PSYMBOL opIndex) may return only part of the data. You may need
634 * to call it and set $(D_KEYWORD +=) several times until
635 * $(D_PSYMBOL length) is 0. If all the data can be written,
636 * maximally 3 calls are required.
637 *
638 * Returns: A chunk of data buffer.
639 */
640 T[] opIndex()
641 {
642 return opSlice(0, length);
643 }
644
645 mixin DefaultAllocator;
646 }
647
648 @nogc nothrow pure @system unittest
649 {
650 auto b = WriteBuffer!ubyte(4);
651 ubyte[3] buf = [48, 23, 255];
652
653 b ~= buf;
654 assert(b.capacity == 4);
655 assert(b.buffer_[0] == 48 && b.buffer_[1] == 23 && b.buffer_[2] == 255);
656
657 b += 2;
658 b ~= buf;
659 assert(b.capacity == 4);
660 assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
661 && b.buffer_[2] == 255 && b.buffer_[3] == 48);
662
663 b += 2;
664 b ~= buf;
665 assert(b.capacity == 8);
666 assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
667 && b.buffer_[2] == 48 && b.buffer_[3] == 23 && b.buffer_[4] == 255);
668 }
669
670 @nogc nothrow pure @system unittest
671 {
672 auto b = WriteBuffer!ubyte(2);
673 ubyte[3] buf = [48, 23, 255];
674
675 b ~= buf;
676 assert(b.start == 0);
677 assert(b.capacity == 4);
678 assert(b.ring == 3);
679 assert(b.position == 3);
680 }