Vector should be able to easily create from a list of movable only items
[WebKit-https.git] / Source / WTF / wtf / Vector.h
1 /*
2  *  Copyright (C) 2005-2017 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/Forward.h>
32 #include <wtf/MallocPtr.h>
33 #include <wtf/Noncopyable.h>
34 #include <wtf/NotFound.h>
35 #include <wtf/StdLibExtras.h>
36 #include <wtf/ValueCheck.h>
37 #include <wtf/VectorTraits.h>
38
39 #if ASAN_ENABLED
40 extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid);
41 #endif
42
43 namespace WTF {
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, typename Malloc>
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*>(Malloc::malloc(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 = static_cast<T*>(Malloc::tryMalloc(sizeToAllocate));
280         if (!newBuffer)
281             return false;
282         m_capacity = sizeToAllocate / sizeof(T);
283         m_buffer = newBuffer;
284         return true;
285     }
286
287     bool shouldReallocateBuffer(size_t newCapacity) const
288     {
289         return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
290     }
291
292     void reallocateBuffer(size_t newCapacity)
293     {
294         ASSERT(shouldReallocateBuffer(newCapacity));
295         if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
296             CRASH();
297         size_t sizeToAllocate = newCapacity * sizeof(T);
298         m_capacity = sizeToAllocate / sizeof(T);
299         m_buffer = static_cast<T*>(Malloc::realloc(m_buffer, sizeToAllocate));
300     }
301
302     void deallocateBuffer(T* bufferToDeallocate)
303     {
304         if (!bufferToDeallocate)
305             return;
306         
307         if (m_buffer == bufferToDeallocate) {
308             m_buffer = 0;
309             m_capacity = 0;
310         }
311
312         Malloc::free(bufferToDeallocate);
313     }
314
315     T* buffer() { return m_buffer; }
316     const T* buffer() const { return m_buffer; }
317     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
318     size_t capacity() const { return m_capacity; }
319
320     MallocPtr<T> releaseBuffer()
321     {
322         T* buffer = m_buffer;
323         m_buffer = 0;
324         m_capacity = 0;
325         return adoptMallocPtr(buffer);
326     }
327
328 protected:
329     VectorBufferBase()
330         : m_buffer(0)
331         , m_capacity(0)
332         , m_size(0)
333     {
334     }
335
336     VectorBufferBase(T* buffer, size_t capacity, size_t size)
337         : m_buffer(buffer)
338         , m_capacity(capacity)
339         , m_size(size)
340     {
341     }
342
343     ~VectorBufferBase()
344     {
345         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
346     }
347
348     T* m_buffer;
349     unsigned m_capacity;
350     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
351 };
352
353 template<typename T, size_t inlineCapacity, typename Malloc>
354 class VectorBuffer;
355
356 template<typename T, typename Malloc>
357 class VectorBuffer<T, 0, Malloc> : private VectorBufferBase<T, Malloc> {
358 private:
359     typedef VectorBufferBase<T, Malloc> Base;
360 public:
361     VectorBuffer()
362     {
363     }
364
365     VectorBuffer(size_t capacity, size_t size = 0)
366     {
367         m_size = size;
368         // Calling malloc(0) might take a lock and may actually do an
369         // allocation on some systems.
370         if (capacity)
371             allocateBuffer(capacity);
372     }
373
374     ~VectorBuffer()
375     {
376         deallocateBuffer(buffer());
377     }
378     
379     void swap(VectorBuffer<T, 0, Malloc>& other, size_t, size_t)
380     {
381         std::swap(m_buffer, other.m_buffer);
382         std::swap(m_capacity, other.m_capacity);
383     }
384     
385     void restoreInlineBufferIfNeeded() { }
386
387 #if ASAN_ENABLED
388     void* endOfBuffer()
389     {
390         return buffer() + capacity();
391     }
392 #endif
393
394     using Base::allocateBuffer;
395     using Base::tryAllocateBuffer;
396     using Base::shouldReallocateBuffer;
397     using Base::reallocateBuffer;
398     using Base::deallocateBuffer;
399
400     using Base::buffer;
401     using Base::capacity;
402     using Base::bufferMemoryOffset;
403
404     using Base::releaseBuffer;
405
406 protected:
407     using Base::m_size;
408
409 private:
410     using Base::m_buffer;
411     using Base::m_capacity;
412 };
413
414 template<typename T, size_t inlineCapacity, typename Malloc>
415 class VectorBuffer : private VectorBufferBase<T, Malloc> {
416     WTF_MAKE_NONCOPYABLE(VectorBuffer);
417 private:
418     typedef VectorBufferBase<T, Malloc> Base;
419 public:
420     VectorBuffer()
421         : Base(inlineBuffer(), inlineCapacity, 0)
422     {
423     }
424
425     VectorBuffer(size_t capacity, size_t size = 0)
426         : Base(inlineBuffer(), inlineCapacity, size)
427     {
428         if (capacity > inlineCapacity)
429             Base::allocateBuffer(capacity);
430     }
431
432     ~VectorBuffer()
433     {
434         deallocateBuffer(buffer());
435     }
436
437     void allocateBuffer(size_t newCapacity)
438     {
439         // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
440         if (newCapacity > inlineCapacity)
441             Base::allocateBuffer(newCapacity);
442         else {
443             m_buffer = inlineBuffer();
444             m_capacity = inlineCapacity;
445         }
446     }
447
448     bool tryAllocateBuffer(size_t newCapacity)
449     {
450         if (newCapacity > inlineCapacity)
451             return Base::tryAllocateBuffer(newCapacity);
452         m_buffer = inlineBuffer();
453         m_capacity = inlineCapacity;
454         return true;
455     }
456
457     void deallocateBuffer(T* bufferToDeallocate)
458     {
459         if (bufferToDeallocate == inlineBuffer())
460             return;
461         Base::deallocateBuffer(bufferToDeallocate);
462     }
463
464     bool shouldReallocateBuffer(size_t newCapacity) const
465     {
466         // We cannot reallocate the inline buffer.
467         return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
468     }
469
470     void reallocateBuffer(size_t newCapacity)
471     {
472         ASSERT(shouldReallocateBuffer(newCapacity));
473         Base::reallocateBuffer(newCapacity);
474     }
475
476     void swap(VectorBuffer& other, size_t mySize, size_t otherSize)
477     {
478         if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
479             swapInlineBuffer(other, mySize, otherSize);
480             std::swap(m_capacity, other.m_capacity);
481         } else if (buffer() == inlineBuffer()) {
482             m_buffer = other.m_buffer;
483             other.m_buffer = other.inlineBuffer();
484             swapInlineBuffer(other, mySize, 0);
485             std::swap(m_capacity, other.m_capacity);
486         } else if (other.buffer() == other.inlineBuffer()) {
487             other.m_buffer = m_buffer;
488             m_buffer = inlineBuffer();
489             swapInlineBuffer(other, 0, otherSize);
490             std::swap(m_capacity, other.m_capacity);
491         } else {
492             std::swap(m_buffer, other.m_buffer);
493             std::swap(m_capacity, other.m_capacity);
494         }
495     }
496
497     void restoreInlineBufferIfNeeded()
498     {
499         if (m_buffer)
500             return;
501         m_buffer = inlineBuffer();
502         m_capacity = inlineCapacity;
503     }
504
505 #if ASAN_ENABLED
506     void* endOfBuffer()
507     {
508         ASSERT(buffer());
509         static_assert((offsetof(VectorBuffer, m_inlineBuffer) + sizeof(m_inlineBuffer)) % 8 == 0, "Inline buffer end needs to be on 8 byte boundary for ASan annotations to work.");
510
511         if (buffer() == inlineBuffer())
512             return reinterpret_cast<char*>(m_inlineBuffer) + sizeof(m_inlineBuffer);
513
514         return buffer() + capacity();
515     }
516 #endif
517
518     using Base::buffer;
519     using Base::capacity;
520     using Base::bufferMemoryOffset;
521
522     MallocPtr<T> releaseBuffer()
523     {
524         if (buffer() == inlineBuffer())
525             return nullptr;
526         return Base::releaseBuffer();
527     }
528
529 protected:
530     using Base::m_size;
531
532 private:
533     using Base::m_buffer;
534     using Base::m_capacity;
535     
536     void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize)
537     {
538         // FIXME: We could make swap part of VectorTypeOperations
539         // https://bugs.webkit.org/show_bug.cgi?id=128863
540         swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
541     }
542     
543     static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
544     {
545         if (left == right)
546             return;
547         
548         ASSERT(leftSize <= inlineCapacity);
549         ASSERT(rightSize <= inlineCapacity);
550         
551         size_t swapBound = std::min(leftSize, rightSize);
552         for (unsigned i = 0; i < swapBound; ++i)
553             std::swap(left[i], right[i]);
554         VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
555         VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
556     }
557
558     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
559     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
560
561 #if ASAN_ENABLED
562     // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work.
563     // FIXME: Add a redzone before the buffer to catch off by one accesses. We don't need a guard after, because the buffer is the last member variable.
564     static const size_t asanInlineBufferAlignment = std::alignment_of<T>::value >= 8 ? std::alignment_of<T>::value : 8;
565     static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T);
566     typename std::aligned_storage<sizeof(T), asanInlineBufferAlignment>::type m_inlineBuffer[asanAdjustedInlineCapacity];
567 #else
568     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
569 #endif
570 };
571
572 struct UnsafeVectorOverflow {
573     static NO_RETURN_DUE_TO_ASSERT void overflowed()
574     {
575         ASSERT_NOT_REACHED();
576     }
577 };
578
579 // Template default values are in Forward.h.
580 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
581 class Vector : private VectorBuffer<T, inlineCapacity, Malloc> {
582     WTF_MAKE_FAST_ALLOCATED;
583 private:
584     typedef VectorBuffer<T, inlineCapacity, Malloc> Base;
585     typedef VectorTypeOperations<T> TypeOperations;
586
587 public:
588     typedef T ValueType;
589
590     typedef T* iterator;
591     typedef const T* const_iterator;
592     typedef std::reverse_iterator<iterator> reverse_iterator;
593     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
594
595     Vector()
596     {
597     }
598
599     // Unlike in std::vector, this constructor does not initialize POD types.
600     explicit Vector(size_t size)
601         : Base(size, size)
602     {
603         asanSetInitialBufferSizeTo(size);
604
605         if (begin())
606             TypeOperations::initialize(begin(), end());
607     }
608
609     Vector(size_t size, const T& val)
610         : Base(size, size)
611     {
612         asanSetInitialBufferSizeTo(size);
613
614         if (begin())
615             TypeOperations::uninitializedFill(begin(), end(), val);
616     }
617
618     Vector(std::initializer_list<T> initializerList)
619     {
620         reserveInitialCapacity(initializerList.size());
621
622         asanSetInitialBufferSizeTo(initializerList.size());
623
624         for (const auto& element : initializerList)
625             uncheckedAppend(element);
626     }
627
628     template<typename... Items>
629     static Vector from(Items&&... items)
630     {
631         Vector result;
632         auto size = sizeof...(items);
633
634         result.reserveInitialCapacity(size);
635         result.asanSetInitialBufferSizeTo(size);
636         result.m_size = size;
637
638         result.uncheckedInitialize<0>(std::forward<Items>(items)...);
639         return result;
640     }
641
642     ~Vector()
643     {
644         if (m_size)
645             TypeOperations::destruct(begin(), end());
646
647         asanSetBufferSizeToFullCapacity(0);
648     }
649
650     Vector(const Vector&);
651     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity, typename OtherMalloc>
652     explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity, OtherMalloc>&);
653
654     Vector& operator=(const Vector&);
655     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity, typename OtherMalloc>
656     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity, OtherMalloc>&);
657
658     Vector(Vector&&);
659     Vector& operator=(Vector&&);
660
661     size_t size() const { return m_size; }
662     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
663     size_t capacity() const { return Base::capacity(); }
664     bool isEmpty() const { return !size(); }
665
666     T& at(size_t i)
667     {
668         if (UNLIKELY(i >= size()))
669             OverflowHandler::overflowed();
670         return Base::buffer()[i];
671     }
672     const T& at(size_t i) const 
673     {
674         if (UNLIKELY(i >= size()))
675             OverflowHandler::overflowed();
676         return Base::buffer()[i];
677     }
678     T& at(Checked<size_t> i)
679     {
680         RELEASE_ASSERT(i < size());
681         return Base::buffer()[i];
682     }
683     const T& at(Checked<size_t> i) const
684     {
685         RELEASE_ASSERT(i < size());
686         return Base::buffer()[i];
687     }
688
689     T& operator[](size_t i) { return at(i); }
690     const T& operator[](size_t i) const { return at(i); }
691     T& operator[](Checked<size_t> i) { return at(i); }
692     const T& operator[](Checked<size_t> i) const { return at(i); }
693
694     T* data() { return Base::buffer(); }
695     const T* data() const { return Base::buffer(); }
696     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
697
698     iterator begin() { return data(); }
699     iterator end() { return begin() + m_size; }
700     const_iterator begin() const { return data(); }
701     const_iterator end() const { return begin() + m_size; }
702
703     reverse_iterator rbegin() { return reverse_iterator(end()); }
704     reverse_iterator rend() { return reverse_iterator(begin()); }
705     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
706     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
707
708     T& first() { return at(0); }
709     const T& first() const { return at(0); }
710     T& last() { return at(size() - 1); }
711     const T& last() const { return at(size() - 1); }
712     
713     T takeLast()
714     {
715         T result = WTFMove(last());
716         removeLast();
717         return result;
718     }
719     
720     template<typename U> bool contains(const U&) const;
721     template<typename U> size_t find(const U&) const;
722     template<typename MatchFunction> size_t findMatching(const MatchFunction&) const;
723     template<typename U> size_t reverseFind(const U&) const;
724     
725     template<typename U> bool appendIfNotContains(const U&);
726
727     void shrink(size_t size);
728     void grow(size_t size);
729     void resize(size_t size);
730     void resizeToFit(size_t size);
731     void reserveCapacity(size_t newCapacity);
732     bool tryReserveCapacity(size_t newCapacity);
733     void reserveInitialCapacity(size_t initialCapacity);
734     void shrinkCapacity(size_t newCapacity);
735     void shrinkToFit() { shrinkCapacity(size()); }
736
737     void clear() { shrinkCapacity(0); }
738
739     void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
740     template<typename U> void append(U&&);
741     template<typename... Args> void constructAndAppend(Args&&...);
742     template<typename... Args> bool tryConstructAndAppend(Args&&...);
743
744     void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
745     template<typename U> void uncheckedAppend(U&&);
746
747     template<typename U> void append(const U*, size_t);
748     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
749     template<typename U> bool tryAppend(const U*, size_t);
750
751     template<typename U> void insert(size_t position, const U*, size_t);
752     template<typename U> void insert(size_t position, U&&);
753     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
754
755     void remove(size_t position);
756     void remove(size_t position, size_t length);
757     template<typename U> bool removeFirst(const U&);
758     template<typename MatchFunction> bool removeFirstMatching(const MatchFunction&, size_t startIndex = 0);
759     template<typename U> unsigned removeAll(const U&);
760     template<typename MatchFunction> unsigned removeAllMatching(const MatchFunction&, size_t startIndex = 0);
761
762     void removeLast() 
763     {
764         if (UNLIKELY(isEmpty()))
765             OverflowHandler::overflowed();
766         shrink(size() - 1); 
767     }
768
769     void fill(const T&, size_t);
770     void fill(const T& val) { fill(val, size()); }
771
772     template<typename Iterator> void appendRange(Iterator start, Iterator end);
773
774     MallocPtr<T> releaseBuffer();
775
776     void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
777     {
778 #if ASAN_ENABLED
779         if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
780             return;
781 #endif
782
783         // Make it possible to copy inline buffers.
784         asanSetBufferSizeToFullCapacity();
785         other.asanSetBufferSizeToFullCapacity();
786
787         Base::swap(other, m_size, other.m_size);
788         std::swap(m_size, other.m_size);
789
790         asanSetInitialBufferSizeTo(m_size);
791         other.asanSetInitialBufferSizeTo(other.m_size);
792     }
793
794     void reverse();
795
796     void checkConsistency();
797
798     template<typename MapFunction, typename R = typename std::result_of<MapFunction(const T&)>::type> Vector<R> map(MapFunction) const;
799
800 private:
801     void expandCapacity(size_t newMinCapacity);
802     T* expandCapacity(size_t newMinCapacity, T*);
803     bool tryExpandCapacity(size_t newMinCapacity);
804     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
805     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
806     template<typename U> void appendSlowCase(U&&);
807     template<typename... Args> void constructAndAppendSlowCase(Args&&...);
808     template<typename... Args> bool tryConstructAndAppendSlowCase(Args&&...);
809
810     template<size_t position, typename U, typename... Items>
811     void uncheckedInitialize(U&& item, Items&&... items)
812     {
813         uncheckedInitialize<position>(std::forward<U>(item));
814         uncheckedInitialize<position + 1>(std::forward<Items>(items)...);
815     }
816     template<size_t position, typename U>
817     void uncheckedInitialize(U&& value)
818     {
819         ASSERT(position < size());
820         ASSERT(position < capacity());
821         new (NotNull, begin() + position) T(std::forward<U>(value));
822     }
823
824     void asanSetInitialBufferSizeTo(size_t);
825     void asanSetBufferSizeToFullCapacity(size_t);
826     void asanSetBufferSizeToFullCapacity() { asanSetBufferSizeToFullCapacity(size()); }
827
828     void asanBufferSizeWillChangeTo(size_t);
829
830     using Base::m_size;
831     using Base::buffer;
832     using Base::capacity;
833     using Base::swap;
834     using Base::allocateBuffer;
835     using Base::deallocateBuffer;
836     using Base::tryAllocateBuffer;
837     using Base::shouldReallocateBuffer;
838     using Base::reallocateBuffer;
839     using Base::restoreInlineBufferIfNeeded;
840     using Base::releaseBuffer;
841 #if ASAN_ENABLED
842     using Base::endOfBuffer;
843 #endif
844 };
845
846 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
847 Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::Vector(const Vector& other)
848     : Base(other.capacity(), other.size())
849 {
850     asanSetInitialBufferSizeTo(other.size());
851
852     if (begin())
853         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
854 }
855
856 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
857 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity, typename OtherMalloc>
858 Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity, OtherMalloc>& other)
859     : Base(other.capacity(), other.size())
860 {
861     asanSetInitialBufferSizeTo(other.size());
862
863     if (begin())
864         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
865 }
866
867 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
868 Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& other)
869 {
870     if (&other == this)
871         return *this;
872     
873     if (size() > other.size())
874         shrink(other.size());
875     else if (other.size() > capacity()) {
876         clear();
877         reserveCapacity(other.size());
878         ASSERT(begin());
879     }
880
881     asanBufferSizeWillChangeTo(other.size());
882
883     std::copy(other.begin(), other.begin() + size(), begin());
884     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
885     m_size = other.size();
886
887     return *this;
888 }
889
890 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
891
892 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
893 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity, typename OtherMalloc>
894 Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity, OtherMalloc>& other)
895 {
896     // If the inline capacities match, we should call the more specific
897     // template.  If the inline capacities don't match, the two objects
898     // shouldn't be allocated the same address.
899     ASSERT(!typelessPointersAreEqual(&other, this));
900
901     if (size() > other.size())
902         shrink(other.size());
903     else if (other.size() > capacity()) {
904         clear();
905         reserveCapacity(other.size());
906         ASSERT(begin());
907     }
908     
909     asanBufferSizeWillChangeTo(other.size());
910
911     std::copy(other.begin(), other.begin() + size(), begin());
912     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
913     m_size = other.size();
914
915     return *this;
916 }
917
918 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
919 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>&& other)
920 {
921     swap(other);
922 }
923
924 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
925 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>&& other)
926 {
927     swap(other);
928     return *this;
929 }
930
931 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
932 template<typename U>
933 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::contains(const U& value) const
934 {
935     return find(value) != notFound;
936 }
937
938 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
939 template<typename MatchFunction>
940 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::findMatching(const MatchFunction& matches) const
941 {
942     for (size_t i = 0; i < size(); ++i) {
943         if (matches(at(i)))
944             return i;
945     }
946     return notFound;
947 }
948
949 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
950 template<typename U>
951 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::find(const U& value) const
952 {
953     return findMatching([&](auto& item) {
954         return item == value;
955     });
956 }
957
958 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
959 template<typename U>
960 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::reverseFind(const U& value) const
961 {
962     for (size_t i = 1; i <= size(); ++i) {
963         const size_t index = size() - i;
964         if (at(index) == value)
965             return index;
966     }
967     return notFound;
968 }
969
970 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
971 template<typename U>
972 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::appendIfNotContains(const U& value)
973 {
974     if (contains(value))
975         return false;
976     append(value);
977     return true;
978 }
979
980 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
981 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::fill(const T& val, size_t newSize)
982 {
983     if (size() > newSize)
984         shrink(newSize);
985     else if (newSize > capacity()) {
986         clear();
987         reserveCapacity(newSize);
988         ASSERT(begin());
989     }
990
991     asanBufferSizeWillChangeTo(newSize);
992
993     std::fill(begin(), end(), val);
994     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
995     m_size = newSize;
996 }
997
998 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
999 template<typename Iterator>
1000 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::appendRange(Iterator start, Iterator end)
1001 {
1002     for (Iterator it = start; it != end; ++it)
1003         append(*it);
1004 }
1005
1006 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1007 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::expandCapacity(size_t newMinCapacity)
1008 {
1009     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1010 }
1011
1012 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1013 T* Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::expandCapacity(size_t newMinCapacity, T* ptr)
1014 {
1015     if (ptr < begin() || ptr >= end()) {
1016         expandCapacity(newMinCapacity);
1017         return ptr;
1018     }
1019     size_t index = ptr - begin();
1020     expandCapacity(newMinCapacity);
1021     return begin() + index;
1022 }
1023
1024 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1025 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryExpandCapacity(size_t newMinCapacity)
1026 {
1027     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1028 }
1029
1030 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1031 const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
1032 {
1033     if (ptr < begin() || ptr >= end()) {
1034         if (!tryExpandCapacity(newMinCapacity))
1035             return 0;
1036         return ptr;
1037     }
1038     size_t index = ptr - begin();
1039     if (!tryExpandCapacity(newMinCapacity))
1040         return 0;
1041     return begin() + index;
1042 }
1043
1044 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1045 template<typename U>
1046 inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::expandCapacity(size_t newMinCapacity, U* ptr)
1047 {
1048     expandCapacity(newMinCapacity);
1049     return ptr;
1050 }
1051
1052 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1053 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::resize(size_t size)
1054 {
1055     if (size <= m_size) {
1056         TypeOperations::destruct(begin() + size, end());
1057         asanBufferSizeWillChangeTo(size);
1058     } else {
1059         if (size > capacity())
1060             expandCapacity(size);
1061         asanBufferSizeWillChangeTo(size);
1062         if (begin())
1063             TypeOperations::initialize(end(), begin() + size);
1064     }
1065     
1066     m_size = size;
1067 }
1068
1069 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1070 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::resizeToFit(size_t size)
1071 {
1072     reserveCapacity(size);
1073     resize(size);
1074 }
1075
1076 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1077 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::shrink(size_t size)
1078 {
1079     ASSERT(size <= m_size);
1080     TypeOperations::destruct(begin() + size, end());
1081     asanBufferSizeWillChangeTo(size);
1082     m_size = size;
1083 }
1084
1085 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1086 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::grow(size_t size)
1087 {
1088     ASSERT(size >= m_size);
1089     if (size > capacity())
1090         expandCapacity(size);
1091     asanBufferSizeWillChangeTo(size);
1092     if (begin())
1093         TypeOperations::initialize(end(), begin() + size);
1094     m_size = size;
1095 }
1096
1097 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1098 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::asanSetInitialBufferSizeTo(size_t size)
1099 {
1100 #if ASAN_ENABLED
1101     if (!buffer())
1102         return;
1103
1104     // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1105     // when accessing elements in [end(), endOfBuffer()) range.
1106     // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1107     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1108 #else
1109     UNUSED_PARAM(size);
1110 #endif
1111 }
1112
1113 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1114 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::asanSetBufferSizeToFullCapacity(size_t size)
1115 {
1116 #if ASAN_ENABLED
1117     if (!buffer())
1118         return;
1119
1120     // ASan requires that the annotation is returned to its initial state before deallocation.
1121     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size, endOfBuffer());
1122 #else
1123     UNUSED_PARAM(size);
1124 #endif
1125 }
1126
1127 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1128 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::asanBufferSizeWillChangeTo(size_t newSize)
1129 {
1130 #if ASAN_ENABLED
1131     if (!buffer())
1132         return;
1133
1134     // Change allowed range.
1135     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1136 #else
1137     UNUSED_PARAM(newSize);
1138 #endif
1139 }
1140
1141 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1142 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::reserveCapacity(size_t newCapacity)
1143 {
1144     if (newCapacity <= capacity())
1145         return;
1146     T* oldBuffer = begin();
1147     T* oldEnd = end();
1148
1149     asanSetBufferSizeToFullCapacity();
1150
1151     Base::allocateBuffer(newCapacity);
1152     ASSERT(begin());
1153
1154     asanSetInitialBufferSizeTo(size());
1155
1156     TypeOperations::move(oldBuffer, oldEnd, begin());
1157     Base::deallocateBuffer(oldBuffer);
1158 }
1159
1160 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1161 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryReserveCapacity(size_t newCapacity)
1162 {
1163     if (newCapacity <= capacity())
1164         return true;
1165     T* oldBuffer = begin();
1166     T* oldEnd = end();
1167
1168     asanSetBufferSizeToFullCapacity();
1169
1170     if (!Base::tryAllocateBuffer(newCapacity)) {
1171         asanSetInitialBufferSizeTo(size());
1172         return false;
1173     }
1174     ASSERT(begin());
1175
1176     asanSetInitialBufferSizeTo(size());
1177
1178     TypeOperations::move(oldBuffer, oldEnd, begin());
1179     Base::deallocateBuffer(oldBuffer);
1180     return true;
1181 }
1182
1183 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1184 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::reserveInitialCapacity(size_t initialCapacity)
1185 {
1186     ASSERT(!m_size);
1187     ASSERT(capacity() == inlineCapacity);
1188     if (initialCapacity > inlineCapacity)
1189         Base::allocateBuffer(initialCapacity);
1190 }
1191
1192 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1193 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::shrinkCapacity(size_t newCapacity)
1194 {
1195     if (newCapacity >= capacity())
1196         return;
1197
1198     if (newCapacity < size()) 
1199         shrink(newCapacity);
1200
1201     asanSetBufferSizeToFullCapacity();
1202
1203     T* oldBuffer = begin();
1204     if (newCapacity > 0) {
1205         if (Base::shouldReallocateBuffer(newCapacity)) {
1206             Base::reallocateBuffer(newCapacity);
1207             asanSetInitialBufferSizeTo(size());
1208             return;
1209         }
1210
1211         T* oldEnd = end();
1212         Base::allocateBuffer(newCapacity);
1213         if (begin() != oldBuffer)
1214             TypeOperations::move(oldBuffer, oldEnd, begin());
1215     }
1216
1217     Base::deallocateBuffer(oldBuffer);
1218     Base::restoreInlineBufferIfNeeded();
1219
1220     asanSetInitialBufferSizeTo(size());
1221 }
1222
1223 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1224 template<typename U>
1225 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::append(const U* data, size_t dataSize)
1226 {
1227     size_t newSize = m_size + dataSize;
1228     if (newSize > capacity()) {
1229         data = expandCapacity(newSize, data);
1230         ASSERT(begin());
1231     }
1232     if (newSize < m_size)
1233         CRASH();
1234     asanBufferSizeWillChangeTo(newSize);
1235     T* dest = end();
1236     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1237     m_size = newSize;
1238 }
1239
1240 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1241 template<typename U>
1242 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryAppend(const U* data, size_t dataSize)
1243 {
1244     size_t newSize = m_size + dataSize;
1245     if (newSize > capacity()) {
1246         data = tryExpandCapacity(newSize, data);
1247         if (!data)
1248             return false;
1249         ASSERT(begin());
1250     }
1251     if (newSize < m_size)
1252         return false;
1253     asanBufferSizeWillChangeTo(newSize);
1254     T* dest = end();
1255     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1256     m_size = newSize;
1257     return true;
1258 }
1259
1260 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1261 template<typename U>
1262 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::append(U&& value)
1263 {
1264     if (size() != capacity()) {
1265         asanBufferSizeWillChangeTo(m_size + 1);
1266         new (NotNull, end()) T(std::forward<U>(value));
1267         ++m_size;
1268         return;
1269     }
1270
1271     appendSlowCase(std::forward<U>(value));
1272 }
1273
1274 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1275 template<typename... Args>
1276 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::constructAndAppend(Args&&... args)
1277 {
1278     if (size() != capacity()) {
1279         asanBufferSizeWillChangeTo(m_size + 1);
1280         new (NotNull, end()) T(std::forward<Args>(args)...);
1281         ++m_size;
1282         return;
1283     }
1284
1285     constructAndAppendSlowCase(std::forward<Args>(args)...);
1286 }
1287
1288 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1289 template<typename... Args>
1290 ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryConstructAndAppend(Args&&... args)
1291 {
1292     if (size() != capacity()) {
1293         asanBufferSizeWillChangeTo(m_size + 1);
1294         new (NotNull, end()) T(std::forward<Args>(args)...);
1295         ++m_size;
1296         return true;
1297     }
1298     
1299     return tryConstructAndAppendSlowCase(std::forward<Args>(args)...);
1300 }
1301
1302 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1303 template<typename U>
1304 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::appendSlowCase(U&& value)
1305 {
1306     ASSERT(size() == capacity());
1307
1308     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1309     ptr = expandCapacity(size() + 1, ptr);
1310     ASSERT(begin());
1311
1312     asanBufferSizeWillChangeTo(m_size + 1);
1313     new (NotNull, end()) T(std::forward<U>(*ptr));
1314     ++m_size;
1315 }
1316
1317 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1318 template<typename... Args>
1319 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::constructAndAppendSlowCase(Args&&... args)
1320 {
1321     ASSERT(size() == capacity());
1322
1323     expandCapacity(size() + 1);
1324     ASSERT(begin());
1325
1326     asanBufferSizeWillChangeTo(m_size + 1);
1327     new (NotNull, end()) T(std::forward<Args>(args)...);
1328     ++m_size;
1329 }
1330
1331 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1332 template<typename... Args>
1333 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::tryConstructAndAppendSlowCase(Args&&... args)
1334 {
1335     ASSERT(size() == capacity());
1336     
1337     if (UNLIKELY(!tryExpandCapacity(size() + 1)))
1338         return false;
1339     ASSERT(begin());
1340     
1341     asanBufferSizeWillChangeTo(m_size + 1);
1342     new (NotNull, end()) T(std::forward<Args>(args)...);
1343     ++m_size;
1344     return true;
1345 }
1346
1347 // This version of append saves a branch in the case where you know that the
1348 // vector's capacity is large enough for the append to succeed.
1349
1350 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1351 template<typename U>
1352 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::uncheckedAppend(U&& value)
1353 {
1354     ASSERT(size() < capacity());
1355
1356     asanBufferSizeWillChangeTo(m_size + 1);
1357
1358     new (NotNull, end()) T(std::forward<U>(value));
1359     ++m_size;
1360 }
1361
1362 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1363 template<typename U, size_t otherCapacity>
1364 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::appendVector(const Vector<U, otherCapacity>& val)
1365 {
1366     append(val.begin(), val.size());
1367 }
1368
1369 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1370 template<typename U>
1371 void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::insert(size_t position, const U* data, size_t dataSize)
1372 {
1373     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1374     size_t newSize = m_size + dataSize;
1375     if (newSize > capacity()) {
1376         data = expandCapacity(newSize, data);
1377         ASSERT(begin());
1378     }
1379     if (newSize < m_size)
1380         CRASH();
1381     asanBufferSizeWillChangeTo(newSize);
1382     T* spot = begin() + position;
1383     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1384     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1385     m_size = newSize;
1386 }
1387  
1388 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1389 template<typename U>
1390 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::insert(size_t position, U&& value)
1391 {
1392     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1393
1394     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1395     if (size() == capacity()) {
1396         ptr = expandCapacity(size() + 1, ptr);
1397         ASSERT(begin());
1398     }
1399
1400     asanBufferSizeWillChangeTo(m_size + 1);
1401
1402     T* spot = begin() + position;
1403     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1404     new (NotNull, spot) T(std::forward<U>(*ptr));
1405     ++m_size;
1406 }
1407
1408 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1409 template<typename U, size_t c>
1410 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::insertVector(size_t position, const Vector<U, c>& val)
1411 {
1412     insert(position, val.begin(), val.size());
1413 }
1414
1415 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1416 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::remove(size_t position)
1417 {
1418     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1419     T* spot = begin() + position;
1420     spot->~T();
1421     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1422     asanBufferSizeWillChangeTo(m_size - 1);
1423     --m_size;
1424 }
1425
1426 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1427 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::remove(size_t position, size_t length)
1428 {
1429     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1430     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1431     T* beginSpot = begin() + position;
1432     T* endSpot = beginSpot + length;
1433     TypeOperations::destruct(beginSpot, endSpot); 
1434     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1435     asanBufferSizeWillChangeTo(m_size - length);
1436     m_size -= length;
1437 }
1438
1439 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1440 template<typename U>
1441 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::removeFirst(const U& value)
1442 {
1443     return removeFirstMatching([&value] (const T& current) {
1444         return current == value;
1445     });
1446 }
1447
1448 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1449 template<typename MatchFunction>
1450 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::removeFirstMatching(const MatchFunction& matches, size_t startIndex)
1451 {
1452     for (size_t i = startIndex; i < size(); ++i) {
1453         if (matches(at(i))) {
1454             remove(i);
1455             return true;
1456         }
1457     }
1458     return false;
1459 }
1460
1461 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1462 template<typename U>
1463 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::removeAll(const U& value)
1464 {
1465     return removeAllMatching([&value] (const T& current) {
1466         return current == value;
1467     });
1468 }
1469
1470 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1471 template<typename MatchFunction>
1472 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::removeAllMatching(const MatchFunction& matches, size_t startIndex)
1473 {
1474     iterator holeBegin = end();
1475     iterator holeEnd = end();
1476     unsigned matchCount = 0;
1477     for (auto it = begin() + startIndex, itEnd = end(); it < itEnd; ++it) {
1478         if (matches(*it)) {
1479             if (holeBegin == end())
1480                 holeBegin = it;
1481             else if (holeEnd != it) {
1482                 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1483                 holeBegin += it - holeEnd;
1484             }
1485             holeEnd = it + 1;
1486             it->~T();
1487             ++matchCount;
1488         }
1489     }
1490     if (holeEnd != end())
1491         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1492     asanBufferSizeWillChangeTo(m_size - matchCount);
1493     m_size -= matchCount;
1494     return matchCount;
1495 }
1496
1497 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1498 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::reverse()
1499 {
1500     for (size_t i = 0; i < m_size / 2; ++i)
1501         std::swap(at(i), at(m_size - 1 - i));
1502 }
1503
1504 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1505 template<typename MapFunction, typename R>
1506 inline Vector<R> Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::map(MapFunction mapFunction) const
1507 {
1508     Vector<R> result;
1509     result.reserveInitialCapacity(size());
1510     for (size_t i = 0; i < size(); ++i)
1511         result.uncheckedAppend(mapFunction(at(i)));
1512     return result;
1513 }
1514
1515 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1516 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::releaseBuffer()
1517 {
1518     // FIXME: Find a way to preserve annotations on the returned buffer.
1519     // ASan requires that all annotations are removed before deallocation,
1520     // and MallocPtr doesn't implement that.
1521     asanSetBufferSizeToFullCapacity();
1522
1523     auto buffer = Base::releaseBuffer();
1524     if (inlineCapacity && !buffer && m_size) {
1525         // If the vector had some data, but no buffer to release,
1526         // that means it was using the inline buffer. In that case,
1527         // we create a brand new buffer so the caller always gets one.
1528         size_t bytes = m_size * sizeof(T);
1529         buffer = adoptMallocPtr(static_cast<T*>(Malloc::malloc(bytes)));
1530         memcpy(buffer.get(), data(), bytes);
1531     }
1532     m_size = 0;
1533     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1534     return buffer;
1535 }
1536
1537 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1538 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::checkConsistency()
1539 {
1540 #if !ASSERT_DISABLED
1541     for (size_t i = 0; i < size(); ++i)
1542         ValueCheck<T>::checkConsistency(at(i));
1543 #endif
1544 }
1545
1546 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1547 inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& b)
1548 {
1549     a.swap(b);
1550 }
1551
1552 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1553 bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& b)
1554 {
1555     if (a.size() != b.size())
1556         return false;
1557
1558     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1559 }
1560
1561 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1562 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& b)
1563 {
1564     return !(a == b);
1565 }
1566
1567 #if !ASSERT_DISABLED
1568 template<typename T> struct ValueCheck<Vector<T>> {
1569     typedef Vector<T> TraitType;
1570     static void checkConsistency(const Vector<T>& v)
1571     {
1572         v.checkConsistency();
1573     }
1574 };
1575 #endif
1576
1577 template<typename VectorType, typename Func>
1578 size_t removeRepeatedElements(VectorType& vector, const Func& func)
1579 {
1580     auto end = std::unique(vector.begin(), vector.end(), func);
1581     size_t newSize = end - vector.begin();
1582     vector.shrink(newSize);
1583     return newSize;
1584 }
1585
1586 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
1587 size_t removeRepeatedElements(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& vector)
1588 {
1589     return removeRepeatedElements(vector, [] (T& a, T& b) { return a == b; });
1590 }
1591
1592 template<typename SourceType>
1593 struct CollectionInspector {
1594     using RealSourceType = typename std::remove_reference<SourceType>::type;
1595     using IteratorType = decltype(std::begin(std::declval<RealSourceType>()));
1596     using SourceItemType = typename std::iterator_traits<IteratorType>::value_type;
1597 };
1598
1599 template<typename MapFunction, typename SourceType, typename Enable = void>
1600 struct Mapper {
1601     using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1602     using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&)>::type;
1603
1604     static Vector<DestinationItemType> map(SourceType source, const MapFunction& mapFunction)
1605     {
1606         Vector<DestinationItemType> result;
1607         // FIXME: Use std::size when available on all compilers.
1608         result.reserveInitialCapacity(source.size());
1609         for (auto& item : source)
1610             result.uncheckedAppend(mapFunction(item));
1611         return result;
1612     }
1613 };
1614
1615 template<typename MapFunction, typename SourceType>
1616 struct Mapper<MapFunction, SourceType, typename std::enable_if<std::is_rvalue_reference<SourceType&&>::value>::type> {
1617     using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1618     using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&&)>::type;
1619
1620     static Vector<DestinationItemType> map(SourceType&& source, const MapFunction& mapFunction)
1621     {
1622         Vector<DestinationItemType> result;
1623         // FIXME: Use std::size when available on all compilers.
1624         result.reserveInitialCapacity(source.size());
1625         for (auto& item : source)
1626             result.uncheckedAppend(mapFunction(WTFMove(item)));
1627         return result;
1628     }
1629 };
1630
1631 template<typename MapFunction, typename SourceType>
1632 Vector<typename Mapper<MapFunction, SourceType>::DestinationItemType> map(SourceType&& source, MapFunction&& mapFunction)
1633 {
1634     return Mapper<MapFunction, SourceType>::map(std::forward<SourceType>(source), std::forward<MapFunction>(mapFunction));
1635 }
1636
1637 template<typename DestinationItemType, typename Collection>
1638 inline auto copyToVectorOf(const Collection& collection) -> Vector<DestinationItemType>
1639 {
1640     return WTF::map(collection, [] (const auto& v) -> DestinationItemType { return v; });
1641 }
1642
1643 template<typename Collection>
1644 struct CopyToVectorResult {
1645     using Type = typename std::remove_cv<typename CollectionInspector<Collection>::SourceItemType>::type;
1646 };
1647
1648 template<typename Collection>
1649 inline auto copyToVector(const Collection& collection) -> Vector<typename CopyToVectorResult<Collection>::Type>
1650 {
1651     return copyToVectorOf<typename CopyToVectorResult<Collection>::Type>(collection);
1652 }
1653
1654 } // namespace WTF
1655
1656 using WTF::UnsafeVectorOverflow;
1657 using WTF::Vector;
1658 using WTF::copyToVector;
1659 using WTF::copyToVectorOf;
1660 using WTF::removeRepeatedElements;
1661
1662 #endif // WTF_Vector_h