Unreviewed, rolling out r215518.
[WebKit-https.git] / Source / WTF / wtf / Vector.h
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
37 #if ASAN_ENABLED
38 extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid);
39 #endif
40
41 namespace WTF {
42
43 const size_t notFound = static_cast<size_t>(-1);
44
45 template <bool needsDestruction, typename T>
46 struct VectorDestructor;
47
48 template<typename T>
49 struct VectorDestructor<false, T>
50 {
51     static void destruct(T*, T*) {}
52 };
53
54 template<typename T>
55 struct VectorDestructor<true, T>
56 {
57     static void destruct(T* begin, T* end) 
58     {
59         for (T* cur = begin; cur != end; ++cur)
60             cur->~T();
61     }
62 };
63
64 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
65 struct VectorInitializer;
66
67 template<bool ignore, typename T>
68 struct VectorInitializer<false, ignore, T>
69 {
70     static void initialize(T*, T*) {}
71 };
72
73 template<typename T>
74 struct VectorInitializer<true, false, T>
75 {
76     static void initialize(T* begin, T* end) 
77     {
78         for (T* cur = begin; cur != end; ++cur)
79             new (NotNull, cur) T;
80     }
81 };
82
83 template<typename T>
84 struct VectorInitializer<true, true, T>
85 {
86     static void initialize(T* begin, T* end) 
87     {
88         memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
89     }
90 };
91
92 template <bool canMoveWithMemcpy, typename T>
93 struct VectorMover;
94
95 template<typename T>
96 struct VectorMover<false, T>
97 {
98     static void move(T* src, T* srcEnd, T* dst)
99     {
100         while (src != srcEnd) {
101             new (NotNull, dst) T(WTFMove(*src));
102             src->~T();
103             ++dst;
104             ++src;
105         }
106     }
107     static void moveOverlapping(T* src, T* srcEnd, T* dst)
108     {
109         if (src > dst)
110             move(src, srcEnd, dst);
111         else {
112             T* dstEnd = dst + (srcEnd - src);
113             while (src != srcEnd) {
114                 --srcEnd;
115                 --dstEnd;
116                 new (NotNull, dstEnd) T(WTFMove(*srcEnd));
117                 srcEnd->~T();
118             }
119         }
120     }
121 };
122
123 template<typename T>
124 struct VectorMover<true, T>
125 {
126     static void move(const T* src, const T* srcEnd, T* dst) 
127     {
128         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
129     }
130     static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
131     {
132         memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
133     }
134 };
135
136 template <bool canCopyWithMemcpy, typename T>
137 struct VectorCopier;
138
139 template<typename T>
140 struct VectorCopier<false, T>
141 {
142     template<typename U>
143     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
144     {
145         while (src != srcEnd) {
146             new (NotNull, dst) U(*src);
147             ++dst;
148             ++src;
149         }
150     }
151 };
152
153 template<typename T>
154 struct VectorCopier<true, T>
155 {
156     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
157     {
158         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
159     }
160     template<typename U>
161     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
162     {
163         VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst);
164     }
165 };
166
167 template <bool canFillWithMemset, typename T>
168 struct VectorFiller;
169
170 template<typename T>
171 struct VectorFiller<false, T>
172 {
173     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
174     {
175         while (dst != dstEnd) {
176             new (NotNull, dst) T(val);
177             ++dst;
178         }
179     }
180 };
181
182 template<typename T>
183 struct VectorFiller<true, T>
184 {
185     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
186     {
187         static_assert(sizeof(T) == 1, "Size of type T should be equal to one!");
188 #if COMPILER(GCC_OR_CLANG) && defined(_FORTIFY_SOURCE)
189         if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst)))
190 #endif
191             memset(dst, val, dstEnd - dst);
192     }
193 };
194
195 template<bool canCompareWithMemcmp, typename T>
196 struct VectorComparer;
197
198 template<typename T>
199 struct VectorComparer<false, T>
200 {
201     static bool compare(const T* a, const T* b, size_t size)
202     {
203         for (size_t i = 0; i < size; ++i)
204             if (!(a[i] == b[i]))
205                 return false;
206         return true;
207     }
208 };
209
210 template<typename T>
211 struct VectorComparer<true, T>
212 {
213     static bool compare(const T* a, const T* b, size_t size)
214     {
215         return memcmp(a, b, sizeof(T) * size) == 0;
216     }
217 };
218
219 template<typename T>
220 struct VectorTypeOperations
221 {
222     static void destruct(T* begin, T* end)
223     {
224         VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end);
225     }
226
227     static void initialize(T* begin, T* end)
228     {
229         VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
230     }
231
232     static void move(T* src, T* srcEnd, T* dst)
233     {
234         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
235     }
236
237     static void moveOverlapping(T* src, T* srcEnd, T* dst)
238     {
239         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
240     }
241
242     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
243     {
244         VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
245     }
246
247     static void uninitializedFill(T* dst, T* dstEnd, const T& val)
248     {
249         VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
250     }
251     
252     static bool compare(const T* a, const T* b, size_t size)
253     {
254         return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
255     }
256 };
257
258 template<typename T>
259 class VectorBufferBase {
260     WTF_MAKE_NONCOPYABLE(VectorBufferBase);
261 public:
262     void allocateBuffer(size_t newCapacity)
263     {
264         ASSERT(newCapacity);
265         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
266             CRASH();
267         size_t sizeToAllocate = newCapacity * sizeof(T);
268         m_capacity = sizeToAllocate / sizeof(T);
269         m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate));
270     }
271
272     bool tryAllocateBuffer(size_t newCapacity)
273     {
274         ASSERT(newCapacity);
275         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
276             return false;
277
278         size_t sizeToAllocate = newCapacity * sizeof(T);
279         T* newBuffer;
280         if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) {
281             m_capacity = sizeToAllocate / sizeof(T);
282             m_buffer = newBuffer;
283             return true;
284         }
285         return false;
286     }
287
288     bool shouldReallocateBuffer(size_t newCapacity) const
289     {
290         return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
291     }
292
293     void reallocateBuffer(size_t newCapacity)
294     {
295         ASSERT(shouldReallocateBuffer(newCapacity));
296         if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
297             CRASH();
298         size_t sizeToAllocate = newCapacity * sizeof(T);
299         m_capacity = sizeToAllocate / sizeof(T);
300         m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate));
301     }
302
303     void deallocateBuffer(T* bufferToDeallocate)
304     {
305         if (!bufferToDeallocate)
306             return;
307         
308         if (m_buffer == bufferToDeallocate) {
309             m_buffer = 0;
310             m_capacity = 0;
311         }
312
313         fastFree(bufferToDeallocate);
314     }
315
316     T* buffer() { return m_buffer; }
317     const T* buffer() const { return m_buffer; }
318     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
319     size_t capacity() const { return m_capacity; }
320
321     MallocPtr<T> releaseBuffer()
322     {
323         T* buffer = m_buffer;
324         m_buffer = 0;
325         m_capacity = 0;
326         return adoptMallocPtr(buffer);
327     }
328
329 protected:
330     VectorBufferBase()
331         : m_buffer(0)
332         , m_capacity(0)
333         , m_size(0)
334     {
335     }
336
337     VectorBufferBase(T* buffer, size_t capacity, size_t size)
338         : m_buffer(buffer)
339         , m_capacity(capacity)
340         , m_size(size)
341     {
342     }
343
344     ~VectorBufferBase()
345     {
346         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
347     }
348
349     T* m_buffer;
350     unsigned m_capacity;
351     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
352 };
353
354 template<typename T, size_t inlineCapacity>
355 class VectorBuffer;
356
357 template<typename T>
358 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
359 private:
360     typedef VectorBufferBase<T> Base;
361 public:
362     VectorBuffer()
363     {
364     }
365
366     VectorBuffer(size_t capacity, size_t size = 0)
367     {
368         m_size = size;
369         // Calling malloc(0) might take a lock and may actually do an
370         // allocation on some systems.
371         if (capacity)
372             allocateBuffer(capacity);
373     }
374
375     ~VectorBuffer()
376     {
377         deallocateBuffer(buffer());
378     }
379     
380     void swap(VectorBuffer<T, 0>& other, size_t, size_t)
381     {
382         std::swap(m_buffer, other.m_buffer);
383         std::swap(m_capacity, other.m_capacity);
384     }
385     
386     void restoreInlineBufferIfNeeded() { }
387
388 #if ASAN_ENABLED
389     void* endOfBuffer()
390     {
391         return buffer() + capacity();
392     }
393 #endif
394
395     using Base::allocateBuffer;
396     using Base::tryAllocateBuffer;
397     using Base::shouldReallocateBuffer;
398     using Base::reallocateBuffer;
399     using Base::deallocateBuffer;
400
401     using Base::buffer;
402     using Base::capacity;
403     using Base::bufferMemoryOffset;
404
405     using Base::releaseBuffer;
406
407 protected:
408     using Base::m_size;
409
410 private:
411     using Base::m_buffer;
412     using Base::m_capacity;
413 };
414
415 template<typename T, size_t inlineCapacity>
416 class VectorBuffer : private VectorBufferBase<T> {
417     WTF_MAKE_NONCOPYABLE(VectorBuffer);
418 private:
419     typedef VectorBufferBase<T> Base;
420 public:
421     VectorBuffer()
422         : Base(inlineBuffer(), inlineCapacity, 0)
423     {
424     }
425
426     VectorBuffer(size_t capacity, size_t size = 0)
427         : Base(inlineBuffer(), inlineCapacity, size)
428     {
429         if (capacity > inlineCapacity)
430             Base::allocateBuffer(capacity);
431     }
432
433     ~VectorBuffer()
434     {
435         deallocateBuffer(buffer());
436     }
437
438     void allocateBuffer(size_t newCapacity)
439     {
440         // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
441         if (newCapacity > inlineCapacity)
442             Base::allocateBuffer(newCapacity);
443         else {
444             m_buffer = inlineBuffer();
445             m_capacity = inlineCapacity;
446         }
447     }
448
449     bool tryAllocateBuffer(size_t newCapacity)
450     {
451         if (newCapacity > inlineCapacity)
452             return Base::tryAllocateBuffer(newCapacity);
453         m_buffer = inlineBuffer();
454         m_capacity = inlineCapacity;
455         return true;
456     }
457
458     void deallocateBuffer(T* bufferToDeallocate)
459     {
460         if (bufferToDeallocate == inlineBuffer())
461             return;
462         Base::deallocateBuffer(bufferToDeallocate);
463     }
464
465     bool shouldReallocateBuffer(size_t newCapacity) const
466     {
467         // We cannot reallocate the inline buffer.
468         return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
469     }
470
471     void reallocateBuffer(size_t newCapacity)
472     {
473         ASSERT(shouldReallocateBuffer(newCapacity));
474         Base::reallocateBuffer(newCapacity);
475     }
476
477     void swap(VectorBuffer& other, size_t mySize, size_t otherSize)
478     {
479         if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
480             swapInlineBuffer(other, mySize, otherSize);
481             std::swap(m_capacity, other.m_capacity);
482         } else if (buffer() == inlineBuffer()) {
483             m_buffer = other.m_buffer;
484             other.m_buffer = other.inlineBuffer();
485             swapInlineBuffer(other, mySize, 0);
486             std::swap(m_capacity, other.m_capacity);
487         } else if (other.buffer() == other.inlineBuffer()) {
488             other.m_buffer = m_buffer;
489             m_buffer = inlineBuffer();
490             swapInlineBuffer(other, 0, otherSize);
491             std::swap(m_capacity, other.m_capacity);
492         } else {
493             std::swap(m_buffer, other.m_buffer);
494             std::swap(m_capacity, other.m_capacity);
495         }
496     }
497
498     void restoreInlineBufferIfNeeded()
499     {
500         if (m_buffer)
501             return;
502         m_buffer = inlineBuffer();
503         m_capacity = inlineCapacity;
504     }
505
506 #if ASAN_ENABLED
507     void* endOfBuffer()
508     {
509         ASSERT(buffer());
510         static_assert((offsetof(VectorBuffer, m_inlineBuffer) + sizeof(m_inlineBuffer)) % 8 == 0, "Inline buffer end needs to be on 8 byte boundary for ASan annotations to work.");
511
512         if (buffer() == inlineBuffer())
513             return reinterpret_cast<char*>(m_inlineBuffer) + sizeof(m_inlineBuffer);
514
515         return buffer() + capacity();
516     }
517 #endif
518
519     using Base::buffer;
520     using Base::capacity;
521     using Base::bufferMemoryOffset;
522
523     MallocPtr<T> releaseBuffer()
524     {
525         if (buffer() == inlineBuffer())
526             return nullptr;
527         return Base::releaseBuffer();
528     }
529
530 protected:
531     using Base::m_size;
532
533 private:
534     using Base::m_buffer;
535     using Base::m_capacity;
536     
537     void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize)
538     {
539         // FIXME: We could make swap part of VectorTypeOperations
540         // https://bugs.webkit.org/show_bug.cgi?id=128863
541         swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
542     }
543     
544     static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
545     {
546         if (left == right)
547             return;
548         
549         ASSERT(leftSize <= inlineCapacity);
550         ASSERT(rightSize <= inlineCapacity);
551         
552         size_t swapBound = std::min(leftSize, rightSize);
553         for (unsigned i = 0; i < swapBound; ++i)
554             std::swap(left[i], right[i]);
555         VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
556         VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
557     }
558
559     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
560     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
561
562 #if ASAN_ENABLED
563     // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work.
564     // FIXME: Add a redzone before the buffer to catch off by one accesses. We don't need a guard after, because the buffer is the last member variable.
565     static const size_t asanInlineBufferAlignment = std::alignment_of<T>::value >= 8 ? std::alignment_of<T>::value : 8;
566     static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T);
567     typename std::aligned_storage<sizeof(T), asanInlineBufferAlignment>::type m_inlineBuffer[asanAdjustedInlineCapacity];
568 #else
569     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
570 #endif
571 };
572
573 struct UnsafeVectorOverflow {
574     static NO_RETURN_DUE_TO_ASSERT void overflowed()
575     {
576         ASSERT_NOT_REACHED();
577     }
578 };
579
580 template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow, size_t minCapacity = 16>
581 class Vector : private VectorBuffer<T, inlineCapacity> {
582     WTF_MAKE_FAST_ALLOCATED;
583 private:
584     typedef VectorBuffer<T, inlineCapacity> Base;
585     typedef VectorTypeOperations<T> TypeOperations;
586
587 public:
588     typedef T ValueType;
589
590     typedef T* iterator;
591     typedef const T* const_iterator;
592     typedef std::reverse_iterator<iterator> reverse_iterator;
593     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
594
595     Vector()
596     {
597     }
598
599     // Unlike in std::vector, this constructor does not initialize POD types.
600     explicit Vector(size_t size)
601         : Base(size, size)
602     {
603         asanSetInitialBufferSizeTo(size);
604
605         if (begin())
606             TypeOperations::initialize(begin(), end());
607     }
608
609     Vector(size_t size, const T& val)
610         : Base(size, size)
611     {
612         asanSetInitialBufferSizeTo(size);
613
614         if (begin())
615             TypeOperations::uninitializedFill(begin(), end(), val);
616     }
617
618     Vector(std::initializer_list<T> initializerList)
619     {
620         reserveInitialCapacity(initializerList.size());
621
622         asanSetInitialBufferSizeTo(initializerList.size());
623
624         for (const auto& element : initializerList)
625             uncheckedAppend(element);
626     }
627
628     ~Vector()
629     {
630         if (m_size)
631             TypeOperations::destruct(begin(), end());
632
633         asanSetBufferSizeToFullCapacity(0);
634     }
635
636     Vector(const Vector&);
637     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
638     explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
639
640     Vector& operator=(const Vector&);
641     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
642     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
643
644     Vector(Vector&&);
645     Vector& operator=(Vector&&);
646
647     size_t size() const { return m_size; }
648     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
649     size_t capacity() const { return Base::capacity(); }
650     bool isEmpty() const { return !size(); }
651
652     T& at(size_t i)
653     {
654         if (UNLIKELY(i >= size()))
655             OverflowHandler::overflowed();
656         return Base::buffer()[i];
657     }
658     const T& at(size_t i) const 
659     {
660         if (UNLIKELY(i >= size()))
661             OverflowHandler::overflowed();
662         return Base::buffer()[i];
663     }
664     T& at(Checked<size_t> i)
665     {
666         RELEASE_ASSERT(i < size());
667         return Base::buffer()[i];
668     }
669     const T& at(Checked<size_t> i) const
670     {
671         RELEASE_ASSERT(i < size());
672         return Base::buffer()[i];
673     }
674
675     T& operator[](size_t i) { return at(i); }
676     const T& operator[](size_t i) const { return at(i); }
677     T& operator[](Checked<size_t> i) { return at(i); }
678     const T& operator[](Checked<size_t> i) const { return at(i); }
679
680     T* data() { return Base::buffer(); }
681     const T* data() const { return Base::buffer(); }
682     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
683
684     iterator begin() { return data(); }
685     iterator end() { return begin() + m_size; }
686     const_iterator begin() const { return data(); }
687     const_iterator end() const { return begin() + m_size; }
688
689     reverse_iterator rbegin() { return reverse_iterator(end()); }
690     reverse_iterator rend() { return reverse_iterator(begin()); }
691     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
692     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
693
694     T& first() { return at(0); }
695     const T& first() const { return at(0); }
696     T& last() { return at(size() - 1); }
697     const T& last() const { return at(size() - 1); }
698     
699     T takeLast()
700     {
701         T result = WTFMove(last());
702         removeLast();
703         return result;
704     }
705     
706     template<typename U> bool contains(const U&) const;
707     template<typename U> size_t find(const U&) const;
708     template<typename U> size_t reverseFind(const U&) const;
709     
710     template<typename U> bool appendIfNotContains(const U&);
711
712     void shrink(size_t size);
713     void grow(size_t size);
714     void resize(size_t size);
715     void resizeToFit(size_t size);
716     void reserveCapacity(size_t newCapacity);
717     bool tryReserveCapacity(size_t newCapacity);
718     void reserveInitialCapacity(size_t initialCapacity);
719     void shrinkCapacity(size_t newCapacity);
720     void shrinkToFit() { shrinkCapacity(size()); }
721
722     void clear() { shrinkCapacity(0); }
723
724     void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
725     template<typename U> void append(U&&);
726     template<typename... Args> void constructAndAppend(Args&&...);
727     template<typename... Args> bool tryConstructAndAppend(Args&&...);
728
729     void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
730     template<typename U> void uncheckedAppend(U&&);
731
732     template<typename U> void append(const U*, size_t);
733     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
734     template<typename U> bool tryAppend(const U*, size_t);
735
736     template<typename U> void insert(size_t position, const U*, size_t);
737     template<typename U> void insert(size_t position, U&&);
738     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
739
740     void remove(size_t position);
741     void remove(size_t position, size_t length);
742     template<typename U> bool removeFirst(const U&);
743     template<typename MatchFunction> bool removeFirstMatching(const MatchFunction&);
744     template<typename U> unsigned removeAll(const U&);
745     template<typename MatchFunction> unsigned removeAllMatching(const MatchFunction&);
746
747     void removeLast() 
748     {
749         if (UNLIKELY(isEmpty()))
750             OverflowHandler::overflowed();
751         shrink(size() - 1); 
752     }
753
754     void fill(const T&, size_t);
755     void fill(const T& val) { fill(val, size()); }
756
757     template<typename Iterator> void appendRange(Iterator start, Iterator end);
758
759     MallocPtr<T> releaseBuffer();
760
761     void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
762     {
763 #if ASAN_ENABLED
764         if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
765             return;
766 #endif
767
768         // Make it possible to copy inline buffers.
769         asanSetBufferSizeToFullCapacity();
770         other.asanSetBufferSizeToFullCapacity();
771
772         Base::swap(other, m_size, other.m_size);
773         std::swap(m_size, other.m_size);
774
775         asanSetInitialBufferSizeTo(m_size);
776         other.asanSetInitialBufferSizeTo(other.m_size);
777     }
778
779     void reverse();
780
781     void checkConsistency();
782
783 private:
784     void expandCapacity(size_t newMinCapacity);
785     T* expandCapacity(size_t newMinCapacity, T*);
786     bool tryExpandCapacity(size_t newMinCapacity);
787     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
788     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
789     template<typename U> void appendSlowCase(U&&);
790     template<typename... Args> void constructAndAppendSlowCase(Args&&...);
791     template<typename... Args> bool tryConstructAndAppendSlowCase(Args&&...);
792
793     void asanSetInitialBufferSizeTo(size_t);
794     void asanSetBufferSizeToFullCapacity(size_t);
795     void asanSetBufferSizeToFullCapacity() { asanSetBufferSizeToFullCapacity(size()); }
796
797     void asanBufferSizeWillChangeTo(size_t);
798
799     using Base::m_size;
800     using Base::buffer;
801     using Base::capacity;
802     using Base::swap;
803     using Base::allocateBuffer;
804     using Base::deallocateBuffer;
805     using Base::tryAllocateBuffer;
806     using Base::shouldReallocateBuffer;
807     using Base::reallocateBuffer;
808     using Base::restoreInlineBufferIfNeeded;
809     using Base::releaseBuffer;
810 #if ASAN_ENABLED
811     using Base::endOfBuffer;
812 #endif
813 };
814
815 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
816 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
817     : Base(other.capacity(), other.size())
818 {
819     asanSetInitialBufferSizeTo(other.size());
820
821     if (begin())
822         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
823 }
824
825 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
826 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
827 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
828     : Base(other.capacity(), other.size())
829 {
830     asanSetInitialBufferSizeTo(other.size());
831
832     if (begin())
833         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
834 }
835
836 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
837 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
838 {
839     if (&other == this)
840         return *this;
841     
842     if (size() > other.size())
843         shrink(other.size());
844     else if (other.size() > capacity()) {
845         clear();
846         reserveCapacity(other.size());
847         ASSERT(begin());
848     }
849
850     asanBufferSizeWillChangeTo(other.size());
851
852     std::copy(other.begin(), other.begin() + size(), begin());
853     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
854     m_size = other.size();
855
856     return *this;
857 }
858
859 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
860
861 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
862 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
863 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
864 {
865     // If the inline capacities match, we should call the more specific
866     // template.  If the inline capacities don't match, the two objects
867     // shouldn't be allocated the same address.
868     ASSERT(!typelessPointersAreEqual(&other, this));
869
870     if (size() > other.size())
871         shrink(other.size());
872     else if (other.size() > capacity()) {
873         clear();
874         reserveCapacity(other.size());
875         ASSERT(begin());
876     }
877     
878     asanBufferSizeWillChangeTo(other.size());
879
880     std::copy(other.begin(), other.begin() + size(), begin());
881     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
882     m_size = other.size();
883
884     return *this;
885 }
886
887 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
888 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
889 {
890     swap(other);
891 }
892
893 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
894 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
895 {
896     swap(other);
897     return *this;
898 }
899
900 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
901 template<typename U>
902 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
903 {
904     return find(value) != notFound;
905 }
906
907 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
908 template<typename U>
909 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
910 {
911     for (size_t i = 0; i < size(); ++i) {
912         if (at(i) == value)
913             return i;
914     }
915     return notFound;
916 }
917
918 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
919 template<typename U>
920 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
921 {
922     for (size_t i = 1; i <= size(); ++i) {
923         const size_t index = size() - i;
924         if (at(index) == value)
925             return index;
926     }
927     return notFound;
928 }
929
930 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
931 template<typename U>
932 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendIfNotContains(const U& value)
933 {
934     if (contains(value))
935         return false;
936     append(value);
937     return true;
938 }
939
940 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
941 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
942 {
943     if (size() > newSize)
944         shrink(newSize);
945     else if (newSize > capacity()) {
946         clear();
947         reserveCapacity(newSize);
948         ASSERT(begin());
949     }
950
951     asanBufferSizeWillChangeTo(newSize);
952
953     std::fill(begin(), end(), val);
954     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
955     m_size = newSize;
956 }
957
958 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
959 template<typename Iterator>
960 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
961 {
962     for (Iterator it = start; it != end; ++it)
963         append(*it);
964 }
965
966 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
967 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
968 {
969     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
970 }
971
972 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
973 T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
974 {
975     if (ptr < begin() || ptr >= end()) {
976         expandCapacity(newMinCapacity);
977         return ptr;
978     }
979     size_t index = ptr - begin();
980     expandCapacity(newMinCapacity);
981     return begin() + index;
982 }
983
984 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
985 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
986 {
987     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
988 }
989
990 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
991 const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
992 {
993     if (ptr < begin() || ptr >= end()) {
994         if (!tryExpandCapacity(newMinCapacity))
995             return 0;
996         return ptr;
997     }
998     size_t index = ptr - begin();
999     if (!tryExpandCapacity(newMinCapacity))
1000         return 0;
1001     return begin() + index;
1002 }
1003
1004 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1005 inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
1006 {
1007     expandCapacity(newMinCapacity);
1008     return ptr;
1009 }
1010
1011 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1012 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
1013 {
1014     if (size <= m_size) {
1015         TypeOperations::destruct(begin() + size, end());
1016         asanBufferSizeWillChangeTo(size);
1017     } else {
1018         if (size > capacity())
1019             expandCapacity(size);
1020         asanBufferSizeWillChangeTo(size);
1021         if (begin())
1022             TypeOperations::initialize(end(), begin() + size);
1023     }
1024     
1025     m_size = size;
1026 }
1027
1028 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1029 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
1030 {
1031     reserveCapacity(size);
1032     resize(size);
1033 }
1034
1035 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1036 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
1037 {
1038     ASSERT(size <= m_size);
1039     TypeOperations::destruct(begin() + size, end());
1040     asanBufferSizeWillChangeTo(size);
1041     m_size = size;
1042 }
1043
1044 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1045 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
1046 {
1047     ASSERT(size >= m_size);
1048     if (size > capacity())
1049         expandCapacity(size);
1050     asanBufferSizeWillChangeTo(size);
1051     if (begin())
1052         TypeOperations::initialize(end(), begin() + size);
1053     m_size = size;
1054 }
1055
1056 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1057 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
1058 {
1059 #if ASAN_ENABLED
1060     if (!buffer())
1061         return;
1062
1063     // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1064     // when accessing elements in [end(), endOfBuffer()) range.
1065     // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1066     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1067 #else
1068     UNUSED_PARAM(size);
1069 #endif
1070 }
1071
1072 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1073 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity(size_t size)
1074 {
1075 #if ASAN_ENABLED
1076     if (!buffer())
1077         return;
1078
1079     // ASan requires that the annotation is returned to its initial state before deallocation.
1080     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size, endOfBuffer());
1081 #else
1082     UNUSED_PARAM(size);
1083 #endif
1084 }
1085
1086 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1087 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
1088 {
1089 #if ASAN_ENABLED
1090     if (!buffer())
1091         return;
1092
1093     // Change allowed range.
1094     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1095 #else
1096     UNUSED_PARAM(newSize);
1097 #endif
1098 }
1099
1100 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1101 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
1102 {
1103     if (newCapacity <= capacity())
1104         return;
1105     T* oldBuffer = begin();
1106     T* oldEnd = end();
1107
1108     asanSetBufferSizeToFullCapacity();
1109
1110     Base::allocateBuffer(newCapacity);
1111     ASSERT(begin());
1112
1113     asanSetInitialBufferSizeTo(size());
1114
1115     TypeOperations::move(oldBuffer, oldEnd, begin());
1116     Base::deallocateBuffer(oldBuffer);
1117 }
1118
1119 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1120 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
1121 {
1122     if (newCapacity <= capacity())
1123         return true;
1124     T* oldBuffer = begin();
1125     T* oldEnd = end();
1126
1127     asanSetBufferSizeToFullCapacity();
1128
1129     if (!Base::tryAllocateBuffer(newCapacity)) {
1130         asanSetInitialBufferSizeTo(size());
1131         return false;
1132     }
1133     ASSERT(begin());
1134
1135     asanSetInitialBufferSizeTo(size());
1136
1137     TypeOperations::move(oldBuffer, oldEnd, begin());
1138     Base::deallocateBuffer(oldBuffer);
1139     return true;
1140 }
1141
1142 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1143 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
1144 {
1145     ASSERT(!m_size);
1146     ASSERT(capacity() == inlineCapacity);
1147     if (initialCapacity > inlineCapacity)
1148         Base::allocateBuffer(initialCapacity);
1149 }
1150
1151 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1152 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
1153 {
1154     if (newCapacity >= capacity())
1155         return;
1156
1157     if (newCapacity < size()) 
1158         shrink(newCapacity);
1159
1160     asanSetBufferSizeToFullCapacity();
1161
1162     T* oldBuffer = begin();
1163     if (newCapacity > 0) {
1164         if (Base::shouldReallocateBuffer(newCapacity)) {
1165             Base::reallocateBuffer(newCapacity);
1166             asanSetInitialBufferSizeTo(size());
1167             return;
1168         }
1169
1170         T* oldEnd = end();
1171         Base::allocateBuffer(newCapacity);
1172         if (begin() != oldBuffer)
1173             TypeOperations::move(oldBuffer, oldEnd, begin());
1174     }
1175
1176     Base::deallocateBuffer(oldBuffer);
1177     Base::restoreInlineBufferIfNeeded();
1178
1179     asanSetInitialBufferSizeTo(size());
1180 }
1181
1182 // Templatizing these is better than just letting the conversion happen implicitly,
1183 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1184 // without refcount thrash.
1185 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1186 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
1187 {
1188     size_t newSize = m_size + dataSize;
1189     if (newSize > capacity()) {
1190         data = expandCapacity(newSize, data);
1191         ASSERT(begin());
1192     }
1193     if (newSize < m_size)
1194         CRASH();
1195     asanBufferSizeWillChangeTo(newSize);
1196     T* dest = end();
1197     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1198     m_size = newSize;
1199 }
1200
1201 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1202 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
1203 {
1204     size_t newSize = m_size + dataSize;
1205     if (newSize > capacity()) {
1206         data = tryExpandCapacity(newSize, data);
1207         if (!data)
1208             return false;
1209         ASSERT(begin());
1210     }
1211     if (newSize < m_size)
1212         return false;
1213     asanBufferSizeWillChangeTo(newSize);
1214     T* dest = end();
1215     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1216     m_size = newSize;
1217     return true;
1218 }
1219
1220 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1221 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
1222 {
1223     if (size() != capacity()) {
1224         asanBufferSizeWillChangeTo(m_size + 1);
1225         new (NotNull, end()) T(std::forward<U>(value));
1226         ++m_size;
1227         return;
1228     }
1229
1230     appendSlowCase(std::forward<U>(value));
1231 }
1232
1233 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
1234 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend(Args&&... args)
1235 {
1236     if (size() != capacity()) {
1237         asanBufferSizeWillChangeTo(m_size + 1);
1238         new (NotNull, end()) T(std::forward<Args>(args)...);
1239         ++m_size;
1240         return;
1241     }
1242
1243     constructAndAppendSlowCase(std::forward<Args>(args)...);
1244 }
1245
1246 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
1247 ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppend(Args&&... args)
1248 {
1249     if (size() != capacity()) {
1250         asanBufferSizeWillChangeTo(m_size + 1);
1251         new (NotNull, end()) T(std::forward<Args>(args)...);
1252         ++m_size;
1253         return true;
1254     }
1255     
1256     return tryConstructAndAppendSlowCase(std::forward<Args>(args)...);
1257 }
1258
1259 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1260 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
1261 {
1262     ASSERT(size() == capacity());
1263
1264     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1265     ptr = expandCapacity(size() + 1, ptr);
1266     ASSERT(begin());
1267
1268     asanBufferSizeWillChangeTo(m_size + 1);
1269     new (NotNull, end()) T(std::forward<U>(*ptr));
1270     ++m_size;
1271 }
1272
1273 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
1274 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppendSlowCase(Args&&... args)
1275 {
1276     ASSERT(size() == capacity());
1277
1278     expandCapacity(size() + 1);
1279     ASSERT(begin());
1280
1281     asanBufferSizeWillChangeTo(m_size + 1);
1282     new (NotNull, end()) T(std::forward<Args>(args)...);
1283     ++m_size;
1284 }
1285
1286 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
1287 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppendSlowCase(Args&&... args)
1288 {
1289     ASSERT(size() == capacity());
1290     
1291     if (UNLIKELY(!tryExpandCapacity(size() + 1)))
1292         return false;
1293     ASSERT(begin());
1294     
1295     asanBufferSizeWillChangeTo(m_size + 1);
1296     new (NotNull, end()) T(std::forward<Args>(args)...);
1297     ++m_size;
1298     return true;
1299 }
1300
1301 // This version of append saves a branch in the case where you know that the
1302 // vector's capacity is large enough for the append to succeed.
1303
1304 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1305 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
1306 {
1307     ASSERT(size() < capacity());
1308
1309     asanBufferSizeWillChangeTo(m_size + 1);
1310
1311     auto ptr = std::addressof(value);
1312     new (NotNull, end()) T(std::forward<U>(*ptr));
1313     ++m_size;
1314 }
1315
1316 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t otherCapacity>
1317 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1318 {
1319     append(val.begin(), val.size());
1320 }
1321
1322 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1323 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
1324 {
1325     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1326     size_t newSize = m_size + dataSize;
1327     if (newSize > capacity()) {
1328         data = expandCapacity(newSize, data);
1329         ASSERT(begin());
1330     }
1331     if (newSize < m_size)
1332         CRASH();
1333     asanBufferSizeWillChangeTo(newSize);
1334     T* spot = begin() + position;
1335     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1336     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1337     m_size = newSize;
1338 }
1339  
1340 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1341 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
1342 {
1343     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1344
1345     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1346     if (size() == capacity()) {
1347         ptr = expandCapacity(size() + 1, ptr);
1348         ASSERT(begin());
1349     }
1350
1351     asanBufferSizeWillChangeTo(m_size + 1);
1352
1353     T* spot = begin() + position;
1354     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1355     new (NotNull, spot) T(std::forward<U>(*ptr));
1356     ++m_size;
1357 }
1358
1359 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t c>
1360 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
1361 {
1362     insert(position, val.begin(), val.size());
1363 }
1364
1365 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1366 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
1367 {
1368     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1369     T* spot = begin() + position;
1370     spot->~T();
1371     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1372     asanBufferSizeWillChangeTo(m_size - 1);
1373     --m_size;
1374 }
1375
1376 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1377 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
1378 {
1379     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1380     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1381     T* beginSpot = begin() + position;
1382     T* endSpot = beginSpot + length;
1383     TypeOperations::destruct(beginSpot, endSpot); 
1384     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1385     asanBufferSizeWillChangeTo(m_size - length);
1386     m_size -= length;
1387 }
1388
1389 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1390 template<typename U>
1391 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
1392 {
1393     return removeFirstMatching([&value] (const T& current) {
1394         return current == value;
1395     });
1396 }
1397
1398 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1399 template<typename MatchFunction>
1400 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches)
1401 {
1402     for (size_t i = 0; i < size(); ++i) {
1403         if (matches(at(i))) {
1404             remove(i);
1405             return true;
1406         }
1407     }
1408     return false;
1409 }
1410
1411 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1412 template<typename U>
1413 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
1414 {
1415     return removeAllMatching([&value] (const T& current) {
1416         return current == value;
1417     });
1418 }
1419
1420 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1421 template<typename MatchFunction>
1422 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches)
1423 {
1424     iterator holeBegin = end();
1425     iterator holeEnd = end();
1426     unsigned matchCount = 0;
1427     for (auto it = begin(), itEnd = end(); it != itEnd; ++it) {
1428         if (matches(*it)) {
1429             if (holeBegin == end())
1430                 holeBegin = it;
1431             else if (holeEnd != it) {
1432                 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1433                 holeBegin += it - holeEnd;
1434             }
1435             holeEnd = it + 1;
1436             it->~T();
1437             ++matchCount;
1438         }
1439     }
1440     if (holeEnd != end())
1441         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1442     asanBufferSizeWillChangeTo(m_size - matchCount);
1443     m_size -= matchCount;
1444     return matchCount;
1445 }
1446
1447 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1448 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
1449 {
1450     for (size_t i = 0; i < m_size / 2; ++i)
1451         std::swap(at(i), at(m_size - 1 - i));
1452 }
1453
1454 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1455 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
1456 {
1457     // FIXME: Find a way to preserve annotations on the returned buffer.
1458     // ASan requires that all annotations are removed before deallocation,
1459     // and MallocPtr doesn't implement that.
1460     asanSetBufferSizeToFullCapacity();
1461
1462     auto buffer = Base::releaseBuffer();
1463     if (inlineCapacity && !buffer && m_size) {
1464         // If the vector had some data, but no buffer to release,
1465         // that means it was using the inline buffer. In that case,
1466         // we create a brand new buffer so the caller always gets one.
1467         size_t bytes = m_size * sizeof(T);
1468         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1469         memcpy(buffer.get(), data(), bytes);
1470     }
1471     m_size = 0;
1472     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1473     return buffer;
1474 }
1475
1476 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1477 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
1478 {
1479 #if !ASSERT_DISABLED
1480     for (size_t i = 0; i < size(); ++i)
1481         ValueCheck<T>::checkConsistency(at(i));
1482 #endif
1483 }
1484
1485 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1486 inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1487 {
1488     a.swap(b);
1489 }
1490
1491 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1492 bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1493 {
1494     if (a.size() != b.size())
1495         return false;
1496
1497     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1498 }
1499
1500 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1501 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1502 {
1503     return !(a == b);
1504 }
1505
1506 #if !ASSERT_DISABLED
1507 template<typename T> struct ValueCheck<Vector<T>> {
1508     typedef Vector<T> TraitType;
1509     static void checkConsistency(const Vector<T>& v)
1510     {
1511         v.checkConsistency();
1512     }
1513 };
1514 #endif
1515
1516 template<typename VectorType, typename Func>
1517 size_t removeRepeatedElements(VectorType& vector, const Func& func)
1518 {
1519     auto end = std::unique(vector.begin(), vector.end(), func);
1520     size_t newSize = end - vector.begin();
1521     vector.resize(newSize);
1522     return newSize;
1523 }
1524
1525 template<typename VectorType>
1526 size_t removeRepeatedElements(VectorType& vector)
1527 {
1528     return removeRepeatedElements(vector, [] (auto& a, auto& b) { return a == b; });
1529 }
1530
1531 } // namespace WTF
1532
1533 using WTF::Vector;
1534 using WTF::UnsafeVectorOverflow;
1535 using WTF::notFound;
1536 using WTF::removeRepeatedElements;
1537
1538 #endif // WTF_Vector_h