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