wtf/Vector.h

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  *  Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Library General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Library General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Library General Public License
  16  *  along with this library; see the file COPYING.LIB.  If not, write to
  17  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  *  Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 #ifndef WTF_Vector_h
  23 #define WTF_Vector_h
  24
  25 #include "Assertions.h"
  26 #include "FastMalloc.h"
  27 #include "Noncopyable.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     template <bool needsDestruction, typename T>
  40     class VectorDestructor;
  41
  42     template<typename T>
  43     struct VectorDestructor<false, T>
  44     {
  45         static void destruct(T*, T*) {}
  46     };
  47
  48     template<typename T>
  49     struct VectorDestructor<true, T>
  50     {
  51         static void destruct(T* begin, T* end)
  52         {
  53             for (T* cur = begin; cur != end; ++cur)
  54                 cur->~T();
  55         }
  56     };
  57
  58     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
  59     class VectorInitializer;
  60
  61     template<bool ignore, typename T>
  62     struct VectorInitializer<false, ignore, T>
  63     {
  64         static void initialize(T*, T*) {}
  65     };
  66
  67     template<typename T>
  68     struct VectorInitializer<true, false, T>
  69     {
  70         static void initialize(T* begin, T* end)
  71         {
  72             for (T* cur = begin; cur != end; ++cur)
  73                 new (cur) T;
  74         }
  75     };
  76
  77     template<typename T>
  78     struct VectorInitializer<true, true, T>
  79     {
  80         static void initialize(T* begin, T* end)
  81         {
  82             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
  83         }
  84     };
  85
  86     template <bool canMoveWithMemcpy, typename T>
  87     class VectorMover;
  88
  89     template<typename T>
  90     struct VectorMover<false, T>
  91     {
  92         static void move(const T* src, const T* srcEnd, T* dst)
  93         {
  94             while (src != srcEnd) {
  95                 new (dst) T(*src);
  96                 src->~T();
  97                 ++dst;
  98                 ++src;
  99             }
 100         }
 101         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 102         {
 103             if (src > dst)
 104                 move(src, srcEnd, dst);
 105             else {
 106                 T* dstEnd = dst + (srcEnd - src);
 107                 while (src != srcEnd) {
 108                     --srcEnd;
 109                     --dstEnd;
 110                     new (dstEnd) T(*srcEnd);
 111                     srcEnd->~T();
 112                 }
 113             }
 114         }
 115     };
 116
 117     template<typename T>
 118     struct VectorMover<true, T>
 119     {
 120         static void move(const T* src, const T* srcEnd, T* dst)
 121         {
 122             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 123         }
 124         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 125         {
 126             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 127         }
 128     };
 129
 130     template <bool canCopyWithMemcpy, typename T>
 131     class VectorCopier;
 132
 133     template<typename T>
 134     struct VectorCopier<false, T>
 135     {
 136         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 137         {
 138             while (src != srcEnd) {
 139                 new (dst) T(*src);
 140                 ++dst;
 141                 ++src;
 142             }
 143         }
 144     };
 145
 146     template<typename T>
 147     struct VectorCopier<true, T>
 148     {
 149         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 150         {
 151             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 152         }
 153     };
 154
 155     template <bool canFillWithMemset, typename T>
 156     class VectorFiller;
 157
 158     template<typename T>
 159     struct VectorFiller<false, T>
 160     {
 161         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 162         {
 163             while (dst != dstEnd) {
 164                 new (dst) T(val);
 165                 ++dst;
 166             }
 167         }
 168     };
 169
 170     template<typename T>
 171     struct VectorFiller<true, T>
 172     {
 173         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 174         {
 175             ASSERT(sizeof(T) == sizeof(char));
 176             memset(dst, val, dstEnd - dst);
 177         }
 178     };
 179
 180     template<bool canCompareWithMemcmp, typename T>
 181     class VectorComparer;
 182
 183     template<typename T>
 184     struct VectorComparer<false, T>
 185     {
 186         static bool compare(const T* a, const T* b, size_t size)
 187         {
 188             for (size_t i = 0; i < size; ++i)
 189                 if (a[i] != b[i])
 190                     return false;
 191             return true;
 192         }
 193     };
 194
 195     template<typename T>
 196     struct VectorComparer<true, T>
 197     {
 198         static bool compare(const T* a, const T* b, size_t size)
 199         {
 200             return memcmp(a, b, sizeof(T) * size) == 0;
 201         }
 202     };
 203
 204     template<typename T>
 205     struct VectorTypeOperations
 206     {
 207         static void destruct(T* begin, T* end)
 208         {
 209             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
 210         }
 211
 212         static void initialize(T* begin, T* end)
 213         {
 214             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
 215         }
 216
 217         static void move(const T* src, const T* srcEnd, T* dst)
 218         {
 219             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
 220         }
 221
 222         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 223         {
 224             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
 225         }
 226
 227         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 228         {
 229             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
 230         }
 231
 232         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 233         {
 234             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
 235         }
 236
 237         static bool compare(const T* a, const T* b, size_t size)
 238         {
 239             return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
 240         }
 241     };
 242
 243     template<typename T>
 244     class VectorBufferBase : Noncopyable {
 245     public:
 246         void allocateBuffer(size_t newCapacity)
 247         {
 248             ASSERT(newCapacity >= m_capacity);
 249             m_capacity = newCapacity;
 250             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 251                 CRASH();
 252             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
 253         }
 254
 255         void deallocateBuffer(T* bufferToDeallocate)
 256         {
 257             fastFree(bufferToDeallocate);
 258         }
 259
 260         T* buffer() { return m_buffer; }
 261         const T* buffer() const { return m_buffer; }
 262         size_t capacity() const { return m_capacity; }
 263
 264         T* releaseBuffer()
 265         {
 266             T* buffer = m_buffer;
 267             m_buffer = 0;
 268             m_capacity = 0;
 269             return buffer;
 270         }
 271
 272     protected:
 273         VectorBufferBase()
 274             : m_buffer(0)
 275             , m_capacity(0)
 276         {
 277         }
 278
 279         VectorBufferBase(T* buffer, size_t capacity)
 280             : m_buffer(buffer)
 281             , m_capacity(capacity)
 282         {
 283         }
 284
 285         ~VectorBufferBase()
 286         {
 287             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
 288         }
 289
 290         T* m_buffer;
 291         size_t m_capacity;
 292     };
 293
 294     template<typename T, size_t inlineCapacity>
 295     class VectorBuffer;
 296
 297     template<typename T>
 298     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
 299     private:
 300         typedef VectorBufferBase<T> Base;
 301     public:
 302         VectorBuffer()
 303         {
 304         }
 305
 306         VectorBuffer(size_t capacity)
 307         {
 308             allocateBuffer(capacity);
 309         }
 310
 311         ~VectorBuffer()
 312         {
 313             deallocateBuffer(buffer());
 314         }
 315
 316         void swap(VectorBuffer<T, 0>& other)
 317         {
 318             std::swap(m_buffer, other.m_buffer);
 319             std::swap(m_capacity, other.m_capacity);
 320         }
 321
 322         using Base::allocateBuffer;
 323         using Base::deallocateBuffer;
 324
 325         using Base::buffer;
 326         using Base::capacity;
 327
 328         using Base::releaseBuffer;
 329     private:
 330         using Base::m_buffer;
 331         using Base::m_capacity;
 332     };
 333
 334     template<typename T, size_t inlineCapacity>
 335     class VectorBuffer : private VectorBufferBase<T> {
 336     private:
 337         typedef VectorBufferBase<T> Base;
 338     public:
 339         VectorBuffer()
 340             : Base(inlineBuffer(), inlineCapacity)
 341         {
 342         }
 343
 344         VectorBuffer(size_t capacity)
 345             : Base(inlineBuffer(), inlineCapacity)
 346         {
 347             if (capacity > inlineCapacity)
 348                 allocateBuffer(capacity);
 349         }
 350
 351         ~VectorBuffer()
 352         {
 353             deallocateBuffer(buffer());
 354         }
 355
 356         using Base::allocateBuffer;
 357
 358         void deallocateBuffer(T* bufferToDeallocate)
 359         {
 360             if (bufferToDeallocate == inlineBuffer())
 361                 return;
 362             Base::deallocateBuffer(bufferToDeallocate);
 363         }
 364
 365         using Base::buffer;
 366         using Base::capacity;
 367
 368         T* releaseBuffer()
 369         {
 370             if (buffer() == inlineBuffer())
 371                 return 0;
 372             return Base::releaseBuffer();
 373         }
 374
 375     private:
 376         using Base::m_buffer;
 377         using Base::m_capacity;
 378
 379         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
 380 #if PLATFORM(ARM)
 381         T *inlineBuffer() { return reinterpret_cast<T*>((void*)((&m_inlineBuffer))); }
 382
 383         __attribute__ ((aligned (4))) char m_inlineBuffer[m_inlineBufferSize];
 384 #else
 385         T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
 386
 387         // FIXME: Nothing guarantees this buffer is appropriately aligned to hold objects of type T.
 388         char m_inlineBuffer[m_inlineBufferSize];
 389 #endif
 390     };
 391
 392     template<typename T, size_t inlineCapacity = 0>
 393     class Vector {
 394     private:
 395         typedef VectorBuffer<T, inlineCapacity> Buffer;
 396         typedef VectorTypeOperations<T> TypeOperations;
 397
 398     public:
 399         typedef T ValueType;
 400
 401         typedef T* iterator;
 402         typedef const T* const_iterator;
 403
 404         Vector()
 405             : m_size(0)
 406         {
 407         }
 408
 409         explicit Vector(size_t size)
 410             : m_size(size)
 411             , m_buffer(size)
 412         {
 413             TypeOperations::initialize(begin(), end());
 414         }
 415
 416         ~Vector()
 417         {
 418             clear();
 419         }
 420
 421         Vector(const Vector&);
 422         template<size_t otherCapacity>
 423         Vector(const Vector<T, otherCapacity>&);
 424
 425         Vector& operator=(const Vector&);
 426         template<size_t otherCapacity>
 427         Vector& operator=(const Vector<T, otherCapacity>&);
 428
 429         size_t size() const { return m_size; }
 430         size_t capacity() const { return m_buffer.capacity(); }
 431         bool isEmpty() const { return !size(); }
 432
 433         T& at(size_t i)
 434         {
 435             ASSERT(i < size());
 436             return m_buffer.buffer()[i];
 437         }
 438         const T& at(size_t i) const
 439         {
 440             ASSERT(i < size());
 441             return m_buffer.buffer()[i];
 442         }
 443
 444         T& operator[](size_t i) { return at(i); }
 445         const T& operator[](size_t i) const { return at(i); }
 446
 447         T* data() { return m_buffer.buffer(); }
 448         const T* data() const { return m_buffer.buffer(); }
 449
 450         iterator begin() { return data(); }
 451         iterator end() { return begin() + m_size; }
 452         const_iterator begin() const { return data(); }
 453         const_iterator end() const { return begin() + m_size; }
 454
 455         T& first() { return at(0); }
 456         const T& first() const { return at(0); }
 457         T& last() { return at(size() - 1); }
 458         const T& last() const { return at(size() - 1); }
 459
 460         void shrink(size_t size);
 461         void grow(size_t size);
 462         void resize(size_t size);
 463         void reserveCapacity(size_t newCapacity);
 464
 465         void clear() { if (m_size) shrink(0); }
 466
 467         template<typename U> void append(const U*, size_t);
 468         template<typename U> void append(const U&);
 469         template<typename U> void uncheckedAppend(const U& val);
 470         template<typename U, size_t c> void append(const Vector<U, c>&);
 471
 472         template<typename U> void insert(size_t position, const U*, size_t);
 473         template<typename U> void insert(size_t position, const U&);
 474         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
 475
 476         template<typename U> void prepend(const U*, size_t);
 477         template<typename U> void prepend(const U&);
 478         template<typename U, size_t c> void prepend(const Vector<U, c>&);
 479
 480         void remove(size_t position);
 481
 482         void removeLast()
 483         {
 484             ASSERT(!isEmpty());
 485             shrink(size() - 1);
 486         }
 487
 488         Vector(size_t size, const T& val)
 489             : m_size(size)
 490             , m_buffer(size)
 491         {
 492             TypeOperations::uninitializedFill(begin(), end(), val);
 493         }
 494
 495         void fill(const T&, size_t);
 496         void fill(const T& val) { fill(val, size()); }
 497
 498         template<typename Iterator> void appendRange(Iterator start, Iterator end);
 499
 500         T* releaseBuffer();
 501
 502         void swap(Vector<T, inlineCapacity>& other)
 503         {
 504             std::swap(m_size, other.m_size);
 505             m_buffer.swap(other.m_buffer);
 506         }
 507
 508     private:
 509         void expandCapacity(size_t newMinCapacity);
 510         const T* expandCapacity(size_t newMinCapacity, const T*);
 511         template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
 512
 513         size_t m_size;
 514         Buffer m_buffer;
 515     };
 516
 517     template<typename T, size_t inlineCapacity>
 518     Vector<T, inlineCapacity>::Vector(const Vector& other)
 519         : m_size(other.size())
 520         , m_buffer(other.capacity())
 521     {
 522         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 523     }
 524
 525     template<typename T, size_t inlineCapacity>
 526     template<size_t otherCapacity>
 527     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
 528         : m_size(other.size())
 529         , m_buffer(other.capacity())
 530     {
 531         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 532     }
 533
 534     template<typename T, size_t inlineCapacity>
 535     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
 536     {
 537         if (&other == this)
 538             return *this;
 539
 540         if (size() > other.size())
 541             shrink(other.size());
 542         else if (other.size() > capacity()) {
 543             clear();
 544             reserveCapacity(other.size());
 545         }
 546
 547         std::copy(other.begin(), other.begin() + size(), begin());
 548         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 549         m_size = other.size();
 550
 551         return *this;
 552     }
 553
 554     template<typename T, size_t inlineCapacity>
 555     template<size_t otherCapacity>
 556     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
 557     {
 558         if (&other == this)
 559             return *this;
 560
 561         if (size() > other.size())
 562             shrink(other.size());
 563         else if (other.size() > capacity()) {
 564             clear();
 565             reserveCapacity(other.size());
 566         }
 567
 568         std::copy(other.begin(), other.begin() + size(), begin());
 569         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 570         m_size = other.size();
 571
 572         return *this;
 573     }
 574
 575     template<typename T, size_t inlineCapacity>
 576     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
 577     {
 578         if (size() > newSize)
 579             shrink(newSize);
 580         else if (newSize > capacity()) {
 581             clear();
 582             reserveCapacity(newSize);
 583         }
 584
 585         std::fill(begin(), end(), val);
 586         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
 587         m_size = newSize;
 588     }
 589
 590     template<typename T, size_t inlineCapacity>
 591     template<typename Iterator>
 592     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
 593     {
 594         for (Iterator it = start; it != end; ++it)
 595             append(*it);
 596     }
 597
 598     template<typename T, size_t inlineCapacity>
 599     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
 600     {
 601         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 602     }
 603
 604     template<typename T, size_t inlineCapacity>
 605     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
 606     {
 607         if (ptr < begin() || ptr >= end()) {
 608             expandCapacity(newMinCapacity);
 609             return ptr;
 610         }
 611         size_t index = ptr - begin();
 612         expandCapacity(newMinCapacity);
 613         return begin() + index;
 614     }
 615
 616     template<typename T, size_t inlineCapacity> template<typename U>
 617     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 618     {
 619         expandCapacity(newMinCapacity);
 620         return ptr;
 621     }
 622
 623     template<typename T, size_t inlineCapacity>
 624     void Vector<T, inlineCapacity>::resize(size_t size)
 625     {
 626         if (size <= m_size)
 627             TypeOperations::destruct(begin() + size, end());
 628         else {
 629             if (size > capacity())
 630                 expandCapacity(size);
 631             TypeOperations::initialize(end(), begin() + size);
 632         }
 633
 634         m_size = size;
 635     }
 636
 637     template<typename T, size_t inlineCapacity>
 638     void Vector<T, inlineCapacity>::shrink(size_t size)
 639     {
 640         ASSERT(size <= m_size);
 641         TypeOperations::destruct(begin() + size, end());
 642         m_size = size;
 643     }
 644
 645     template<typename T, size_t inlineCapacity>
 646     void Vector<T, inlineCapacity>::grow(size_t size)
 647     {
 648         ASSERT(size >= m_size);
 649         if (size > capacity())
 650             expandCapacity(size);
 651         TypeOperations::initialize(end(), begin() + size);
 652         m_size = size;
 653     }
 654
 655     template<typename T, size_t inlineCapacity>
 656     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
 657     {
 658         if (newCapacity <= capacity())
 659             return;
 660         T* oldBuffer = begin();
 661         T* oldEnd = end();
 662         m_buffer.allocateBuffer(newCapacity);
 663         TypeOperations::move(oldBuffer, oldEnd, begin());
 664         m_buffer.deallocateBuffer(oldBuffer);
 665     }
 666
 667     // Templatizing these is better than just letting the conversion happen implicitly,
 668     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 669     // without refcount thrash.
 670
 671     template<typename T, size_t inlineCapacity> template<typename U>
 672     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
 673     {
 674         size_t newSize = m_size + dataSize;
 675         if (newSize > capacity())
 676             data = expandCapacity(newSize, data);
 677         T* dest = end();
 678         for (size_t i = 0; i < dataSize; ++i)
 679             new (&dest[i]) T(data[i]);
 680         m_size = newSize;
 681     }
 682
 683     template<typename T, size_t inlineCapacity> template<typename U>
 684     inline void Vector<T, inlineCapacity>::append(const U& val)
 685     {
 686         const U* ptr = &val;
 687         if (size() == capacity())
 688             ptr = expandCapacity(size() + 1, ptr);
 689
 690 #if COMPILER(MSVC7)
 691         // FIXME: MSVC7 generates compilation errors when trying to assign
 692         // a pointer to a Vector of its base class (i.e. can't downcast). So far
 693         // I've been unable to determine any logical reason for this, so I can
 694         // only assume it is a bug with the compiler. Casting is a bad solution,
 695         // however, because it subverts implicit conversions, so a better
 696         // one is needed.
 697         new (end()) T(static_cast<T>(*ptr));
 698 #else
 699         new (end()) T(*ptr);
 700 #endif
 701         ++m_size;
 702     }
 703
 704     // This version of append saves a branch in the case where you know that the
 705     // vector's capacity is large enough for the append to succeed.
 706
 707     template<typename T, size_t inlineCapacity> template<typename U>
 708     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
 709     {
 710         ASSERT(size() < capacity());
 711         const U* ptr = &val;
 712         new (end()) T(*ptr);
 713         ++m_size;
 714     }
 715
 716     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 717     inline void Vector<T, inlineCapacity>::append(const Vector<U, c>& val)
 718     {
 719         append(val.begin(), val.size());
 720     }
 721
 722     template<typename T, size_t inlineCapacity> template<typename U>
 723     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
 724     {
 725         ASSERT(position <= size());
 726         size_t newSize = m_size + dataSize;
 727         if (newSize > capacity())
 728             data = expandCapacity(newSize, data);
 729         T* spot = begin() + position;
 730         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
 731         for (size_t i = 0; i < dataSize; ++i)
 732             new (&spot[i]) T(data[i]);
 733         m_size = newSize;
 734     }
 735
 736     template<typename T, size_t inlineCapacity> template<typename U>
 737     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
 738     {
 739         ASSERT(position <= size());
 740         const U* data = &val;
 741         if (size() == capacity())
 742             data = expandCapacity(size() + 1, data);
 743         T* spot = begin() + position;
 744         TypeOperations::moveOverlapping(spot, end(), spot + 1);
 745         new (spot) T(*data);
 746         ++m_size;
 747     }
 748
 749     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 750     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
 751     {
 752         insert(position, val.begin(), val.size());
 753     }
 754
 755     template<typename T, size_t inlineCapacity> template<typename U>
 756     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
 757     {
 758         insert(0, data, dataSize);
 759     }
 760
 761     template<typename T, size_t inlineCapacity> template<typename U>
 762     inline void Vector<T, inlineCapacity>::prepend(const U& val)
 763     {
 764         insert(0, val);
 765     }
 766
 767     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
 768     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
 769     {
 770         insert(0, val.begin(), val.size());
 771     }
 772
 773     template<typename T, size_t inlineCapacity>
 774     inline void Vector<T, inlineCapacity>::remove(size_t position)
 775     {
 776         ASSERT(position < size());
 777         T* spot = begin() + position;
 778         spot->~T();
 779         TypeOperations::moveOverlapping(spot + 1, end(), spot);
 780         --m_size;
 781     }
 782
 783     template<typename T, size_t inlineCapacity>
 784     inline T* Vector<T, inlineCapacity>::releaseBuffer()
 785     {
 786         T* buffer = m_buffer.releaseBuffer();
 787         if (inlineCapacity && !buffer && m_size) {
 788             // If the vector had some data, but no buffer to release,
 789             // that means it was using the inline buffer. In that case,
 790             // we create a brand new buffer so the caller always gets one.
 791             size_t bytes = m_size * sizeof(T);
 792             buffer = static_cast<T*>(fastMalloc(bytes));
 793             memcpy(buffer, data(), bytes);
 794         }
 795         ASSERT(buffer);
 796         m_size = 0;
 797         return buffer;
 798     }
 799
 800     template<typename T, size_t inlineCapacity>
 801     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
 802     {
 803         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
 804         iterator end = collection.end();
 805         for (iterator it = collection.begin(); it != end; ++it)
 806             delete *it;
 807     }
 808
 809     template<typename T, size_t inlineCapacity>
 810     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
 811     {
 812         a.swap(b);
 813     }
 814
 815     template<typename T, size_t inlineCapacity>
 816     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
 817     {
 818         if (a.size() != b.size())
 819             return false;
 820
 821         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
 822     }
 823
 824     template<typename T, size_t inlineCapacity>
 825     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
 826     {
 827         return !(a == b);
 828     }
 829
 830
 831 } // namespace WTF
 832
 833 using WTF::Vector;
 834
 835 #endif // WTF_Vector_h