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