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