Source/JavaScriptCore/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 "Alignment.h"
  25 #include "FastAllocBase.h"
  26 #include "Noncopyable.h"
  27 #include "NotFound.h"
  28 #include "StdLibExtras.h"
  29 #include "ValueCheck.h"
  30 #include "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 (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 (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 (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 (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 (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             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             m_capacity = newCapacity;
 259             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 260                 CRASH();
 261             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
 262         }
 263
 264         bool tryAllocateBuffer(size_t newCapacity)
 265         {
 266             ASSERT(newCapacity);
 267             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 268                 return false;
 269
 270             T* newBuffer;
 271             if (tryFastMalloc(newCapacity * sizeof(T)).getValue(newBuffer)) {
 272                 m_capacity = newCapacity;
 273                 m_buffer = newBuffer;
 274                 return true;
 275             }
 276             return false;
 277         }
 278
 279         void deallocateBuffer(T* bufferToDeallocate)
 280         {
 281             if (m_buffer == bufferToDeallocate) {
 282                 m_buffer = 0;
 283                 m_capacity = 0;
 284             }
 285             fastFree(bufferToDeallocate);
 286         }
 287
 288         T* buffer() { return m_buffer; }
 289         const T* buffer() const { return m_buffer; }
 290         T** bufferSlot() { return &m_buffer; }
 291         size_t capacity() const { return m_capacity; }
 292
 293         T* releaseBuffer()
 294         {
 295             T* buffer = m_buffer;
 296             m_buffer = 0;
 297             m_capacity = 0;
 298             return buffer;
 299         }
 300
 301     protected:
 302         VectorBufferBase()
 303             : m_buffer(0)
 304             , m_capacity(0)
 305         {
 306         }
 307
 308         VectorBufferBase(T* buffer, size_t capacity)
 309             : m_buffer(buffer)
 310             , m_capacity(capacity)
 311         {
 312         }
 313
 314         ~VectorBufferBase()
 315         {
 316             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
 317         }
 318
 319         T* m_buffer;
 320         size_t m_capacity;
 321     };
 322
 323     template<typename T, size_t inlineCapacity>
 324     class VectorBuffer;
 325
 326     template<typename T>
 327     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
 328     private:
 329         typedef VectorBufferBase<T> Base;
 330     public:
 331         VectorBuffer()
 332         {
 333         }
 334
 335         VectorBuffer(size_t capacity)
 336         {
 337             // Calling malloc(0) might take a lock and may actually do an
 338             // allocation on some systems.
 339             if (capacity)
 340                 allocateBuffer(capacity);
 341         }
 342
 343         ~VectorBuffer()
 344         {
 345             deallocateBuffer(buffer());
 346         }
 347
 348         void swap(VectorBuffer<T, 0>& other)
 349         {
 350             std::swap(m_buffer, other.m_buffer);
 351             std::swap(m_capacity, other.m_capacity);
 352         }
 353
 354         void restoreInlineBufferIfNeeded() { }
 355
 356         using Base::allocateBuffer;
 357         using Base::tryAllocateBuffer;
 358         using Base::deallocateBuffer;
 359
 360         using Base::buffer;
 361         using Base::bufferSlot;
 362         using Base::capacity;
 363
 364         using Base::releaseBuffer;
 365     private:
 366         using Base::m_buffer;
 367         using Base::m_capacity;
 368     };
 369
 370     template<typename T, size_t inlineCapacity>
 371     class VectorBuffer : private VectorBufferBase<T> {
 372         WTF_MAKE_NONCOPYABLE(VectorBuffer);
 373     private:
 374         typedef VectorBufferBase<T> Base;
 375     public:
 376         VectorBuffer()
 377             : Base(inlineBuffer(), inlineCapacity)
 378         {
 379         }
 380
 381         VectorBuffer(size_t capacity)
 382             : Base(inlineBuffer(), inlineCapacity)
 383         {
 384             if (capacity > inlineCapacity)
 385                 Base::allocateBuffer(capacity);
 386         }
 387
 388         ~VectorBuffer()
 389         {
 390             deallocateBuffer(buffer());
 391         }
 392
 393         void allocateBuffer(size_t newCapacity)
 394         {
 395             // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
 396             if (newCapacity > inlineCapacity)
 397                 Base::allocateBuffer(newCapacity);
 398             else {
 399                 m_buffer = inlineBuffer();
 400                 m_capacity = inlineCapacity;
 401             }
 402         }
 403
 404         bool tryAllocateBuffer(size_t newCapacity)
 405         {
 406             if (newCapacity > inlineCapacity)
 407                 return Base::tryAllocateBuffer(newCapacity);
 408             m_buffer = inlineBuffer();
 409             m_capacity = inlineCapacity;
 410             return true;
 411         }
 412
 413         void deallocateBuffer(T* bufferToDeallocate)
 414         {
 415             if (bufferToDeallocate == inlineBuffer())
 416                 return;
 417             Base::deallocateBuffer(bufferToDeallocate);
 418         }
 419
 420         void swap(VectorBuffer<T, inlineCapacity>& other)
 421         {
 422             if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
 423                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 424                 std::swap(m_capacity, other.m_capacity);
 425             } else if (buffer() == inlineBuffer()) {
 426                 m_buffer = other.m_buffer;
 427                 other.m_buffer = other.inlineBuffer();
 428                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 429                 std::swap(m_capacity, other.m_capacity);
 430             } else if (other.buffer() == other.inlineBuffer()) {
 431                 other.m_buffer = m_buffer;
 432                 m_buffer = inlineBuffer();
 433                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 434                 std::swap(m_capacity, other.m_capacity);
 435             } else {
 436                 std::swap(m_buffer, other.m_buffer);
 437                 std::swap(m_capacity, other.m_capacity);
 438             }
 439         }
 440
 441         void restoreInlineBufferIfNeeded()
 442         {
 443             if (m_buffer)
 444                 return;
 445             m_buffer = inlineBuffer();
 446             m_capacity = inlineCapacity;
 447         }
 448
 449         using Base::buffer;
 450         using Base::bufferSlot;
 451         using Base::capacity;
 452
 453         T* releaseBuffer()
 454         {
 455             if (buffer() == inlineBuffer())
 456                 return 0;
 457             return Base::releaseBuffer();
 458         }
 459
 460     private:
 461         using Base::m_buffer;
 462         using Base::m_capacity;
 463
 464         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
 465         T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); }
 466
 467         AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
 468     };
 469
 470     template<typename T, size_t inlineCapacity = 0>
 471     class Vector {
 472         WTF_MAKE_FAST_ALLOCATED;
 473     private:
 474         typedef VectorBuffer<T, inlineCapacity> Buffer;
 475         typedef VectorTypeOperations<T> TypeOperations;
 476
 477     public:
 478         typedef T ValueType;
 479
 480         typedef T* iterator;
 481         typedef const T* const_iterator;
 482
 483         Vector()
 484             : m_size(0)
 485         {
 486         }
 487
 488         explicit Vector(size_t size)
 489             : m_size(size)
 490             , m_buffer(size)
 491         {
 492             if (begin())
 493                 TypeOperations::initialize(begin(), end());
 494         }
 495
 496         ~Vector()
 497         {
 498             if (m_size) shrink(0);
 499         }
 500
 501         Vector(const Vector&);
 502         template<size_t otherCapacity>
 503         Vector(const Vector<T, otherCapacity>&);
 504
 505         Vector& operator=(const Vector&);
 506         template<size_t otherCapacity>
 507         Vector& operator=(const Vector<T, otherCapacity>&);
 508
 509         size_t size() const { return m_size; }
 510         size_t capacity() const { return m_buffer.capacity(); }
 511         bool isEmpty() const { return !size(); }
 512
 513         T& at(size_t i)
 514         {
 515             ASSERT(i < size());
 516             return m_buffer.buffer()[i];
 517         }
 518         const T& at(size_t i) const
 519         {
 520             ASSERT(i < size());
 521             return m_buffer.buffer()[i];
 522         }
 523
 524         T& operator[](size_t i) { return at(i); }
 525         const T& operator[](size_t i) const { return at(i); }
 526
 527         T* data() { return m_buffer.buffer(); }
 528         const T* data() const { return m_buffer.buffer(); }
 529         T** dataSlot() { return m_buffer.bufferSlot(); }
 530
 531         iterator begin() { return data(); }
 532         iterator end() { return begin() + m_size; }
 533         const_iterator begin() const { return data(); }
 534         const_iterator end() const { return begin() + m_size; }
 535
 536         T& first() { return at(0); }
 537         const T& first() const { return at(0); }
 538         T& last() { return at(size() - 1); }
 539         const T& last() const { return at(size() - 1); }
 540
 541         template<typename U> bool contains(const U&) const;
 542         template<typename U> size_t find(const U&) const;
 543         template<typename U> size_t reverseFind(const U&) const;
 544
 545         void shrink(size_t size);
 546         void grow(size_t size);
 547         void resize(size_t size);
 548         void reserveCapacity(size_t newCapacity);
 549         bool tryReserveCapacity(size_t newCapacity);
 550         void reserveInitialCapacity(size_t initialCapacity);
 551         void shrinkCapacity(size_t newCapacity);
 552         void shrinkToFit() { shrinkCapacity(size()); }
 553
 554         void clear() { shrinkCapacity(0); }
 555
 556         template<typename U> void append(const U*, size_t);
 557         template<typename U> void append(const U&);
 558         template<typename U> void uncheckedAppend(const U& val);
 559         template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
 560         template<typename U> bool tryAppend(const U*, size_t);
 561
 562         template<typename U> void insert(size_t position, const U*, size_t);
 563         template<typename U> void insert(size_t position, const U&);
 564         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
 565
 566         template<typename U> void prepend(const U*, size_t);
 567         template<typename U> void prepend(const U&);
 568         template<typename U, size_t c> void prepend(const Vector<U, c>&);
 569
 570         void remove(size_t position);
 571         void remove(size_t position, size_t length);
 572
 573         void removeLast()
 574         {
 575             ASSERT(!isEmpty());
 576             shrink(size() - 1);
 577         }
 578
 579         Vector(size_t size, const T& val)
 580             : m_size(size)
 581             , m_buffer(size)
 582         {
 583             if (begin())
 584                 TypeOperations::uninitializedFill(begin(), end(), val);
 585         }
 586
 587         void fill(const T&, size_t);
 588         void fill(const T& val) { fill(val, size()); }
 589
 590         template<typename Iterator> void appendRange(Iterator start, Iterator end);
 591
 592         T* releaseBuffer();
 593
 594         void swap(Vector<T, inlineCapacity>& other)
 595         {
 596             std::swap(m_size, other.m_size);
 597             m_buffer.swap(other.m_buffer);
 598         }
 599
 600         void reverse();
 601
 602         void checkConsistency();
 603
 604     private:
 605         void expandCapacity(size_t newMinCapacity);
 606         const T* expandCapacity(size_t newMinCapacity, const T*);
 607         bool tryExpandCapacity(size_t newMinCapacity);
 608         const T* tryExpandCapacity(size_t newMinCapacity, const T*);
 609         template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
 610
 611         size_t m_size;
 612         Buffer m_buffer;
 613     };
 614
 615 #if PLATFORM(QT)
 616     template<typename T>
 617     QDataStream& operator<<(QDataStream& stream, const Vector<T>& data)
 618     {
 619         stream << qint64(data.size());
 620         foreach (const T& i, data)
 621             stream << i;
 622         return stream;
 623     }
 624
 625     template<typename T>
 626     QDataStream& operator>>(QDataStream& stream, Vector<T>& data)
 627     {
 628         data.clear();
 629         qint64 count;
 630         T item;
 631         stream >> count;
 632         data.reserveCapacity(count);
 633         for (qint64 i = 0; i < count; ++i) {
 634             stream >> item;
 635             data.append(item);
 636         }
 637         return stream;
 638     }
 639 #endif
 640
 641     template<typename T, size_t inlineCapacity>
 642     Vector<T, inlineCapacity>::Vector(const Vector& other)
 643         : m_size(other.size())
 644         , m_buffer(other.capacity())
 645     {
 646         if (begin())
 647             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 648     }
 649
 650     template<typename T, size_t inlineCapacity>
 651     template<size_t otherCapacity>
 652     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
 653         : m_size(other.size())
 654         , m_buffer(other.capacity())
 655     {
 656         if (begin())
 657             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 658     }
 659
 660     template<typename T, size_t inlineCapacity>
 661     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
 662     {
 663         if (&other == this)
 664             return *this;
 665
 666         if (size() > other.size())
 667             shrink(other.size());
 668         else if (other.size() > capacity()) {
 669             clear();
 670             reserveCapacity(other.size());
 671             if (!begin())
 672                 return *this;
 673         }
 674
 675 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
 676 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
 677         if (!begin())
 678             return *this;
 679 #endif
 680
 681         std::copy(other.begin(), other.begin() + size(), begin());
 682         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 683         m_size = other.size();
 684
 685         return *this;
 686     }
 687
 688     inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
 689
 690     template<typename T, size_t inlineCapacity>
 691     template<size_t otherCapacity>
 692     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
 693     {
 694         // If the inline capacities match, we should call the more specific
 695         // template.  If the inline capacities don't match, the two objects
 696         // shouldn't be allocated the same address.
 697         ASSERT(!typelessPointersAreEqual(&other, this));
 698
 699         if (size() > other.size())
 700             shrink(other.size());
 701         else if (other.size() > capacity()) {
 702             clear();
 703             reserveCapacity(other.size());
 704             if (!begin())
 705                 return *this;
 706         }
 707
 708 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
 709 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
 710         if (!begin())
 711             return *this;
 712 #endif
 713
 714         std::copy(other.begin(), other.begin() + size(), begin());
 715         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 716         m_size = other.size();
 717
 718         return *this;
 719     }
 720
 721     template<typename T, size_t inlineCapacity>
 722     template<typename U>
 723     bool Vector<T, inlineCapacity>::contains(const U& value) const
 724     {
 725         return find(value) != notFound;
 726     }
 727
 728     template<typename T, size_t inlineCapacity>
 729     template<typename U>
 730     size_t Vector<T, inlineCapacity>::find(const U& value) const
 731     {
 732         for (size_t i = 0; i < size(); ++i) {
 733             if (at(i) == value)
 734                 return i;
 735         }
 736         return notFound;
 737     }
 738
 739     template<typename T, size_t inlineCapacity>
 740     template<typename U>
 741     size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
 742     {
 743         for (size_t i = 1; i <= size(); ++i) {
 744             const size_t index = size() - i;
 745             if (at(index) == value)
 746                 return index;
 747         }
 748         return notFound;
 749     }
 750
 751     template<typename T, size_t inlineCapacity>
 752     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
 753     {
 754         if (size() > newSize)
 755             shrink(newSize);
 756         else if (newSize > capacity()) {
 757             clear();
 758             reserveCapacity(newSize);
 759             if (!begin())
 760                 return;
 761         }
 762
 763         std::fill(begin(), end(), val);
 764         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
 765         m_size = newSize;
 766     }
 767
 768     template<typename T, size_t inlineCapacity>
 769     template<typename Iterator>
 770     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
 771     {
 772         for (Iterator it = start; it != end; ++it)
 773             append(*it);
 774     }
 775
 776     template<typename T, size_t inlineCapacity>
 777     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
 778     {
 779         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 780     }
 781
 782     template<typename T, size_t inlineCapacity>
 783     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
 784     {
 785         if (ptr < begin() || ptr >= end()) {
 786             expandCapacity(newMinCapacity);
 787             return ptr;
 788         }
 789         size_t index = ptr - begin();
 790         expandCapacity(newMinCapacity);
 791         return begin() + index;
 792     }
 793
 794     template<typename T, size_t inlineCapacity>
 795     bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity)
 796     {
 797         return tryReserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 798     }
 799
 800     template<typename T, size_t inlineCapacity>
 801     const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
 802     {
 803         if (ptr < begin() || ptr >= end()) {
 804             if (!tryExpandCapacity(newMinCapacity))
 805                 return 0;
 806             return ptr;
 807         }
 808         size_t index = ptr - begin();
 809         if (!tryExpandCapacity(newMinCapacity))
 810             return 0;
 811         return begin() + index;
 812     }
 813
 814     template<typename T, size_t inlineCapacity> template<typename U>
 815     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 816     {
 817         expandCapacity(newMinCapacity);
 818         return ptr;
 819     }
 820
 821     template<typename T, size_t inlineCapacity>
 822     inline void Vector<T, inlineCapacity>::resize(size_t size)
 823     {
 824         if (size <= m_size)
 825             TypeOperations::destruct(begin() + size, end());
 826         else {
 827             if (size > capacity())
 828                 expandCapacity(size);
 829             if (begin())
 830                 TypeOperations::initialize(end(), begin() + size);
 831         }
 832
 833         m_size = size;
 834     }
 835
 836     template<typename T, size_t inlineCapacity>
 837     void Vector<T, inlineCapacity>::shrink(size_t size)
 838     {
 839         ASSERT(size <= m_size);
 840         TypeOperations::destruct(begin() + size, end());
 841         m_size = size;
 842     }
 843
 844     template<typename T, size_t inlineCapacity>
 845     void Vector<T, inlineCapacity>::grow(size_t size)
 846     {
 847         ASSERT(size >= m_size);
 848         if (size > capacity())
 849             expandCapacity(size);
 850         if (begin())
 851             TypeOperations::initialize(end(), begin() + size);
 852         m_size = size;
 853     }
 854
 855     template<typename T, size_t inlineCapacity>
 856     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
 857     {
 858         if (newCapacity <= capacity())
 859             return;
 860         T* oldBuffer = begin();
 861         T* oldEnd = end();
 862         m_buffer.allocateBuffer(newCapacity);
 863         if (begin())
 864             TypeOperations::move(oldBuffer, oldEnd, begin());
 865         m_buffer.deallocateBuffer(oldBuffer);
 866     }
 867
 868     template<typename T, size_t inlineCapacity>
 869     bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity)
 870     {
 871         if (newCapacity <= capacity())
 872             return true;
 873         T* oldBuffer = begin();
 874         T* oldEnd = end();
 875         if (!m_buffer.tryAllocateBuffer(newCapacity))
 876             return false;
 877         ASSERT(begin());
 878         TypeOperations::move(oldBuffer, oldEnd, begin());
 879         m_buffer.deallocateBuffer(oldBuffer);
 880         return true;
 881     }
 882
 883     template<typename T, size_t inlineCapacity>
 884     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
 885     {
 886         ASSERT(!m_size);
 887         ASSERT(capacity() == inlineCapacity);
 888         if (initialCapacity > inlineCapacity)
 889             m_buffer.allocateBuffer(initialCapacity);
 890     }
 891
 892     template<typename T, size_t inlineCapacity>
 893     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
 894     {
 895         if (newCapacity >= capacity())
 896             return;
 897
 898         if (newCapacity < size())
 899             shrink(newCapacity);
 900
 901         T* oldBuffer = begin();
 902         if (newCapacity > 0) {
 903             T* oldEnd = end();
 904             m_buffer.allocateBuffer(newCapacity);
 905             if (begin() != oldBuffer)
 906                 TypeOperations::move(oldBuffer, oldEnd, begin());
 907         }
 908
 909         m_buffer.deallocateBuffer(oldBuffer);
 910         m_buffer.restoreInlineBufferIfNeeded();
 911     }
 912
 913     // Templatizing these is better than just letting the conversion happen implicitly,
 914     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 915     // without refcount thrash.
 916
 917     template<typename T, size_t inlineCapacity> template<typename U>
 918     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
 919     {
 920         size_t newSize = m_size + dataSize;
 921         if (newSize > capacity()) {
 922             data = expandCapacity(newSize, data);
 923             if (!begin())
 924                 return;
 925         }
 926         if (newSize < m_size)
 927             CRASH();
 928         T* dest = end();
 929         for (size_t i = 0; i < dataSize; ++i)
 930             new (&dest[i]) T(data[i]);
 931         m_size = newSize;
 932     }
 933
 934     template<typename T, size_t inlineCapacity> template<typename U>
 935     bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize)
 936     {
 937         size_t newSize = m_size + dataSize;
 938         if (newSize > capacity()) {
 939             data = tryExpandCapacity(newSize, data);
 940             if (!data)
 941                 return false;
 942             ASSERT(begin());
 943         }
 944         if (newSize < m_size)
 945             return false;
 946         T* dest = end();
 947         for (size_t i = 0; i < dataSize; ++i)
 948             new (&dest[i]) T(data[i]);
 949         m_size = newSize;
 950         return true;
 951     }
 952
 953     template<typename T, size_t inlineCapacity> template<typename U>
 954     ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
 955     {
 956         const U* ptr = &val;
 957         if (size() == capacity()) {
 958             ptr = expandCapacity(size() + 1, ptr);
 959             if (!begin())
 960                 return;
 961         }
 962
 963 #if COMPILER(MSVC7_OR_LOWER)
 964         // FIXME: MSVC7 generates compilation errors when trying to assign
 965         // a pointer to a Vector of its base class (i.e. can't downcast). So far
 966         // I've been unable to determine any logical reason for this, so I can
 967         // only assume it is a bug with the compiler. Casting is a bad solution,
 968         // however, because it subverts implicit conversions, so a better
 969         // one is needed.
 970         new (end()) T(static_cast<T>(*ptr));
 971 #else
 972         new (end()) T(*ptr);
 973 #endif
 974         ++m_size;
 975     }
 976
 977     // This version of append saves a branch in the case where you know that the
 978     // vector's capacity is large enough for the append to succeed.
 979
 980     template<typename T, size_t inlineCapacity> template<typename U>
 981     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
 982     {
 983         ASSERT(size() < capacity());
 984         const U* ptr = &val;
 985         new (end()) T(*ptr);
 986         ++m_size;
 987     }
 988
 989     // This method should not be called append, a better name would be appendElements.
 990     // It could also be eliminated entirely, and call sites could just use
 991     // appendRange(val.begin(), val.end()).
 992     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
 993     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
 994     {
 995         append(val.begin(), val.size());
 996     }
 997
 998     template<typename T, size_t inlineCapacity> template<typename U>
 999     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
