1 /** 2 * D header file for interaction with C++ std::vector. 3 * 4 * Copyright: Copyright (c) 2018 D Language Foundation 5 * License: Distributed under the 6 * $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0). 7 * (See accompanying file LICENSE) 8 * Authors: Guillaume Chatelet 9 * Manu Evans 10 * Source: $(DRUNTIMESRC core/stdcpp/vector.d) 11 */ 12 13 module core.stdcpp.vector; 14 15 // LDC: empty module for unsupported C++ runtimes 16 version (CppRuntime_Microsoft) version = Supported; 17 version (Supported): 18 19 /////////////////////////////////////////////////////////////////////////////// 20 // std::vector declaration. 21 // 22 // Current caveats : 23 // - missing noexcept 24 // - nothrow @trusted @nogc for most functions depend on knowledge 25 // of T's construction/destruction/assignment semantics 26 /////////////////////////////////////////////////////////////////////////////// 27 28 import core.stdcpp.allocator; 29 30 enum DefaultConstruct { value } 31 32 /// Constructor argument for default construction 33 enum Default = DefaultConstruct(); 34 35 extern(C++, "std"): 36 37 alias vector(T) = vector!(T, allocator!T); 38 extern(C++, class) struct vector(T, Alloc) 39 { 40 import core.lifetime : forward, move, core_emplace = emplace; 41 42 static assert(!is(T == bool), "vector!bool not supported!"); 43 extern(D): 44 45 /// 46 alias size_type = size_t; 47 /// 48 alias difference_type = ptrdiff_t; 49 /// 50 alias value_type = T; 51 /// 52 alias allocator_type = Alloc; 53 /// 54 alias pointer = T*; 55 /// 56 alias const_pointer = const(T)*; 57 58 /// MSVC allocates on default initialisation in debug, which can't be modelled by D `struct` 59 @disable this(); 60 61 /// 62 alias length = size; 63 /// 64 alias opDollar = length; 65 66 /// 67 size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const pure nothrow @safe @nogc { return [start, end]; } 68 69 /// 70 ref inout(T) opIndex(size_t index) inout pure nothrow @safe @nogc { return as_array[index]; } 71 /// 72 inout(T)[] opIndex(size_t[2] slice) inout pure nothrow @safe @nogc { return as_array[slice[0] .. slice[1]]; } 73 /// 74 inout(T)[] opIndex() inout pure nothrow @safe @nogc { return as_array(); } 75 76 /// 77 ref vector opAssign(U)(auto ref vector!(U, Alloc) s) { opAssign(s.as_array); return this; } 78 /// 79 ref vector opAssign(T[] array) 80 { 81 clear(); 82 reserve(array.length); 83 insert(0, array); 84 return this; 85 } 86 87 /// 88 void opIndexAssign()(auto ref T val, size_t index) { as_array[index] = val; } 89 /// 90 void opIndexAssign()(auto ref T val, size_t[2] slice) { as_array[slice[0] .. slice[1]] = val; } 91 /// 92 void opIndexAssign(T[] val, size_t[2] slice) { as_array[slice[0] .. slice[1]] = val[]; } 93 /// 94 void opIndexAssign()(auto ref T val) { as_array[] = val; } 95 /// 96 void opIndexAssign(T[] val) { as_array[] = val[]; } 97 98 /// 99 void opIndexOpAssign(string op)(auto ref T val, size_t index) { mixin("as_array[index] " ~ op ~ "= val;"); } 100 /// 101 void opIndexOpAssign(string op)(auto ref T val, size_t[2] slice) { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= val;"); } 102 /// 103 void opIndexOpAssign(string op)(T[] val, size_t[2] slice) { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= val[];"); } 104 /// 105 void opIndexOpAssign(string op)(auto ref T val) { mixin("as_array[] " ~ op ~ "= val;"); } 106 /// 107 void opIndexOpAssign(string op)(T[] val) { mixin("as_array[] " ~ op ~ "= val[];"); } 108 109 /// 110 ref inout(T) front() inout pure nothrow @safe @nogc { return as_array[0]; } 111 /// 112 ref inout(T) back() inout pure nothrow @safe @nogc { return as_array[$-1]; } 113 114 /// 115 ref vector opOpAssign(string op : "~")(auto ref T item) { push_back(forward!item); return this; } 116 /// 117 ref vector opOpAssign(string op : "~")(T[] array) { insert(length, array); return this; } 118 119 /// 120 void append(T[] array) { insert(length, array); } 121 122 /// Performs elementwise equality check. 123 bool opEquals(this This, That)(auto ref That rhs) 124 if (is(immutable That == immutable vector)) { return as_array == rhs.as_array; } 125 126 /// Performs lexicographical comparison. 127 static if (is(typeof((ref T a, ref T b) => a < b))) 128 int opCmp(this This, That)(auto ref That rhs) 129 if (is(immutable That == immutable vector)) { return __cmp(as_array, rhs.as_array); } 130 131 /// Hash to allow `vector`s to be used as keys for built-in associative arrays. 132 /// **The result will generally not be the same as C++ `std::hash<std::vector<T>>`.** 133 size_t toHash() const { return .hashOf(as_array); } 134 135 // Modifiers 136 /// 137 void push_back(U)(auto ref U element) 138 { 139 emplace_back(forward!element); 140 } 141 142 version (CppRuntime_Microsoft) 143 { 144 //---------------------------------------------------------------------------------- 145 // Microsoft runtime 146 //---------------------------------------------------------------------------------- 147 148 /// 149 this(DefaultConstruct) @nogc { _Alloc_proxy(); } 150 /// 151 this()(size_t count) 152 { 153 _Alloc_proxy(); 154 _Buy(count); 155 scope(failure) _Tidy(); 156 _Get_data()._Mylast = _Udefault(_Get_data()._Myfirst, count); 157 } 158 /// 159 this()(size_t count, auto ref T val) 160 { 161 _Alloc_proxy(); 162 _Buy(count); 163 scope(failure) _Tidy(); 164 _Get_data()._Mylast = _Ufill(_Get_data()._Myfirst, count, val); 165 } 166 /// 167 this()(T[] array) 168 { 169 _Alloc_proxy(); 170 _Buy(array.length); 171 scope(failure) _Tidy(); 172 _Get_data()._Mylast = _Utransfer!false(array.ptr, array.ptr + array.length, _Get_data()._Myfirst); 173 } 174 /// 175 this(this) 176 { 177 _Alloc_proxy(); 178 pointer _First = _Get_data()._Myfirst; 179 pointer _Last = _Get_data()._Mylast; 180 _Buy(_Last - _First); 181 scope(failure) _Tidy(); 182 _Get_data()._Mylast = _Utransfer!false(_First, _Last, _Get_data()._Myfirst); 183 } 184 185 /// 186 ~this() { _Tidy(); } 187 188 /// 189 ref inout(Alloc) get_allocator() inout pure nothrow @safe @nogc { return _Getal(); } 190 191 /// 192 size_type max_size() const pure nothrow @safe @nogc { return ((size_t.max / T.sizeof) - 1) / 2; } // HACK: clone the windows version precisely? 193 194 /// 195 size_type size() const pure nothrow @safe @nogc { return _Get_data()._Mylast - _Get_data()._Myfirst; } 196 /// 197 size_type capacity() const pure nothrow @safe @nogc { return _Get_data()._Myend - _Get_data()._Myfirst; } 198 /// 199 bool empty() const pure nothrow @safe @nogc { return _Get_data()._Myfirst == _Get_data()._Mylast; } 200 /// 201 inout(T)* data() inout pure nothrow @safe @nogc { return _Get_data()._Myfirst; } 202 /// 203 inout(T)[] as_array() inout pure nothrow @trusted @nogc { return _Get_data()._Myfirst[0 .. size()]; } 204 /// 205 ref inout(T) at(size_type i) inout pure nothrow @trusted @nogc { return _Get_data()._Myfirst[0 .. size()][i]; } 206 207 /// 208 ref T emplace_back(Args...)(auto ref Args args) 209 { 210 if (_Has_unused_capacity()) 211 return _Emplace_back_with_unused_capacity(forward!args); 212 return *_Emplace_reallocate(_Get_data()._Mylast, forward!args); 213 } 214 215 /// 216 void reserve(const size_type newCapacity) 217 { 218 if (newCapacity > capacity()) 219 { 220 // if (newCapacity > max_size()) 221 // _Xlength(); 222 _Reallocate_exactly(newCapacity); 223 } 224 } 225 226 /// 227 void shrink_to_fit() 228 { 229 if (_Has_unused_capacity()) 230 { 231 if (empty()) 232 _Tidy(); 233 else 234 _Reallocate_exactly(size()); 235 } 236 } 237 238 /// 239 void pop_back() 240 { 241 static if (_ITERATOR_DEBUG_LEVEL == 2) 242 { 243 assert(!empty(), "vector empty before pop"); 244 _Orphan_range(_Get_data()._Mylast - 1, _Get_data()._Mylast); 245 } 246 destroy!false(_Get_data()._Mylast[-1]); 247 --_Get_data()._Mylast; 248 } 249 250 /// 251 void clear() 252 { 253 _Base._Orphan_all(); 254 _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast); 255 _Get_data()._Mylast = _Get_data()._Myfirst; 256 } 257 258 /// 259 void resize()(const size_type newsize) 260 { 261 static assert(is(typeof({static T i;})), T.stringof ~ ".this() is annotated with @disable."); 262 _Resize(newsize, (pointer _Dest, size_type _Count) => _Udefault(_Dest, _Count)); 263 } 264 265 /// 266 void resize()(const size_type newsize, auto ref T val) 267 { 268 _Resize(newsize, (pointer _Dest, size_type _Count) => _Ufill(_Dest, _Count, forward!val)); 269 } 270 271 void emplace(Args...)(size_t offset, auto ref Args args) 272 { 273 pointer _Whereptr = _Get_data()._Myfirst + offset; 274 pointer _Oldlast = _Get_data()._Mylast; 275 if (_Has_unused_capacity()) 276 { 277 if (_Whereptr == _Oldlast) 278 _Emplace_back_with_unused_capacity(forward!args); 279 else 280 { 281 T _Obj = T(forward!args); 282 static if (_ITERATOR_DEBUG_LEVEL == 2) 283 _Orphan_range(_Whereptr, _Oldlast); 284 move(_Oldlast[-1], *_Oldlast); 285 ++_Get_data()._Mylast; 286 _Move_backward_unchecked(_Whereptr, _Oldlast - 1, _Oldlast); 287 move(_Obj, *_Whereptr); 288 } 289 return; 290 } 291 _Emplace_reallocate(_Whereptr, forward!args); 292 } 293 294 /// 295 void insert(size_t offset, T[] array) 296 { 297 pointer _Where = _Get_data()._Myfirst + offset; 298 pointer _First = array.ptr; 299 pointer _Last = _First + array.length; 300 301 const size_type _Count = array.length; 302 const size_type _Whereoff = offset; 303 const bool _One_at_back = _Count == 1 && _Get_data()._Myfirst + _Whereoff == _Get_data()._Mylast; 304 305 if (_Count == 0) 306 { 307 // nothing to do, avoid invalidating iterators 308 } 309 else if (_Count > _Unused_capacity()) 310 { // reallocate 311 const size_type _Oldsize = size(); 312 313 // if (_Count > max_size() - _Oldsize) 314 // _Xlength(); 315 316 const size_type _Newsize = _Oldsize + _Count; 317 const size_type _Newcapacity = _Calculate_growth(_Newsize); 318 319 pointer _Newvec = _Getal().allocate(_Newcapacity); 320 pointer _Constructed_last = _Newvec + _Whereoff + _Count; 321 pointer _Constructed_first = _Constructed_last; 322 323 try 324 { 325 _Utransfer!false(_First, _Last, _Newvec + _Whereoff); 326 _Constructed_first = _Newvec + _Whereoff; 327 328 if (_One_at_back) 329 { 330 _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec); 331 } 332 else 333 { 334 _Utransfer!true(_Get_data()._Myfirst, _Where, _Newvec); 335 _Constructed_first = _Newvec; 336 _Utransfer!true(_Where, _Get_data()._Mylast, _Newvec + _Whereoff + _Count); 337 } 338 } 339 catch (Throwable e) 340 { 341 _Destroy(_Constructed_first, _Constructed_last); 342 _Getal().deallocate(_Newvec, _Newcapacity); 343 throw e; 344 } 345 346 _Change_array(_Newvec, _Newsize, _Newcapacity); 347 } 348 else 349 { // Attempt to provide the strong guarantee for EmplaceConstructible failure. 350 // If we encounter copy/move construction/assignment failure, provide the basic guarantee. 351 // (For one-at-back, this provides the strong guarantee.) 352 353 pointer _Oldlast = _Get_data()._Mylast; 354 const size_type _Affected_elements = cast(size_type)(_Oldlast - _Where); 355 356 if (_Count < _Affected_elements) 357 { // some affected elements must be assigned 358 _Get_data()._Mylast = _Utransfer!true(_Oldlast - _Count, _Oldlast, _Oldlast); 359 _Move_backward_unchecked(_Where, _Oldlast - _Count, _Oldlast); 360 _Destroy(_Where, _Where + _Count); 361 362 try 363 { 364 _Utransfer!false(_First, _Last, _Where); 365 } 366 catch (Throwable e) 367 { 368 // glue the broken pieces back together 369 try 370 { 371 _Utransfer!true(_Where + _Count, _Where + 2 * _Count, _Where); 372 } 373 catch (Throwable e) 374 { 375 // vaporize the detached piece 376 static if (_ITERATOR_DEBUG_LEVEL == 2) 377 _Orphan_range(_Where, _Oldlast); 378 _Destroy(_Where + _Count, _Get_data()._Mylast); 379 _Get_data()._Mylast = _Where; 380 throw e; 381 } 382 383 _Move_unchecked(_Where + 2 * _Count, _Get_data()._Mylast, _Where + _Count); 384 _Destroy(_Oldlast, _Get_data()._Mylast); 385 _Get_data()._Mylast = _Oldlast; 386 throw e; 387 } 388 } 389 else 390 { // affected elements don't overlap before/after 391 pointer _Relocated = _Where + _Count; 392 _Get_data()._Mylast = _Utransfer!true(_Where, _Oldlast, _Relocated); 393 _Destroy(_Where, _Oldlast); 394 395 try 396 { 397 _Utransfer!false(_First, _Last, _Where); 398 } 399 catch (Throwable e) 400 { 401 // glue the broken pieces back together 402 try 403 { 404 _Utransfer!true(_Relocated, _Get_data()._Mylast, _Where); 405 } 406 catch (Throwable e) 407 { 408 // vaporize the detached piece 409 static if (_ITERATOR_DEBUG_LEVEL == 2) 410 _Orphan_range(_Where, _Oldlast); 411 _Destroy(_Relocated, _Get_data()._Mylast); 412 _Get_data()._Mylast = _Where; 413 throw e; 414 } 415 416 _Destroy(_Relocated, _Get_data()._Mylast); 417 _Get_data()._Mylast = _Oldlast; 418 throw e; 419 } 420 } 421 static if (_ITERATOR_DEBUG_LEVEL == 2) 422 _Orphan_range(_Where, _Oldlast); 423 } 424 } 425 426 private: 427 import core.stdcpp.xutility : MSVCLinkDirectives; 428 429 // Make sure the object files wont link against mismatching objects 430 mixin MSVCLinkDirectives!true; 431 432 pragma(inline, true) 433 { 434 ref inout(_Base.Alloc) _Getal() inout pure nothrow @safe @nogc { return _Base._Mypair._Myval1; } 435 ref inout(_Base.ValTy) _Get_data() inout pure nothrow @safe @nogc { return _Base._Mypair._Myval2; } 436 } 437 438 void _Alloc_proxy() @nogc 439 { 440 static if (_ITERATOR_DEBUG_LEVEL > 0) 441 _Base._Alloc_proxy(); 442 } 443 444 void _AssignAllocator(ref const(allocator_type) al) nothrow @nogc 445 { 446 static if (_Base._Mypair._HasFirst) 447 _Getal() = al; 448 } 449 450 bool _Buy(size_type _Newcapacity) @trusted @nogc 451 { 452 _Get_data()._Myfirst = null; 453 _Get_data()._Mylast = null; 454 _Get_data()._Myend = null; 455 456 if (_Newcapacity == 0) 457 return false; 458 459 // TODO: how to handle this in D? kinda like a range exception... 460 // if (_Newcapacity > max_size()) 461 // _Xlength(); 462 463 _Get_data()._Myfirst = _Getal().allocate(_Newcapacity); 464 _Get_data()._Mylast = _Get_data()._Myfirst; 465 _Get_data()._Myend = _Get_data()._Myfirst + _Newcapacity; 466 467 return true; 468 } 469 470 static void _Destroy(pointer _First, pointer _Last) 471 { 472 for (; _First != _Last; ++_First) 473 destroy!false(*_First); 474 } 475 476 void _Tidy() 477 { 478 _Base._Orphan_all(); 479 if (_Get_data()._Myfirst) 480 { 481 _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast); 482 _Getal().deallocate(_Get_data()._Myfirst, capacity()); 483 _Get_data()._Myfirst = null; 484 _Get_data()._Mylast = null; 485 _Get_data()._Myend = null; 486 } 487 } 488 489 size_type _Unused_capacity() const pure nothrow @safe @nogc 490 { 491 return _Get_data()._Myend - _Get_data()._Mylast; 492 } 493 494 bool _Has_unused_capacity() const pure nothrow @safe @nogc 495 { 496 return _Get_data()._Myend != _Get_data()._Mylast; 497 } 498 499 ref T _Emplace_back_with_unused_capacity(Args...)(auto ref Args args) 500 { 501 core_emplace(_Get_data()._Mylast, forward!args); 502 static if (_ITERATOR_DEBUG_LEVEL == 2) 503 _Orphan_range(_Get_data()._Mylast, _Get_data()._Mylast); 504 return *_Get_data()._Mylast++; 505 } 506 507 pointer _Emplace_reallocate(_Valty...)(pointer _Whereptr, auto ref _Valty _Val) 508 { 509 const size_type _Whereoff = _Whereptr - _Get_data()._Myfirst; 510 const size_type _Oldsize = size(); 511 512 // TODO: what should we do in D? kinda like a range overflow? 513 // if (_Oldsize == max_size()) 514 // _Xlength(); 515 516 const size_type _Newsize = _Oldsize + 1; 517 const size_type _Newcapacity = _Calculate_growth(_Newsize); 518 519 pointer _Newvec = _Getal().allocate(_Newcapacity); 520 pointer _Constructed_last = _Newvec + _Whereoff + 1; 521 pointer _Constructed_first = _Constructed_last; 522 523 try 524 { 525 core_emplace(_Newvec + _Whereoff, forward!_Val); 526 _Constructed_first = _Newvec + _Whereoff; 527 if (_Whereptr == _Get_data()._Mylast) 528 _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec); 529 else 530 { 531 _Utransfer!true(_Get_data()._Myfirst, _Whereptr, _Newvec); 532 _Constructed_first = _Newvec; 533 _Utransfer!true(_Whereptr, _Get_data()._Mylast, _Newvec + _Whereoff + 1); 534 } 535 } 536 catch (Throwable e) 537 { 538 _Destroy(_Constructed_first, _Constructed_last); 539 _Getal().deallocate(_Newvec, _Newcapacity); 540 throw e; 541 } 542 543 _Change_array(_Newvec, _Newsize, _Newcapacity); 544 return _Get_data()._Myfirst + _Whereoff; 545 } 546 547 void _Resize(_Lambda)(const size_type _Newsize, _Lambda _Udefault_or_fill) 548 { 549 const size_type _Oldsize = size(); 550 const size_type _Oldcapacity = capacity(); 551 552 if (_Newsize > _Oldcapacity) 553 { 554 // if (_Newsize > max_size()) 555 // _Xlength(); 556 557 const size_type _Newcapacity = _Calculate_growth(_Newsize); 558 559 pointer _Newvec = _Getal().allocate(_Newcapacity); 560 pointer _Appended_first = _Newvec + _Oldsize; 561 pointer _Appended_last = _Appended_first; 562 563 try 564 { 565 _Appended_last = _Udefault_or_fill(_Appended_first, _Newsize - _Oldsize); 566 _Utransfer!(true, true)(_Get_data()._Myfirst, _Get_data()._Mylast, _Newvec); 567 } 568 catch (Throwable e) 569 { 570 _Destroy(_Appended_first, _Appended_last); 571 _Getal().deallocate(_Newvec, _Newcapacity); 572 throw e; 573 } 574 _Change_array(_Newvec, _Newsize, _Newcapacity); 575 } 576 else if (_Newsize > _Oldsize) 577 { 578 pointer _Oldlast = _Get_data()._Mylast; 579 _Get_data()._Mylast = _Udefault_or_fill(_Oldlast, _Newsize - _Oldsize); 580 static if (_ITERATOR_DEBUG_LEVEL == 2) 581 _Orphan_range(_Oldlast, _Oldlast); 582 } 583 else if (_Newsize == _Oldsize) 584 { 585 // nothing to do, avoid invalidating iterators 586 } 587 else 588 { 589 pointer _Newlast = _Get_data()._Myfirst + _Newsize; 590 static if (_ITERATOR_DEBUG_LEVEL == 2) 591 _Orphan_range(_Newlast, _Get_data()._Mylast); 592 _Destroy(_Newlast, _Get_data()._Mylast); 593 _Get_data()._Mylast = _Newlast; 594 } 595 } 596 597 void _Reallocate_exactly(const size_type _Newcapacity) 598 { 599 import core.lifetime : moveEmplace; 600 601 const size_type _Size = size(); 602 pointer _Newvec = _Getal().allocate(_Newcapacity); 603 604 try 605 { 606 for (size_t i = _Size; i > 0; ) 607 { 608 --i; 609 moveEmplace(_Get_data()._Myfirst[i], _Newvec[i]); 610 } 611 } 612 catch (Throwable e) 613 { 614 _Getal().deallocate(_Newvec, _Newcapacity); 615 throw e; 616 } 617 618 _Change_array(_Newvec, _Size, _Newcapacity); 619 } 620 621 void _Change_array(pointer _Newvec, const size_type _Newsize, const size_type _Newcapacity) 622 { 623 _Base._Orphan_all(); 624 625 if (_Get_data()._Myfirst != null) 626 { 627 _Destroy(_Get_data()._Myfirst, _Get_data()._Mylast); 628 _Getal().deallocate(_Get_data()._Myfirst, capacity()); 629 } 630 631 _Get_data()._Myfirst = _Newvec; 632 _Get_data()._Mylast = _Newvec + _Newsize; 633 _Get_data()._Myend = _Newvec + _Newcapacity; 634 } 635 636 size_type _Calculate_growth(const size_type _Newsize) const pure nothrow @nogc @safe 637 { 638 const size_type _Oldcapacity = capacity(); 639 if (_Oldcapacity > max_size() - _Oldcapacity/2) 640 return _Newsize; 641 const size_type _Geometric = _Oldcapacity + _Oldcapacity/2; 642 if (_Geometric < _Newsize) 643 return _Newsize; 644 return _Geometric; 645 } 646 647 struct _Uninitialized_backout 648 { 649 this() @disable; 650 this(pointer _Dest) 651 { 652 _First = _Dest; 653 _Last = _Dest; 654 } 655 ~this() 656 { 657 _Destroy(_First, _Last); 658 } 659 void _Emplace_back(Args...)(auto ref Args args) 660 { 661 core_emplace(_Last, forward!args); 662 ++_Last; 663 } 664 pointer _Release() 665 { 666 _First = _Last; 667 return _Last; 668 } 669 private: 670 pointer _First; 671 pointer _Last; 672 } 673 pointer _Utransfer(bool _move, bool _ifNothrow = false)(pointer _First, pointer _Last, pointer _Dest) 674 { 675 // TODO: if copy/move are trivial, then we can memcpy/memmove 676 auto _Backout = _Uninitialized_backout(_Dest); 677 for (; _First != _Last; ++_First) 678 { 679 static if (_move && (!_ifNothrow || true)) // isNothrow!T (move in D is always nothrow! ...until opPostMove) 680 _Backout._Emplace_back(move(*_First)); 681 else 682 _Backout._Emplace_back(*_First); 683 } 684 return _Backout._Release(); 685 } 686 pointer _Ufill()(pointer _Dest, size_t _Count, auto ref T val) 687 { 688 // TODO: if T.sizeof == 1 and no elaborate constructor, fast-path to memset 689 // TODO: if copy ctor/postblit are nothrow, just range assign 690 auto _Backout = _Uninitialized_backout(_Dest); 691 for (; 0 < _Count; --_Count) 692 _Backout._Emplace_back(val); 693 return _Backout._Release(); 694 } 695 pointer _Udefault()(pointer _Dest, size_t _Count) 696 { 697 // TODO: if zero init, then fast-path to zeromem 698 auto _Backout = _Uninitialized_backout(_Dest); 699 for (; 0 < _Count; --_Count) 700 _Backout._Emplace_back(); 701 return _Backout._Release(); 702 } 703 pointer _Move_unchecked(pointer _First, pointer _Last, pointer _Dest) 704 { 705 // TODO: can `memmove` if conditions are right... 706 for (; _First != _Last; ++_Dest, ++_First) 707 move(*_First, *_Dest); 708 return _Dest; 709 } 710 pointer _Move_backward_unchecked(pointer _First, pointer _Last, pointer _Dest) 711 { 712 while (_First != _Last) 713 move(*--_Last, *--_Dest); 714 return _Dest; 715 } 716 717 static if (_ITERATOR_DEBUG_LEVEL == 2) 718 { 719 void _Orphan_range(pointer _First, pointer _Last) const @nogc 720 { 721 import core.stdcpp.xutility : _Lockit, _LOCK_DEBUG; 722 723 alias const_iterator = _Base.const_iterator; 724 auto _Lock = _Lockit(_LOCK_DEBUG); 725 726 const_iterator** _Pnext = cast(const_iterator**)_Get_data()._Base._Getpfirst(); 727 if (!_Pnext) 728 return; 729 730 while (*_Pnext) 731 { 732 if ((*_Pnext)._Ptr < _First || _Last < (*_Pnext)._Ptr) 733 { 734 _Pnext = cast(const_iterator**)(*_Pnext)._Base._Getpnext(); 735 } 736 else 737 { 738 (*_Pnext)._Base._Clrcont(); 739 *_Pnext = *cast(const_iterator**)(*_Pnext)._Base._Getpnext(); 740 } 741 } 742 } 743 } 744 745 _Vector_alloc!(_Vec_base_types!(T, Alloc)) _Base; 746 } 747 else version (None) 748 { 749 size_type size() const pure nothrow @safe @nogc { return 0; } 750 size_type capacity() const pure nothrow @safe @nogc { return 0; } 751 bool empty() const pure nothrow @safe @nogc { return true; } 752 753 inout(T)* data() inout pure nothrow @safe @nogc { return null; } 754 inout(T)[] as_array() inout pure nothrow @trusted @nogc { return null; } 755 ref inout(T) at(size_type i) inout pure nothrow @trusted @nogc { data()[0]; } 756 } 757 else 758 { 759 static assert(false, "C++ runtime not supported"); 760 } 761 } 762 763 764 // platform detail 765 private: 766 version (CppRuntime_Microsoft) 767 { 768 import core.stdcpp.xutility : _ITERATOR_DEBUG_LEVEL; 769 770 extern (C++, struct) struct _Vec_base_types(_Ty, _Alloc0) 771 { 772 alias Ty = _Ty; 773 alias Alloc = _Alloc0; 774 } 775 776 extern (C++, class) struct _Vector_alloc(_Alloc_types) 777 { 778 import core.stdcpp.xutility : _Compressed_pair; 779 extern(D): 780 @nogc: 781 782 alias Ty = _Alloc_types.Ty; 783 alias Alloc = _Alloc_types.Alloc; 784 alias ValTy = _Vector_val!Ty; 785 786 void _Orphan_all() nothrow @safe 787 { 788 static if (is(typeof(ValTy._Base))) 789 _Mypair._Myval2._Base._Orphan_all(); 790 } 791 792 static if (_ITERATOR_DEBUG_LEVEL != 0) 793 { 794 import core.stdcpp.xutility : _Container_proxy; 795 796 alias const_iterator = _Vector_const_iterator!(ValTy); 797 798 ~this() 799 { 800 _Free_proxy(); 801 } 802 803 void _Alloc_proxy() @trusted 804 { 805 import core.lifetime : emplace; 806 807 alias _Alproxy = Alloc.rebind!_Container_proxy; 808 _Alproxy _Proxy_allocator = _Alproxy(_Mypair._Myval1); 809 _Mypair._Myval2._Base._Myproxy = _Proxy_allocator.allocate(1); 810 emplace(_Mypair._Myval2._Base._Myproxy); 811 _Mypair._Myval2._Base._Myproxy._Mycont = &_Mypair._Myval2._Base; 812 } 813 void _Free_proxy() 814 { 815 alias _Alproxy = Alloc.rebind!_Container_proxy; 816 _Alproxy _Proxy_allocator = _Alproxy(_Mypair._Myval1); 817 _Orphan_all(); 818 destroy!false(_Mypair._Myval2._Base._Myproxy); 819 _Proxy_allocator.deallocate(_Mypair._Myval2._Base._Myproxy, 1); 820 _Mypair._Myval2._Base._Myproxy = null; 821 } 822 } 823 824 _Compressed_pair!(Alloc, ValTy) _Mypair; 825 } 826 827 extern (C++, class) struct _Vector_val(T) 828 { 829 import core.stdcpp.xutility : _Container_base; 830 import core.stdcpp.type_traits : is_empty; 831 832 alias pointer = T*; 833 834 static if (!is_empty!_Container_base.value) 835 _Container_base _Base; 836 837 pointer _Myfirst; // pointer to beginning of array 838 pointer _Mylast; // pointer to current end of sequence 839 pointer _Myend; // pointer to end of array 840 } 841 842 static if (_ITERATOR_DEBUG_LEVEL > 0) 843 { 844 extern (C++, class) struct _Vector_const_iterator(_Myvec) 845 { 846 import core.stdcpp.xutility : _Iterator_base; 847 import core.stdcpp.type_traits : is_empty; 848 849 static if (!is_empty!_Iterator_base.value) 850 _Iterator_base _Base; 851 _Myvec.pointer _Ptr; 852 } 853 } 854 }