Do not use fastMallocGoodSize anywhere
[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(WTF::move(*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(WTF::move(*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) && 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>
642     explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
643
644     Vector& operator=(const Vector&);
645     template<size_t otherCapacity, typename otherOverflowBehaviour>
646     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
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 = WTF::move(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     template<typename U> void append(const U*, size_t);
727     template<typename U> void append(U&&);
728     template<typename U> void uncheckedAppend(U&& val);
729     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
730     template<typename U> bool tryAppend(const U*, size_t);
731
732     template<typename U> void insert(size_t position, const U*, size_t);
733     template<typename U> void insert(size_t position, U&&);
734     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
735
736     void remove(size_t position);
737     void remove(size_t position, size_t length);
738     template<typename U> bool removeFirst(const U&);
739     template<typename MatchFunction> bool removeFirstMatching(const MatchFunction&);
740     template<typename U> unsigned removeAll(const U&);
741     template<typename MatchFunction> unsigned removeAllMatching(const MatchFunction&);
742
743     void removeLast() 
744     {
745         if (UNLIKELY(isEmpty()))
746             OverflowHandler::overflowed();
747         shrink(size() - 1); 
748     }
749
750     void fill(const T&, size_t);
751     void fill(const T& val) { fill(val, size()); }
752
753     template<typename Iterator> void appendRange(Iterator start, Iterator end);
754
755     MallocPtr<T> releaseBuffer();
756
757     void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
758     {
759 #if ASAN_ENABLED
760         if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
761             return;
762 #endif
763
764         // Make it possible to copy inline buffers.
765         asanSetBufferSizeToFullCapacity();
766         other.asanSetBufferSizeToFullCapacity();
767
768         Base::swap(other, m_size, other.m_size);
769         std::swap(m_size, other.m_size);
770
771         asanSetInitialBufferSizeTo(m_size);
772         other.asanSetInitialBufferSizeTo(other.m_size);
773     }
774
775     void reverse();
776
777     void checkConsistency();
778
779 private:
780     void expandCapacity(size_t newMinCapacity);
781     T* expandCapacity(size_t newMinCapacity, T*);
782     bool tryExpandCapacity(size_t newMinCapacity);
783     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
784     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
785     template<typename U> void appendSlowCase(U&&);
786
787     void asanSetInitialBufferSizeTo(size_t);
788     void asanSetBufferSizeToFullCapacity();
789     void asanBufferSizeWillChangeTo(size_t);
790
791     using Base::m_size;
792     using Base::buffer;
793     using Base::capacity;
794     using Base::swap;
795     using Base::allocateBuffer;
796     using Base::deallocateBuffer;
797     using Base::tryAllocateBuffer;
798     using Base::shouldReallocateBuffer;
799     using Base::reallocateBuffer;
800     using Base::restoreInlineBufferIfNeeded;
801     using Base::releaseBuffer;
802 #if ASAN_ENABLED
803     using Base::endOfBuffer;
804 #endif
805 };
806
807 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
808 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
809     : Base(other.capacity(), other.size())
810 {
811     asanSetInitialBufferSizeTo(other.size());
812
813     if (begin())
814         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
815 }
816
817 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
818 template<size_t otherCapacity, typename otherOverflowBehaviour>
819 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
820     : Base(other.capacity(), other.size())
821 {
822     asanSetInitialBufferSizeTo(other.size());
823
824     if (begin())
825         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
826 }
827
828 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
829 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
830 {
831     if (&other == this)
832         return *this;
833     
834     if (size() > other.size())
835         shrink(other.size());
836     else if (other.size() > capacity()) {
837         clear();
838         reserveCapacity(other.size());
839         ASSERT(begin());
840     }
841
842     asanBufferSizeWillChangeTo(other.size());
843
844     std::copy(other.begin(), other.begin() + size(), begin());
845     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
846     m_size = other.size();
847
848     return *this;
849 }
850
851 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
852
853 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
854 template<size_t otherCapacity, typename otherOverflowBehaviour>
855 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
856 {
857     // If the inline capacities match, we should call the more specific
858     // template.  If the inline capacities don't match, the two objects
859     // shouldn't be allocated the same address.
860     ASSERT(!typelessPointersAreEqual(&other, this));
861
862     if (size() > other.size())
863         shrink(other.size());
864     else if (other.size() > capacity()) {
865         clear();
866         reserveCapacity(other.size());
867         ASSERT(begin());
868     }
869     
870     asanBufferSizeWillChangeTo(other.size());
871
872     std::copy(other.begin(), other.begin() + size(), begin());
873     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
874     m_size = other.size();
875
876     return *this;
877 }
878
879 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
880 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
881 {
882     swap(other);
883 }
884
885 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
886 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
887 {
888     swap(other);
889     return *this;
890 }
891
892 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
893 template<typename U>
894 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
895 {
896     return find(value) != notFound;
897 }
898
899 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
900 template<typename U>
901 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
902 {
903     for (size_t i = 0; i < size(); ++i) {
904         if (at(i) == value)
905             return i;
906     }
907     return notFound;
908 }
909
910 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
911 template<typename U>
912 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
913 {
914     for (size_t i = 1; i <= size(); ++i) {
915         const size_t index = size() - i;
916         if (at(index) == value)
917             return index;
918     }
919     return notFound;
920 }
921
922 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
923 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
924 {
925     if (size() > newSize)
926         shrink(newSize);
927     else if (newSize > capacity()) {
928         clear();
929         reserveCapacity(newSize);
930         ASSERT(begin());
931     }
932
933     asanBufferSizeWillChangeTo(newSize);
934
935     std::fill(begin(), end(), val);
936     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
937     m_size = newSize;
938 }
939
940 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
941 template<typename Iterator>
942 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
943 {
944     for (Iterator it = start; it != end; ++it)
945         append(*it);
946 }
947
948 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
949 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
950 {
951     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
952 }
953
954 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
955 T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
956 {
957     if (ptr < begin() || ptr >= end()) {
958         expandCapacity(newMinCapacity);
959         return ptr;
960     }
961     size_t index = ptr - begin();
962     expandCapacity(newMinCapacity);
963     return begin() + index;
964 }
965
966 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
967 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
968 {
969     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
970 }
971
972 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
973 const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
974 {
975     if (ptr < begin() || ptr >= end()) {
976         if (!tryExpandCapacity(newMinCapacity))
977             return 0;
978         return ptr;
979     }
980     size_t index = ptr - begin();
981     if (!tryExpandCapacity(newMinCapacity))
982         return 0;
983     return begin() + index;
984 }
985
986 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
987 inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
988 {
989     expandCapacity(newMinCapacity);
990     return ptr;
991 }
992
993 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
994 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
995 {
996     if (size <= m_size) {
997         TypeOperations::destruct(begin() + size, end());
998         asanBufferSizeWillChangeTo(size);
999     } else {
1000         if (size > capacity())
1001             expandCapacity(size);
1002         asanBufferSizeWillChangeTo(size);
1003         if (begin())
1004             TypeOperations::initialize(end(), begin() + size);
1005     }
1006     
1007     m_size = size;
1008 }
1009
1010 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1011 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
1012 {
1013     reserveCapacity(size);
1014     resize(size);
1015 }
1016
1017 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1018 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
1019 {
1020     ASSERT(size <= m_size);
1021     TypeOperations::destruct(begin() + size, end());
1022     asanBufferSizeWillChangeTo(size);
1023     m_size = size;
1024 }
1025
1026 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1027 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
1028 {
1029     ASSERT(size >= m_size);
1030     if (size > capacity())
1031         expandCapacity(size);
1032     asanBufferSizeWillChangeTo(size);
1033     if (begin())
1034         TypeOperations::initialize(end(), begin() + size);
1035     m_size = size;
1036 }
1037
1038 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1039 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
1040 {
1041 #if ASAN_ENABLED
1042     if (!buffer())
1043         return;
1044
1045     // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1046     // when accessing elements in [end(), endOfBuffer()) range.
1047     // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1048     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1049 #else
1050     UNUSED_PARAM(size);
1051 #endif
1052 }
1053
1054 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1055 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity()
1056 {
1057 #if ASAN_ENABLED
1058     if (!buffer())
1059         return;
1060
1061     // ASan requires that the annotation is returned to its initial state before deallocation.
1062     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), endOfBuffer());
1063 #endif
1064 }
1065
1066 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1067 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
1068 {
1069 #if ASAN_ENABLED
1070     if (!buffer())
1071         return;
1072
1073     // Change allowed range.
1074     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1075 #else
1076     UNUSED_PARAM(newSize);
1077 #endif
1078 }
1079
1080 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1081 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
1082 {
1083     if (newCapacity <= capacity())
1084         return;
1085     T* oldBuffer = begin();
1086     T* oldEnd = end();
1087
1088     asanSetBufferSizeToFullCapacity();
1089
1090     Base::allocateBuffer(newCapacity);
1091     ASSERT(begin());
1092
1093     asanSetInitialBufferSizeTo(size());
1094
1095     TypeOperations::move(oldBuffer, oldEnd, begin());
1096     Base::deallocateBuffer(oldBuffer);
1097 }
1098
1099 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1100 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
1101 {
1102     if (newCapacity <= capacity())
1103         return true;
1104     T* oldBuffer = begin();
1105     T* oldEnd = end();
1106
1107     asanSetBufferSizeToFullCapacity();
1108
1109     if (!Base::tryAllocateBuffer(newCapacity)) {
1110         asanSetInitialBufferSizeTo(size());
1111         return false;
1112     }
1113     ASSERT(begin());
1114
1115     asanSetInitialBufferSizeTo(size());
1116
1117     TypeOperations::move(oldBuffer, oldEnd, begin());
1118     Base::deallocateBuffer(oldBuffer);
1119     return true;
1120 }
1121
1122 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1123 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
1124 {
1125     ASSERT(!m_size);
1126     ASSERT(capacity() == inlineCapacity);
1127     if (initialCapacity > inlineCapacity)
1128         Base::allocateBuffer(initialCapacity);
1129 }
1130
1131 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1132 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
1133 {
1134     if (newCapacity >= capacity())
1135         return;
1136
1137     if (newCapacity < size()) 
1138         shrink(newCapacity);
1139
1140     asanSetBufferSizeToFullCapacity();
1141
1142     T* oldBuffer = begin();
1143     if (newCapacity > 0) {
1144         if (Base::shouldReallocateBuffer(newCapacity)) {
1145             Base::reallocateBuffer(newCapacity);
1146             asanSetInitialBufferSizeTo(size());
1147             return;
1148         }
1149
1150         T* oldEnd = end();
1151         Base::allocateBuffer(newCapacity);
1152         if (begin() != oldBuffer)
1153             TypeOperations::move(oldBuffer, oldEnd, begin());
1154     }
1155
1156     Base::deallocateBuffer(oldBuffer);
1157     Base::restoreInlineBufferIfNeeded();
1158
1159     asanSetInitialBufferSizeTo(size());
1160 }
1161
1162 // Templatizing these is better than just letting the conversion happen implicitly,
1163 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1164 // without refcount thrash.
1165 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1166 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
1167 {
1168     size_t newSize = m_size + dataSize;
1169     if (newSize > capacity()) {
1170         data = expandCapacity(newSize, data);
1171         ASSERT(begin());
1172     }
1173     if (newSize < m_size)
1174         CRASH();
1175     asanBufferSizeWillChangeTo(newSize);
1176     T* dest = end();
1177     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1178     m_size = newSize;
1179 }
1180
1181 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1182 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
1183 {
1184     size_t newSize = m_size + dataSize;
1185     if (newSize > capacity()) {
1186         data = tryExpandCapacity(newSize, data);
1187         if (!data)
1188             return false;
1189         ASSERT(begin());
1190     }
1191     if (newSize < m_size)
1192         return false;
1193     asanBufferSizeWillChangeTo(newSize);
1194     T* dest = end();
1195     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1196     m_size = newSize;
1197     return true;
1198 }
1199
1200 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1201 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
1202 {
1203     if (size() != capacity()) {
1204         asanBufferSizeWillChangeTo(m_size + 1);
1205         new (NotNull, end()) T(std::forward<U>(value));
1206         ++m_size;
1207         return;
1208     }
1209
1210     appendSlowCase(std::forward<U>(value));
1211 }
1212
1213 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1214 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
1215 {
1216     ASSERT(size() == capacity());
1217
1218     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1219     ptr = expandCapacity(size() + 1, ptr);
1220     ASSERT(begin());
1221
1222     asanBufferSizeWillChangeTo(m_size + 1);
1223     new (NotNull, end()) T(std::forward<U>(*ptr));
1224     ++m_size;
1225 }
1226
1227 // This version of append saves a branch in the case where you know that the
1228 // vector's capacity is large enough for the append to succeed.
1229
1230 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1231 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
1232 {
1233     ASSERT(size() < capacity());
1234
1235     asanBufferSizeWillChangeTo(m_size + 1);
1236
1237     auto ptr = std::addressof(value);
1238     new (NotNull, end()) T(std::forward<U>(*ptr));
1239     ++m_size;
1240 }
1241
1242 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t otherCapacity>
1243 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1244 {
1245     append(val.begin(), val.size());
1246 }
1247
1248 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1249 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
1250 {
1251     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1252     size_t newSize = m_size + dataSize;
1253     if (newSize > capacity()) {
1254         data = expandCapacity(newSize, data);
1255         ASSERT(begin());
1256     }
1257     if (newSize < m_size)
1258         CRASH();
1259     asanBufferSizeWillChangeTo(newSize);
1260     T* spot = begin() + position;
1261     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1262     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1263     m_size = newSize;
1264 }
1265  
1266 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
1267 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
1268 {
1269     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1270
1271     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1272     if (size() == capacity()) {
1273         ptr = expandCapacity(size() + 1, ptr);
1274         ASSERT(begin());
1275     }
1276
1277     asanBufferSizeWillChangeTo(m_size + 1);
1278
1279     T* spot = begin() + position;
1280     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1281     new (NotNull, spot) T(std::forward<U>(*ptr));
1282     ++m_size;
1283 }
1284
1285 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U, size_t c>
1286 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
1287 {
1288     insert(position, val.begin(), val.size());
1289 }
1290
1291 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1292 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
1293 {
1294     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1295     T* spot = begin() + position;
1296     spot->~T();
1297     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1298     asanBufferSizeWillChangeTo(m_size - 1);
1299     --m_size;
1300 }
1301
1302 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1303 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
1304 {
1305     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1306     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1307     T* beginSpot = begin() + position;
1308     T* endSpot = beginSpot + length;
1309     TypeOperations::destruct(beginSpot, endSpot); 
1310     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1311     asanBufferSizeWillChangeTo(m_size - length);
1312     m_size -= length;
1313 }
1314
1315 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1316 template<typename U>
1317 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
1318 {
1319     return removeFirstMatching([&value] (const T& current) {
1320         return current == value;
1321     });
1322 }
1323
1324 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1325 template<typename MatchFunction>
1326 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches)
1327 {
1328     for (size_t i = 0; i < size(); ++i) {
1329         if (matches(at(i))) {
1330             remove(i);
1331             return true;
1332         }
1333     }
1334     return false;
1335 }
1336
1337 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1338 template<typename U>
1339 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
1340 {
1341     return removeAllMatching([&value] (const T& current) {
1342         return current == value;
1343     });
1344 }
1345
1346 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1347 template<typename MatchFunction>
1348 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches)
1349 {
1350     iterator holeBegin = end();
1351     iterator holeEnd = end();
1352     unsigned matchCount = 0;
1353     for (auto it = begin(), itEnd = end(); it != itEnd; ++it) {
1354         if (matches(*it)) {
1355             if (holeBegin == end())
1356                 holeBegin = it;
1357             else if (holeEnd != it) {
1358                 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1359                 holeBegin += it - holeEnd;
1360             }
1361             holeEnd = it + 1;
1362             it->~T();
1363             ++matchCount;
1364         }
1365     }
1366     if (holeEnd != end())
1367         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1368     asanBufferSizeWillChangeTo(m_size - matchCount);
1369     m_size -= matchCount;
1370     return matchCount;
1371 }
1372
1373 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1374 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
1375 {
1376     for (size_t i = 0; i < m_size / 2; ++i)
1377         std::swap(at(i), at(m_size - 1 - i));
1378 }
1379
1380 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1381 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
1382 {
1383     // FIXME: Find a way to preserve annotations on the returned buffer.
1384     // ASan requires that all annotations are removed before deallocation,
1385     // and MallocPtr doesn't implement that.
1386     asanSetBufferSizeToFullCapacity();
1387
1388     auto buffer = Base::releaseBuffer();
1389     if (inlineCapacity && !buffer && m_size) {
1390         // If the vector had some data, but no buffer to release,
1391         // that means it was using the inline buffer. In that case,
1392         // we create a brand new buffer so the caller always gets one.
1393         size_t bytes = m_size * sizeof(T);
1394         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1395         memcpy(buffer.get(), data(), bytes);
1396     }
1397     m_size = 0;
1398     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1399     return buffer;
1400 }
1401
1402 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1403 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
1404 {
1405 #if !ASSERT_DISABLED
1406     for (size_t i = 0; i < size(); ++i)
1407         ValueCheck<T>::checkConsistency(at(i));
1408 #endif
1409 }
1410
1411 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1412 inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1413 {
1414     a.swap(b);
1415 }
1416
1417 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1418 bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1419 {
1420     if (a.size() != b.size())
1421         return false;
1422
1423     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1424 }
1425
1426 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1427 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1428 {
1429     return !(a == b);
1430 }
1431
1432 #if !ASSERT_DISABLED
1433 template<typename T> struct ValueCheck<Vector<T>> {
1434     typedef Vector<T> TraitType;
1435     static void checkConsistency(const Vector<T>& v)
1436     {
1437         v.checkConsistency();
1438     }
1439 };
1440 #endif
1441
1442 } // namespace WTF
1443
1444 using WTF::Vector;
1445 using WTF::UnsafeVectorOverflow;
1446 using WTF::notFound;
1447
1448 #endif // WTF_Vector_h