1000     {
1001         ASSERT(position <= size());
1002         size_t newSize = m_size + dataSize;
1003         if (newSize > capacity()) {
1004             data = expandCapacity(newSize, data);
1005             if (!begin())
1006                 return;
1007         }
1008         if (newSize < m_size)
1009             CRASH();
1010         T* spot = begin() + position;
1011         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1012         for (size_t i = 0; i < dataSize; ++i)
1013             new (&spot[i]) T(data[i]);
1014         m_size = newSize;
1015     }
1016
1017     template<typename T, size_t inlineCapacity> template<typename U>
1018     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
1019     {
1020         ASSERT(position <= size());
1021         const U* data = &val;
1022         if (size() == capacity()) {
1023             data = expandCapacity(size() + 1, data);
1024             if (!begin())
1025                 return;
1026         }
1027         T* spot = begin() + position;
1028         TypeOperations::moveOverlapping(spot, end(), spot + 1);
1029         new (spot) T(*data);
1030         ++m_size;
1031     }
1032
1033     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1034     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
1035     {
1036         insert(position, val.begin(), val.size());
1037     }
1038
1039     template<typename T, size_t inlineCapacity> template<typename U>
1040     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
1041     {
1042         insert(0, data, dataSize);
1043     }
1044
1045     template<typename T, size_t inlineCapacity> template<typename U>
1046     inline void Vector<T, inlineCapacity>::prepend(const U& val)
1047     {
1048         insert(0, val);
1049     }
1050
1051     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1052     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
1053     {
1054         insert(0, val.begin(), val.size());
1055     }
1056
1057     template<typename T, size_t inlineCapacity>
1058     inline void Vector<T, inlineCapacity>::remove(size_t position)
1059     {
1060         ASSERT(position < size());
1061         T* spot = begin() + position;
1062         spot->~T();
1063         TypeOperations::moveOverlapping(spot + 1, end(), spot);
1064         --m_size;
1065     }
1066
1067     template<typename T, size_t inlineCapacity>
1068     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
1069     {
1070         ASSERT(position < size());
1071         ASSERT(position + length <= size());
1072         T* beginSpot = begin() + position;
1073         T* endSpot = beginSpot + length;
1074         TypeOperations::destruct(beginSpot, endSpot);
1075         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1076         m_size -= length;
1077     }
1078
1079     template<typename T, size_t inlineCapacity>
1080     inline void Vector<T, inlineCapacity>::reverse()
1081     {
1082         for (size_t i = 0; i < m_size / 2; ++i)
1083             std::swap(at(i), at(m_size - 1 - i));
1084     }
1085
1086     template<typename T, size_t inlineCapacity>
1087     inline T* Vector<T, inlineCapacity>::releaseBuffer()
1088     {
1089         T* buffer = m_buffer.releaseBuffer();
1090         if (inlineCapacity && !buffer && m_size) {
1091             // If the vector had some data, but no buffer to release,
1092             // that means it was using the inline buffer. In that case,
1093             // we create a brand new buffer so the caller always gets one.
1094             size_t bytes = m_size * sizeof(T);
1095             buffer = static_cast<T*>(fastMalloc(bytes));
1096             memcpy(buffer, data(), bytes);
1097         }
1098         m_size = 0;
1099         return buffer;
1100     }
1101
1102     template<typename T, size_t inlineCapacity>
1103     inline void Vector<T, inlineCapacity>::checkConsistency()
1104     {
1105 #if !ASSERT_DISABLED
1106         for (size_t i = 0; i < size(); ++i)
1107             ValueCheck<T>::checkConsistency(at(i));
1108 #endif
1109     }
1110
1111     template<typename T, size_t inlineCapacity>
1112     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
1113     {
1114         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
1115         iterator end = collection.end();
1116         for (iterator it = collection.begin(); it != end; ++it)
1117             delete *it;
1118     }
1119
1120     template<typename T, size_t inlineCapacity>
1121     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
1122     {
1123         a.swap(b);
1124     }
1125
1126     template<typename T, size_t inlineCapacity>
1127     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1128     {
1129         if (a.size() != b.size())
1130             return false;
1131
1132         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1133     }
1134
1135     template<typename T, size_t inlineCapacity>
1136     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1137     {
1138         return !(a == b);
1139     }
1140
1141 #if !ASSERT_DISABLED
1142     template<typename T> struct ValueCheck<Vector<T> > {
1143         typedef Vector<T> TraitType;
1144         static void checkConsistency(const Vector<T>& v)
1145         {
1146             v.checkConsistency();
1147         }
1148     };
1149 #endif
1150
1151 } // namespace WTF
1152
1153 using WTF::Vector;
1154
1155 #endif // WTF_Vector_h