/*

 *  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(); }