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