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