Unreviewed, rolling out r177284.
[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(WTF::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(WTF::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 = WTF::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     std::copy(other.begin(), other.begin() + size(), begin());
775     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
776     m_size = other.size();
777
778     return *this;
779 }
780
781 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
782
783 template<typename T, size_t inlineCapacity, typename OverflowHandler>
784 template<size_t otherCapacity, typename otherOverflowBehaviour>
785 Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
786 {
787     // If the inline capacities match, we should call the more specific
788     // template.  If the inline capacities don't match, the two objects
789     // shouldn't be allocated the same address.
790     ASSERT(!typelessPointersAreEqual(&other, this));
791
792     if (size() > other.size())
793         shrink(other.size());
794     else if (other.size() > capacity()) {
795         clear();
796         reserveCapacity(other.size());
797         ASSERT(begin());
798     }
799     
800     std::copy(other.begin(), other.begin() + size(), begin());
801     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
802     m_size = other.size();
803
804     return *this;
805 }
806
807 template<typename T, size_t inlineCapacity, typename OverflowHandler>
808 inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other)
809 {
810     swap(other);
811 }
812
813 template<typename T, size_t inlineCapacity, typename OverflowHandler>
814 inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other)
815 {
816     swap(other);
817     return *this;
818 }
819
820 template<typename T, size_t inlineCapacity, typename OverflowHandler>
821 template<typename U>
822 bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const
823 {
824     return find(value) != notFound;
825 }
826
827 template<typename T, size_t inlineCapacity, typename OverflowHandler>
828 template<typename U>
829 size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const
830 {
831     for (size_t i = 0; i < size(); ++i) {
832         if (at(i) == value)
833             return i;
834     }
835     return notFound;
836 }
837
838 template<typename T, size_t inlineCapacity, typename OverflowHandler>
839 template<typename U>
840 size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const
841 {
842     for (size_t i = 1; i <= size(); ++i) {
843         const size_t index = size() - i;
844         if (at(index) == value)
845             return index;
846     }
847     return notFound;
848 }
849
850 template<typename T, size_t inlineCapacity, typename OverflowHandler>
851 void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize)
852 {
853     if (size() > newSize)
854         shrink(newSize);
855     else if (newSize > capacity()) {
856         clear();
857         reserveCapacity(newSize);
858         ASSERT(begin());
859     }
860     
861     std::fill(begin(), end(), val);
862     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
863     m_size = newSize;
864 }
865
866 template<typename T, size_t inlineCapacity, typename OverflowHandler>
867 template<typename Iterator>
868 void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end)
869 {
870     for (Iterator it = start; it != end; ++it)
871         append(*it);
872 }
873
874 template<typename T, size_t inlineCapacity, typename OverflowHandler>
875 void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity)
876 {
877     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
878 }
879
880 template<typename T, size_t inlineCapacity, typename OverflowHandler>
881 T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
882 {
883     if (ptr < begin() || ptr >= end()) {
884         expandCapacity(newMinCapacity);
885         return ptr;
886     }
887     size_t index = ptr - begin();
888     expandCapacity(newMinCapacity);
889     return begin() + index;
890 }
891
892 template<typename T, size_t inlineCapacity, typename OverflowHandler>
893 bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity)
894 {
895     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
896 }
897
898 template<typename T, size_t inlineCapacity, typename OverflowHandler>
899 const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
900 {
901     if (ptr < begin() || ptr >= end()) {
902         if (!tryExpandCapacity(newMinCapacity))
903             return 0;
904         return ptr;
905     }
906     size_t index = ptr - begin();
907     if (!tryExpandCapacity(newMinCapacity))
908         return 0;
909     return begin() + index;
910 }
911
912 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
913 inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr)
914 {
915     expandCapacity(newMinCapacity);
916     return ptr;
917 }
918
919 template<typename T, size_t inlineCapacity, typename OverflowHandler>
920 inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
921 {
922     if (size <= m_size)
923         TypeOperations::destruct(begin() + size, end());
924     else {
925         if (size > capacity())
926             expandCapacity(size);
927         if (begin())
928             TypeOperations::initialize(end(), begin() + size);
929     }
930     
931     m_size = size;
932 }
933
934 template<typename T, size_t inlineCapacity, typename OverflowHandler>
935 void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size)
936 {
937     reserveCapacity(size);
938     resize(size);
939 }
940
941 template<typename T, size_t inlineCapacity, typename OverflowHandler>
942 void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
943 {
944     ASSERT(size <= m_size);
945     TypeOperations::destruct(begin() + size, end());
946     m_size = size;
947 }
948
949 template<typename T, size_t inlineCapacity, typename OverflowHandler>
950 void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
951 {
952     ASSERT(size >= m_size);
953     if (size > capacity())
954         expandCapacity(size);
955     if (begin())
956         TypeOperations::initialize(end(), begin() + size);
957     m_size = size;
958 }
959
960 template<typename T, size_t inlineCapacity, typename OverflowHandler>
961 void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity)
962 {
963     if (newCapacity <= capacity())
964         return;
965     T* oldBuffer = begin();
966     T* oldEnd = end();
967     Base::allocateBuffer(newCapacity);
968     ASSERT(begin());
969     TypeOperations::move(oldBuffer, oldEnd, begin());
970     Base::deallocateBuffer(oldBuffer);
971 }
972
973 template<typename T, size_t inlineCapacity, typename OverflowHandler>
974 bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity)
975 {
976     if (newCapacity <= capacity())
977         return true;
978     T* oldBuffer = begin();
979     T* oldEnd = end();
980     if (!Base::tryAllocateBuffer(newCapacity))
981         return false;
982     ASSERT(begin());
983     TypeOperations::move(oldBuffer, oldEnd, begin());
984     Base::deallocateBuffer(oldBuffer);
985     return true;
986 }
987
988 template<typename T, size_t inlineCapacity, typename OverflowHandler>
989 inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity)
990 {
991     ASSERT(!m_size);
992     ASSERT(capacity() == inlineCapacity);
993     if (initialCapacity > inlineCapacity)
994         Base::allocateBuffer(initialCapacity);
995 }
996
997 template<typename T, size_t inlineCapacity, typename OverflowHandler>
998 void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity)
999 {
1000     if (newCapacity >= capacity())
1001         return;
1002
1003     if (newCapacity < size()) 
1004         shrink(newCapacity);
1005
1006     T* oldBuffer = begin();
1007     if (newCapacity > 0) {
1008         if (Base::shouldReallocateBuffer(newCapacity)) {
1009             Base::reallocateBuffer(newCapacity);
1010             return;
1011         }
1012
1013         T* oldEnd = end();
1014         Base::allocateBuffer(newCapacity);
1015         if (begin() != oldBuffer)
1016             TypeOperations::move(oldBuffer, oldEnd, begin());
1017     }
1018
1019     Base::deallocateBuffer(oldBuffer);
1020     Base::restoreInlineBufferIfNeeded();
1021 }
1022
1023 // Templatizing these is better than just letting the conversion happen implicitly,
1024 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1025 // without refcount thrash.
1026 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1027 void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize)
1028 {
1029     size_t newSize = m_size + dataSize;
1030     if (newSize > capacity()) {
1031         data = expandCapacity(newSize, data);
1032         ASSERT(begin());
1033     }
1034     if (newSize < m_size)
1035         CRASH();
1036     T* dest = end();
1037     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
1038     m_size = newSize;
1039 }
1040
1041 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1042 bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
1043 {
1044     size_t newSize = m_size + dataSize;
1045     if (newSize > capacity()) {
1046         data = tryExpandCapacity(newSize, data);
1047         if (!data)
1048             return false;
1049         ASSERT(begin());
1050     }
1051     if (newSize < m_size)
1052         return false;
1053     T* dest = end();
1054     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], dest);
1055     m_size = newSize;
1056     return true;
1057 }
1058
1059 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1060 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
1061 {
1062     if (size() != capacity()) {
1063         new (NotNull, end()) T(std::forward<U>(value));
1064         ++m_size;
1065         return;
1066     }
1067
1068     appendSlowCase(std::forward<U>(value));
1069 }
1070
1071 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1072 void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
1073 {
1074     ASSERT(size() == capacity());
1075
1076     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1077     ptr = expandCapacity(size() + 1, ptr);
1078     ASSERT(begin());
1079
1080     new (NotNull, end()) T(std::forward<U>(*ptr));
1081     ++m_size;
1082 }
1083
1084 // This version of append saves a branch in the case where you know that the
1085 // vector's capacity is large enough for the append to succeed.
1086
1087 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1088 inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value)
1089 {
1090     ASSERT(size() < capacity());
1091
1092     auto ptr = std::addressof(value);
1093     new (NotNull, end()) T(std::forward<U>(*ptr));
1094     ++m_size;
1095 }
1096
1097 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
1098 inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
1099 {
1100     append(val.begin(), val.size());
1101 }
1102
1103 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1104 void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize)
1105 {
1106     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1107     size_t newSize = m_size + dataSize;
1108     if (newSize > capacity()) {
1109         data = expandCapacity(newSize, data);
1110         ASSERT(begin());
1111     }
1112     if (newSize < m_size)
1113         CRASH();
1114     T* spot = begin() + position;
1115     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1116     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, &data[dataSize], spot);
1117     m_size = newSize;
1118 }
1119  
1120 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1121 inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value)
1122 {
1123     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1124
1125     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1126     if (size() == capacity()) {
1127         ptr = expandCapacity(size() + 1, ptr);
1128         ASSERT(begin());
1129     }
1130
1131     T* spot = begin() + position;
1132     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1133     new (NotNull, spot) T(std::forward<U>(*ptr));
1134     ++m_size;
1135 }
1136
1137 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
1138 inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
1139 {
1140     insert(position, val.begin(), val.size());
1141 }
1142
1143 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1144 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
1145 {
1146     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1147     T* spot = begin() + position;
1148     spot->~T();
1149     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1150     --m_size;
1151 }
1152
1153 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1154 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length)
1155 {
1156     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1157     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1158     T* beginSpot = begin() + position;
1159     T* endSpot = beginSpot + length;
1160     TypeOperations::destruct(beginSpot, endSpot); 
1161     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1162     m_size -= length;
1163 }
1164
1165 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1166 inline void Vector<T, inlineCapacity, OverflowHandler>::reverse()
1167 {
1168     for (size_t i = 0; i < m_size / 2; ++i)
1169         std::swap(at(i), at(m_size - 1 - i));
1170 }
1171
1172 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1173 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer()
1174 {
1175     auto buffer = Base::releaseBuffer();
1176     if (inlineCapacity && !buffer && m_size) {
1177         // If the vector had some data, but no buffer to release,
1178         // that means it was using the inline buffer. In that case,
1179         // we create a brand new buffer so the caller always gets one.
1180         size_t bytes = m_size * sizeof(T);
1181         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1182         memcpy(buffer.get(), data(), bytes);
1183     }
1184     m_size = 0;
1185     return buffer;
1186 }
1187
1188 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1189 inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency()
1190 {
1191 #if !ASSERT_DISABLED
1192     for (size_t i = 0; i < size(); ++i)
1193         ValueCheck<T>::checkConsistency(at(i));
1194 #endif
1195 }
1196
1197 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1198 inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b)
1199 {
1200     a.swap(b);
1201 }
1202
1203 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1204 bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1205 {
1206     if (a.size() != b.size())
1207         return false;
1208
1209     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1210 }
1211
1212 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1213 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1214 {
1215     return !(a == b);
1216 }
1217
1218 #if !ASSERT_DISABLED
1219 template<typename T> struct ValueCheck<Vector<T>> {
1220     typedef Vector<T> TraitType;
1221     static void checkConsistency(const Vector<T>& v)
1222     {
1223         v.checkConsistency();
1224     }
1225 };
1226 #endif
1227
1228 } // namespace WTF
1229
1230 using WTF::Vector;
1231 using WTF::UnsafeVectorOverflow;
1232 using WTF::notFound;
1233
1234 #endif // WTF_Vector_h