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