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