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