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