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