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 "Assertions.h"
  25 #include "FastMalloc.h"
  26 #include "Noncopyable.h"
  27 #include "NotFound.h"
  28 #include "VectorTraits.h"
  29 #include <limits>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <utility>
  33
  34 namespace WTF {
  35
  36     using std::min;
  37     using std::max;
  38
  39     // WTF_ALIGN_OF / WTF_ALIGNED
  40     #if COMPILER(GCC) || COMPILER(MINGW) || COMPILER(RVCT) || COMPILER(WINSCW)
  41         #define WTF_ALIGN_OF(type) __alignof__(type)
  42         #define WTF_ALIGNED(variable_type, variable, n) variable_type variable __attribute__((__aligned__(n)))
  43     #elif COMPILER(MSVC)
  44         #define WTF_ALIGN_OF(type) __alignof(type)
  45         #define WTF_ALIGNED(variable_type, variable, n) __declspec(align(n)) variable_type variable
  46     #else
  47         #error WTF_ALIGN macros need alignment control.
  48     #endif
  49
  50     #if COMPILER(GCC) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 303)
  51         typedef char __attribute__((__may_alias__)) AlignedBufferChar;
  52     #else
  53         typedef char AlignedBufferChar;
  54     #endif
  55
  56     template <size_t size, size_t alignment> struct AlignedBuffer;
  57     template <size_t size> struct AlignedBuffer<size, 1> { AlignedBufferChar buffer[size]; };
  58     template <size_t size> struct AlignedBuffer<size, 2> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 2);  };
  59     template <size_t size> struct AlignedBuffer<size, 4> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 4);  };
  60     template <size_t size> struct AlignedBuffer<size, 8> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 8);  };
  61     template <size_t size> struct AlignedBuffer<size, 16> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 16); };
  62     template <size_t size> struct AlignedBuffer<size, 32> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 32); };
  63     template <size_t size> struct AlignedBuffer<size, 64> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 64); };
  64
  65     template <bool needsDestruction, typename T>
  66     class VectorDestructor;
  67
  68     template<typename T>
  69     struct VectorDestructor<false, T>
  70     {
  71         static void destruct(T*, T*) {}
  72     };
  73
  74     template<typename T>
  75     struct VectorDestructor<true, T>
  76     {
  77         static void destruct(T* begin, T* end)
  78         {
  79             for (T* cur = begin; cur != end; ++cur)
  80                 cur->~T();
  81         }
  82     };
  83
  84     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
  85     class VectorInitializer;
  86
  87     template<bool ignore, typename T>
  88     struct VectorInitializer<false, ignore, T>
  89     {
  90         static void initialize(T*, T*) {}
  91     };
  92
  93     template<typename T>
  94     struct VectorInitializer<true, false, T>
  95     {
  96         static void initialize(T* begin, T* end)
  97         {
  98             for (T* cur = begin; cur != end; ++cur)
  99                 new (cur) T;
 100         }
 101     };
 102
 103     template<typename T>
 104     struct VectorInitializer<true, true, T>
 105     {
 106         static void initialize(T* begin, T* end)
 107         {
 108             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
 109         }
 110     };
 111
 112     template <bool canMoveWithMemcpy, typename T>
 113     class VectorMover;
 114
 115     template<typename T>
 116     struct VectorMover<false, T>
 117     {
 118         static void move(const T* src, const T* srcEnd, T* dst)
 119         {
 120             while (src != srcEnd) {
 121                 new (dst) T(*src);
 122                 src->~T();
 123                 ++dst;
 124                 ++src;
 125             }
 126         }
 127         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 128         {
 129             if (src > dst)
 130                 move(src, srcEnd, dst);
 131             else {
 132                 T* dstEnd = dst + (srcEnd - src);
 133                 while (src != srcEnd) {
 134                     --srcEnd;
 135                     --dstEnd;
 136                     new (dstEnd) T(*srcEnd);
 137                     srcEnd->~T();
 138                 }
 139             }
 140         }
 141     };
 142
 143     template<typename T>
 144     struct VectorMover<true, T>
 145     {
 146         static void move(const T* src, const T* srcEnd, T* dst)
 147         {
 148             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 149         }
 150         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 151         {
 152             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 153         }
 154     };
 155
 156     template <bool canCopyWithMemcpy, typename T>
 157     class VectorCopier;
 158
 159     template<typename T>
 160     struct VectorCopier<false, T>
 161     {
 162         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 163         {
 164             while (src != srcEnd) {
 165                 new (dst) T(*src);
 166                 ++dst;
 167                 ++src;
 168             }
 169         }
 170     };
 171
 172     template<typename T>
 173     struct VectorCopier<true, T>
 174     {
 175         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 176         {
 177             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 178         }
 179     };
 180
 181     template <bool canFillWithMemset, typename T>
 182     class VectorFiller;
 183
 184     template<typename T>
 185     struct VectorFiller<false, T>
 186     {
 187         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 188         {
 189             while (dst != dstEnd) {
 190                 new (dst) T(val);
 191                 ++dst;
 192             }
 193         }
 194     };
 195
 196     template<typename T>
 197     struct VectorFiller<true, T>
 198     {
 199         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 200         {
 201             ASSERT(sizeof(T) == sizeof(char));
 202             memset(dst, val, dstEnd - dst);
 203         }
 204     };
 205
 206     template<bool canCompareWithMemcmp, typename T>
 207     class VectorComparer;
 208
 209     template<typename T>
 210     struct VectorComparer<false, T>
 211     {
 212         static bool compare(const T* a, const T* b, size_t size)
 213         {
 214             for (size_t i = 0; i < size; ++i)
 215                 if (a[i] != b[i])
 216                     return false;
 217             return true;
 218         }
 219     };
 220
 221     template<typename T>
 222     struct VectorComparer<true, T>
 223     {
 224         static bool compare(const T* a, const T* b, size_t size)
 225         {
 226             return memcmp(a, b, sizeof(T) * size) == 0;
 227         }
 228     };
 229
 230     template<typename T>
 231     struct VectorTypeOperations
 232     {
 233         static void destruct(T* begin, T* end)
 234         {
 235             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
 236         }
 237
 238         static void initialize(T* begin, T* end)
 239         {
 240             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
 241         }
 242
 243         static void move(const T* src, const T* srcEnd, T* dst)
 244         {
 245             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
 246         }
 247
 248         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 249         {
 250             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
 251         }
 252
 253         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 254         {
 255             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
 256         }
 257
 258         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 259         {
 260             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
 261         }
 262
 263         static bool compare(const T* a, const T* b, size_t size)
 264         {
 265             return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
 266         }
 267     };
 268
 269     template<typename T>
 270     class VectorBufferBase : Noncopyable {
 271     public:
 272         void allocateBuffer(size_t newCapacity)
 273         {
 274             m_capacity = newCapacity;
 275             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 276                 CRASH();
 277             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
 278         }
 279
 280         void deallocateBuffer(T* bufferToDeallocate)
 281         {
 282             if (m_buffer == bufferToDeallocate) {
 283                 m_buffer = 0;
 284                 m_capacity = 0;
 285             }
 286             fastFree(bufferToDeallocate);
 287         }
 288
 289         T* buffer() { return m_buffer; }
 290         const T* buffer() const { return m_buffer; }
 291         T** bufferSlot() { return &m_buffer; }
 292         size_t capacity() const { return m_capacity; }
 293
 294         T* releaseBuffer()
 295         {
 296             T* buffer = m_buffer;
 297             m_buffer = 0;
 298             m_capacity = 0;
 299             return buffer;
 300         }
 301
 302     protected:
 303         VectorBufferBase()
 304             : m_buffer(0)
 305             , m_capacity(0)
 306         {
 307         }
 308
 309         VectorBufferBase(T* buffer, size_t capacity)
 310             : m_buffer(buffer)
 311             , m_capacity(capacity)
 312         {
 313         }
 314
 315         ~VectorBufferBase()
 316         {
 317             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
 318         }
 319
 320         T* m_buffer;
 321         size_t m_capacity;
 322     };
 323
 324     template<typename T, size_t inlineCapacity>
 325     class VectorBuffer;
 326
 327     template<typename T>
 328     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
 329     private:
 330         typedef VectorBufferBase<T> Base;
 331     public:
 332         VectorBuffer()
 333         {
 334         }
 335
 336         VectorBuffer(size_t capacity)
 337         {
 338             allocateBuffer(capacity);
 339         }
 340
 341         ~VectorBuffer()
 342         {
 343             deallocateBuffer(buffer());
 344         }
 345
 346         void swap(VectorBuffer<T, 0>& other)
 347         {
 348             std::swap(m_buffer, other.m_buffer);
 349             std::swap(m_capacity, other.m_capacity);
 350         }
 351
 352         void restoreInlineBufferIfNeeded() { }
 353
 354         using Base::allocateBuffer;
 355         using Base::deallocateBuffer;
 356
 357         using Base::buffer;
 358         using Base::bufferSlot;
 359         using Base::capacity;
 360
 361         using Base::releaseBuffer;
 362     private:
 363         using Base::m_buffer;
 364         using Base::m_capacity;
 365     };
 366
 367     template<typename T, size_t inlineCapacity>
 368     class VectorBuffer : private VectorBufferBase<T> {
 369     private:
 370         typedef VectorBufferBase<T> Base;
 371     public:
 372         VectorBuffer()
 373             : Base(inlineBuffer(), inlineCapacity)
 374         {
 375         }
 376
 377         VectorBuffer(size_t capacity)
 378             : Base(inlineBuffer(), inlineCapacity)
 379         {
 380             allocateBuffer(capacity);
 381         }
 382
 383         ~VectorBuffer()
 384         {
 385             deallocateBuffer(buffer());
 386         }
 387
 388         void allocateBuffer(size_t newCapacity)
 389         {
 390             if (newCapacity > inlineCapacity)
 391                 Base::allocateBuffer(newCapacity);
 392         }
 393
 394         void deallocateBuffer(T* bufferToDeallocate)
 395         {
 396             if (bufferToDeallocate == inlineBuffer())
 397                 return;
 398             Base::deallocateBuffer(bufferToDeallocate);
 399         }
 400
 401         void restoreInlineBufferIfNeeded()
 402         {
 403             if (m_buffer)
 404                 return;
 405             m_buffer = inlineBuffer();
 406             m_capacity = inlineCapacity;
 407         }
 408
 409         using Base::buffer;
 410         using Base::bufferSlot;
 411         using Base::capacity;
 412
 413         T* releaseBuffer()
 414         {
 415             if (buffer() == inlineBuffer())
 416                 return 0;
 417             return Base::releaseBuffer();
 418         }
 419
 420     private:
 421         using Base::m_buffer;
 422         using Base::m_capacity;
 423
 424         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
 425 #if PLATFORM(ARM)
 426         // FIXME: <rdar://problem/6546253&6546260>
 427         T* inlineBuffer() { return reinterpret_cast<T*>(static_cast<void*>(m_inlineBuffer.buffer)); }
 428 #else
 429         T* inlineBuffer() { return reinterpret_cast<T*>(m_inlineBuffer.buffer); }
 430 #endif
 431
 432         AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
 433     };
 434
 435     template<typename T, size_t inlineCapacity = 0>
 436     class Vector {
 437     private:
 438         typedef VectorBuffer<T, inlineCapacity> Buffer;
 439         typedef VectorTypeOperations<T> TypeOperations;
 440
 441     public:
 442         typedef T ValueType;
 443
 444         typedef T* iterator;
 445         typedef const T* const_iterator;
 446
 447         Vector()
 448             : m_size(0)
 449         {
 450         }
 451
 452         explicit Vector(size_t size)
 453             : m_size(size)
 454             , m_buffer(size)
 455         {
 456             if (begin())
 457                 TypeOperations::initialize(begin(), end());
 458         }
 459
 460         ~Vector()
 461         {
 462             if (m_size) shrink(0);
 463         }
 464
 465         Vector(const Vector&);
 466         template<size_t otherCapacity>
 467         Vector(const Vector<T, otherCapacity>&);
 468
 469         Vector& operator=(const Vector&);
 470         template<size_t otherCapacity>
 471         Vector& operator=(const Vector<T, otherCapacity>&);
 472
 473         size_t size() const { return m_size; }
 474         size_t capacity() const { return m_buffer.capacity(); }
 475         bool isEmpty() const { return !size(); }
 476
 477         T& at(size_t i)
 478         {
 479             ASSERT(i < size());
 480             return m_buffer.buffer()[i];
 481         }
 482         const T& at(size_t i) const
 483         {
 484             ASSERT(i < size());
 485             return m_buffer.buffer()[i];
 486         }
 487
 488         T& operator[](size_t i) { return at(i); }
 489         const T& operator[](size_t i) const { return at(i); }
 490
 491         T* data() { return m_buffer.buffer(); }
 492         const T* data() const { return m_buffer.buffer(); }
 493         T** dataSlot() { return m_buffer.bufferSlot(); }
 494
 495         iterator begin() { return data(); }
 496         iterator end() { return begin() + m_size; }
 497         const_iterator begin() const { return data(); }
 498         const_iterator end() const { return begin() + m_size; }
 499
 500         T& first() { return at(0); }
 501         const T& first() const { return at(0); }
 502         T& last() { return at(size() - 1); }
 503         const T& last() const { return at(size() - 1); }
 504
 505         template<typename U> size_t find(const U&) const;
 506
 507         void shrink(size_t size);
 508         void grow(size_t size);
 509         void resize(size_t size);
 510         void reserveCapacity(size_t newCapacity);
 511         void reserveInitialCapacity(size_t initialCapacity);
 512         void shrinkCapacity(size_t newCapacity);
 513         void shrinkToFit() { shrinkCapacity(size()); }
 514
 515         void clear() { shrinkCapacity(0); }
 516
 517         template<typename U> void append(const U*, size_t);
 518         template<typename U> void append(const U&);
 519         template<typename U> void uncheckedAppend(const U& val);
 520         template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
 521
 522         template<typename U> void insert(size_t position, const U*, size_t);
 523         template<typename U> void insert(size_t position, const U&);
 524         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
 525
 526         template<typename U> void prepend(const U*, size_t);
 527         template<typename U> void prepend(const U&);
 528         template<typename U, size_t c> void prepend(const Vector<U, c>&);
 529
 530         void remove(size_t position);
 531         void remove(size_t position, size_t length);
 532
 533         void removeLast()
 534         {
 535             ASSERT(!isEmpty());
 536             shrink(size() - 1);
 537         }
 538
 539         Vector(size_t size, const T& val)
 540             : m_size(size)
 541             , m_buffer(size)
 542         {
 543             if (begin())
 544                 TypeOperations::uninitializedFill(begin(), end(), val);
 545         }
 546
 547         void fill(const T&, size_t);
 548         void fill(const T& val) { fill(val, size()); }
 549
 550         template<typename Iterator> void appendRange(Iterator start, Iterator end);
 551
 552         T* releaseBuffer();
 553
 554         void swap(Vector<T, inlineCapacity>& other)
 555         {
 556             std::swap(m_size, other.m_size);
 557             m_buffer.swap(other.m_buffer);
 558         }
 559
 560     private:
 561         void expandCapacity(size_t newMinCapacity);
 562         const T* expandCapacity(size_t newMinCapacity, const T*);
 563         template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
 564
 565         size_t m_size;
 566         Buffer m_buffer;
 567     };
 568
 569     template<typename T, size_t inlineCapacity>
 570     Vector<T, inlineCapacity>::Vector(const Vector& other)
 571         : m_size(other.size())
 572         , m_buffer(other.capacity())
 573     {
 574         if (begin())
 575             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 576     }
 577
 578     template<typename T, size_t inlineCapacity>
 579     template<size_t otherCapacity>
 580     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
 581         : m_size(other.size())
 582         , m_buffer(other.capacity())
 583     {
 584         if (begin())
 585             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 586     }
 587
 588     template<typename T, size_t inlineCapacity>
 589     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
 590     {
 591         if (&other == this)
 592             return *this;
 593
 594         if (size() > other.size())
 595             shrink(other.size());
 596         else if (other.size() > capacity()) {
 597             clear();
 598             reserveCapacity(other.size());
 599             if (!begin())
 600                 return *this;
 601         }
 602
 603         std::copy(other.begin(), other.begin() + size(), begin());
 604         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 605         m_size = other.size();
 606
 607         return *this;
 608     }
 609
 610     template<typename T, size_t inlineCapacity>
 611     template<size_t otherCapacity>
 612     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
 613     {
 614         if (&other == this)
 615             return *this;
 616
 617         if (size() > other.size())
 618             shrink(other.size());
 619         else if (other.size() > capacity()) {
 620             clear();
 621             reserveCapacity(other.size());
 622             if (!begin())
 623                 return *this;
 624         }
 625
 626         std::copy(other.begin(), other.begin() + size(), begin());
 627         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 628         m_size = other.size();
 629
 630         return *this;
 631     }
 632
 633     template<typename T, size_t inlineCapacity>
 634     template<typename U>
 635     size_t Vector<T, inlineCapacity>::find(const U& value) const
 636     {
 637         for (size_t i = 0; i < size(); ++i) {
 638             if (at(i) == value)
 639                 return i;
 640         }
 641         return notFound;
 642     }
 643
 644     template<typename T, size_t inlineCapacity>
 645     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
 646     {
 647         if (size() > newSize)
 648             shrink(newSize);
 649         else if (newSize > capacity()) {
 650             clear();
 651             reserveCapacity(newSize);
 652             if (!begin())
 653                 return;
 654         }
 655
 656         std::fill(begin(), end(), val);
 657         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
 658         m_size = newSize;
 659     }
 660
 661     template<typename T, size_t inlineCapacity>
 662     template<typename Iterator>
 663     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
 664     {
 665         for (Iterator it = start; it != end; ++it)
 666             append(*it);
 667     }
 668
 669     template<typename T, size_t inlineCapacity>
 670     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
 671     {
 672         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 673     }
 674
 675     template<typename T, size_t inlineCapacity>
 676     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
 677     {
 678         if (ptr < begin() || ptr >= end()) {
 679             expandCapacity(newMinCapacity);
 680             return ptr;
 681         }
 682         size_t index = ptr - begin();
 683         expandCapacity(newMinCapacity);
 684         return begin() + index;
 685     }
 686
 687     template<typename T, size_t inlineCapacity> template<typename U>
 688     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 689     {
 690         expandCapacity(newMinCapacity);
 691         return ptr;
 692     }
 693
 694     template<typename T, size_t inlineCapacity>
 695     void Vector<T, inlineCapacity>::resize(size_t size)
 696     {
 697         if (size <= m_size)
 698             TypeOperations::destruct(begin() + size, end());
 699         else {
 700             if (size > capacity())
 701                 expandCapacity(size);
 702             if (begin())
 703                 TypeOperations::initialize(end(), begin() + size);
 704         }
 705
 706         m_size = size;
 707     }
 708
 709     template<typename T, size_t inlineCapacity>
 710     void Vector<T, inlineCapacity>::shrink(size_t size)
 711     {
 712         ASSERT(size <= m_size);
 713         TypeOperations::destruct(begin() + size, end());
 714         m_size = size;
 715     }
 716
 717     template<typename T, size_t inlineCapacity>
 718     void Vector<T, inlineCapacity>::grow(size_t size)
 719     {
 720         ASSERT(size >= m_size);
 721         if (size > capacity())
 722             expandCapacity(size);
 723         if (begin())
 724             TypeOperations::initialize(end(), begin() + size);
 725         m_size = size;
 726     }
 727
 728     template<typename T, size_t inlineCapacity>
 729     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
 730     {
 731         if (newCapacity <= capacity())
 732             return;
 733         T* oldBuffer = begin();
 734         T* oldEnd = end();
 735         m_buffer.allocateBuffer(newCapacity);
 736         if (begin())
 737             TypeOperations::move(oldBuffer, oldEnd, begin());
 738         m_buffer.deallocateBuffer(oldBuffer);
 739     }
 740
 741     template<typename T, size_t inlineCapacity>
 742     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
 743     {
 744         ASSERT(!m_size);
 745         ASSERT(capacity() == inlineCapacity);
 746         if (initialCapacity > inlineCapacity)
 747             m_buffer.allocateBuffer(initialCapacity);
 748     }
 749
 750     template<typename T, size_t inlineCapacity>
 751     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
 752     {
 753         if (newCapacity >= capacity())
 754             return;
 755
 756         if (newCapacity < size())
 757             shrink(newCapacity);
 758
 759         T* oldBuffer = begin();
 760         if (newCapacity > 0) {
 761             T* oldEnd = end();
 762             m_buffer.allocateBuffer(newCapacity);
 763             if (begin() != oldBuffer)
 764                 TypeOperations::move(oldBuffer, oldEnd, begin());
 765         }
 766
 767         m_buffer.deallocateBuffer(oldBuffer);
 768         m_buffer.restoreInlineBufferIfNeeded();
 769     }
 770
 771     // Templatizing these is better than just letting the conversion happen implicitly,
 772     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 773     // without refcount thrash.
 774
 775     template<typename T, size_t inlineCapacity> template<typename U>
 776     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
 777     {
 778         size_t newSize = m_size + dataSize;
 779         if (newSize > capacity()) {
 780             data = expandCapacity(newSize, data);
 781             if (!begin())
 782                 return;
 783         }
 784         if (newSize < m_size)
 785             CRASH();
 786         T* dest = end();
 787         for (size_t i = 0; i < dataSize; ++i)
 788             new (&dest[i]) T(data[i]);
 789         m_size = newSize;
 790     }
 791
 792     template<typename T, size_t inlineCapacity> template<typename U>
 793     inline void Vector<T, inlineCapacity>::append(const U& val)
 794     {
 795         const U* ptr = &val;
 796         if (size() == capacity()) {
 797             ptr = expandCapacity(size() + 1, ptr);
 798             if (!begin())
 799                 return;
 800         }
 801
 802 #if COMPILER(MSVC7)
 803         // FIXME: MSVC7 generates compilation errors when trying to assign
 804         // a pointer to a Vector of its base class (i.e. can't downcast). So far
 805         // I've been unable to determine any logical reason for this, so I can
 806         // only assume it is a bug with the compiler. Casting is a bad solution,
 807         // however, because it subverts implicit conversions, so a better
 808         // one is needed.
 809         new (end()) T(static_cast<T>(*ptr));
 810 #else
 811         new (end()) T(*ptr);
 812 #endif
 813         ++m_size;
 814     }
 815
 816     // This version of append saves a branch in the case where you know that the
 817     // vector's capacity is large enough for the append to succeed.
 818
 819     template<typename T, size_t inlineCapacity> template<typename U>
 820     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
 821     {
 822         ASSERT(size() < capacity());
 823         const U* ptr = &val;
 824         new (end()) T(*ptr);
 825         ++m_size;
 826     }
 827
 828     // This method should not be called append, a better name would be appendElements.
 829     // It could also be eliminated entirely, and call sites could just use
 830     // appendRange(val.begin(), val.end()).
 831     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
 832     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
 833     {
 834         append(val.begin(), val.size());
 835     }
 836
 837     template<typename T, size_t inlineCapacity> template<typename U>
 838     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
 839     {
 840         ASSERT(position <= size());
 841         size_t newSize = m_size + dataSize;
 842         if (newSize > capacity()) {
 843             data = expandCapacity(newSize, data);
 844             if (!begin())
 845                 return;
 846         }
 847         if (newSize < m_size)
 848             CRASH();
 849         T* spot = begin() + position;
 850         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
 851         for (size_t i = 0; i < dataSize; ++i)
 852             new (&spot[i]) T(data[i]);
 853         m_size = newSize;
 854     }
 855
 856     template<typename T, size_t inlineCapacity> template<typename U>
 857     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
 858     {
 859         ASSERT(position <= size());
 860         const U* data = &val;
 861         if (size() == capacity()) {
 862             data = expandCapacity(size() + 1, data);
 863             if (!begin())
 864                 return;
 865         }
 866         T* spot = begin() + position;
 867         TypeOperations::moveOverlapping(spot, end(), spot + 1);
 868         new (spot) T(*data);
 869         ++m_size;
 870     }
 871
 872     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 873     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
 874     {
 875         insert(position, val.begin(), val.size());
 876     }
 877
 878     template<typename T, size_t inlineCapacity> template<typename U>
 879     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
 880     {
 881         insert(0, data, dataSize);
 882     }
 883
 884     template<typename T, size_t inlineCapacity> template<typename U>
 885     inline void Vector<T, inlineCapacity>::prepend(const U& val)
 886     {
 887         insert(0, val);
 888     }
 889
 890     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 891     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
 892     {
 893         insert(0, val.begin(), val.size());
 894     }
 895
 896     template<typename T, size_t inlineCapacity>
 897     inline void Vector<T, inlineCapacity>::remove(size_t position)
 898     {
 899         ASSERT(position < size());
 900         T* spot = begin() + position;
 901         spot->~T();
 902         TypeOperations::moveOverlapping(spot + 1, end(), spot);
 903         --m_size;
 904     }
 905
 906     template<typename T, size_t inlineCapacity>
 907     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
 908     {
 909         ASSERT(position < size());
 910         ASSERT(position + length < size());
 911         T* beginSpot = begin() + position;
 912         T* endSpot = beginSpot + length;
 913         TypeOperations::destruct(beginSpot, endSpot);
 914         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
 915         m_size -= length;
 916     }
 917
 918     template<typename T, size_t inlineCapacity>
 919     inline T* Vector<T, inlineCapacity>::releaseBuffer()
 920     {
 921         T* buffer = m_buffer.releaseBuffer();
 922         if (inlineCapacity && !buffer && m_size) {
 923             // If the vector had some data, but no buffer to release,
 924             // that means it was using the inline buffer. In that case,
 925             // we create a brand new buffer so the caller always gets one.
 926             size_t bytes = m_size * sizeof(T);
 927             buffer = static_cast<T*>(fastMalloc(bytes));
 928             memcpy(buffer, data(), bytes);
 929         }
 930         m_size = 0;
 931         return buffer;
 932     }
 933
 934     template<typename T, size_t inlineCapacity>
 935     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
 936     {
 937         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
 938         iterator end = collection.end();
 939         for (iterator it = collection.begin(); it != end; ++it)
 940             delete *it;
 941     }
 942
 943     template<typename T, size_t inlineCapacity>
 944     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
 945     {
 946         a.swap(b);
 947     }
 948
 949     template<typename T, size_t inlineCapacity>
 950     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
 951     {
 952         if (a.size() != b.size())
 953             return false;
 954
 955         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
 956     }
 957
 958     template<typename T, size_t inlineCapacity>
 959     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
 960     {
 961         return !(a == b);
 962     }
 963
 964
 965 } // namespace WTF
 966
 967 using WTF::Vector;
 968
 969 #endif // WTF_Vector_h