1/* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved. 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public License 15 * along with this library; see the file COPYING.LIB. If not, write to 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 17 * Boston, MA 02110-1301, USA. 18 * 19 */ 20 21#ifndef WTF_Vector_h 22#define WTF_Vector_h 23 24#include <initializer_list> 25#include <limits> 26#include <string.h> 27#include <type_traits> 28#include <utility> 29#include <wtf/CheckedArithmetic.h> 30#include <wtf/FastMalloc.h> 31#include <wtf/MallocPtr.h> 32#include <wtf/Noncopyable.h> 33#include <wtf/StdLibExtras.h> 34#include <wtf/ValueCheck.h> 35#include <wtf/VectorTraits.h> 36 37namespace WTF { 38 39const size_t notFound = static_cast<size_t>(-1); 40 41template <bool needsDestruction, typename T> 42struct VectorDestructor; 43 44template<typename T> 45struct VectorDestructor<false, T> 46{ 47 static void destruct(T*, T*) {} 48}; 49 50template<typename T> 51struct VectorDestructor<true, T> 52{ 53 static void destruct(T* begin, T* end) 54 { 55 for (T* cur = begin; cur != end; ++cur) 56 cur->~T(); 57 } 58}; 59 60template <bool needsInitialization, bool canInitializeWithMemset, typename T> 61struct VectorInitializer; 62 63template<bool ignore, typename T> 64struct VectorInitializer<false, ignore, T> 65{ 66 static void initialize(T*, T*) {} 67}; 68 69template<typename T> 70struct VectorInitializer<true, false, T> 71{ 72 static void initialize(T* begin, T* end) 73 { 74 for (T* cur = begin; cur != end; ++cur) 75 new (NotNull, cur) T; 76 } 77}; 78 79template<typename T> 80struct VectorInitializer<true, true, T> 81{ 82 static void initialize(T* begin, T* end) 83 { 84 memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin)); 85 } 86}; 87 88template <bool canMoveWithMemcpy, typename T> 89struct VectorMover; 90 91template<typename T> 92struct VectorMover<false, T> 93{ 94 static void move(T* src, T* srcEnd, T* dst) 95 { 96 while (src != srcEnd) { 97 new (NotNull, dst) T(WTF::move(*src)); 98 src->~T(); 99 ++dst; 100 ++src; 101 } 102 } 103 static void moveOverlapping(T* src, T* srcEnd, T* dst) 104 { 105 if (src > dst) 106 move(src, srcEnd, dst); 107 else { 108 T* dstEnd = dst + (srcEnd - src); 109 while (src != srcEnd) { 110 --srcEnd; 111 --dstEnd; 112 new (NotNull, dstEnd) T(WTF::move(*srcEnd)); 113 srcEnd->~T(); 114 } 115 } 116 } 117}; 118 119template<typename T> 120struct VectorMover<true, T> 121{ 122 static void move(const T* src, const T* srcEnd, T* dst) 123 { 124 memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 125 } 126 static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 127 { 128 memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 129 } 130}; 131 132template <bool canCopyWithMemcpy, typename T> 133struct VectorCopier; 134 135template<typename T> 136struct VectorCopier<false, T> 137{ 138 template<typename U> 139 static void uninitializedCopy(const T* src, const T* srcEnd, U* dst) 140 { 141 while (src != srcEnd) { 142 new (NotNull, dst) U(*src); 143 ++dst; 144 ++src; 145 } 146 } 147}; 148 149template<typename T> 150struct VectorCopier<true, T> 151{ 152 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 153 { 154 memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src)); 155 } 156 template<typename U> 157 static void uninitializedCopy(const T* src, const T* srcEnd, U* dst) 158 { 159 VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst); 160 } 161}; 162 163template <bool canFillWithMemset, typename T> 164struct VectorFiller; 165 166template<typename T> 167struct VectorFiller<false, T> 168{ 169 static void uninitializedFill(T* dst, T* dstEnd, const T& val) 170 { 171 while (dst != dstEnd) { 172 new (NotNull, dst) T(val); 173 ++dst; 174 } 175 } 176}; 177 178template<typename T> 179struct VectorFiller<true, T> 180{ 181 static void uninitializedFill(T* dst, T* dstEnd, const T& val) 182 { 183 static_assert(sizeof(T) == 1, "Size of type T should be equal to one!"); 184#if COMPILER(GCC) && defined(_FORTIFY_SOURCE) 185 if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst))) 186#endif 187 memset(dst, val, dstEnd - dst); 188 } 189}; 190 191template<bool canCompareWithMemcmp, typename T> 192struct VectorComparer; 193 194template<typename T> 195struct VectorComparer<false, T> 196{ 197 static bool compare(const T* a, const T* b, size_t size) 198 { 199 for (size_t i = 0; i < size; ++i) 200 if (!(a[i] == b[i])) 201 return false; 202 return true; 203 } 204}; 205 206template<typename T> 207struct VectorComparer<true, T> 208{ 209 static bool compare(const T* a, const T* b, size_t size) 210 { 211 return memcmp(a, b, sizeof(T) * size) == 0; 212 } 213}; 214 215template<typename T> 216struct VectorTypeOperations 217{ 218 static void destruct(T* begin, T* end) 219 { 220 VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end); 221 } 222 223 static void initialize(T* begin, T* end) 224 { 225 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end); 226 } 227 228 static void move(T* src, T* srcEnd, T* dst) 229 { 230 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst); 231 } 232 233 static void moveOverlapping(T* src, T* srcEnd, T* dst) 234 { 235 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst); 236 } 237 238 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 239 { 240 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst); 241 } 242 243 static void uninitializedFill(T* dst, T* dstEnd, const T& val) 244 { 245 VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val); 246 } 247 248 static bool compare(const T* a, const T* b, size_t size) 249 { 250 return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size); 251 } 252}; 253 254template<typename T> 255class VectorBufferBase { 256 WTF_MAKE_NONCOPYABLE(VectorBufferBase); 257public: 258 void allocateBuffer(size_t newCapacity) 259 { 260 ASSERT(newCapacity); 261 if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T)) 262 CRASH(); 263 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); 264 m_capacity = sizeToAllocate / sizeof(T); 265 m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate)); 266 } 267 268 bool tryAllocateBuffer(size_t newCapacity) 269 { 270 ASSERT(newCapacity); 271 if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T)) 272 return false; 273 274 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); 275 T* newBuffer; 276 if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) { 277 m_capacity = sizeToAllocate / sizeof(T); 278 m_buffer = newBuffer; 279 return true; 280 } 281 return false; 282 } 283 284 bool shouldReallocateBuffer(size_t newCapacity) const 285 { 286 return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity; 287 } 288 289 void reallocateBuffer(size_t newCapacity) 290 { 291 ASSERT(shouldReallocateBuffer(newCapacity)); 292 if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T)) 293 CRASH(); 294 size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); 295 m_capacity = sizeToAllocate / sizeof(T); 296 m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate)); 297 } 298 299 void deallocateBuffer(T* bufferToDeallocate) 300 { 301 if (!bufferToDeallocate) 302 return; 303 304 if (m_buffer == bufferToDeallocate) { 305 m_buffer = 0; 306 m_capacity = 0; 307 } 308 309 fastFree(bufferToDeallocate); 310 } 311 312 T* buffer() { return m_buffer; } 313 const T* buffer() const { return m_buffer; } 314 static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); } 315 size_t capacity() const { return m_capacity; } 316 317 MallocPtr<T> releaseBuffer() 318 { 319 T* buffer = m_buffer; 320 m_buffer = 0; 321 m_capacity = 0; 322 return adoptMallocPtr(buffer); 323 } 324 325protected: 326 VectorBufferBase() 327 : m_buffer(0) 328 , m_capacity(0) 329 , m_size(0) 330 { 331 } 332 333 VectorBufferBase(T* buffer, size_t capacity, size_t size) 334 : m_buffer(buffer) 335 , m_capacity(capacity) 336 , m_size(size) 337 { 338 } 339 340 ~VectorBufferBase() 341 { 342 // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here. 343 } 344 345 T* m_buffer; 346 unsigned m_capacity; 347 unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct. 348}; 349 350template<typename T, size_t inlineCapacity> 351class VectorBuffer; 352 353template<typename T> 354class VectorBuffer<T, 0> : private VectorBufferBase<T> { 355private: 356 typedef VectorBufferBase<T> Base; 357public: 358 VectorBuffer() 359 { 360 } 361 362 VectorBuffer(size_t capacity, size_t size = 0) 363 { 364 m_size = size; 365 // Calling malloc(0) might take a lock and may actually do an 366 // allocation on some systems. 367 if (capacity) 368 allocateBuffer(capacity); 369 } 370 371 ~VectorBuffer() 372 { 373 deallocateBuffer(buffer()); 374 } 375 376 void swap(VectorBuffer<T, 0>& other, size_t, size_t) 377 { 378 std::swap(m_buffer, other.m_buffer); 379 std::swap(m_capacity, other.m_capacity); 380 } 381 382 void restoreInlineBufferIfNeeded() { } 383 384 using Base::allocateBuffer; 385 using Base::tryAllocateBuffer; 386 using Base::shouldReallocateBuffer; 387 using Base::reallocateBuffer; 388 using Base::deallocateBuffer; 389 390 using Base::buffer; 391 using Base::capacity; 392 using Base::bufferMemoryOffset; 393 394 using Base::releaseBuffer; 395 396protected: 397 using Base::m_size; 398 399private: 400 using Base::m_buffer; 401 using Base::m_capacity; 402}; 403 404template<typename T, size_t inlineCapacity> 405class VectorBuffer : private VectorBufferBase<T> { 406 WTF_MAKE_NONCOPYABLE(VectorBuffer); 407private: 408 typedef VectorBufferBase<T> Base; 409public: 410 VectorBuffer() 411 : Base(inlineBuffer(), inlineCapacity, 0) 412 { 413 } 414 415 VectorBuffer(size_t capacity, size_t size = 0) 416 : Base(inlineBuffer(), inlineCapacity, size) 417 { 418 if (capacity > inlineCapacity) 419 Base::allocateBuffer(capacity); 420 } 421 422 ~VectorBuffer() 423 { 424 deallocateBuffer(buffer()); 425 } 426 427 void allocateBuffer(size_t newCapacity) 428 { 429 // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks. 430 if (newCapacity > inlineCapacity) 431 Base::allocateBuffer(newCapacity); 432 else { 433 m_buffer = inlineBuffer(); 434 m_capacity = inlineCapacity; 435 } 436 } 437 438 bool tryAllocateBuffer(size_t newCapacity) 439 { 440 if (newCapacity > inlineCapacity) 441 return Base::tryAllocateBuffer(newCapacity); 442 m_buffer = inlineBuffer(); 443 m_capacity = inlineCapacity; 444 return true; 445 } 446 447 void deallocateBuffer(T* bufferToDeallocate) 448 { 449 if (bufferToDeallocate == inlineBuffer()) 450 return; 451 Base::deallocateBuffer(bufferToDeallocate); 452 } 453 454 bool shouldReallocateBuffer(size_t newCapacity) const 455 { 456 // We cannot reallocate the inline buffer. 457 return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity; 458 } 459 460 void reallocateBuffer(size_t newCapacity) 461 { 462 ASSERT(shouldReallocateBuffer(newCapacity)); 463 Base::reallocateBuffer(newCapacity); 464 } 465 466 void swap(VectorBuffer& other, size_t mySize, size_t otherSize) 467 { 468 if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) { 469 swapInlineBuffer(other, mySize, otherSize); 470 std::swap(m_capacity, other.m_capacity); 471 } else if (buffer() == inlineBuffer()) { 472 m_buffer = other.m_buffer; 473 other.m_buffer = other.inlineBuffer(); 474 swapInlineBuffer(other, mySize, 0); 475 std::swap(m_capacity, other.m_capacity); 476 } else if (other.buffer() == other.inlineBuffer()) { 477 other.m_buffer = m_buffer; 478 m_buffer = inlineBuffer(); 479 swapInlineBuffer(other, 0, otherSize); 480 std::swap(m_capacity, other.m_capacity); 481 } else { 482 std::swap(m_buffer, other.m_buffer); 483 std::swap(m_capacity, other.m_capacity); 484 } 485 } 486 487 void restoreInlineBufferIfNeeded() 488 { 489 if (m_buffer) 490 return; 491 m_buffer = inlineBuffer(); 492 m_capacity = inlineCapacity; 493 } 494 495 using Base::buffer; 496 using Base::capacity; 497 using Base::bufferMemoryOffset; 498 499 MallocPtr<T> releaseBuffer() 500 { 501 if (buffer() == inlineBuffer()) 502 return nullptr; 503 return Base::releaseBuffer(); 504 } 505 506protected: 507 using Base::m_size; 508 509private: 510 using Base::m_buffer; 511 using Base::m_capacity; 512 513 void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize) 514 { 515 // FIXME: We could make swap part of VectorTypeOperations 516 // https://bugs.webkit.org/show_bug.cgi?id=128863 517 518 if (std::is_pod<T>::value) 519 std::swap(m_inlineBuffer, other.m_inlineBuffer); 520 else 521 swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize); 522 } 523 524 static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize) 525 { 526 if (left == right) 527 return; 528 529 ASSERT(leftSize <= inlineCapacity); 530 ASSERT(rightSize <= inlineCapacity); 531 532 size_t swapBound = std::min(leftSize, rightSize); 533 for (unsigned i = 0; i < swapBound; ++i) 534 std::swap(left[i], right[i]); 535 VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound); 536 VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound); 537 } 538 539 T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); } 540 const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); } 541 542 typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity]; 543}; 544 545struct UnsafeVectorOverflow { 546 static NO_RETURN_DUE_TO_ASSERT void overflowed() 547 { 548 ASSERT_NOT_REACHED(); 549 } 550}; 551 552template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow> 553class Vector : private VectorBuffer<T, inlineCapacity> { 554 WTF_MAKE_FAST_ALLOCATED; 555private: 556 typedef VectorBuffer<T, inlineCapacity> Base; 557 typedef VectorTypeOperations<T> TypeOperations; 558 559public: 560 typedef T ValueType; 561 562 typedef T* iterator; 563 typedef const T* const_iterator; 564 typedef std::reverse_iterator<iterator> reverse_iterator; 565 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 566 567 Vector() 568 { 569 } 570 571 // Unlike in std::vector, this constructor does not initialize POD types. 572 explicit Vector(size_t size) 573 : Base(size, size) 574 { 575 if (begin()) 576 TypeOperations::initialize(begin(), end()); 577 } 578 579 Vector(size_t size, const T& val) 580 : Base(size, size) 581 { 582 if (begin()) 583 TypeOperations::uninitializedFill(begin(), end(), val); 584 } 585 586 Vector(std::initializer_list<T> initializerList) 587 { 588 reserveInitialCapacity(initializerList.size()); 589 for (const auto& element : initializerList) 590 uncheckedAppend(element); 591 } 592 593 ~Vector() 594 { 595 if (m_size) 596 shrink(0); 597 } 598 599 Vector(const Vector&); 600 template<size_t otherCapacity, typename otherOverflowBehaviour> 601 Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&); 602 603 Vector& operator=(const Vector&); 604 template<size_t otherCapacity, typename otherOverflowBehaviour> 605 Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&); 606 607 Vector(Vector&&); 608 Vector& operator=(Vector&&); 609 610 size_t size() const { return m_size; } 611 static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); } 612 size_t capacity() const { return Base::capacity(); } 613 bool isEmpty() const { return !size(); } 614 615 T& at(size_t i) 616 { 617 if (UNLIKELY(i >= size())) 618 OverflowHandler::overflowed(); 619 return Base::buffer()[i]; 620 } 621 const T& at(size_t i) const 622 { 623 if (UNLIKELY(i >= size())) 624 OverflowHandler::overflowed(); 625 return Base::buffer()[i]; 626 } 627 T& at(Checked<size_t> i) 628 { 629 RELEASE_ASSERT(i < size()); 630 return Base::buffer()[i]; 631 } 632 const T& at(Checked<size_t> i) const 633 { 634 RELEASE_ASSERT(i < size()); 635 return Base::buffer()[i]; 636 } 637 638 T& operator[](size_t i) { return at(i); } 639 const T& operator[](size_t i) const { return at(i); } 640 T& operator[](Checked<size_t> i) { return at(i); } 641 const T& operator[](Checked<size_t> i) const { return at(i); } 642 643 T* data() { return Base::buffer(); } 644 const T* data() const { return Base::buffer(); } 645 static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); } 646 647 iterator begin() { return data(); } 648 iterator end() { return begin() + m_size; } 649 const_iterator begin() const { return data(); } 650 const_iterator end() const { return begin() + m_size; } 651 652 reverse_iterator rbegin() { return reverse_iterator(end()); } 653 reverse_iterator rend() { return reverse_iterator(begin()); } 654 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 655 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 656 657 T& first() { return at(0); } 658 const T& first() const { return at(0); } 659 T& last() { return at(size() - 1); } 660 const T& last() const { return at(size() - 1); } 661 662 T takeLast() 663 { 664 T result = WTF::move(last()); 665 removeLast(); 666 return result; 667 } 668 669 template<typename U> bool contains(const U&) const; 670 template<typename U> size_t find(const U&) const; 671 template<typename U> size_t reverseFind(const U&) const; 672 673 void shrink(size_t size); 674 void grow(size_t size); 675 void resize(size_t size); 676 void resizeToFit(size_t size); 677 void reserveCapacity(size_t newCapacity); 678 bool tryReserveCapacity(size_t newCapacity); 679 void reserveInitialCapacity(size_t initialCapacity); 680 void shrinkCapacity(size_t newCapacity); 681 void shrinkToFit() { shrinkCapacity(size()); } 682 683 void clear() { shrinkCapacity(0); } 684 685 template<typename U> void append(const U*, size_t); 686 template<typename U> void append(U&&); 687 template<typename U> void uncheckedAppend(U&& val); 688 template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&); 689 template<typename U> bool tryAppend(const U*, size_t); 690 691 template<typename U> void insert(size_t position, const U*, size_t); 692 template<typename U> void insert(size_t position, U&&); 693 template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&); 694 695 void remove(size_t position); 696 void remove(size_t position, size_t length); 697 698 void removeLast() 699 { 700 if (UNLIKELY(isEmpty())) 701 OverflowHandler::overflowed(); 702 shrink(size() - 1); 703 } 704 705 void fill(const T&, size_t); 706 void fill(const T& val) { fill(val, size()); } 707 708 template<typename Iterator> void appendRange(Iterator start, Iterator end); 709 710 MallocPtr<T> releaseBuffer(); 711 712 void swap(Vector<T, inlineCapacity, OverflowHandler>& other) 713 { 714 Base::swap(other, m_size, other.m_size); 715 std::swap(m_size, other.m_size); 716 } 717 718 void reverse(); 719 720 void checkConsistency(); 721 722private: 723 void expandCapacity(size_t newMinCapacity); 724 T* expandCapacity(size_t newMinCapacity, T*); 725 bool tryExpandCapacity(size_t newMinCapacity); 726 const T* tryExpandCapacity(size_t newMinCapacity, const T*); 727 template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 728 template<typename U> void appendSlowCase(U&&); 729 730 using Base::m_size; 731 using Base::buffer; 732 using Base::capacity; 733 using Base::swap; 734 using Base::allocateBuffer; 735 using Base::deallocateBuffer; 736 using Base::tryAllocateBuffer; 737 using Base::shouldReallocateBuffer; 738 using Base::reallocateBuffer; 739 using Base::restoreInlineBufferIfNeeded; 740 using Base::releaseBuffer; 741}; 742 743template<typename T, size_t inlineCapacity, typename OverflowHandler> 744Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other) 745 : Base(other.capacity(), other.size()) 746{ 747 if (begin()) 748 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); 749} 750 751template<typename T, size_t inlineCapacity, typename OverflowHandler> 752template<size_t otherCapacity, typename otherOverflowBehaviour> 753Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other) 754 : Base(other.capacity(), other.size()) 755{ 756 if (begin()) 757 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); 758} 759 760template<typename T, size_t inlineCapacity, typename OverflowHandler> 761Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, inlineCapacity, OverflowHandler>& other) 762{ 763 if (&other == this) 764 return *this; 765 766 if (size() > other.size()) 767 shrink(other.size()); 768 else if (other.size() > capacity()) { 769 clear(); 770 reserveCapacity(other.size()); 771 ASSERT(begin()); 772 } 773 774// Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last 775#if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL 776 if (!begin()) 777 return *this; 778#endif 779 780 std::copy(other.begin(), other.begin() + size(), begin()); 781 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); 782 m_size = other.size(); 783 784 return *this; 785} 786 787inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; } 788 789template<typename T, size_t inlineCapacity, typename OverflowHandler> 790template<size_t otherCapacity, typename otherOverflowBehaviour> 791Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other) 792{ 793 // If the inline capacities match, we should call the more specific 794 // template. If the inline capacities don't match, the two objects 795 // shouldn't be allocated the same address. 796 ASSERT(!typelessPointersAreEqual(&other, this)); 797 798 if (size() > other.size()) 799 shrink(other.size()); 800 else if (other.size() > capacity()) { 801 clear(); 802 reserveCapacity(other.size()); 803 ASSERT(begin()); 804 } 805 806// Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last 807#if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL 808 if (!begin()) 809 return *this; 810#endif 811 812 std::copy(other.begin(), other.begin() + size(), begin()); 813 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end()); 814 m_size = other.size(); 815 816 return *this; 817} 818 819template<typename T, size_t inlineCapacity, typename OverflowHandler> 820inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other) 821{ 822 swap(other); 823} 824 825template<typename T, size_t inlineCapacity, typename OverflowHandler> 826inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other) 827{ 828 swap(other); 829 return *this; 830} 831 832template<typename T, size_t inlineCapacity, typename OverflowHandler> 833template<typename U> 834bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const 835{ 836 return find(value) != notFound; 837} 838 839template<typename T, size_t inlineCapacity, typename OverflowHandler> 840template<typename U> 841size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const 842{ 843 for (size_t i = 0; i < size(); ++i) { 844 if (at(i) == value) 845 return i; 846 } 847 return notFound; 848} 849 850template<typename T, size_t inlineCapacity, typename OverflowHandler> 851template<typename U> 852size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const 853{ 854 for (size_t i = 1; i <= size(); ++i) { 855 const size_t index = size() - i; 856 if (at(index) == value) 857 return index; 858 } 859 return notFound; 860} 861 862template<typename T, size_t inlineCapacity, typename OverflowHandler> 863void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize) 864{ 865 if (size() > newSize) 866 shrink(newSize); 867 else if (newSize > capacity()) { 868 clear(); 869 reserveCapacity(newSize); 870 ASSERT(begin()); 871 } 872 873 std::fill(begin(), end(), val); 874 TypeOperations::uninitializedFill(end(), begin() + newSize, val); 875 m_size = newSize; 876} 877 878template<typename T, size_t inlineCapacity, typename OverflowHandler> 879template<typename Iterator> 880void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end) 881{ 882 for (Iterator it = start; it != end; ++it) 883 append(*it); 884} 885 886template<typename T, size_t inlineCapacity, typename OverflowHandler> 887void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity) 888{ 889 reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1))); 890} 891 892template<typename T, size_t inlineCapacity, typename OverflowHandler> 893T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr) 894{ 895 if (ptr < begin() || ptr >= end()) { 896 expandCapacity(newMinCapacity); 897 return ptr; 898 } 899 size_t index = ptr - begin(); 900 expandCapacity(newMinCapacity); 901 return begin() + index; 902} 903 904template<typename T, size_t inlineCapacity, typename OverflowHandler> 905bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity) 906{ 907 return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1))); 908} 909 910template<typename T, size_t inlineCapacity, typename OverflowHandler> 911const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr) 912{ 913 if (ptr < begin() || ptr >= end()) { 914 if (!tryExpandCapacity(newMinCapacity)) 915 return 0; 916 return ptr; 917 } 918 size_t index = ptr - begin(); 919 if (!tryExpandCapacity(newMinCapacity)) 920 return 0; 921 return begin() + index; 922} 923 924template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 925inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr) 926{ 927 expandCapacity(newMinCapacity); 928 return ptr; 929} 930 931template<typename T, size_t inlineCapacity, typename OverflowHandler> 932inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size) 933{ 934 if (size <= m_size) 935 TypeOperations::destruct(begin() + size, end()); 936 else { 937 if (size > capacity()) 938 expandCapacity(size); 939 if (begin()) 940 TypeOperations::initialize(end(), begin() + size); 941 } 942 943 m_size = size; 944} 945 946template<typename T, size_t inlineCapacity, typename OverflowHandler> 947void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size) 948{ 949 reserveCapacity(size); 950 resize(size); 951} 952 953template<typename T, size_t inlineCapacity, typename OverflowHandler> 954void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size) 955{ 956 ASSERT(size <= m_size); 957 TypeOperations::destruct(begin() + size, end()); 958 m_size = size; 959} 960 961template<typename T, size_t inlineCapacity, typename OverflowHandler> 962void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size) 963{ 964 ASSERT(size >= m_size); 965 if (size > capacity()) 966 expandCapacity(size); 967 if (begin()) 968 TypeOperations::initialize(end(), begin() + size); 969 m_size = size; 970} 971 972template<typename T, size_t inlineCapacity, typename OverflowHandler> 973void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity) 974{ 975 if (newCapacity <= capacity()) 976 return; 977 T* oldBuffer = begin(); 978 T* oldEnd = end(); 979 Base::allocateBuffer(newCapacity); 980 ASSERT(begin()); 981 TypeOperations::move(oldBuffer, oldEnd, begin()); 982 Base::deallocateBuffer(oldBuffer); 983} 984 985template<typename T, size_t inlineCapacity, typename OverflowHandler> 986bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity) 987{ 988 if (newCapacity <= capacity()) 989 return true; 990 T* oldBuffer = begin(); 991 T* oldEnd = end(); 992 if (!Base::tryAllocateBuffer(newCapacity)) 993 return false; 994 ASSERT(begin()); 995 TypeOperations::move(oldBuffer, oldEnd, begin()); 996 Base::deallocateBuffer(oldBuffer); 997 return true; 998} 999 1000template<typename T, size_t inlineCapacity, typename OverflowHandler> 1001inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity) 1002{ 1003 ASSERT(!m_size); 1004 ASSERT(capacity() == inlineCapacity); 1005 if (initialCapacity > inlineCapacity) 1006 Base::allocateBuffer(initialCapacity); 1007} 1008 1009template<typename T, size_t inlineCapacity, typename OverflowHandler> 1010void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity) 1011{ 1012 if (newCapacity >= capacity()) 1013 return; 1014 1015 if (newCapacity < size()) 1016 shrink(newCapacity); 1017 1018 T* oldBuffer = begin(); 1019 if (newCapacity > 0) { 1020 if (Base::shouldReallocateBuffer(newCapacity)) { 1021 Base::reallocateBuffer(newCapacity); 1022 return; 1023 } 1024 1025 T* oldEnd = end(); 1026 Base::allocateBuffer(newCapacity); 1027 if (begin() != oldBuffer) 1028 TypeOperations::move(oldBuffer, oldEnd, begin()); 1029 } 1030 1031 Base::deallocateBuffer(oldBuffer); 1032 Base::restoreInlineBufferIfNeeded(); 1033} 1034 1035// Templatizing these is better than just letting the conversion happen implicitly, 1036// because for instance it allows a PassRefPtr to be appended to a RefPtr vector 1037// without refcount thrash. 1038template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1039void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize) 1040{ 1041 size_t newSize = m_size + dataSize; 1042 if (newSize > capacity()) { 1043 data = expandCapacity(newSize, data); 1044 ASSERT(begin()); 1045 } 1046 if (newSize < m_size) 1047 CRASH(); 1048 T* dest = end(); 1049 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest); 1050 m_size = newSize; 1051} 1052 1053template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1054bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize) 1055{ 1056 size_t newSize = m_size + dataSize; 1057 if (newSize > capacity()) { 1058 data = tryExpandCapacity(newSize, data); 1059 if (!data) 1060 return false; 1061 ASSERT(begin()); 1062 } 1063 if (newSize < m_size) 1064 return false; 1065 T* dest = end(); 1066 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest); 1067 m_size = newSize; 1068 return true; 1069} 1070 1071template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1072ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value) 1073{ 1074 if (size() != capacity()) { 1075 new (NotNull, end()) T(std::forward<U>(value)); 1076 ++m_size; 1077 return; 1078 } 1079 1080 appendSlowCase(std::forward<U>(value)); 1081} 1082 1083template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1084void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value) 1085{ 1086 ASSERT(size() == capacity()); 1087 1088 auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value)); 1089 ptr = expandCapacity(size() + 1, ptr); 1090 ASSERT(begin()); 1091 1092 new (NotNull, end()) T(std::forward<U>(*ptr)); 1093 ++m_size; 1094} 1095 1096// This version of append saves a branch in the case where you know that the 1097// vector's capacity is large enough for the append to succeed. 1098 1099template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1100inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value) 1101{ 1102 ASSERT(size() < capacity()); 1103 1104 auto ptr = std::addressof(value); 1105 new (NotNull, end()) T(std::forward<U>(*ptr)); 1106 ++m_size; 1107} 1108 1109template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity> 1110inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val) 1111{ 1112 append(val.begin(), val.size()); 1113} 1114 1115template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1116void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize) 1117{ 1118 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); 1119 size_t newSize = m_size + dataSize; 1120 if (newSize > capacity()) { 1121 data = expandCapacity(newSize, data); 1122 ASSERT(begin()); 1123 } 1124 if (newSize < m_size) 1125 CRASH(); 1126 T* spot = begin() + position; 1127 TypeOperations::moveOverlapping(spot, end(), spot + dataSize); 1128 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], spot); 1129 m_size = newSize; 1130} 1131 1132template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U> 1133inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value) 1134{ 1135 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); 1136 1137 auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value)); 1138 if (size() == capacity()) { 1139 ptr = expandCapacity(size() + 1, ptr); 1140 ASSERT(begin()); 1141 } 1142 1143 T* spot = begin() + position; 1144 TypeOperations::moveOverlapping(spot, end(), spot + 1); 1145 new (NotNull, spot) T(std::forward<U>(*ptr)); 1146 ++m_size; 1147} 1148 1149template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c> 1150inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val) 1151{ 1152 insert(position, val.begin(), val.size()); 1153} 1154 1155template<typename T, size_t inlineCapacity, typename OverflowHandler> 1156inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position) 1157{ 1158 ASSERT_WITH_SECURITY_IMPLICATION(position < size()); 1159 T* spot = begin() + position; 1160 spot->~T(); 1161 TypeOperations::moveOverlapping(spot + 1, end(), spot); 1162 --m_size; 1163} 1164 1165template<typename T, size_t inlineCapacity, typename OverflowHandler> 1166inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length) 1167{ 1168 ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); 1169 ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size()); 1170 T* beginSpot = begin() + position; 1171 T* endSpot = beginSpot + length; 1172 TypeOperations::destruct(beginSpot, endSpot); 1173 TypeOperations::moveOverlapping(endSpot, end(), beginSpot); 1174 m_size -= length; 1175} 1176 1177template<typename T, size_t inlineCapacity, typename OverflowHandler> 1178inline void Vector<T, inlineCapacity, OverflowHandler>::reverse() 1179{ 1180 for (size_t i = 0; i < m_size / 2; ++i) 1181 std::swap(at(i), at(m_size - 1 - i)); 1182} 1183 1184template<typename T, size_t inlineCapacity, typename OverflowHandler> 1185inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer() 1186{ 1187 auto buffer = Base::releaseBuffer(); 1188 if (inlineCapacity && !buffer && m_size) { 1189 // If the vector had some data, but no buffer to release, 1190 // that means it was using the inline buffer. In that case, 1191 // we create a brand new buffer so the caller always gets one. 1192 size_t bytes = m_size * sizeof(T); 1193 buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes))); 1194 memcpy(buffer.get(), data(), bytes); 1195 } 1196 m_size = 0; 1197 return buffer; 1198} 1199 1200template<typename T, size_t inlineCapacity, typename OverflowHandler> 1201inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency() 1202{ 1203#if !ASSERT_DISABLED 1204 for (size_t i = 0; i < size(); ++i) 1205 ValueCheck<T>::checkConsistency(at(i)); 1206#endif 1207} 1208 1209template<typename T, size_t inlineCapacity, typename OverflowHandler> 1210inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b) 1211{ 1212 a.swap(b); 1213} 1214 1215template<typename T, size_t inlineCapacity, typename OverflowHandler> 1216bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b) 1217{ 1218 if (a.size() != b.size()) 1219 return false; 1220 1221 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size()); 1222} 1223 1224template<typename T, size_t inlineCapacity, typename OverflowHandler> 1225inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b) 1226{ 1227 return !(a == b); 1228} 1229 1230#if !ASSERT_DISABLED 1231template<typename T> struct ValueCheck<Vector<T>> { 1232 typedef Vector<T> TraitType; 1233 static void checkConsistency(const Vector<T>& v) 1234 { 1235 v.checkConsistency(); 1236 } 1237}; 1238#endif 1239 1240} // namespace WTF 1241 1242using WTF::Vector; 1243using WTF::UnsafeVectorOverflow; 1244using WTF::notFound; 1245 1246#endif // WTF_Vector_h 1247