1 /****************************************************************************** 2 3 Manages an array buffer for better incremental appending performance 4 5 Manages an array buffer for better performance when elements are 6 incrementally appended to an array. 7 8 Note that, as with each dynamic array, changing the length invalidates 9 existing slices to the array, potentially turning them into dangling 10 references. 11 12 Copyright: 13 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 14 All rights reserved. 15 16 License: 17 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 18 Alternatively, this file may be distributed under the terms of the Tango 19 3-Clause BSD License (see LICENSE_BSD.txt for details). 20 21 ******************************************************************************/ 22 23 module ocean.util.container.AppendBuffer; 24 25 26 import ocean.meta.types.Qualifiers; 27 28 import core.stdc.stdlib: malloc, realloc, free; 29 30 import ocean.core.ExceptionDefinitions: onOutOfMemoryError; 31 32 import ocean.meta.traits.Indirections; 33 34 import ocean.core.Verify; 35 36 version (unittest) import ocean.core.Test; 37 38 /****************************************************************************** 39 40 AppendBuffer Base interface. 41 42 ******************************************************************************/ 43 44 interface IAppendBufferBase 45 { 46 /************************************************************************** 47 48 Returns: 49 number of elements in content 50 51 **************************************************************************/ 52 53 size_t length ( ); 54 } 55 56 /****************************************************************************** 57 58 Read-only AppendBuffer interface. 59 60 Note that there is no strict write protection to an IAppendBufferReader 61 instance because it is still possible to modify the content an obtained 62 slice refers to. However, this is not the intention of this interface and 63 may not result in the desired or even result in undesired side effects. 64 65 ******************************************************************************/ 66 67 interface IAppendBufferReader ( T ) : IAppendBufferBase 68 { 69 alias T ElementType; 70 static immutable element_size = T.sizeof; 71 72 /************************************************************************** 73 74 Checks if T is 'void' or a static array type. 75 76 **************************************************************************/ 77 78 static if (!is (T == void)) 79 { 80 /********************************************************************** 81 82 Unless T is 'void' opIndex() is declared and the 83 static_array_element flag defined which tells whether T is a static 84 array type or not. 85 R is defined as return type of opIndex() and other methods which 86 return an array element. Normally this aliases T; however, if T is a 87 static array type which cannot be the return type, it aliases the 88 dynamic array of the same base type. For example, if T aliases 89 int[4], R aliases int[]. 90 If T is 'void', static_array_element, R and opIndex are not 91 declared/defined at all. 92 93 **********************************************************************/ 94 95 static if (is (T U : U[]) && !is (T == U[])) 96 { 97 static immutable static_array_element = true; 98 99 alias U[] R; 100 } 101 else 102 { 103 static immutable static_array_element = false; 104 105 alias T R; 106 } 107 108 /********************************************************************** 109 110 Returns the i-th element in content. 111 112 Params: 113 i = element index 114 115 Returns: 116 i-th element in content 117 118 **********************************************************************/ 119 120 R opIndex ( size_t i ); 121 } 122 else 123 { 124 static immutable static_array_element = false; 125 } 126 127 /************************************************************************** 128 129 Returns: 130 the current content 131 132 **************************************************************************/ 133 134 T[] opSlice ( ); 135 136 /************************************************************************** 137 138 Returns content[start .. end]. 139 start must be at most end and end must be at most the current content 140 length. 141 142 Params: 143 start = start index 144 end = end index (exclusive) 145 146 Returns: 147 content[start .. end] 148 149 **************************************************************************/ 150 151 T[] opSlice ( size_t start, size_t end ); 152 153 /************************************************************************** 154 155 Returns content[start .. length]. 156 157 Params: 158 start = start index 159 160 Returns: 161 content[start .. length] 162 163 **************************************************************************/ 164 165 T[] tail ( size_t start ); 166 } 167 168 /****************************************************************************** 169 170 AppendBuffer class template 171 172 Params: 173 T = array element type 174 use_malloc = true: use malloc()/realloc()/free() to (re/de)allocate 175 the content buffer 176 false: use new/dynamic array resizing/delete 177 178 ******************************************************************************/ 179 180 public template AppendBuffer ( T ) 181 { 182 alias AppendBuffer!(T, AppendBufferImpl) AppendBuffer; 183 } 184 185 /****************************************************************************** 186 187 AppendBuffer class template 188 189 Params: 190 T = array element type 191 Base = base class 192 193 ******************************************************************************/ 194 195 public class AppendBuffer ( T, Base: AppendBufferImpl ): Base, IAppendBufferReader!(T) 196 { 197 static if (hasIndirections!(T)) 198 { 199 // Cannot use `const` for types with indirections 200 alias T ParamT; 201 } 202 else 203 { 204 alias const(T) ParamT; 205 } 206 207 /********************************************************************** 208 209 Constructor without buffer preallocation 210 211 **********************************************************************/ 212 213 this ( ) 214 { 215 this(0); 216 } 217 218 /************************************************************************** 219 220 Constructor 221 222 Params: 223 n = content length for buffer preallocation 224 limited = true: enable size limitation, false: disable 225 226 **************************************************************************/ 227 228 this ( size_t n, bool limited = false ) 229 { 230 super(T.sizeof, n); 231 232 this.limited = limited; 233 } 234 235 /************************************************************************** 236 237 Methods overloading array operations which deal with array elements. 238 As these array operations are not available for 'void[]', they are not 239 implemented if T is 'void' . 240 241 **************************************************************************/ 242 243 static if (!is (T == void)) 244 { 245 /********************************************************************** 246 247 Returns the i-th element in content. 248 249 If T is a static array type, a slice to the element is returned. 250 251 Params: 252 i = element index 253 254 Returns: 255 i-th element in content 256 257 Out: 258 If T is a static array type, the length of the returned slice is 259 T.length. 260 261 **********************************************************************/ 262 263 R opIndex ( size_t i ) 264 out (element) 265 { 266 static if (static_array_element) 267 { 268 assert (element.length == T.length); 269 } 270 } 271 do 272 { 273 return *cast (T*) this.index_(i); 274 } 275 276 /********************************************************************** 277 278 Sets the i-th element in content. 279 280 Params: 281 val = value to set 282 i = element index 283 284 Returns: 285 element (or a slice to the element if T is a static array type). 286 287 Out: 288 If T is a static array type, the length of the returned slice is 289 T.length. 290 291 **********************************************************************/ 292 293 R opIndexAssign ( T val, size_t i ) 294 out (element) 295 { 296 static if (static_array_element) 297 { 298 assert (element.length == T.length); 299 } 300 } 301 do 302 { 303 static if (static_array_element) 304 { 305 return (*cast (T*) this.index_(i))[] = val; 306 } 307 else 308 { 309 return *cast (T*) this.index_(i) = val; 310 } 311 } 312 313 /************************************************************************** 314 315 Sets all elements in the current content to element. 316 317 Params: 318 element = element to set all elements to 319 320 Returns: 321 current content 322 323 **************************************************************************/ 324 325 T[] opSliceAssign ( ParamT element ) 326 { 327 return this.opSlice()[] = element; 328 } 329 330 /************************************************************************** 331 332 Copies chunk to the content, setting the content length to chunk.length. 333 334 Params: 335 element = chunk to copy to the content 336 start = start of the slice 337 end = end of the slice 338 339 Returns: 340 slice to chunk in the content 341 342 **************************************************************************/ 343 344 T[] opSliceAssign ( ParamT element, size_t start, size_t end ) 345 { 346 return this.opSlice(start, end)[] = element; 347 } 348 349 /************************************************************************** 350 351 Appends element to the content, extending content where required. 352 353 Params: 354 element = element to append to the content 355 356 Returns: 357 slice to element in the content 358 359 **************************************************************************/ 360 361 T[] opCatAssign ( T element ) 362 { 363 T[] dst = this.extend(1); 364 365 if (dst.length) 366 { 367 static if (static_array_element) 368 { 369 dst[0][] = element; 370 } 371 else 372 { 373 dst[0] = element; 374 } 375 } 376 377 return this[]; 378 } 379 } 380 381 382 /*************************************************************************** 383 384 Support for operator ~= for appending elements and concatenating chunks 385 386 Aliased to opCatAssign, for backwards compatibility 387 388 ***************************************************************************/ 389 390 alias opOpAssign ( istring op = "~" ) = opCatAssign; 391 392 393 /************************************************************************** 394 395 Returns: 396 the current content 397 398 **************************************************************************/ 399 400 T[] opSlice ( ) 401 { 402 return cast (T[]) this.slice_(); 403 } 404 405 /************************************************************************** 406 407 Returns content[start .. end]. 408 start must be at most end and end must be at most the current content 409 length. 410 411 Params: 412 start = start index 413 end = end index (exclusive) 414 415 Returns: 416 content[start .. end] 417 418 **************************************************************************/ 419 420 T[] opSlice ( size_t start, size_t end ) 421 { 422 return cast (T[]) this.slice_(start, end); 423 } 424 425 /************************************************************************** 426 427 Returns content[start .. length]. 428 429 Params: 430 start = start index 431 432 Returns: 433 content[start .. length] 434 435 **************************************************************************/ 436 437 T[] tail ( size_t start ) 438 { 439 return this[start .. this.length]; 440 } 441 442 /************************************************************************** 443 444 Copies chunk to the content, setting the content length to chunk.length. 445 446 Params: 447 chunk = chunk to copy to the content 448 449 Returns: 450 slice to chunk in the content 451 452 **************************************************************************/ 453 454 T[] opSliceAssign ( ParamT[] chunk ) 455 { 456 return cast (T[]) this.copy_(chunk); 457 } 458 459 /************************************************************************** 460 461 Copies chunk to content[start .. end]. 462 chunk.length must be end - start and end must be at most the current 463 content length. 464 465 Params: 466 chunk = chunk to copy to the content 467 start = start of the slice 468 end = end of the slice 469 470 Returns: 471 slice to chunk in the content 472 473 **************************************************************************/ 474 475 T[] opSliceAssign ( ParamT[] chunk, size_t start, size_t end ) 476 { 477 return cast (T[]) this.copy_(chunk, start, end); 478 } 479 480 /************************************************************************** 481 482 Appends chunk to the content, extending content where required. 483 484 Params: 485 chunk = chunk to append to the content 486 487 Returns: 488 slice to chunk in the content 489 490 **************************************************************************/ 491 492 T[] opCatAssign ( ParamT[] chunk ) 493 { 494 T[] dst = this.extend(chunk.length); 495 496 dst[] = chunk[0 .. dst.length]; 497 498 return this[]; 499 } 500 501 /************************************************************************** 502 503 Cuts the last n elements from the current content. If n is greater than 504 the current content length, all elements in the content are cut. 505 506 Params: 507 n = number of elements to cut from content, if available 508 509 Returns: 510 last n elements cut from the current content, if n is at most the 511 content length or all elements from the current content otherwise. 512 513 **************************************************************************/ 514 515 T[] cut ( size_t n ) 516 out (elements) 517 { 518 assert (elements.length <= n); 519 } 520 do 521 { 522 size_t end = this.length, 523 start = (end >= n)? end - n : 0; 524 525 scope (success) this.length = start; 526 527 return this[start .. end]; 528 } 529 530 static if (!static_array_element) 531 { 532 /********************************************************************** 533 534 Cuts the last element from the current content. 535 536 TODO: Not available if T is a static array type because a reference 537 to the removed element would be needed to be returned, but the 538 referenced element is erased and may theoretically relocated or 539 deallocated (in fact it currently stays at the same location but 540 there shouldn't be a guarantee.) 541 Should this method be available if T is a static array type? It then 542 would need to return 'void' or a struct with one member of type T. 543 (Or we wait for migration to D2.) 544 545 Returns: 546 the element cut from the current content (unless T is void). 547 548 In: 549 The content must not be empty. 550 551 **********************************************************************/ 552 553 T cut ( ) 554 { 555 verify (this.length > 0, "cannot cut last element: content is empty"); 556 557 size_t n = this.length - 1; 558 559 scope (success) this.length = n; 560 561 static if (!is (T == void)) 562 { 563 return this[n]; 564 } 565 } 566 } 567 568 /************************************************************************** 569 570 Cuts the last n elements from the current content. If n is greater than 571 the current content length, all elements in the content are cut. 572 573 Returns: 574 last n elements cut from the current content, if n is at most the 575 content length or all elements from the current content otherwise. 576 577 **************************************************************************/ 578 579 T[] dump ( ) 580 { 581 scope (exit) this.length = 0; 582 583 return this[]; 584 } 585 586 /************************************************************************** 587 588 Concatenates chunks and appends them to the content, extending the 589 content where required. 590 591 Params: 592 chunks = chunks to concatenate and append to the content 593 594 Returns: 595 slice to concatenated chunks in the content which may be shorter 596 than the chunks to concatenate if the content would have needed to 597 be extended but content length limitation is enabled. 598 599 **************************************************************************/ 600 601 T[] append ( U ... ) ( U chunks ) 602 { 603 size_t start = this.length; 604 605 Top: foreach (i, chunk; chunks) 606 { 607 static if (is (U[i] V : V[]) && is (V W : W[])) 608 { 609 foreach (chun; chunk) 610 { 611 if (!this.append(chun)) break Top; // recursive call 612 } 613 } 614 else static if (is (U[i] : T)) 615 { 616 if (!this.opCatAssign(chunk).length) break; 617 } 618 else 619 { 620 static assert (is (typeof (this.append_(chunk))), "cannot append " ~ U[i].stringof ~ " to " ~ (T[]).stringof); 621 622 if (!this.append_(chunk)) break; 623 } 624 } 625 626 return this.tail(start); 627 } 628 629 /************************************************************************** 630 631 Appends chunk to the content, extending the content where required. 632 633 Params: 634 chunks = chunk to append to the content 635 636 Returns: 637 true on success or false if the content would have needed to be 638 extended but content length limitation is enabled. 639 640 **************************************************************************/ 641 642 private bool append_ ( ParamT[] chunk ) 643 { 644 return chunk.length? this.opCatAssign(chunk).length >= chunk.length : true; 645 } 646 647 /************************************************************************** 648 649 Increases the content length by n elements. 650 651 Note that previously returned slices must not be used after this method 652 has been invoked because the content buffer may be relocated, turning 653 existing slices to it into dangling references. 654 655 Params: 656 n = number of characters to extend content by 657 658 Returns: 659 slice to the portion in content by which content has been extended 660 (last n elements in content after extension) 661 662 **************************************************************************/ 663 664 T[] extend ( size_t n ) 665 { 666 return cast (T[]) this.extend_(n); 667 } 668 669 /************************************************************************** 670 671 Returns: 672 pointer to the content 673 674 **************************************************************************/ 675 676 T* ptr ( ) 677 { 678 return cast (T*) this.index_(0); 679 } 680 681 /************************************************************************** 682 683 Sets all elements in data to the initial value of the element type. 684 data.length is guaranteed to be dividable by the element size. 685 686 Params: 687 data = data to erase 688 689 **************************************************************************/ 690 691 protected override void erase ( void[] data ) 692 { 693 static if (static_array_element && is (T U : U[]) && is (typeof (T.init) == U)) 694 { 695 // work around DMD bug 7752 696 697 static immutable t_init = [U.init]; 698 699 data[] = t_init; 700 } 701 else 702 { 703 static if (is (T == void)) 704 { 705 alias ubyte U; 706 } 707 else 708 { 709 alias T U; 710 } 711 712 (cast (U[]) data)[] = U.init; 713 } 714 } 715 } 716 717 /****************************************************************************** 718 719 Generic append buffer 720 721 ******************************************************************************/ 722 723 private abstract class AppendBufferImpl: IAppendBufferBase 724 { 725 /************************************************************************** 726 727 Content buffer. Declared as void[], but newed as ubyte[] 728 (see newContent()). 729 730 We new as ubyte[], not void[], because the GC scans void[] buffers for 731 references. (The GC determines whether a block of memory possibly 732 contains pointers or not at the point where it is newed, not based on 733 the type it is assigned to. See _d_newarrayT() and _d_newarrayiT() in 734 ocean.core.rt.compiler.dmd.rt.lifetime, lines 232 and 285, 735 "BlkAttr.NO_SCAN".) 736 737 @see http://thecybershadow.net/d/Memory_Management_in_the_D_Programming_Language.pdf 738 739 , page 30. 740 741 **************************************************************************/ 742 743 private void[] content; 744 745 /************************************************************************** 746 747 Number of elements in content 748 749 **************************************************************************/ 750 751 private size_t n = 0; 752 753 /************************************************************************** 754 755 Element size 756 757 **************************************************************************/ 758 759 private size_t e; 760 761 /************************************************************************** 762 763 Limitation flag 764 765 **************************************************************************/ 766 767 private bool limited_ = false; 768 769 /************************************************************************** 770 771 Content base pointer and length which are ensured to be invariant when 772 limitation is enabled unless the capacity is changed. 773 774 **************************************************************************/ 775 776 private struct LimitInvariants 777 { 778 private void* ptr = null; 779 size_t len; 780 } 781 782 private LimitInvariants limit_invariants; 783 784 /************************************************************************** 785 786 Consistency checks for content length and number, limitation and content 787 buffer location if limitation enabled. 788 789 **************************************************************************/ 790 791 invariant ( ) 792 { 793 assert (!(this.content.length % this.e)); 794 assert (this.n * this.e <= this.content.length); 795 796 with (this.limit_invariants) if (this.limited_) 797 { 798 assert (ptr is this.content.ptr); 799 assert (len == this.content.length); 800 } 801 else 802 { 803 assert (ptr is null); 804 } 805 } 806 807 /************************************************************************** 808 809 Constructor 810 811 Params: 812 e = element size (non-zero) 813 n = number of elements in content for preallocation (optional) 814 815 **************************************************************************/ 816 817 protected this ( size_t e, size_t n = 0 ) 818 { 819 verify (e > 0, typeof (this).stringof ~ ": element size must be at least 1"); 820 821 this.e = e; 822 823 if (n) 824 { 825 this.content = this.newContent(e * n); 826 } 827 } 828 829 /************************************************************************** 830 831 Sets the number of elements in content to 0. 832 833 Returns: 834 previous number of elements. 835 836 **************************************************************************/ 837 838 public size_t clear ( ) 839 { 840 scope (success) this.n = 0; 841 842 this.erase(this.content[0 .. this.n * this.e]); 843 844 return this.n; 845 } 846 847 /************************************************************************** 848 849 Enables or disables size limitation. 850 851 Params: 852 limited_ = true: enable size limitation, false: disable 853 854 Returns: 855 limited_ 856 857 **************************************************************************/ 858 859 public bool limited ( bool limited_ ) 860 { 861 scope (exit) this.setLimitInvariants(); 862 863 return this.limited_ = limited_; 864 } 865 866 /************************************************************************** 867 868 Returns: 869 true if size limitation is enabled or false if disabled 870 871 **************************************************************************/ 872 873 public bool limited ( ) 874 { 875 return this.limited_; 876 } 877 878 /************************************************************************** 879 880 Returns: 881 number of elements in content 882 883 **************************************************************************/ 884 885 public size_t length ( ) 886 { 887 return this.n; 888 } 889 890 /************************************************************************** 891 892 Returns: 893 size of currently allocated buffer in bytes. 894 895 **************************************************************************/ 896 897 public size_t dimension ( ) 898 { 899 return this.content.length; 900 } 901 902 /************************************************************************** 903 904 Returns: 905 available space (number of elements) in the content buffer, if 906 limitation is enabled, or size_t.max otherwise. 907 908 **************************************************************************/ 909 910 public size_t available ( ) 911 { 912 return this.limited_? this.content.length / this.e - this.n : size_t.max; 913 } 914 915 /************************************************************************** 916 917 Sets the number of elements in content (content length). If length is 918 increased, spare elements will be appended. If length is decreased, 919 elements will be removed at the end. If limitation is enabled, the 920 new number of elements is truncated to capacity(). 921 922 Note that, unless limitation is enabled, previously returned slices must 923 not be used after this method has been invoked because the content 924 buffer may be relocated, turning existing slices to it into dangling 925 references. 926 927 Params: 928 n = new number of elements in content 929 930 Returns: 931 new number of elements, will be truncated to capacity() if 932 limitation is enabled. 933 934 **************************************************************************/ 935 936 public size_t length ( size_t n ) 937 out (n_new) 938 { 939 if (this.limited_) 940 { 941 assert (n_new <= n); 942 } 943 else 944 { 945 assert (n_new == n); 946 } 947 } 948 do 949 { 950 size_t len = n * this.e; 951 952 size_t old_len = this.content.length; 953 954 if (this.content.length < len) 955 { 956 if (this.limited_) 957 { 958 len = this.content.length; 959 } 960 else 961 { 962 this.setContentLength(this.content, len); 963 } 964 } 965 966 if (old_len < len) 967 { 968 this.erase(this.content[old_len .. len]); 969 } 970 971 return this.n = len / this.e; 972 } 973 974 /************************************************************************** 975 976 Returns: 977 Actual content buffer length (number of elements). This value is 978 always at least length(). 979 980 **************************************************************************/ 981 982 public size_t capacity ( ) 983 { 984 return this.content.length / this.e; 985 } 986 987 /************************************************************************** 988 989 Returns: 990 the element size in bytes. The constructor guarantees it is > 0. 991 992 **************************************************************************/ 993 994 public size_t element_size ( ) 995 { 996 return this.e; 997 } 998 999 /************************************************************************** 1000 1001 Sets the content buffer length, preserving the actual content and 1002 overriding/adjusting the limit if limitation is enabled. 1003 If the new buffer length is less than length(), the buffer length will 1004 be set to length() so that no element is removed. 1005 1006 Note that previously returned slices must not be used after this method 1007 has been invoked because the content buffer may be relocated, turning 1008 existing slices to it into dangling references. 1009 1010 Params: 1011 capacity = new content buffer length (number of elements). 1012 1013 Returns: 1014 New content buffer length (number of elements). This value is always 1015 at least length(). 1016 1017 **************************************************************************/ 1018 1019 public size_t capacity ( size_t capacity ) 1020 { 1021 if (capacity > this.n) 1022 { 1023 this.setContentLength(this.content, capacity * this.e); 1024 1025 this.setLimitInvariants(); 1026 1027 return capacity; 1028 } 1029 else 1030 { 1031 return this.n; 1032 } 1033 } 1034 1035 /************************************************************************** 1036 1037 Sets capacity() to length(). 1038 1039 Note that previously returned slices must not be used after this method 1040 has been invoked because the content buffer may be relocated, turning 1041 existing slices to it into dangling references. 1042 1043 Returns: 1044 previous capacity(). 1045 1046 **************************************************************************/ 1047 1048 public size_t minimize ( ) 1049 { 1050 scope (success) 1051 { 1052 this.setContentLength(this.content, this.n * this.e); 1053 } 1054 1055 return this.content.length / this.e; 1056 } 1057 1058 /************************************************************************** 1059 1060 Sets all elements in data to the initial value of the element type. 1061 data.length is guaranteed to be dividable by the element size. 1062 1063 Params: 1064 data = data to erase 1065 1066 **************************************************************************/ 1067 1068 abstract protected void erase ( void[] data ); 1069 1070 /************************************************************************** 1071 1072 Returns: 1073 current content 1074 1075 **************************************************************************/ 1076 1077 protected void[] slice_ ( ) 1078 { 1079 return this.content[0 .. this.n * this.e]; 1080 } 1081 1082 /************************************************************************** 1083 1084 Slices content. start and end index content elements with element size e 1085 (as passed to the constructor). 1086 start must be at most end and end must be at most the current number 1087 of elements in content. 1088 1089 Params: 1090 start = index of start element 1091 end = index of end element (exclusive) 1092 1093 Returns: 1094 content[start * e .. end * e] 1095 1096 **************************************************************************/ 1097 1098 protected void[] slice_ ( size_t start, size_t end ) 1099 { 1100 verify (start <= end, typeof (this).stringof ~ ": slice start behind end index"); 1101 verify (end <= this.n, typeof (this).stringof ~ ": slice end out of range"); 1102 1103 return this.content[start * this.e .. end * this.e]; 1104 } 1105 1106 /************************************************************************** 1107 1108 Returns a pointer to the i-th element in content. 1109 1110 Params: 1111 i = element index 1112 1113 Returns: 1114 pointer to the i-th element in content 1115 1116 **************************************************************************/ 1117 1118 protected void* index_ ( size_t i ) 1119 { 1120 verify (i <= this.n, typeof (this).stringof ~ ": index out of range"); 1121 1122 return this.content.ptr + i * this.e; 1123 } 1124 1125 /************************************************************************** 1126 1127 Copies chunk to the content, setting the current number of elements in 1128 content to the number of elements in chunk. 1129 chunk.length must be dividable by the element size. 1130 1131 Params: 1132 chunk = chunk to copy to the content 1133 1134 Returns: 1135 slice to chunk in content 1136 1137 **************************************************************************/ 1138 1139 protected void[] copy_ ( const(void)[] src ) 1140 out (dst) 1141 { 1142 if (this.limited_) 1143 { 1144 assert (dst.length <= src.length); 1145 } 1146 else 1147 { 1148 assert (dst.length == src.length); 1149 } 1150 } 1151 do 1152 { 1153 verify (!(src.length % this.e), typeof (this).stringof ~ ": data alignment mismatch"); 1154 1155 this.n = 0; 1156 1157 void[] dst = this.extendBytes(src.length); 1158 1159 verify (dst.ptr is this.content.ptr); 1160 1161 return dst[] = src[0 .. dst.length]; 1162 } 1163 1164 /************************************************************************** 1165 1166 Copies chunk to content[start * e .. end * e]. 1167 chunk.length must be (end - start) * e and end must be at most the 1168 current number of elements in content. 1169 1170 Params: 1171 chunk = chunk to copy to the content 1172 1173 Returns: 1174 slice to chunk in the content 1175 1176 **************************************************************************/ 1177 1178 protected void[] copy_ ( const(void)[] chunk, size_t start, size_t end ) 1179 { 1180 verify (!(chunk.length % this.e), typeof (this).stringof ~ ": data alignment mismatch"); 1181 verify (start <= end, typeof (this).stringof ~ ": slice start behind end index"); 1182 verify (end <= this.n, typeof (this).stringof ~ ": slice end out of range"); 1183 verify (chunk.length == (end - start) * this.e, typeof (this).stringof ~ ": length mismatch of data to copy"); 1184 1185 return this.content[start * this.e .. end * this.e] = cast (ubyte[]) chunk[]; 1186 } 1187 1188 /************************************************************************** 1189 1190 Extends content by n elements. If limitation is enabled, n will be 1191 truncated to the number of available elements. 1192 1193 Params: 1194 n = number of elements to extend content by 1195 1196 Returns: 1197 Slice to the portion in content by which content has been extended 1198 (last n elements in content after extension). 1199 1200 **************************************************************************/ 1201 1202 protected void[] extend_ ( size_t n ) 1203 out (slice) 1204 { 1205 if (this.limited_) 1206 { 1207 assert (slice.length <= n * this.e); 1208 } 1209 else 1210 { 1211 assert (slice.length == n * this.e); 1212 } 1213 } 1214 do 1215 { 1216 return this.extendBytes(n * this.e); 1217 } 1218 1219 /************************************************************************** 1220 1221 Extends content by extent bytes. 1222 extent must be dividable by the element size e. 1223 1224 Params: 1225 extent = number of bytes to extend content by 1226 1227 Returns: 1228 slice to the portion in content by which content has been extended 1229 (last extent bytes in content after extension) 1230 1231 **************************************************************************/ 1232 1233 protected void[] extendBytes ( size_t extent ) 1234 out (slice) 1235 { 1236 assert (!(slice.length % this.e)); 1237 1238 if (this.limited_) 1239 { 1240 assert (slice.length <= extent); 1241 } 1242 else 1243 { 1244 assert (slice.length == extent); 1245 } 1246 } 1247 do 1248 { 1249 verify (!(extent % this.e)); 1250 1251 size_t oldlen = this.n * this.e, 1252 newlen = oldlen + extent; 1253 1254 if (this.content.length < newlen) 1255 { 1256 if (this.limited_) 1257 { 1258 newlen = this.content.length; 1259 } 1260 else 1261 { 1262 this.setContentLength(this.content, newlen); 1263 } 1264 } 1265 1266 this.n = newlen / this.e; 1267 1268 return this.content[oldlen .. newlen]; 1269 } 1270 1271 /************************************************************************** 1272 1273 Allocates a dynamic array of n bytes for the content. 1274 1275 Params: 1276 n = content array length 1277 1278 Returns: 1279 a newly allocated dynamic array. 1280 1281 In: 1282 n must not be zero. 1283 1284 Out: 1285 The array length must be n. 1286 1287 **************************************************************************/ 1288 1289 protected void[] newContent ( size_t n ) 1290 out (content_) 1291 { 1292 assert (content_.length == n); 1293 } 1294 do 1295 { 1296 verify (n > 0, typeof (this).stringof ~ ".newContent: attempted to allocate zero bytes"); 1297 1298 return new ubyte[n]; 1299 } 1300 1301 /************************************************************************** 1302 1303 Sets the content array length to n. 1304 1305 Params: 1306 content_ = content array, previously allocated by newContent() or 1307 modified by setContentLength() 1308 n = new content array length, may be zero 1309 1310 Out: 1311 content_.length must be n. That means, if n is 0, content_ may be 1312 null. 1313 1314 **************************************************************************/ 1315 1316 protected void setContentLength ( ref void[] content_, size_t n ) 1317 out 1318 { 1319 // FIXME assert commented out as it was failing when trying to connect 1320 // to a MySql server using drizzle probably due to a compiler bug 1321 //assert (content_.length == n, 1322 // typeof (this).stringof ~ ".setContentLength: content length mismatch"); 1323 } 1324 do 1325 { 1326 content_.length = n; 1327 assumeSafeAppend(content_); 1328 } 1329 1330 /************************************************************************** 1331 1332 Readjusts limit_invariants. 1333 1334 **************************************************************************/ 1335 1336 private void setLimitInvariants ( ) 1337 { 1338 with (this.limit_invariants) if (this.limited_) 1339 { 1340 ptr = this.content.ptr; 1341 len = this.content.length; 1342 } 1343 else 1344 { 1345 ptr = null; 1346 } 1347 } 1348 } 1349 1350 /******************************************************************************/ 1351 1352 unittest 1353 { 1354 scope ab = new AppendBuffer!(dchar)(10); 1355 1356 test (ab.length == 0); 1357 test (ab.capacity == 10); 1358 test (ab.dimension == 10 * dchar.sizeof); 1359 1360 ab[] = "Die Kotze"d; 1361 1362 test (ab.length == "Die Kotze"d.length); 1363 test (ab[] == "Die Kotze"d); 1364 test (ab.capacity == 10); 1365 test (ab.dimension == 10 * dchar.sizeof); 1366 1367 ab[5] = 'a'; 1368 test (ab.length == "Die Katze"d.length); 1369 test (ab[] == "Die Katze"d); 1370 test (ab[4 .. 9] == "Katze"d); 1371 test (ab.capacity == 10); 1372 test (ab.dimension == 10 * dchar.sizeof); 1373 1374 ab ~= ' '; 1375 1376 test (ab[] == "Die Katze "d); 1377 test (ab.length == "Die Katze "d.length); 1378 test (ab.capacity == 10); 1379 test (ab.dimension == 10 * dchar.sizeof); 1380 1381 ab ~= "tritt"d; 1382 1383 test (ab[] == "Die Katze tritt"d); 1384 test (ab.length == "Die Katze tritt"d.length); 1385 test (ab.capacity == "Die Katze tritt"d.length); 1386 test (ab.dimension == "Die Katze tritt"d.length * dchar.sizeof); 1387 1388 ab.append(" die"d[], " Treppe"d[], " krumm."d[]); 1389 1390 test (ab[] == "Die Katze tritt die Treppe krumm."d); 1391 test (ab.length == "Die Katze tritt die Treppe krumm."d.length); 1392 test (ab.capacity == "Die Katze tritt die Treppe krumm."d.length); 1393 test (ab.dimension == "Die Katze tritt die Treppe krumm."d.length * dchar.sizeof); 1394 1395 test (ab.cut(4) == "umm."d); 1396 1397 test (ab.length == "Die Katze tritt die Treppe kr"d.length); 1398 test (ab.capacity == "Die Katze tritt die Treppe krumm."d.length); 1399 test (ab.dimension == "Die Katze tritt die Treppe krumm."d.length * dchar.sizeof); 1400 1401 test (ab.cut() == 'r'); 1402 1403 test (ab.length == "Die Katze tritt die Treppe k"d.length); 1404 test (ab.capacity == "Die Katze tritt die Treppe krumm."d.length); 1405 test (ab.dimension == "Die Katze tritt die Treppe krumm."d.length * dchar.sizeof); 1406 1407 ab.clear(); 1408 1409 test (!ab.length); 1410 test (ab[] == ""d); 1411 1412 ab.extend(5); 1413 test (ab.length == 5); 1414 1415 ab[] = '~'; 1416 test (ab[] == "~~~~~"d); 1417 } 1418 1419 unittest 1420 { 1421 static struct WithIndirection 1422 { 1423 char[] value; 1424 } 1425 1426 static struct WithoutIndirection 1427 { 1428 char value; 1429 } 1430 1431 1432 scope buffer1 = new AppendBuffer!(WithIndirection); 1433 scope buffer2 = new AppendBuffer!(WithoutIndirection); 1434 1435 WithIndirection w; 1436 WithoutIndirection wo; 1437 1438 buffer1 ~= w; 1439 buffer2 ~= wo; 1440 1441 const(WithIndirection) cw = w; 1442 const(WithoutIndirection) cwo = wo; 1443 1444 static assert(!is(typeof({ buffer1 ~= cw; }))); 1445 buffer2 ~= cwo; 1446 } 1447 1448 1449 unittest 1450 { 1451 static class WithIndirection 1452 { 1453 char[] value; 1454 } 1455 1456 static class WithoutIndirection 1457 { 1458 char value; 1459 } 1460 1461 1462 scope buffer1 = new AppendBuffer!(WithIndirection); 1463 scope buffer2 = new AppendBuffer!(WithoutIndirection); 1464 1465 scope w = new WithIndirection; 1466 scope wo = new WithoutIndirection; 1467 1468 buffer1 ~= w; 1469 buffer2 ~= wo; 1470 1471 const(WithIndirection) cw = w; 1472 const(WithoutIndirection) cwo = wo; 1473 1474 static assert(!is(typeof({ buffer1 ~= cw; }))); 1475 static assert(!is(typeof({ buffer2 ~= cwo; }))); 1476 }