Source/WTF/wtf/Vector.h

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