diff -r 000000000000 -r 4f2f89ce4247 JavaScriptCore/wtf/Vector.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/JavaScriptCore/wtf/Vector.h	Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,1156 @@
+/*
+ *  Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Library General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2 of the License, or (at your option) any later version.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Library General Public License
+ *  along with this library; see the file COPYING.LIB.  If not, write to
+ *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ *  Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef WTF_Vector_h
+#define WTF_Vector_h
+
+#include "FastAllocBase.h"
+#include "Noncopyable.h"
+#include "NotFound.h"
+#include "ValueCheck.h"
+#include "VectorTraits.h"
+#include <limits>
+#include <utility>
+
+#if PLATFORM(QT)
+#include <QDataStream>
+#endif
+
+namespace WTF {
+
+    using std::min;
+    using std::max;
+
+    // WTF_ALIGN_OF / WTF_ALIGNED
+    #if COMPILER(GCC) || COMPILER(MINGW) || COMPILER(RVCT) || COMPILER(WINSCW)
+        #define WTF_ALIGN_OF(type) __alignof__(type)
+        #define WTF_ALIGNED(variable_type, variable, n) variable_type variable __attribute__((__aligned__(n)))
+    #elif COMPILER(MSVC)
+        #define WTF_ALIGN_OF(type) __alignof(type)
+        #define WTF_ALIGNED(variable_type, variable, n) __declspec(align(n)) variable_type variable
+    #else
+        #error WTF_ALIGN macros need alignment control.
+    #endif
+
+    #if COMPILER(GCC) && !COMPILER(INTEL) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 303)
+        typedef char __attribute__((__may_alias__)) AlignedBufferChar; 
+    #else
+        typedef char AlignedBufferChar; 
+    #endif
+
+    template <size_t size, size_t alignment> struct AlignedBuffer;
+    template <size_t size> struct AlignedBuffer<size, 1> { AlignedBufferChar buffer[size]; };
+    template <size_t size> struct AlignedBuffer<size, 2> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 2);  };
+    template <size_t size> struct AlignedBuffer<size, 4> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 4);  };
+    template <size_t size> struct AlignedBuffer<size, 8> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 8);  };
+    template <size_t size> struct AlignedBuffer<size, 16> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 16); };
+    template <size_t size> struct AlignedBuffer<size, 32> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 32); };
+    template <size_t size> struct AlignedBuffer<size, 64> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 64); };
+
+    template <size_t size, size_t alignment>
+    void swap(AlignedBuffer<size, alignment>& a, AlignedBuffer<size, alignment>& b)
+    {
+        for (size_t i = 0; i < size; ++i)
+            std::swap(a.buffer[i], b.buffer[i]);
+    }
+
+    template <bool needsDestruction, typename T>
+    struct VectorDestructor;
+
+    template<typename T>
+    struct VectorDestructor<false, T>
+    {
+        static void destruct(T*, T*) {}
+    };
+
+    template<typename T>
+    struct VectorDestructor<true, T>
+    {
+        static void destruct(T* begin, T* end) 
+        {
+            for (T* cur = begin; cur != end; ++cur)
+                cur->~T();
+        }
+    };
+
+    template <bool needsInitialization, bool canInitializeWithMemset, typename T>
+    struct VectorInitializer;
+
+    template<bool ignore, typename T>
+    struct VectorInitializer<false, ignore, T>
+    {
+        static void initialize(T*, T*) {}
+    };
+
+    template<typename T>
+    struct VectorInitializer<true, false, T>
+    {
+        static void initialize(T* begin, T* end) 
+        {
+            for (T* cur = begin; cur != end; ++cur)
+                new (cur) T;
+        }
+    };
+
+    template<typename T>
+    struct VectorInitializer<true, true, T>
+    {
+        static void initialize(T* begin, T* end) 
+        {
+            memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
+        }
+    };
+
+    template <bool canMoveWithMemcpy, typename T>
+    struct VectorMover;
+
+    template<typename T>
+    struct VectorMover<false, T>
+    {
+        static void move(const T* src, const T* srcEnd, T* dst)
+        {
+            while (src != srcEnd) {
+                new (dst) T(*src);
+                src->~T();
+                ++dst;
+                ++src;
+            }
+        }
+        static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
+        {
+            if (src > dst)
+                move(src, srcEnd, dst);
+            else {
+                T* dstEnd = dst + (srcEnd - src);
+                while (src != srcEnd) {
+                    --srcEnd;
+                    --dstEnd;
+                    new (dstEnd) T(*srcEnd);
+                    srcEnd->~T();
+                }
+            }
+        }
+    };
+
+    template<typename T>
+    struct VectorMover<true, T>
+    {
+        static void move(const T* src, const T* srcEnd, T* dst) 
+        {
+            memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
+        }
+        static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
+        {
+            memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
+        }
+    };
+
+    template <bool canCopyWithMemcpy, typename T>
+    struct VectorCopier;
+
+    template<typename T>
+    struct VectorCopier<false, T>
+    {
+        static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
+        {
+            while (src != srcEnd) {
+                new (dst) T(*src);
+                ++dst;
+                ++src;
+            }
+        }
+    };
+
+    template<typename T>
+    struct VectorCopier<true, T>
+    {
+        static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
+        {
+            memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
+        }
+    };
+
+    template <bool canFillWithMemset, typename T>
+    struct VectorFiller;
+
+    template<typename T>
+    struct VectorFiller<false, T>
+    {
+        static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
+        {
+            while (dst != dstEnd) {
+                new (dst) T(val);
+                ++dst;
+            }
+        }
+    };
+
+    template<typename T>
+    struct VectorFiller<true, T>
+    {
+        static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
+        {
+            ASSERT(sizeof(T) == sizeof(char));
+            memset(dst, val, dstEnd - dst);
+        }
+    };
+    
+    template<bool canCompareWithMemcmp, typename T>
+    struct VectorComparer;
+    
+    template<typename T>
+    struct VectorComparer<false, T>
+    {
+        static bool compare(const T* a, const T* b, size_t size)
+        {
+            for (size_t i = 0; i < size; ++i)
+                if (a[i] != b[i])
+                    return false;
+            return true;
+        }
+    };
+
+    template<typename T>
+    struct VectorComparer<true, T>
+    {
+        static bool compare(const T* a, const T* b, size_t size)
+        {
+            return memcmp(a, b, sizeof(T) * size) == 0;
+        }
+    };
+    
+    template<typename T>
+    struct VectorTypeOperations
+    {
+        static void destruct(T* begin, T* end)
+        {
+            VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
+        }
+
+        static void initialize(T* begin, T* end)
+        {
+            VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
+        }
+
+        static void move(const T* src, const T* srcEnd, T* dst)
+        {
+            VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
+        }
+
+        static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
+        {
+            VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
+        }
+
+        static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
+        {
+            VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
+        }
+
+        static void uninitializedFill(T* dst, T* dstEnd, const T& val)
+        {
+            VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
+        }
+        
+        static bool compare(const T* a, const T* b, size_t size)
+        {
+            return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
+        }
+    };
+
+    template<typename T>
+    class VectorBufferBase : public Noncopyable {
+    public:
+        void allocateBuffer(size_t newCapacity)
+        {
+            m_capacity = newCapacity;
+            if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
+                CRASH();
+            m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
+        }
+
+        bool tryAllocateBuffer(size_t newCapacity)
+        {
+            if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
+                return false;
+
+            T* newBuffer;
+            if (tryFastMalloc(newCapacity * sizeof(T)).getValue(newBuffer)) {
+                m_capacity = newCapacity;
+                m_buffer = newBuffer;
+                return true;
+            }
+            return false;
+        }
+
+        void deallocateBuffer(T* bufferToDeallocate)
+        {
+            if (m_buffer == bufferToDeallocate) {
+                m_buffer = 0;
+                m_capacity = 0;
+            }
+            fastFree(bufferToDeallocate);
+        }
+
+        T* buffer() { return m_buffer; }
+        const T* buffer() const { return m_buffer; }
+        T** bufferSlot() { return &m_buffer; }
+        size_t capacity() const { return m_capacity; }
+
+        T* releaseBuffer()
+        {
+            T* buffer = m_buffer;
+            m_buffer = 0;
+            m_capacity = 0;
+            return buffer;
+        }
+
+    protected:
+        VectorBufferBase()
+            : m_buffer(0)
+            , m_capacity(0)
+        {
+        }
+
+        VectorBufferBase(T* buffer, size_t capacity)
+            : m_buffer(buffer)
+            , m_capacity(capacity)
+        {
+        }
+
+        ~VectorBufferBase()
+        {
+            // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
+        }
+
+        T* m_buffer;
+        size_t m_capacity;
+    };
+
+    template<typename T, size_t inlineCapacity>
+    class VectorBuffer;
+
+    template<typename T>
+    class VectorBuffer<T, 0> : private VectorBufferBase<T> {
+    private:
+        typedef VectorBufferBase<T> Base;
+    public:
+        VectorBuffer()
+        {
+        }
+
+        VectorBuffer(size_t capacity)
+        {
+            allocateBuffer(capacity);
+        }
+
+        ~VectorBuffer()
+        {
+            deallocateBuffer(buffer());
+        }
+        
+        void swap(VectorBuffer<T, 0>& other)
+        {
+            std::swap(m_buffer, other.m_buffer);
+            std::swap(m_capacity, other.m_capacity);
+        }
+        
+        void restoreInlineBufferIfNeeded() { }
+
+        using Base::allocateBuffer;
+        using Base::tryAllocateBuffer;
+        using Base::deallocateBuffer;
+
+        using Base::buffer;
+        using Base::bufferSlot;
+        using Base::capacity;
+
+        using Base::releaseBuffer;
+    private:
+        using Base::m_buffer;
+        using Base::m_capacity;
+    };
+
+    template<typename T, size_t inlineCapacity>
+    class VectorBuffer : private VectorBufferBase<T> {
+    private:
+        typedef VectorBufferBase<T> Base;
+    public:
+        VectorBuffer()
+            : Base(inlineBuffer(), inlineCapacity)
+        {
+        }
+
+        VectorBuffer(size_t capacity)
+            : Base(inlineBuffer(), inlineCapacity)
+        {
+            if (capacity > inlineCapacity)
+                Base::allocateBuffer(capacity);
+        }
+
+        ~VectorBuffer()
+        {
+            deallocateBuffer(buffer());
+        }
+
+        void allocateBuffer(size_t newCapacity)
+        {
+            if (newCapacity > inlineCapacity)
+                Base::allocateBuffer(newCapacity);
+            else {
+                m_buffer = inlineBuffer();
+                m_capacity = inlineCapacity;
+            }
+        }
+
+        bool tryAllocateBuffer(size_t newCapacity)
+        {
+            if (newCapacity > inlineCapacity)
+                return Base::tryAllocateBuffer(newCapacity);
+            m_buffer = inlineBuffer();
+            m_capacity = inlineCapacity;
+            return true;
+        }
+
+        void deallocateBuffer(T* bufferToDeallocate)
+        {
+            if (bufferToDeallocate == inlineBuffer())
+                return;
+            Base::deallocateBuffer(bufferToDeallocate);
+        }
+        
+        void swap(VectorBuffer<T, inlineCapacity>& other)
+        {
+            if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
+                WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
+                std::swap(m_capacity, other.m_capacity);
+            } else if (buffer() == inlineBuffer()) {
+                m_buffer = other.m_buffer;
+                other.m_buffer = other.inlineBuffer();
+                WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
+                std::swap(m_capacity, other.m_capacity);
+            } else if (other.buffer() == other.inlineBuffer()) {
+                other.m_buffer = m_buffer;
+                m_buffer = inlineBuffer();
+                WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
+                std::swap(m_capacity, other.m_capacity);
+            } else {
+                std::swap(m_buffer, other.m_buffer);
+                std::swap(m_capacity, other.m_capacity);
+            }
+        }
+
+        void restoreInlineBufferIfNeeded()
+        {
+            if (m_buffer)
+                return;
+            m_buffer = inlineBuffer();
+            m_capacity = inlineCapacity;
+        }
+
+        using Base::buffer;
+        using Base::bufferSlot;
+        using Base::capacity;
+
+        T* releaseBuffer()
+        {
+            if (buffer() == inlineBuffer())
+                return 0;
+            return Base::releaseBuffer();
+        }
+
+    private:
+        using Base::m_buffer;
+        using Base::m_capacity;
+
+        static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
+        T* inlineBuffer() { return reinterpret_cast<T*>(m_inlineBuffer.buffer); }
+
+        AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
+    };
+
+    template<typename T, size_t inlineCapacity = 0>
+    class Vector : public FastAllocBase {
+    private:
+        typedef VectorBuffer<T, inlineCapacity> Buffer;
+        typedef VectorTypeOperations<T> TypeOperations;
+
+    public:
+        typedef T ValueType;
+
+        typedef T* iterator;
+        typedef const T* const_iterator;
+
+        Vector() 
+            : m_size(0)
+        {
+        }
+        
+        explicit Vector(size_t size) 
+            : m_size(size)
+            , m_buffer(size)
+        {
+            if (begin())
+                TypeOperations::initialize(begin(), end());
+        }
+
+        ~Vector()
+        {
+            if (m_size) shrink(0);
+        }
+
+        Vector(const Vector&);
+        template<size_t otherCapacity> 
+        Vector(const Vector<T, otherCapacity>&);
+
+        Vector& operator=(const Vector&);
+        template<size_t otherCapacity> 
+        Vector& operator=(const Vector<T, otherCapacity>&);
+
+        size_t size() const { return m_size; }
+        size_t capacity() const { return m_buffer.capacity(); }
+        bool isEmpty() const { return !size(); }
+
+        T& at(size_t i) 
+        { 
+            ASSERT(i < size());
+            return m_buffer.buffer()[i]; 
+        }
+        const T& at(size_t i) const 
+        {
+            ASSERT(i < size());
+            return m_buffer.buffer()[i]; 
+        }
+
+        T& operator[](size_t i) { return at(i); }
+        const T& operator[](size_t i) const { return at(i); }
+
+        T* data() { return m_buffer.buffer(); }
+        const T* data() const { return m_buffer.buffer(); }
+        T** dataSlot() { return m_buffer.bufferSlot(); }
+
+        iterator begin() { return data(); }
+        iterator end() { return begin() + m_size; }
+        const_iterator begin() const { return data(); }
+        const_iterator end() const { return begin() + m_size; }
+        
+        T& first() { return at(0); }
+        const T& first() const { return at(0); }
+        T& last() { return at(size() - 1); }
+        const T& last() const { return at(size() - 1); }
+
+        template<typename U> size_t find(const U&) const;
+        template<typename U> size_t reverseFind(const U&) const;
+
+        void shrink(size_t size);
+        void grow(size_t size);
+        void resize(size_t size);
+        void reserveCapacity(size_t newCapacity);
+        bool tryReserveCapacity(size_t newCapacity);
+        void reserveInitialCapacity(size_t initialCapacity);
+        void shrinkCapacity(size_t newCapacity);
+        void shrinkToFit() { shrinkCapacity(size()); }
+
+        void clear() { shrinkCapacity(0); }
+
+        template<typename U> void append(const U*, size_t);
+        template<typename U> void append(const U&);
+        template<typename U> void uncheckedAppend(const U& val);
+        template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
+        template<typename U> bool tryAppend(const U*, size_t);
+
+        template<typename U> void insert(size_t position, const U*, size_t);
+        template<typename U> void insert(size_t position, const U&);
+        template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
+
+        template<typename U> void prepend(const U*, size_t);
+        template<typename U> void prepend(const U&);
+        template<typename U, size_t c> void prepend(const Vector<U, c>&);
+
+        void remove(size_t position);
+        void remove(size_t position, size_t length);
+
+        void removeLast() 
+        {
+            ASSERT(!isEmpty());
+            shrink(size() - 1); 
+        }
+
+        Vector(size_t size, const T& val)
+            : m_size(size)
+            , m_buffer(size)
+        {
+            if (begin())
+                TypeOperations::uninitializedFill(begin(), end(), val);
+        }
+
+        void fill(const T&, size_t);
+        void fill(const T& val) { fill(val, size()); }
+
+        template<typename Iterator> void appendRange(Iterator start, Iterator end);
+
+        T* releaseBuffer();
+
+        void swap(Vector<T, inlineCapacity>& other)
+        {
+            std::swap(m_size, other.m_size);
+            m_buffer.swap(other.m_buffer);
+        }
+
+        void checkConsistency();
+
+    private:
+        void expandCapacity(size_t newMinCapacity);
+        const T* expandCapacity(size_t newMinCapacity, const T*);
+        bool tryExpandCapacity(size_t newMinCapacity);
+        const T* tryExpandCapacity(size_t newMinCapacity, const T*);
+        template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
+
+        size_t m_size;
+        Buffer m_buffer;
+    };
+
+#if PLATFORM(QT)
+    template<typename T>
+    QDataStream& operator<<(QDataStream& stream, const Vector<T>& data)
+    {
+        stream << qint64(data.size());
+        foreach (const T& i, data)
+            stream << i;
+        return stream;
+    }
+
+    template<typename T>
+    QDataStream& operator>>(QDataStream& stream, Vector<T>& data)
+    {
+        data.clear();
+        qint64 count;
+        T item;
+        stream >> count;
+        data.reserveCapacity(count);
+        for (qint64 i = 0; i < count; ++i) {
+            stream >> item;
+            data.append(item);
+        }
+        return stream;
+    }
+#endif
+
+    template<typename T, size_t inlineCapacity>
+    Vector<T, inlineCapacity>::Vector(const Vector& other)
+        : m_size(other.size())
+        , m_buffer(other.capacity())
+    {
+        if (begin())
+            TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
+    }
+
+    template<typename T, size_t inlineCapacity>
+    template<size_t otherCapacity> 
+    Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
+        : m_size(other.size())
+        , m_buffer(other.capacity())
+    {
+        if (begin())
+            TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
+    }
+
+    template<typename T, size_t inlineCapacity>
+    Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
+    {
+        if (&other == this)
+            return *this;
+        
+        if (size() > other.size())
+            shrink(other.size());
+        else if (other.size() > capacity()) {
+            clear();
+            reserveCapacity(other.size());
+            if (!begin())
+                return *this;
+        }
+        
+// Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
+#if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
+        if (!begin())
+            return *this;
+#endif
+
+        std::copy(other.begin(), other.begin() + size(), begin());
+        TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
+        m_size = other.size();
+
+        return *this;
+    }
+
+    inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
+
+    template<typename T, size_t inlineCapacity>
+    template<size_t otherCapacity> 
+    Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
+    {
+        // If the inline capacities match, we should call the more specific
+        // template.  If the inline capacities don't match, the two objects
+        // shouldn't be allocated the same address.
+        ASSERT(!typelessPointersAreEqual(&other, this));
+
+        if (size() > other.size())
+            shrink(other.size());
+        else if (other.size() > capacity()) {
+            clear();
+            reserveCapacity(other.size());
+            if (!begin())
+                return *this;
+        }
+        
+// Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
+#if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
+        if (!begin())
+            return *this;
+#endif
+
+        std::copy(other.begin(), other.begin() + size(), begin());
+        TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
+        m_size = other.size();
+
+        return *this;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    template<typename U>
+    size_t Vector<T, inlineCapacity>::find(const U& value) const
+    {
+        for (size_t i = 0; i < size(); ++i) {
+            if (at(i) == value)
+                return i;
+        }
+        return notFound;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    template<typename U>
+    size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
+    {
+        for (size_t i = 1; i <= size(); ++i) {
+            const size_t index = size() - i;
+            if (at(index) == value)
+                return index;
+        }
+        return notFound;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
+    {
+        if (size() > newSize)
+            shrink(newSize);
+        else if (newSize > capacity()) {
+            clear();
+            reserveCapacity(newSize);
+            if (!begin())
+                return;
+        }
+        
+        std::fill(begin(), end(), val);
+        TypeOperations::uninitializedFill(end(), begin() + newSize, val);
+        m_size = newSize;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    template<typename Iterator>
+    void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
+    {
+        for (Iterator it = start; it != end; ++it)
+            append(*it);
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
+    {
+        reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
+    {
+        if (ptr < begin() || ptr >= end()) {
+            expandCapacity(newMinCapacity);
+            return ptr;
+        }
+        size_t index = ptr - begin();
+        expandCapacity(newMinCapacity);
+        return begin() + index;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity)
+    {
+        return tryReserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
+    {
+        if (ptr < begin() || ptr >= end()) {
+            if (!tryExpandCapacity(newMinCapacity))
+                return 0;
+            return ptr;
+        }
+        size_t index = ptr - begin();
+        if (!tryExpandCapacity(newMinCapacity))
+            return 0;
+        return begin() + index;
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
+    {
+        expandCapacity(newMinCapacity);
+        return ptr;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline void Vector<T, inlineCapacity>::resize(size_t size)
+    {
+        if (size <= m_size)
+            TypeOperations::destruct(begin() + size, end());
+        else {
+            if (size > capacity())
+                expandCapacity(size);
+            if (begin())
+                TypeOperations::initialize(end(), begin() + size);
+        }
+        
+        m_size = size;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::shrink(size_t size)
+    {
+        ASSERT(size <= m_size);
+        TypeOperations::destruct(begin() + size, end());
+        m_size = size;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::grow(size_t size)
+    {
+        ASSERT(size >= m_size);
+        if (size > capacity())
+            expandCapacity(size);
+        if (begin())
+            TypeOperations::initialize(end(), begin() + size);
+        m_size = size;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
+    {
+        if (newCapacity <= capacity())
+            return;
+        T* oldBuffer = begin();
+        T* oldEnd = end();
+        m_buffer.allocateBuffer(newCapacity);
+        if (begin())
+            TypeOperations::move(oldBuffer, oldEnd, begin());
+        m_buffer.deallocateBuffer(oldBuffer);
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity)
+    {
+        if (newCapacity <= capacity())
+            return true;
+        T* oldBuffer = begin();
+        T* oldEnd = end();
+        if (!m_buffer.tryAllocateBuffer(newCapacity))
+            return false;
+        ASSERT(begin());
+        TypeOperations::move(oldBuffer, oldEnd, begin());
+        m_buffer.deallocateBuffer(oldBuffer);
+        return true;
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
+    {
+        ASSERT(!m_size);
+        ASSERT(capacity() == inlineCapacity);
+        if (initialCapacity > inlineCapacity)
+            m_buffer.allocateBuffer(initialCapacity);
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
+    {
+        if (newCapacity >= capacity())
+            return;
+
+        if (newCapacity < size()) 
+            shrink(newCapacity);
+
+        T* oldBuffer = begin();
+        if (newCapacity > 0) {
+            T* oldEnd = end();
+            m_buffer.allocateBuffer(newCapacity);
+            if (begin() != oldBuffer)
+                TypeOperations::move(oldBuffer, oldEnd, begin());
+        }
+
+        m_buffer.deallocateBuffer(oldBuffer);
+        m_buffer.restoreInlineBufferIfNeeded();
+    }
+
+    // Templatizing these is better than just letting the conversion happen implicitly,
+    // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
+    // without refcount thrash.
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
+    {
+        size_t newSize = m_size + dataSize;
+        if (newSize > capacity()) {
+            data = expandCapacity(newSize, data);
+            if (!begin())
+                return;
+        }
+        if (newSize < m_size)
+            CRASH();
+        T* dest = end();
+        for (size_t i = 0; i < dataSize; ++i)
+            new (&dest[i]) T(data[i]);
+        m_size = newSize;
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize)
+    {
+        size_t newSize = m_size + dataSize;
+        if (newSize > capacity()) {
+            data = tryExpandCapacity(newSize, data);
+            if (!data)
+                return false;
+            ASSERT(begin());
+        }
+        if (newSize < m_size)
+            return false;
+        T* dest = end();
+        for (size_t i = 0; i < dataSize; ++i)
+            new (&dest[i]) T(data[i]);
+        m_size = newSize;
+        return true;
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
+    {
+        const U* ptr = &val;
+        if (size() == capacity()) {
+            ptr = expandCapacity(size() + 1, ptr);
+            if (!begin())
+                return;
+        }
+            
+#if COMPILER(MSVC7_OR_LOWER)
+        // FIXME: MSVC7 generates compilation errors when trying to assign
+        // a pointer to a Vector of its base class (i.e. can't downcast). So far
+        // I've been unable to determine any logical reason for this, so I can
+        // only assume it is a bug with the compiler. Casting is a bad solution,
+        // however, because it subverts implicit conversions, so a better 
+        // one is needed. 
+        new (end()) T(static_cast<T>(*ptr));
+#else
+        new (end()) T(*ptr);
+#endif
+        ++m_size;
+    }
+
+    // This version of append saves a branch in the case where you know that the
+    // vector's capacity is large enough for the append to succeed.
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
+    {
+        ASSERT(size() < capacity());
+        const U* ptr = &val;
+        new (end()) T(*ptr);
+        ++m_size;
+    }
+
+    // This method should not be called append, a better name would be appendElements.
+    // It could also be eliminated entirely, and call sites could just use
+    // appendRange(val.begin(), val.end()).
+    template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
+    inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
+    {
+        append(val.begin(), val.size());
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
+    {
+        ASSERT(position <= size());
+        size_t newSize = m_size + dataSize;
+        if (newSize > capacity()) {
+            data = expandCapacity(newSize, data);
+            if (!begin())
+                return;
+        }
+        if (newSize < m_size)
+            CRASH();
+        T* spot = begin() + position;
+        TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
+        for (size_t i = 0; i < dataSize; ++i)
+            new (&spot[i]) T(data[i]);
+        m_size = newSize;
+    }
+     
+    template<typename T, size_t inlineCapacity> template<typename U>
+    inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
+    {
+        ASSERT(position <= size());
+        const U* data = &val;
+        if (size() == capacity()) {
+            data = expandCapacity(size() + 1, data);
+            if (!begin())
+                return;
+        }
+        T* spot = begin() + position;
+        TypeOperations::moveOverlapping(spot, end(), spot + 1);
+        new (spot) T(*data);
+        ++m_size;
+    }
+   
+    template<typename T, size_t inlineCapacity> template<typename U, size_t c>
+    inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
+    {
+        insert(position, val.begin(), val.size());
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
+    {
+        insert(0, data, dataSize);
+    }
+
+    template<typename T, size_t inlineCapacity> template<typename U>
+    inline void Vector<T, inlineCapacity>::prepend(const U& val)
+    {
+        insert(0, val);
+    }
+   
+    template<typename T, size_t inlineCapacity> template<typename U, size_t c>
+    inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
+    {
+        insert(0, val.begin(), val.size());
+    }
+    
+    template<typename T, size_t inlineCapacity>
+    inline void Vector<T, inlineCapacity>::remove(size_t position)
+    {
+        ASSERT(position < size());
+        T* spot = begin() + position;
+        spot->~T();
+        TypeOperations::moveOverlapping(spot + 1, end(), spot);
+        --m_size;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
+    {
+        ASSERT(position < size());
+        ASSERT(position + length <= size());
+        T* beginSpot = begin() + position;
+        T* endSpot = beginSpot + length;
+        TypeOperations::destruct(beginSpot, endSpot); 
+        TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
+        m_size -= length;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline T* Vector<T, inlineCapacity>::releaseBuffer()
+    {
+        T* buffer = m_buffer.releaseBuffer();
+        if (inlineCapacity && !buffer && m_size) {
+            // If the vector had some data, but no buffer to release,
+            // that means it was using the inline buffer. In that case,
+            // we create a brand new buffer so the caller always gets one.
+            size_t bytes = m_size * sizeof(T);
+            buffer = static_cast<T*>(fastMalloc(bytes));
+            memcpy(buffer, data(), bytes);
+        }
+        m_size = 0;
+        return buffer;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline void Vector<T, inlineCapacity>::checkConsistency()
+    {
+#if !ASSERT_DISABLED
+        for (size_t i = 0; i < size(); ++i)
+            ValueCheck<T>::checkConsistency(at(i));
+#endif
+    }
+
+    template<typename T, size_t inlineCapacity>
+    void deleteAllValues(const Vector<T, inlineCapacity>& collection)
+    {
+        typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
+        iterator end = collection.end();
+        for (iterator it = collection.begin(); it != end; ++it)
+            delete *it;
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
+    {
+        a.swap(b);
+    }
+
+    template<typename T, size_t inlineCapacity>
+    bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
+    {
+        if (a.size() != b.size())
+            return false;
+
+        return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
+    }
+
+    template<typename T, size_t inlineCapacity>
+    inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
+    {
+        return !(a == b);
+    }
+
+#if !ASSERT_DISABLED
+    template<typename T> struct ValueCheck<Vector<T> > {
+        typedef Vector<T> TraitType;
+        static void checkConsistency(const Vector<T>& v)
+        {
+            v.checkConsistency();
+        }
+    };
+#endif
+
+} // namespace WTF
+
+using WTF::Vector;
+
+#endif // WTF_Vector_h