Replace WTF::move with WTFMove
[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         
542         if (std::is_pod<T>::value)
543             std::swap(m_inlineBuffer, other.m_inlineBuffer);
544         else
545             swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
546     }
547     
548     static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
549     {
550         if (left == right)
551             return;
552         
553         ASSERT(leftSize <= inlineCapacity);
554         ASSERT(rightSize <= inlineCapacity);
555         
556         size_t swapBound = std::min(leftSize, rightSize);
557         for (unsigned i = 0; i < swapBound; ++i)
558             std::swap(left[i], right[i]);
559         VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
560         VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
561     }
562
563     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
564     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
565
566 #if ASAN_ENABLED
567     // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work.
568     // 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.
569     static const size_t asanInlineBufferAlignment = std::alignment_of<T>::value >= 8 ? std::alignment_of<T>::value : 8;
570     static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T);
571     typename std::aligned_storage<sizeof(T), asanInlineBufferAlignment>::type m_inlineBuffer[asanAdjustedInlineCapacity];
572 #else
573     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
574 #endif
575 };
576
577 struct UnsafeVectorOverflow {
578     static NO_RETURN_DUE_TO_ASSERT void overflowed()
579     {
580         ASSERT_NOT_REACHED();
581     }
582 };
583
584 template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow, size_t minCapacity = 16>
585 class Vector : private VectorBuffer<T, inlineCapacity> {
586     WTF_MAKE_FAST_ALLOCATED;
587 private:
588     typedef VectorBuffer<T, inlineCapacity> Base;
589     typedef VectorTypeOperations<T> TypeOperations;
590
591 public:
592     typedef T ValueType;
593
594     typedef T* iterator;
595     typedef const T* const_iterator;
596     typedef std::reverse_iterator<iterator> reverse_iterator;
597     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
598
599     Vector()
600     {
601     }
602
603     // Unlike in std::vector, this constructor does not initialize POD types.
604     explicit Vector(size_t size)
605         : Base(size, size)
606     {
607         asanSetInitialBufferSizeTo(size);
608
609         if (begin())
610             TypeOperations::initialize(begin(), end());
611     }
612
613     Vector(size_t size, const T& val)
614         : Base(size, size)
615     {
616         asanSetInitialBufferSizeTo(size);
617
618         if (begin())
619             TypeOperations::uninitializedFill(begin(), end(), val);
620     }
621
622     Vector(std::initializer_list<T> initializerList)
623     {
624         reserveInitialCapacity(initializerList.size());
625
626         asanSetInitialBufferSizeTo(initializerList.size());
627
628         for (const auto& element : initializerList)
629             uncheckedAppend(element);
630     }
631
632     ~Vector()
633     {
634         if (m_size)
635             shrink(0);
636
637         asanSetBufferSizeToFullCapacity();
638     }
639
640     Vector(const Vector&);
641     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
642     explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
643
644     Vector& operator=(const Vector&);
645     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
646     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
647
648     Vector(Vector&&);
649     Vector& operator=(Vector&&);
650
651     size_t size() const { return m_size; }
652     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
653     size_t capacity() const { return Base::capacity(); }
654     bool isEmpty() const { return !size(); }
655
656     T& at(size_t i)
657     {
658         if (UNLIKELY(i >= size()))
659             OverflowHandler::overflowed();
660         return Base::buffer()[i];
661     }
662     const T& at(size_t i) const 
663     {
664         if (UNLIKELY(i >= size()))
665             OverflowHandler::overflowed();
666         return Base::buffer()[i];
667     }
668     T& at(Checked<size_t> i)
669     {
670         RELEASE_ASSERT(i < size());
671         return Base::buffer()[i];
672     }
673     const T& at(Checked<size_t> i) const
674     {
675         RELEASE_ASSERT(i < size());
676         return Base::buffer()[i];
677     }
678
679     T& operator[](size_t i) { return at(i); }
680     const T& operator[](size_t i) const { return at(i); }
681     T& operator[](Checked<size_t> i) { return at(i); }
682     const T& operator[](Checked<size_t> i) const { return at(i); }
683
684     T* data() { return Base::buffer(); }
685     const T* data() const { return Base::buffer(); }
686     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
687
688     iterator begin() { return data(); }
689     iterator end() { return begin() + m_size; }
690     const_iterator begin() const { return data(); }
691     const_iterator end() const { return begin() + m_size; }
692
693     reverse_iterator rbegin() { return reverse_iterator(end()); }
694     reverse_iterator rend() { return reverse_iterator(begin()); }
695     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
696     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
697
698     T& first() { return at(0); }
699     const T& first() const { return at(0); }
700     T& last() { return at(size() - 1); }
701     const T& last() const { return at(size() - 1); }
702     
703     T takeLast()
704     {
705         T result = WTFMove(last());
706         removeLast();
707         return result;
708     }
709     
710     template<typename U> bool contains(const U&) const;
711     template<typename U> size_t find(const U&) const;
712     template<typename U> size_t reverseFind(const U&) const;
713
714     void shrink(size_t size);
715     void grow(size_t size);
716     void resize(size_t size);
717     void resizeToFit(size_t size);
718     void reserveCapacity(size_t newCapacity);
719     bool tryReserveCapacity(size_t newCapacity);
720     void reserveInitialCapacity(size_t initialCapacity);
721     void shrinkCapacity(size_t newCapacity);
722     void shrinkToFit() { shrinkCapacity(size()); }
723
724     void clear() { shrinkCapacity(0); }
725
726     void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
727     template<typename U> void append(U&&);
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
791     void asanSetInitialBufferSizeTo(size_t);
792     void asanSetBufferSizeToFullCapacity();
793     void asanBufferSizeWillChangeTo(size_t);
794
795     using Base::m_size;
796     using Base::buffer;
797     using Base::capacity;
798     using Base::swap;
799     using Base::allocateBuffer;
800     using Base::deallocateBuffer;
801     using Base::tryAllocateBuffer;
802     using Base::shouldReallocateBuffer;
803     using Base::reallocateBuffer;
804     using Base::restoreInlineBufferIfNeeded;
805     using Base::releaseBuffer;
806 #if ASAN_ENABLED
807     using Base::endOfBuffer;
808 #endif
809 };
810
811 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
812 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
813     : Base(other.capacity(), other.size())
814 {
815     asanSetInitialBufferSizeTo(other.size());
816
817     if (begin())
818         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
819 }
820
821 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
822 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
823 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
824     : Base(other.capacity(), other.size())
825 {
826     asanSetInitialBufferSizeTo(other.size());
827
828     if (begin())
829         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
830 }
831
832 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
833 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
834 {
835     if (&other == this)
836         return *this;
837     
838     if (size() > other.size())
839         shrink(other.size());
840     else if (other.size() > capacity()) {
841         clear();
842         reserveCapacity(other.size());
843         ASSERT(begin());
844     }
845
846     asanBufferSizeWillChangeTo(other.size());
847
848     std::copy(other.begin(), other.begin() + size(), begin());
849     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
850     m_size = other.size();
851
852     return *this;
853 }
854
855 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
856
857 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
858 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
859 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
860 {
861     // If the inline capacities match, we should call the more specific
862     // template.  If the inline capacities don't match, the two objects
863     // shouldn't be allocated the same address.
864     ASSERT(!typelessPointersAreEqual(&other, this));
865
866     if (size() > other.size())
867         shrink(other.size());
868     else if (other.size() > capacity()) {
869         clear();
870         reserveCapacity(other.size());
871         ASSERT(begin());
872     }
873     
874     asanBufferSizeWillChangeTo(other.size());
875
876     std::copy(other.begin(), other.begin() + size(), begin());
877     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
878     m_size = other.size();
879
880     return *this;
881 }
882
883 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
884 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
885 {
886     swap(other);
887 }
888
889 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
890 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
891 {
892     swap(other);
893     return *this;
894 }
895
896 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
897 template<typename U>
898 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
899 {
900     return find(value) != notFound;
901 }
902
903 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
904 template<typename U>
905 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
906 {
907     for (size_t i = 0; i < size(); ++i) {
908         if (at(i) == value)
909             return i;
910     }
911     return notFound;
912 }
913
914 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
915 template<typename U>
916 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
917 {
918     for (size_t i = 1; i <= size(); ++i) {
919         const size_t index = size() - i;
920         if (at(index) == value)
921             return index;
922     }
923     return notFound;
924 }
925
926 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
927 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
928 {
929     if (size() > newSize)
930         shrink(newSize);
931     else if (newSize > capacity()) {
932         clear();
933         reserveCapacity(newSize);
934         ASSERT(begin());
935     }
936
937     asanBufferSizeWillChangeTo(newSize);
938
939     std::fill(begin(), end(), val);
940     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
941     m_size = newSize;
942 }
943
944 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
945 template<typename Iterator>
946 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
947 {
948     for (Iterator it = start; it != end; ++it)
949         append(*it);
950 }
951
952 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
953 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
954 {
955     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
956 }
957
958 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
959 T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
960 {
961     if (ptr < begin() || ptr >= end()) {
962         expandCapacity(newMinCapacity);
963         return ptr;
964     }
965     size_t index = ptr - begin();
966     expandCapacity(newMinCapacity);
967     return begin() + index;
968 }
969
970 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
971 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
972 {
973     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
974 }
975
976 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
977 const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
978 {
979     if (ptr < begin() || ptr >= end()) {
980         if (!tryExpandCapacity(newMinCapacity))
981             return 0;
982         return ptr;
983     }
984     size_t index = ptr - begin();
985     if (!tryExpandCapacity(newMinCapacity))
986         return 0;
987     return begin() + index;
988 }
989
990 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
991 inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
992 {
993     expandCapacity(newMinCapacity);
994     return ptr;
995 }
996
997 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
998 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
999 {
1000     if (size <= m_size) {
1001         TypeOperations::destruct(begin() + size, end());
1002         asanBufferSizeWillChangeTo(size);
1003     } else {
1004         if (size > capacity())
1005             expandCapacity(size);
1006         asanBufferSizeWillChangeTo(size);
1007         if (begin())
1008             TypeOperations::initialize(end(), begin() + size);
1009     }
1010     
1011     m_size = size;
1012 }
1013
1014 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1015 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
1016 {
1017     reserveCapacity(size);
1018     resize(size);
1019 }
1020
1021 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1022 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
1023 {
1024     ASSERT(size <= m_size);
1025     TypeOperations::destruct(begin() + size, end());
1026     asanBufferSizeWillChangeTo(size);
1027     m_size = size;
1028 }
1029
1030 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1031 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
1032 {
1033     ASSERT(size >= m_size);
1034     if (size > capacity())
1035         expandCapacity(size);
1036     asanBufferSizeWillChangeTo(size);
1037     if (begin())
1038         TypeOperations::initialize(end(), begin() + size);
1039     m_size = size;
1040 }
1041
1042 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1043 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
1044 {
1045 #if ASAN_ENABLED
1046     if (!buffer())
1047         return;
1048
1049     // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1050     // when accessing elements in [end(), endOfBuffer()) range.
1051     // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1052     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1053 #else
1054     UNUSED_PARAM(size);
1055 #endif
1056 }
1057
1058 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1059 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity()
1060 {
1061 #if ASAN_ENABLED
1062     if (!buffer())
1063         return;
1064
1065     // ASan requires that the annotation is returned to its initial state before deallocation.
1066     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), endOfBuffer());
1067 #endif
1068 }
1069
1070 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1071 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
1072 {
1073 #if ASAN_ENABLED
1074     if (!buffer())
1075         return;
1076
1077     // Change allowed range.
1078     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1079 #else
1080     UNUSED_PARAM(newSize);
1081 #endif
1082 }
1083
1084 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1085 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
1086 {
1087     if (newCapacity <= capacity())
1088         return;
1089     T* oldBuffer = begin();
1090     T* oldEnd = end();
1091
1092     asanSetBufferSizeToFullCapacity();
1093
1094     Base::allocateBuffer(newCapacity);
1095     ASSERT(begin());
1096
1097     asanSetInitialBufferSizeTo(size());
1098
1099     TypeOperations::move(oldBuffer, oldEnd, begin());
1100     Base::deallocateBuffer(oldBuffer);
1101 }
1102
1103 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1104 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
1105 {
1106     if (newCapacity <= capacity())
1107         return true;
1108     T* oldBuffer = begin();
1109     T* oldEnd = end();
1110
1111     asanSetBufferSizeToFullCapacity();
1112
1113     if (!Base::tryAllocateBuffer(newCapacity)) {
1114         asanSetInitialBufferSizeTo(size());
1115         return false;
1116     }
1117     ASSERT(begin());
1118
1119     asanSetInitialBufferSizeTo(size());
1120
1121     TypeOperations::move(oldBuffer, oldEnd, begin());
1122     Base::deallocateBuffer(oldBuffer);
1123     return true;
1124 }
1125
1126 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1127 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
1128 {
1129     ASSERT(!m_size);
1130     ASSERT(capacity() == inlineCapacity);
1131     if (initialCapacity > inlineCapacity)
1132         Base::allocateBuffer(initialCapacity);
1133 }
1134
1135 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1136 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
1137 {
1138     if (newCapacity >= capacity())
1139         return;
1140
1141     if (newCapacity < size()) 
1142         shrink(newCapacity);
1143
1144     asanSetBufferSizeToFullCapacity();
1145
1146     T* oldBuffer = begin();
1147     if (newCapacity > 0) {
1148         if (Base::shouldReallocateBuffer(newCapacity)) {
1149             Base::reallocateBuffer(newCapacity);
1150             asanSetInitialBufferSizeTo(size());
1151             return;
1152         }
1153
1154         T* oldEnd = end();
1155         Base::allocateBuffer(newCapacity);
1156         if (begin() != oldBuffer)
1157             TypeOperations::move(oldBuffer, oldEnd, begin());
1158     }
1159
1160     Base::deallocateBuffer(oldBuffer);
1161     Base::restoreInlineBufferIfNeeded();
1162
1163     asanSetInitialBufferSizeTo(size());
1164 }
1165
1166 // Templatizing these is better than just letting the conversion happen implicitly,
1167 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1168 // without refcount thrash.
1169 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1170 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
1171 {
1172     size_t newSize = m_size + dataSize;
1173     if (newSize > capacity()) {
1174         data = expandCapacity(newSize, data);
1175         ASSERT(begin());
1176     }
1177     if (newSize < m_size)
1178         CRASH();
1179     asanBufferSizeWillChangeTo(newSize);
1180     T* dest = end();
1181     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1182     m_size = newSize;
1183 }
1184
1185 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1186 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
1187 {
1188     size_t newSize = m_size + dataSize;
1189     if (newSize > capacity()) {
1190         data = tryExpandCapacity(newSize, data);
1191         if (!data)
1192             return false;
1193         ASSERT(begin());
1194     }
1195     if (newSize < m_size)
1196         return false;
1197     asanBufferSizeWillChangeTo(newSize);
1198     T* dest = end();
1199     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1200     m_size = newSize;
1201     return true;
1202 }
1203
1204 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1205 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
1206 {
1207     if (size() != capacity()) {
1208         asanBufferSizeWillChangeTo(m_size + 1);
1209         new (NotNull, end()) T(std::forward<U>(value));
1210         ++m_size;
1211         return;
1212     }
1213
1214     appendSlowCase(std::forward<U>(value));
1215 }
1216
1217 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1218 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
1219 {
1220     ASSERT(size() == capacity());
1221
1222     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1223     ptr = expandCapacity(size() + 1, ptr);
1224     ASSERT(begin());
1225
1226     asanBufferSizeWillChangeTo(m_size + 1);
1227     new (NotNull, end()) T(std::forward<U>(*ptr));
1228     ++m_size;
1229 }
1230
1231 // This version of append saves a branch in the case where you know that the
1232 // vector's capacity is large enough for the append to succeed.
1233
1234 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1235 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
1236 {
1237     ASSERT(size() < capacity());
1238
1239     asanBufferSizeWillChangeTo(m_size + 1);
1240
1241     auto ptr = std::addressof(value);
1242     new (NotNull, end()) T(std::forward<U>(*ptr));
1243     ++m_size;
1244 }
1245
1246 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t otherCapacity>
1247 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1248 {
1249     append(val.begin(), val.size());
1250 }
1251
1252 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1253 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
1254 {
1255     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1256     size_t newSize = m_size + dataSize;
1257     if (newSize > capacity()) {
1258         data = expandCapacity(newSize, data);
1259         ASSERT(begin());
1260     }
1261     if (newSize < m_size)
1262         CRASH();
1263     asanBufferSizeWillChangeTo(newSize);
1264     T* spot = begin() + position;
1265     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1266     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1267     m_size = newSize;
1268 }
1269  
1270 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1271 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
1272 {
1273     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1274
1275     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1276     if (size() == capacity()) {
1277         ptr = expandCapacity(size() + 1, ptr);
1278         ASSERT(begin());
1279     }
1280
1281     asanBufferSizeWillChangeTo(m_size + 1);
1282
1283     T* spot = begin() + position;
1284     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1285     new (NotNull, spot) T(std::forward<U>(*ptr));
1286     ++m_size;
1287 }
1288
1289 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t c>
1290 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
1291 {
1292     insert(position, val.begin(), val.size());
1293 }
1294
1295 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1296 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
1297 {
1298     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1299     T* spot = begin() + position;
1300     spot->~T();
1301     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1302     asanBufferSizeWillChangeTo(m_size - 1);
1303     --m_size;
1304 }
1305
1306 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1307 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
1308 {
1309     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1310     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1311     T* beginSpot = begin() + position;
1312     T* endSpot = beginSpot + length;
1313     TypeOperations::destruct(beginSpot, endSpot); 
1314     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1315     asanBufferSizeWillChangeTo(m_size - length);
1316     m_size -= length;
1317 }
1318
1319 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1320 template<typename U>
1321 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
1322 {
1323     return removeFirstMatching([&value] (const T& current) {
1324         return current == value;
1325     });
1326 }
1327
1328 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1329 template<typename MatchFunction>
1330 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches)
1331 {
1332     for (size_t i = 0; i < size(); ++i) {
1333         if (matches(at(i))) {
1334             remove(i);
1335             return true;
1336         }
1337     }
1338     return false;
1339 }
1340
1341 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1342 template<typename U>
1343 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
1344 {
1345     return removeAllMatching([&value] (const T& current) {
1346         return current == value;
1347     });
1348 }
1349
1350 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1351 template<typename MatchFunction>
1352 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches)
1353 {
1354     iterator holeBegin = end();
1355     iterator holeEnd = end();
1356     unsigned matchCount = 0;
1357     for (auto it = begin(), itEnd = end(); it != itEnd; ++it) {
1358         if (matches(*it)) {
1359             if (holeBegin == end())
1360                 holeBegin = it;
1361             else if (holeEnd != it) {
1362                 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1363                 holeBegin += it - holeEnd;
1364             }
1365             holeEnd = it + 1;
1366             it->~T();
1367             ++matchCount;
1368         }
1369     }
1370     if (holeEnd != end())
1371         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1372     asanBufferSizeWillChangeTo(m_size - matchCount);
1373     m_size -= matchCount;
1374     return matchCount;
1375 }
1376
1377 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1378 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
1379 {
1380     for (size_t i = 0; i < m_size / 2; ++i)
1381         std::swap(at(i), at(m_size - 1 - i));
1382 }
1383
1384 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1385 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
1386 {
1387     // FIXME: Find a way to preserve annotations on the returned buffer.
1388     // ASan requires that all annotations are removed before deallocation,
1389     // and MallocPtr doesn't implement that.
1390     asanSetBufferSizeToFullCapacity();
1391
1392     auto buffer = Base::releaseBuffer();
1393     if (inlineCapacity && !buffer && m_size) {
1394         // If the vector had some data, but no buffer to release,
1395         // that means it was using the inline buffer. In that case,
1396         // we create a brand new buffer so the caller always gets one.
1397         size_t bytes = m_size * sizeof(T);
1398         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1399         memcpy(buffer.get(), data(), bytes);
1400     }
1401     m_size = 0;
1402     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1403     return buffer;
1404 }
1405
1406 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1407 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
1408 {
1409 #if !ASSERT_DISABLED
1410     for (size_t i = 0; i < size(); ++i)
1411         ValueCheck<T>::checkConsistency(at(i));
1412 #endif
1413 }
1414
1415 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1416 inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1417 {
1418     a.swap(b);
1419 }
1420
1421 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1422 bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1423 {
1424     if (a.size() != b.size())
1425         return false;
1426
1427     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1428 }
1429
1430 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1431 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1432 {
1433     return !(a == b);
1434 }
1435
1436 #if !ASSERT_DISABLED
1437 template<typename T> struct ValueCheck<Vector<T>> {
1438     typedef Vector<T> TraitType;
1439     static void checkConsistency(const Vector<T>& v)
1440     {
1441         v.checkConsistency();
1442     }
1443 };
1444 #endif
1445
1446 } // namespace WTF
1447
1448 using WTF::Vector;
1449 using WTF::UnsafeVectorOverflow;
1450 using WTF::notFound;
1451
1452 #endif // WTF_Vector_h