Make Vector::takeLast work with move-only types (and optimize for types where move...
[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 namespace WTF {
38
39 const size_t notFound = static_cast<size_t>(-1);
40
41 template <bool needsDestruction, typename T>
42 struct VectorDestructor;
43
44 template<typename T>
45 struct VectorDestructor<false, T>
46 {
47     static void destruct(T*, T*) {}
48 };
49
50 template<typename T>
51 struct VectorDestructor<true, T>
52 {
53     static void destruct(T* begin, T* end) 
54     {
55         for (T* cur = begin; cur != end; ++cur)
56             cur->~T();
57     }
58 };
59
60 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
61 struct VectorInitializer;
62
63 template<bool ignore, typename T>
64 struct VectorInitializer<false, ignore, T>
65 {
66     static void initialize(T*, T*) {}
67 };
68
69 template<typename T>
70 struct VectorInitializer<true, false, T>
71 {
72     static void initialize(T* begin, T* end) 
73     {
74         for (T* cur = begin; cur != end; ++cur)
75             new (NotNull, cur) T;
76     }
77 };
78
79 template<typename T>
80 struct VectorInitializer<true, true, T>
81 {
82     static void initialize(T* begin, T* end) 
83     {
84         memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
85     }
86 };
87
88 template <bool canMoveWithMemcpy, typename T>
89 struct VectorMover;
90
91 template<typename T>
92 struct VectorMover<false, T>
93 {
94     static void move(T* src, T* srcEnd, T* dst)
95     {
96         while (src != srcEnd) {
97             new (NotNull, dst) T(std::move(*src));
98             src->~T();
99             ++dst;
100             ++src;
101         }
102     }
103     static void moveOverlapping(T* src, T* srcEnd, T* dst)
104     {
105         if (src > dst)
106             move(src, srcEnd, dst);
107         else {
108             T* dstEnd = dst + (srcEnd - src);
109             while (src != srcEnd) {
110                 --srcEnd;
111                 --dstEnd;
112                 new (NotNull, dstEnd) T(std::move(*srcEnd));
113                 srcEnd->~T();
114             }
115         }
116     }
117 };
118
119 template<typename T>
120 struct VectorMover<true, T>
121 {
122     static void move(const T* src, const T* srcEnd, T* dst) 
123     {
124         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
125     }
126     static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
127     {
128         memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
129     }
130 };
131
132 template <bool canCopyWithMemcpy, typename T>
133 struct VectorCopier;
134
135 template<typename T>
136 struct VectorCopier<false, T>
137 {
138     template<typename U>
139     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
140     {
141         while (src != srcEnd) {
142             new (NotNull, dst) U(*src);
143             ++dst;
144             ++src;
145         }
146     }
147 };
148
149 template<typename T>
150 struct VectorCopier<true, T>
151 {
152     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
153     {
154         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
155     }
156     template<typename U>
157     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
158     {
159         VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst);
160     }
161 };
162
163 template <bool canFillWithMemset, typename T>
164 struct VectorFiller;
165
166 template<typename T>
167 struct VectorFiller<false, T>
168 {
169     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
170     {
171         while (dst != dstEnd) {
172             new (NotNull, dst) T(val);
173             ++dst;
174         }
175     }
176 };
177
178 template<typename T>
179 struct VectorFiller<true, T>
180 {
181     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
182     {
183         static_assert(sizeof(T) == 1, "Size of type T should be equal to one!");
184 #if COMPILER(GCC) && defined(_FORTIFY_SOURCE)
185         if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst)))
186 #endif
187             memset(dst, val, dstEnd - dst);
188     }
189 };
190
191 template<bool canCompareWithMemcmp, typename T>
192 struct VectorComparer;
193
194 template<typename T>
195 struct VectorComparer<false, T>
196 {
197     static bool compare(const T* a, const T* b, size_t size)
198     {
199         for (size_t i = 0; i < size; ++i)
200             if (!(a[i] == b[i]))
201                 return false;
202         return true;
203     }
204 };
205
206 template<typename T>
207 struct VectorComparer<true, T>
208 {
209     static bool compare(const T* a, const T* b, size_t size)
210     {
211         return memcmp(a, b, sizeof(T) * size) == 0;
212     }
213 };
214
215 template<typename T>
216 struct VectorTypeOperations
217 {
218     static void destruct(T* begin, T* end)
219     {
220         VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end);
221     }
222
223     static void initialize(T* begin, T* end)
224     {
225         VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
226     }
227
228     static void move(T* src, T* srcEnd, T* dst)
229     {
230         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
231     }
232
233     static void moveOverlapping(T* src, T* srcEnd, T* dst)
234     {
235         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
236     }
237
238     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
239     {
240         VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
241     }
242
243     static void uninitializedFill(T* dst, T* dstEnd, const T& val)
244     {
245         VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
246     }
247     
248     static bool compare(const T* a, const T* b, size_t size)
249     {
250         return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
251     }
252 };
253
254 template<typename T>
255 class VectorBufferBase {
256     WTF_MAKE_NONCOPYABLE(VectorBufferBase);
257 public:
258     void allocateBuffer(size_t newCapacity)
259     {
260         ASSERT(newCapacity);
261         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
262             CRASH();
263         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
264         m_capacity = sizeToAllocate / sizeof(T);
265         m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate));
266     }
267
268     bool tryAllocateBuffer(size_t newCapacity)
269     {
270         ASSERT(newCapacity);
271         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
272             return false;
273
274         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
275         T* newBuffer;
276         if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) {
277             m_capacity = sizeToAllocate / sizeof(T);
278             m_buffer = newBuffer;
279             return true;
280         }
281         return false;
282     }
283
284     bool shouldReallocateBuffer(size_t newCapacity) const
285     {
286         return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
287     }
288
289     void reallocateBuffer(size_t newCapacity)
290     {
291         ASSERT(shouldReallocateBuffer(newCapacity));
292         if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
293             CRASH();
294         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
295         m_capacity = sizeToAllocate / sizeof(T);
296         m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate));
297     }
298
299     void deallocateBuffer(T* bufferToDeallocate)
300     {
301         if (!bufferToDeallocate)
302             return;
303         
304         if (m_buffer == bufferToDeallocate) {
305             m_buffer = 0;
306             m_capacity = 0;
307         }
308
309         fastFree(bufferToDeallocate);
310     }
311
312     T* buffer() { return m_buffer; }
313     const T* buffer() const { return m_buffer; }
314     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
315     size_t capacity() const { return m_capacity; }
316
317     MallocPtr<T> releaseBuffer()
318     {
319         T* buffer = m_buffer;
320         m_buffer = 0;
321         m_capacity = 0;
322         return adoptMallocPtr(buffer);
323     }
324
325 protected:
326     VectorBufferBase()
327         : m_buffer(0)
328         , m_capacity(0)
329         , m_size(0)
330     {
331     }
332
333     VectorBufferBase(T* buffer, size_t capacity, size_t size)
334         : m_buffer(buffer)
335         , m_capacity(capacity)
336         , m_size(size)
337     {
338     }
339
340     ~VectorBufferBase()
341     {
342         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
343     }
344
345     T* m_buffer;
346     unsigned m_capacity;
347     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
348 };
349
350 template<typename T, size_t inlineCapacity>
351 class VectorBuffer;
352
353 template<typename T>
354 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
355 private:
356     typedef VectorBufferBase<T> Base;
357 public:
358     VectorBuffer()
359     {
360     }
361
362     VectorBuffer(size_t capacity, size_t size = 0)
363     {
364         m_size = size;
365         // Calling malloc(0) might take a lock and may actually do an
366         // allocation on some systems.
367         if (capacity)
368             allocateBuffer(capacity);
369     }
370
371     ~VectorBuffer()
372     {
373         deallocateBuffer(buffer());
374     }
375     
376     void swap(VectorBuffer<T, 0>& other, size_t, size_t)
377     {
378         std::swap(m_buffer, other.m_buffer);
379         std::swap(m_capacity, other.m_capacity);
380     }
381     
382     void restoreInlineBufferIfNeeded() { }
383
384     using Base::allocateBuffer;
385     using Base::tryAllocateBuffer;
386     using Base::shouldReallocateBuffer;
387     using Base::reallocateBuffer;
388     using Base::deallocateBuffer;
389
390     using Base::buffer;
391     using Base::capacity;
392     using Base::bufferMemoryOffset;
393
394     using Base::releaseBuffer;
395
396 protected:
397     using Base::m_size;
398
399 private:
400     using Base::m_buffer;
401     using Base::m_capacity;
402 };
403
404 template<typename T, size_t inlineCapacity>
405 class VectorBuffer : private VectorBufferBase<T> {
406     WTF_MAKE_NONCOPYABLE(VectorBuffer);
407 private:
408     typedef VectorBufferBase<T> Base;
409 public:
410     VectorBuffer()
411         : Base(inlineBuffer(), inlineCapacity, 0)
412     {
413     }
414
415     VectorBuffer(size_t capacity, size_t size = 0)
416         : Base(inlineBuffer(), inlineCapacity, size)
417     {
418         if (capacity > inlineCapacity)
419             Base::allocateBuffer(capacity);
420     }
421
422     ~VectorBuffer()
423     {
424         deallocateBuffer(buffer());
425     }
426
427     void allocateBuffer(size_t newCapacity)
428     {
429         // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
430         if (newCapacity > inlineCapacity)
431             Base::allocateBuffer(newCapacity);
432         else {
433             m_buffer = inlineBuffer();
434             m_capacity = inlineCapacity;
435         }
436     }
437
438     bool tryAllocateBuffer(size_t newCapacity)
439     {
440         if (newCapacity > inlineCapacity)
441             return Base::tryAllocateBuffer(newCapacity);
442         m_buffer = inlineBuffer();
443         m_capacity = inlineCapacity;
444         return true;
445     }
446
447     void deallocateBuffer(T* bufferToDeallocate)
448     {
449         if (bufferToDeallocate == inlineBuffer())
450             return;
451         Base::deallocateBuffer(bufferToDeallocate);
452     }
453
454     bool shouldReallocateBuffer(size_t newCapacity) const
455     {
456         // We cannot reallocate the inline buffer.
457         return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
458     }
459
460     void reallocateBuffer(size_t newCapacity)
461     {
462         ASSERT(shouldReallocateBuffer(newCapacity));
463         Base::reallocateBuffer(newCapacity);
464     }
465
466     void swap(VectorBuffer& other, size_t mySize, size_t otherSize)
467     {
468         if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
469             swapInlineBuffer(other, mySize, otherSize);
470             std::swap(m_capacity, other.m_capacity);
471         } else if (buffer() == inlineBuffer()) {
472             m_buffer = other.m_buffer;
473             other.m_buffer = other.inlineBuffer();
474             swapInlineBuffer(other, mySize, 0);
475             std::swap(m_capacity, other.m_capacity);
476         } else if (other.buffer() == other.inlineBuffer()) {
477             other.m_buffer = m_buffer;
478             m_buffer = inlineBuffer();
479             swapInlineBuffer(other, 0, otherSize);
480             std::swap(m_capacity, other.m_capacity);
481         } else {
482             std::swap(m_buffer, other.m_buffer);
483             std::swap(m_capacity, other.m_capacity);
484         }
485     }
486
487     void restoreInlineBufferIfNeeded()
488     {
489         if (m_buffer)
490             return;
491         m_buffer = inlineBuffer();
492         m_capacity = inlineCapacity;
493     }
494
495     using Base::buffer;
496     using Base::capacity;
497     using Base::bufferMemoryOffset;
498
499     MallocPtr<T> releaseBuffer()
500     {
501         if (buffer() == inlineBuffer())
502             return nullptr;
503         return Base::releaseBuffer();
504     }
505
506 protected:
507     using Base::m_size;
508
509 private:
510     using Base::m_buffer;
511     using Base::m_capacity;
512     
513     void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize)
514     {
515         // FIXME: We could make swap part of VectorTypeOperations
516         // https://bugs.webkit.org/show_bug.cgi?id=128863
517         
518         if (std::is_pod<T>::value)
519             std::swap(m_inlineBuffer, other.m_inlineBuffer);
520         else
521             swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
522     }
523     
524     static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
525     {
526         if (left == right)
527             return;
528         
529         ASSERT(leftSize <= inlineCapacity);
530         ASSERT(rightSize <= inlineCapacity);
531         
532         size_t swapBound = std::min(leftSize, rightSize);
533         for (unsigned i = 0; i < swapBound; ++i)
534             std::swap(left[i], right[i]);
535         VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
536         VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
537     }
538
539     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
540     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
541
542     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
543 };
544
545 struct UnsafeVectorOverflow {
546     static NO_RETURN_DUE_TO_ASSERT void overflowed()
547     {
548         ASSERT_NOT_REACHED();
549     }
550 };
551
552 template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow>
553 class Vector : private VectorBuffer<T, inlineCapacity> {
554     WTF_MAKE_FAST_ALLOCATED;
555 private:
556     typedef VectorBuffer<T, inlineCapacity> Base;
557     typedef VectorTypeOperations<T> TypeOperations;
558
559 public:
560     typedef T ValueType;
561
562     typedef T* iterator;
563     typedef const T* const_iterator;
564     typedef std::reverse_iterator<iterator> reverse_iterator;
565     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
566
567     Vector()
568     {
569     }
570
571     // Unlike in std::vector, this constructor does not initialize POD types.
572     explicit Vector(size_t size)
573         : Base(size, size)
574     {
575         if (begin())
576             TypeOperations::initialize(begin(), end());
577     }
578
579     Vector(size_t size, const T& val)
580         : Base(size, size)
581     {
582         if (begin())
583             TypeOperations::uninitializedFill(begin(), end(), val);
584     }
585
586     Vector(std::initializer_list<T> initializerList)
587     {
588         reserveInitialCapacity(initializerList.size());
589         for (const auto& element : initializerList)
590             uncheckedAppend(element);
591     }
592
593     ~Vector()
594     {
595         if (m_size)
596             shrink(0);
597     }
598
599     Vector(const Vector&);
600     template<size_t otherCapacity, typename otherOverflowBehaviour>
601     Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
602
603     Vector& operator=(const Vector&);
604     template<size_t otherCapacity, typename otherOverflowBehaviour>
605     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
606
607     Vector(Vector&&);
608     Vector& operator=(Vector&&);
609
610     size_t size() const { return m_size; }
611     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
612     size_t capacity() const { return Base::capacity(); }
613     bool isEmpty() const { return !size(); }
614
615     T& at(size_t i)
616     {
617         if (UNLIKELY(i >= size()))
618             OverflowHandler::overflowed();
619         return Base::buffer()[i];
620     }
621     const T& at(size_t i) const 
622     {
623         if (UNLIKELY(i >= size()))
624             OverflowHandler::overflowed();
625         return Base::buffer()[i];
626     }
627     T& at(Checked<size_t> i)
628     {
629         RELEASE_ASSERT(i < size());
630         return Base::buffer()[i];
631     }
632     const T& at(Checked<size_t> i) const
633     {
634         RELEASE_ASSERT(i < size());
635         return Base::buffer()[i];
636     }
637
638     T& operator[](size_t i) { return at(i); }
639     const T& operator[](size_t i) const { return at(i); }
640     T& operator[](Checked<size_t> i) { return at(i); }
641     const T& operator[](Checked<size_t> i) const { return at(i); }
642
643     T* data() { return Base::buffer(); }
644     const T* data() const { return Base::buffer(); }
645     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
646
647     iterator begin() { return data(); }
648     iterator end() { return begin() + m_size; }
649     const_iterator begin() const { return data(); }
650     const_iterator end() const { return begin() + m_size; }
651
652     reverse_iterator rbegin() { return reverse_iterator(end()); }
653     reverse_iterator rend() { return reverse_iterator(begin()); }
654     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
655     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
656
657     T& first() { return at(0); }
658     const T& first() const { return at(0); }
659     T& last() { return at(size() - 1); }
660     const T& last() const { return at(size() - 1); }
661     
662     T takeLast()
663     {
664         T result = std::move(last());
665         removeLast();
666         return result;
667     }
668     
669     template<typename U> bool contains(const U&) const;
670     template<typename U> size_t find(const U&) const;
671     template<typename U> size_t reverseFind(const U&) const;
672
673     void shrink(size_t size);
674     void grow(size_t size);
675     void resize(size_t size);
676     void resizeToFit(size_t size);
677     void reserveCapacity(size_t newCapacity);
678     bool tryReserveCapacity(size_t newCapacity);
679     void reserveInitialCapacity(size_t initialCapacity);
680     void shrinkCapacity(size_t newCapacity);
681     void shrinkToFit() { shrinkCapacity(size()); }
682
683     void clear() { shrinkCapacity(0); }
684
685     template<typename U> void append(const U*, size_t);
686     template<typename U> void append(U&&);
687     template<typename U> void uncheckedAppend(U&& val);
688     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
689     template<typename U> bool tryAppend(const U*, size_t);
690
691     template<typename U> void insert(size_t position, const U*, size_t);
692     template<typename U> void insert(size_t position, U&&);
693     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
694
695     void remove(size_t position);
696     void remove(size_t position, size_t length);
697
698     void removeLast() 
699     {
700         if (UNLIKELY(isEmpty()))
701             OverflowHandler::overflowed();
702         shrink(size() - 1); 
703     }
704
705     void fill(const T&, size_t);
706     void fill(const T& val) { fill(val, size()); }
707
708     template<typename Iterator> void appendRange(Iterator start, Iterator end);
709
710     MallocPtr<T> releaseBuffer();
711
712     void swap(Vector<T, inlineCapacity, OverflowHandler>& other)
713     {
714         Base::swap(other, m_size, other.m_size);
715         std::swap(m_size, other.m_size);
716     }
717
718     void reverse();
719
720     void checkConsistency();
721
722 private:
723     void expandCapacity(size_t newMinCapacity);
724     T* expandCapacity(size_t newMinCapacity, T*);
725     bool tryExpandCapacity(size_t newMinCapacity);
726     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
727     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
728     template<typename U> void appendSlowCase(U&&);
729
730     using Base::m_size;
731     using Base::buffer;
732     using Base::capacity;
733     using Base::swap;
734     using Base::allocateBuffer;
735     using Base::deallocateBuffer;
736     using Base::tryAllocateBuffer;
737     using Base::shouldReallocateBuffer;
738     using Base::reallocateBuffer;
739     using Base::restoreInlineBufferIfNeeded;
740     using Base::releaseBuffer;
741 };
742
743 template<typename T, size_t inlineCapacity, typename OverflowHandler>
744 Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other)
745     : Base(other.capacity(), other.size())
746 {
747     if (begin())
748         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
749 }
750
751 template<typename T, size_t inlineCapacity, typename OverflowHandler>
752 template<size_t otherCapacity, typename otherOverflowBehaviour>
753 Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
754     : Base(other.capacity(), other.size())
755 {
756     if (begin())
757         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
758 }
759
760 template<typename T, size_t inlineCapacity, typename OverflowHandler>
761 Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, inlineCapacity, OverflowHandler>& other)
762 {
763     if (&other == this)
764         return *this;
765     
766     if (size() > other.size())
767         shrink(other.size());
768     else if (other.size() > capacity()) {
769         clear();
770         reserveCapacity(other.size());
771         ASSERT(begin());
772     }
773     
774 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
775 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
776     if (!begin())
777         return *this;
778 #endif
779
780     std::copy(other.begin(), other.begin() + size(), begin());
781     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
782     m_size = other.size();
783
784     return *this;
785 }
786
787 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
788
789 template<typename T, size_t inlineCapacity, typename OverflowHandler>
790 template<size_t otherCapacity, typename otherOverflowBehaviour>
791 Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
792 {
793     // If the inline capacities match, we should call the more specific
794     // template.  If the inline capacities don't match, the two objects
795     // shouldn't be allocated the same address.
796     ASSERT(!typelessPointersAreEqual(&other, this));
797
798     if (size() > other.size())
799         shrink(other.size());
800     else if (other.size() > capacity()) {
801         clear();
802         reserveCapacity(other.size());
803         ASSERT(begin());
804     }
805     
806 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
807 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
808     if (!begin())
809         return *this;
810 #endif
811
812     std::copy(other.begin(), other.begin() + size(), begin());
813     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
814     m_size = other.size();
815
816     return *this;
817 }
818
819 template<typename T, size_t inlineCapacity, typename OverflowHandler>
820 inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other)
821 {
822     swap(other);
823 }
824
825 template<typename T, size_t inlineCapacity, typename OverflowHandler>
826 inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other)
827 {
828     swap(other);
829     return *this;
830 }
831
832 template<typename T, size_t inlineCapacity, typename OverflowHandler>
833 template<typename U>
834 bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const
835 {
836     return find(value) != notFound;
837 }
838
839 template<typename T, size_t inlineCapacity, typename OverflowHandler>
840 template<typename U>
841 size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const
842 {
843     for (size_t i = 0; i < size(); ++i) {
844         if (at(i) == value)
845             return i;
846     }
847     return notFound;
848 }
849
850 template<typename T, size_t inlineCapacity, typename OverflowHandler>
851 template<typename U>
852 size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const
853 {
854     for (size_t i = 1; i <= size(); ++i) {
855         const size_t index = size() - i;
856         if (at(index) == value)
857             return index;
858     }
859     return notFound;
860 }
861
862 template<typename T, size_t inlineCapacity, typename OverflowHandler>
863 void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize)
864 {
865     if (size() > newSize)
866         shrink(newSize);
867     else if (newSize > capacity()) {
868         clear();
869         reserveCapacity(newSize);
870         ASSERT(begin());
871     }
872     
873     std::fill(begin(), end(), val);
874     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
875     m_size = newSize;
876 }
877
878 template<typename T, size_t inlineCapacity, typename OverflowHandler>
879 template<typename Iterator>
880 void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end)
881 {
882     for (Iterator it = start; it != end; ++it)
883         append(*it);
884 }
885
886 template<typename T, size_t inlineCapacity, typename OverflowHandler>
887 void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity)
888 {
889     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
890 }
891
892 template<typename T, size_t inlineCapacity, typename OverflowHandler>
893 T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
894 {
895     if (ptr < begin() || ptr >= end()) {
896         expandCapacity(newMinCapacity);
897         return ptr;
898     }
899     size_t index = ptr - begin();
900     expandCapacity(newMinCapacity);
901     return begin() + index;
902 }
903
904 template<typename T, size_t inlineCapacity, typename OverflowHandler>
905 bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity)
906 {
907     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
908 }
909
910 template<typename T, size_t inlineCapacity, typename OverflowHandler>
911 const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
912 {
913     if (ptr < begin() || ptr >= end()) {
914         if (!tryExpandCapacity(newMinCapacity))
915             return 0;
916         return ptr;
917     }
918     size_t index = ptr - begin();
919     if (!tryExpandCapacity(newMinCapacity))
920         return 0;
921     return begin() + index;
922 }
923
924 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
925 inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr)
926 {
927     expandCapacity(newMinCapacity);
928     return ptr;
929 }
930
931 template<typename T, size_t inlineCapacity, typename OverflowHandler>
932 inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
933 {
934     if (size <= m_size)
935         TypeOperations::destruct(begin() + size, end());
936     else {
937         if (size > capacity())
938             expandCapacity(size);
939         if (begin())
940             TypeOperations::initialize(end(), begin() + size);
941     }
942     
943     m_size = size;
944 }
945
946 template<typename T, size_t inlineCapacity, typename OverflowHandler>
947 void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size)
948 {
949     reserveCapacity(size);
950     resize(size);
951 }
952
953 template<typename T, size_t inlineCapacity, typename OverflowHandler>
954 void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
955 {
956     ASSERT(size <= m_size);
957     TypeOperations::destruct(begin() + size, end());
958     m_size = size;
959 }
960
961 template<typename T, size_t inlineCapacity, typename OverflowHandler>
962 void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
963 {
964     ASSERT(size >= m_size);
965     if (size > capacity())
966         expandCapacity(size);
967     if (begin())
968         TypeOperations::initialize(end(), begin() + size);
969     m_size = size;
970 }
971
972 template<typename T, size_t inlineCapacity, typename OverflowHandler>
973 void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity)
974 {
975     if (newCapacity <= capacity())
976         return;
977     T* oldBuffer = begin();
978     T* oldEnd = end();
979     Base::allocateBuffer(newCapacity);
980     ASSERT(begin());
981     TypeOperations::move(oldBuffer, oldEnd, begin());
982     Base::deallocateBuffer(oldBuffer);
983 }
984
985 template<typename T, size_t inlineCapacity, typename OverflowHandler>
986 bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity)
987 {
988     if (newCapacity <= capacity())
989         return true;
990     T* oldBuffer = begin();
991     T* oldEnd = end();
992     if (!Base::tryAllocateBuffer(newCapacity))
993         return false;
994     ASSERT(begin());
995     TypeOperations::move(oldBuffer, oldEnd, begin());
996     Base::deallocateBuffer(oldBuffer);
997     return true;
998 }
999
1000 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1001 inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity)
1002 {
1003     ASSERT(!m_size);
1004     ASSERT(capacity() == inlineCapacity);
1005     if (initialCapacity > inlineCapacity)
1006         Base::allocateBuffer(initialCapacity);
1007 }
1008
1009 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1010 void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity)
1011 {
1012     if (newCapacity >= capacity())
1013         return;
1014
1015     if (newCapacity < size()) 
1016         shrink(newCapacity);
1017
1018     T* oldBuffer = begin();
1019     if (newCapacity > 0) {
1020         if (Base::shouldReallocateBuffer(newCapacity)) {
1021             Base::reallocateBuffer(newCapacity);
1022             return;
1023         }
1024
1025         T* oldEnd = end();
1026         Base::allocateBuffer(newCapacity);
1027         if (begin() != oldBuffer)
1028             TypeOperations::move(oldBuffer, oldEnd, begin());
1029     }
1030
1031     Base::deallocateBuffer(oldBuffer);
1032     Base::restoreInlineBufferIfNeeded();
1033 }
1034
1035 // Templatizing these is better than just letting the conversion happen implicitly,
1036 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1037 // without refcount thrash.
1038 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1039 void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize)
1040 {
1041     size_t newSize = m_size + dataSize;
1042     if (newSize > capacity()) {
1043         data = expandCapacity(newSize, data);
1044         ASSERT(begin());
1045     }
1046     if (newSize < m_size)
1047         CRASH();
1048     T* dest = end();
1049     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
1050     m_size = newSize;
1051 }
1052
1053 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1054 bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
1055 {
1056     size_t newSize = m_size + dataSize;
1057     if (newSize > capacity()) {
1058         data = tryExpandCapacity(newSize, data);
1059         if (!data)
1060             return false;
1061         ASSERT(begin());
1062     }
1063     if (newSize < m_size)
1064         return false;
1065     T* dest = end();
1066     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
1067     m_size = newSize;
1068     return true;
1069 }
1070
1071 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1072 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
1073 {
1074     if (size() != capacity()) {
1075         new (NotNull, end()) T(std::forward<U>(value));
1076         ++m_size;
1077         return;
1078     }
1079
1080     appendSlowCase(std::forward<U>(value));
1081 }
1082
1083 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1084 void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
1085 {
1086     ASSERT(size() == capacity());
1087
1088     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1089     ptr = expandCapacity(size() + 1, ptr);
1090     ASSERT(begin());
1091
1092     new (NotNull, end()) T(std::forward<U>(*ptr));
1093     ++m_size;
1094 }
1095
1096 // This version of append saves a branch in the case where you know that the
1097 // vector's capacity is large enough for the append to succeed.
1098
1099 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1100 inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value)
1101 {
1102     ASSERT(size() < capacity());
1103
1104     auto ptr = std::addressof(value);
1105     new (NotNull, end()) T(std::forward<U>(*ptr));
1106     ++m_size;
1107 }
1108
1109 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
1110 inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
1111 {
1112     append(val.begin(), val.size());
1113 }
1114
1115 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1116 void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize)
1117 {
1118     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1119     size_t newSize = m_size + dataSize;
1120     if (newSize > capacity()) {
1121         data = expandCapacity(newSize, data);
1122         ASSERT(begin());
1123     }
1124     if (newSize < m_size)
1125         CRASH();
1126     T* spot = begin() + position;
1127     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1128     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], spot);
1129     m_size = newSize;
1130 }
1131  
1132 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1133 inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value)
1134 {
1135     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1136
1137     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1138     if (size() == capacity()) {
1139         ptr = expandCapacity(size() + 1, ptr);
1140         ASSERT(begin());
1141     }
1142
1143     T* spot = begin() + position;
1144     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1145     new (NotNull, spot) T(std::forward<U>(*ptr));
1146     ++m_size;
1147 }
1148
1149 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
1150 inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
1151 {
1152     insert(position, val.begin(), val.size());
1153 }
1154
1155 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1156 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
1157 {
1158     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1159     T* spot = begin() + position;
1160     spot->~T();
1161     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1162     --m_size;
1163 }
1164
1165 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1166 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length)
1167 {
1168     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1169     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1170     T* beginSpot = begin() + position;
1171     T* endSpot = beginSpot + length;
1172     TypeOperations::destruct(beginSpot, endSpot); 
1173     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1174     m_size -= length;
1175 }
1176
1177 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1178 inline void Vector<T, inlineCapacity, OverflowHandler>::reverse()
1179 {
1180     for (size_t i = 0; i < m_size / 2; ++i)
1181         std::swap(at(i), at(m_size - 1 - i));
1182 }
1183
1184 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1185 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer()
1186 {
1187     auto buffer = Base::releaseBuffer();
1188     if (inlineCapacity && !buffer && m_size) {
1189         // If the vector had some data, but no buffer to release,
1190         // that means it was using the inline buffer. In that case,
1191         // we create a brand new buffer so the caller always gets one.
1192         size_t bytes = m_size * sizeof(T);
1193         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1194         memcpy(buffer.get(), data(), bytes);
1195     }
1196     m_size = 0;
1197     return buffer;
1198 }
1199
1200 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1201 inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency()
1202 {
1203 #if !ASSERT_DISABLED
1204     for (size_t i = 0; i < size(); ++i)
1205         ValueCheck<T>::checkConsistency(at(i));
1206 #endif
1207 }
1208
1209 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1210 void deprecatedDeleteAllValues(const Vector<T, inlineCapacity, OverflowHandler>& collection)
1211 {
1212     typedef typename Vector<T, inlineCapacity, OverflowHandler>::const_iterator iterator;
1213     iterator end = collection.end();
1214     for (iterator it = collection.begin(); it != end; ++it)
1215         delete *it;
1216 }
1217
1218 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1219 inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b)
1220 {
1221     a.swap(b);
1222 }
1223
1224 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1225 bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1226 {
1227     if (a.size() != b.size())
1228         return false;
1229
1230     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1231 }
1232
1233 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1234 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1235 {
1236     return !(a == b);
1237 }
1238
1239 #if !ASSERT_DISABLED
1240 template<typename T> struct ValueCheck<Vector<T>> {
1241     typedef Vector<T> TraitType;
1242     static void checkConsistency(const Vector<T>& v)
1243     {
1244         v.checkConsistency();
1245     }
1246 };
1247 #endif
1248
1249 } // namespace WTF
1250
1251 using WTF::Vector;
1252 using WTF::UnsafeVectorOverflow;
1253 using WTF::notFound;
1254
1255 #endif // WTF_Vector_h