Add ASSERT_WITH_SECURITY_IMPLICATION to detect out of bounds access
[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/FastAllocBase.h>
26 #include <wtf/Noncopyable.h>
27 #include <wtf/NotFound.h>
28 #include <wtf/StdLibExtras.h>
29 #include <wtf/UnusedParam.h>
30 #include <wtf/ValueCheck.h>
31 #include <wtf/VectorTraits.h>
32 #include <limits>
33 #include <utility>
34
35 namespace WTF {
36
37     template <bool needsDestruction, typename T>
38     struct VectorDestructor;
39
40     template<typename T>
41     struct VectorDestructor<false, T>
42     {
43         static void destruct(T*, T*) {}
44     };
45
46     template<typename T>
47     struct VectorDestructor<true, T>
48     {
49         static void destruct(T* begin, T* end) 
50         {
51             for (T* cur = begin; cur != end; ++cur)
52                 cur->~T();
53         }
54     };
55
56     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
57     struct VectorInitializer;
58
59     template<bool ignore, typename T>
60     struct VectorInitializer<false, ignore, T>
61     {
62         static void initialize(T*, T*) {}
63     };
64
65     template<typename T>
66     struct VectorInitializer<true, false, T>
67     {
68         static void initialize(T* begin, T* end) 
69         {
70             for (T* cur = begin; cur != end; ++cur)
71                 new (NotNull, cur) T;
72         }
73     };
74
75     template<typename T>
76     struct VectorInitializer<true, true, T>
77     {
78         static void initialize(T* begin, T* end) 
79         {
80             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
81         }
82     };
83
84     template <bool canMoveWithMemcpy, typename T>
85     struct VectorMover;
86
87     template<typename T>
88     struct VectorMover<false, T>
89     {
90         static void move(const T* src, const T* srcEnd, T* dst)
91         {
92             while (src != srcEnd) {
93                 new (NotNull, dst) T(*src);
94 #if COMPILER(SUNCC) && __SUNPRO_CC <= 0x590
95                 const_cast<T*>(src)->~T(); // Work around obscure SunCC 12 compiler bug.
96 #else
97                 src->~T();
98 #endif
99                 ++dst;
100                 ++src;
101             }
102         }
103         static void moveOverlapping(const T* src, const 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(*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             ASSERT(sizeof(T) == sizeof(char));
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(const T* src, const T* srcEnd, T* dst)
223         {
224             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
225         }
226
227         static void moveOverlapping(const T* src, const 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<size_t>::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<size_t>::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         T* releaseBuffer()
311         {
312             T* buffer = m_buffer;
313             m_buffer = 0;
314             m_capacity = 0;
315             return buffer;
316         }
317
318     protected:
319         VectorBufferBase()
320             : m_buffer(0)
321             , m_capacity(0)
322         {
323         }
324
325         VectorBufferBase(T* buffer, size_t capacity)
326             : m_buffer(buffer)
327             , m_capacity(capacity)
328         {
329         }
330
331         ~VectorBufferBase()
332         {
333             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
334         }
335
336         T* m_buffer;
337         size_t m_capacity;
338     };
339
340     template<typename T, size_t inlineCapacity>
341     class VectorBuffer;
342
343     template<typename T>
344     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
345     private:
346         typedef VectorBufferBase<T> Base;
347     public:
348         VectorBuffer()
349         {
350         }
351
352         VectorBuffer(size_t capacity)
353         {
354             // Calling malloc(0) might take a lock and may actually do an
355             // allocation on some systems.
356             if (capacity)
357                 allocateBuffer(capacity);
358         }
359
360         ~VectorBuffer()
361         {
362             deallocateBuffer(buffer());
363         }
364         
365         void swap(VectorBuffer<T, 0>& other)
366         {
367             std::swap(m_buffer, other.m_buffer);
368             std::swap(m_capacity, other.m_capacity);
369         }
370         
371         void restoreInlineBufferIfNeeded() { }
372
373         using Base::allocateBuffer;
374         using Base::tryAllocateBuffer;
375         using Base::shouldReallocateBuffer;
376         using Base::reallocateBuffer;
377         using Base::deallocateBuffer;
378
379         using Base::buffer;
380         using Base::capacity;
381
382         using Base::releaseBuffer;
383     private:
384         using Base::m_buffer;
385         using Base::m_capacity;
386     };
387
388     template<typename T, size_t inlineCapacity>
389     class VectorBuffer : private VectorBufferBase<T> {
390         WTF_MAKE_NONCOPYABLE(VectorBuffer);
391     private:
392         typedef VectorBufferBase<T> Base;
393     public:
394         VectorBuffer()
395             : Base(inlineBuffer(), inlineCapacity)
396         {
397         }
398
399         VectorBuffer(size_t capacity)
400             : Base(inlineBuffer(), inlineCapacity)
401         {
402             if (capacity > inlineCapacity)
403                 Base::allocateBuffer(capacity);
404         }
405
406         ~VectorBuffer()
407         {
408             deallocateBuffer(buffer());
409         }
410
411         void allocateBuffer(size_t newCapacity)
412         {
413             // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
414             if (newCapacity > inlineCapacity)
415                 Base::allocateBuffer(newCapacity);
416             else {
417                 m_buffer = inlineBuffer();
418                 m_capacity = inlineCapacity;
419             }
420         }
421
422         bool tryAllocateBuffer(size_t newCapacity)
423         {
424             if (newCapacity > inlineCapacity)
425                 return Base::tryAllocateBuffer(newCapacity);
426             m_buffer = inlineBuffer();
427             m_capacity = inlineCapacity;
428             return true;
429         }
430
431         void deallocateBuffer(T* bufferToDeallocate)
432         {
433             if (bufferToDeallocate == inlineBuffer())
434                 return;
435             Base::deallocateBuffer(bufferToDeallocate);
436         }
437
438         bool shouldReallocateBuffer(size_t newCapacity) const
439         {
440             // We cannot reallocate the inline buffer.
441             return Base::shouldReallocateBuffer(newCapacity) && std::min(m_capacity, newCapacity) > inlineCapacity;
442         }
443
444         void reallocateBuffer(size_t newCapacity)
445         {
446             ASSERT(shouldReallocateBuffer(newCapacity));
447             Base::reallocateBuffer(newCapacity);
448         }
449
450         void swap(VectorBuffer<T, inlineCapacity>& other)
451         {
452             if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
453                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
454                 std::swap(m_capacity, other.m_capacity);
455             } else if (buffer() == inlineBuffer()) {
456                 m_buffer = other.m_buffer;
457                 other.m_buffer = other.inlineBuffer();
458                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
459                 std::swap(m_capacity, other.m_capacity);
460             } else if (other.buffer() == other.inlineBuffer()) {
461                 other.m_buffer = m_buffer;
462                 m_buffer = inlineBuffer();
463                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
464                 std::swap(m_capacity, other.m_capacity);
465             } else {
466                 std::swap(m_buffer, other.m_buffer);
467                 std::swap(m_capacity, other.m_capacity);
468             }
469         }
470
471         void restoreInlineBufferIfNeeded()
472         {
473             if (m_buffer)
474                 return;
475             m_buffer = inlineBuffer();
476             m_capacity = inlineCapacity;
477         }
478
479         using Base::buffer;
480         using Base::capacity;
481
482         T* releaseBuffer()
483         {
484             if (buffer() == inlineBuffer())
485                 return 0;
486             return Base::releaseBuffer();
487         }
488
489     private:
490         using Base::m_buffer;
491         using Base::m_capacity;
492
493         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
494         T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); }
495         const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer.buffer); }
496
497         AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
498     };
499
500     template<typename T, size_t inlineCapacity = 0>
501     class Vector {
502         WTF_MAKE_FAST_ALLOCATED;
503     private:
504         typedef VectorBuffer<T, inlineCapacity> Buffer;
505         typedef VectorTypeOperations<T> TypeOperations;
506
507     public:
508         typedef T ValueType;
509
510         typedef T* iterator;
511         typedef const T* const_iterator;
512         typedef std::reverse_iterator<iterator> reverse_iterator;
513         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
514
515         Vector() 
516             : m_size(0)
517         {
518         }
519         
520         explicit Vector(size_t size) 
521             : m_size(size)
522             , m_buffer(size)
523         {
524             if (begin())
525                 TypeOperations::initialize(begin(), end());
526         }
527
528         ~Vector()
529         {
530             if (m_size)
531                 shrink(0);
532         }
533
534         Vector(const Vector&);
535         template<size_t otherCapacity> 
536         Vector(const Vector<T, otherCapacity>&);
537
538         Vector& operator=(const Vector&);
539         template<size_t otherCapacity> 
540         Vector& operator=(const Vector<T, otherCapacity>&);
541
542 #if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES)
543         Vector(Vector&&);
544         Vector& operator=(Vector&&);
545 #endif
546
547         size_t size() const { return m_size; }
548         size_t capacity() const { return m_buffer.capacity(); }
549         bool isEmpty() const { return !size(); }
550
551         T& at(size_t i) 
552         { 
553             ASSERT_WITH_SECURITY_IMPLICATION(i < size());
554             return m_buffer.buffer()[i]; 
555         }
556         const T& at(size_t i) const 
557         {
558             ASSERT_WITH_SECURITY_IMPLICATION(i < size());
559             return m_buffer.buffer()[i]; 
560         }
561
562         T& operator[](size_t i) { return at(i); }
563         const T& operator[](size_t i) const { return at(i); }
564
565         T* data() { return m_buffer.buffer(); }
566         const T* data() const { return m_buffer.buffer(); }
567         T** dataSlot() { return m_buffer.bufferSlot(); }
568
569         iterator begin() { return data(); }
570         iterator end() { return begin() + m_size; }
571         const_iterator begin() const { return data(); }
572         const_iterator end() const { return begin() + m_size; }
573
574         reverse_iterator rbegin() { return reverse_iterator(end()); }
575         reverse_iterator rend() { return reverse_iterator(begin()); }
576         const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
577         const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
578
579         T& first() { return at(0); }
580         const T& first() const { return at(0); }
581         T& last() { return at(size() - 1); }
582         const T& last() const { return at(size() - 1); }
583
584         template<typename U> bool contains(const U&) const;
585         template<typename U> size_t find(const U&) const;
586         template<typename U> size_t reverseFind(const U&) const;
587
588         void shrink(size_t size);
589         void grow(size_t size);
590         void resize(size_t size);
591         void reserveCapacity(size_t newCapacity);
592         bool tryReserveCapacity(size_t newCapacity);
593         void reserveInitialCapacity(size_t initialCapacity);
594         void shrinkCapacity(size_t newCapacity);
595         void shrinkToFit() { shrinkCapacity(size()); }
596
597         void clear() { shrinkCapacity(0); }
598
599         template<typename U> void append(const U*, size_t);
600         template<typename U> void append(const U&);
601         template<typename U> void uncheckedAppend(const U& val);
602         template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
603         template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
604         template<typename U> bool tryAppend(const U*, size_t);
605
606         template<typename U> void insert(size_t position, const U*, size_t);
607         template<typename U> void insert(size_t position, const U&);
608         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
609
610         template<typename U> void prepend(const U*, size_t);
611         template<typename U> void prepend(const U&);
612         template<typename U, size_t c> void prepend(const Vector<U, c>&);
613
614         void remove(size_t position);
615         void remove(size_t position, size_t length);
616
617         void removeLast() 
618         {
619             ASSERT(!isEmpty());
620             shrink(size() - 1); 
621         }
622
623         Vector(size_t size, const T& val)
624             : m_size(size)
625             , m_buffer(size)
626         {
627             if (begin())
628                 TypeOperations::uninitializedFill(begin(), end(), val);
629         }
630
631         void fill(const T&, size_t);
632         void fill(const T& val) { fill(val, size()); }
633
634         template<typename Iterator> void appendRange(Iterator start, Iterator end);
635
636         T* releaseBuffer();
637
638         void swap(Vector<T, inlineCapacity>& other)
639         {
640             std::swap(m_size, other.m_size);
641             m_buffer.swap(other.m_buffer);
642         }
643
644         void reverse();
645
646         void checkConsistency();
647
648     private:
649         void expandCapacity(size_t newMinCapacity);
650         const T* expandCapacity(size_t newMinCapacity, const T*);
651         bool tryExpandCapacity(size_t newMinCapacity);
652         const T* tryExpandCapacity(size_t newMinCapacity, const T*);
653         template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
654         template<typename U> void appendSlowCase(const U&);
655
656         size_t m_size;
657         Buffer m_buffer;
658     };
659
660     template<typename T, size_t inlineCapacity>
661     Vector<T, inlineCapacity>::Vector(const Vector& other)
662         : m_size(other.size())
663         , m_buffer(other.capacity())
664     {
665         if (begin())
666             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
667     }
668
669     template<typename T, size_t inlineCapacity>
670     template<size_t otherCapacity> 
671     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
672         : m_size(other.size())
673         , m_buffer(other.capacity())
674     {
675         if (begin())
676             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
677     }
678
679     template<typename T, size_t inlineCapacity>
680     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
681     {
682         if (&other == this)
683             return *this;
684         
685         if (size() > other.size())
686             shrink(other.size());
687         else if (other.size() > capacity()) {
688             clear();
689             reserveCapacity(other.size());
690             if (!begin())
691                 return *this;
692         }
693         
694 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
695 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
696         if (!begin())
697             return *this;
698 #endif
699
700         std::copy(other.begin(), other.begin() + size(), begin());
701         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
702         m_size = other.size();
703
704         return *this;
705     }
706
707     inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
708
709     template<typename T, size_t inlineCapacity>
710     template<size_t otherCapacity> 
711     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
712     {
713         // If the inline capacities match, we should call the more specific
714         // template.  If the inline capacities don't match, the two objects
715         // shouldn't be allocated the same address.
716         ASSERT(!typelessPointersAreEqual(&other, this));
717
718         if (size() > other.size())
719             shrink(other.size());
720         else if (other.size() > capacity()) {
721             clear();
722             reserveCapacity(other.size());
723             if (!begin())
724                 return *this;
725         }
726         
727 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
728 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
729         if (!begin())
730             return *this;
731 #endif
732
733         std::copy(other.begin(), other.begin() + size(), begin());
734         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
735         m_size = other.size();
736
737         return *this;
738     }
739
740 #if COMPILER_SUPPORTS(CXX_RVALUE_REFERENCES)
741     template<typename T, size_t inlineCapacity>
742     Vector<T, inlineCapacity>::Vector(Vector<T, inlineCapacity>&& other)
743         : m_size(0)
744     {
745         // It's a little weird to implement a move constructor using swap but this way we
746         // don't have to add a move constructor to VectorBuffer.
747         swap(other);
748     }
749
750     template<typename T, size_t inlineCapacity>
751     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(Vector<T, inlineCapacity>&& other)
752     {
753         swap(other);
754         return *this;
755     }
756 #endif
757
758     template<typename T, size_t inlineCapacity>
759     template<typename U>
760     bool Vector<T, inlineCapacity>::contains(const U& value) const
761     {
762         return find(value) != notFound;
763     }
764  
765     template<typename T, size_t inlineCapacity>
766     template<typename U>
767     size_t Vector<T, inlineCapacity>::find(const U& value) const
768     {
769         for (size_t i = 0; i < size(); ++i) {
770             if (at(i) == value)
771                 return i;
772         }
773         return notFound;
774     }
775
776     template<typename T, size_t inlineCapacity>
777     template<typename U>
778     size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
779     {
780         for (size_t i = 1; i <= size(); ++i) {
781             const size_t index = size() - i;
782             if (at(index) == value)
783                 return index;
784         }
785         return notFound;
786     }
787
788     template<typename T, size_t inlineCapacity>
789     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
790     {
791         if (size() > newSize)
792             shrink(newSize);
793         else if (newSize > capacity()) {
794             clear();
795             reserveCapacity(newSize);
796             if (!begin())
797                 return;
798         }
799         
800         std::fill(begin(), end(), val);
801         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
802         m_size = newSize;
803     }
804
805     template<typename T, size_t inlineCapacity>
806     template<typename Iterator>
807     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
808     {
809         for (Iterator it = start; it != end; ++it)
810             append(*it);
811     }
812
813     template<typename T, size_t inlineCapacity>
814     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
815     {
816         reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
817     }
818     
819     template<typename T, size_t inlineCapacity>
820     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
821     {
822         if (ptr < begin() || ptr >= end()) {
823             expandCapacity(newMinCapacity);
824             return ptr;
825         }
826         size_t index = ptr - begin();
827         expandCapacity(newMinCapacity);
828         return begin() + index;
829     }
830
831     template<typename T, size_t inlineCapacity>
832     bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity)
833     {
834         return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
835     }
836     
837     template<typename T, size_t inlineCapacity>
838     const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
839     {
840         if (ptr < begin() || ptr >= end()) {
841             if (!tryExpandCapacity(newMinCapacity))
842                 return 0;
843             return ptr;
844         }
845         size_t index = ptr - begin();
846         if (!tryExpandCapacity(newMinCapacity))
847             return 0;
848         return begin() + index;
849     }
850
851     template<typename T, size_t inlineCapacity> template<typename U>
852     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
853     {
854         expandCapacity(newMinCapacity);
855         return ptr;
856     }
857
858     template<typename T, size_t inlineCapacity>
859     inline void Vector<T, inlineCapacity>::resize(size_t size)
860     {
861         if (size <= m_size)
862             TypeOperations::destruct(begin() + size, end());
863         else {
864             if (size > capacity())
865                 expandCapacity(size);
866             if (begin())
867                 TypeOperations::initialize(end(), begin() + size);
868         }
869         
870         m_size = size;
871     }
872
873     template<typename T, size_t inlineCapacity>
874     void Vector<T, inlineCapacity>::shrink(size_t size)
875     {
876         ASSERT(size <= m_size);
877         TypeOperations::destruct(begin() + size, end());
878         m_size = size;
879     }
880
881     template<typename T, size_t inlineCapacity>
882     void Vector<T, inlineCapacity>::grow(size_t size)
883     {
884         ASSERT(size >= m_size);
885         if (size > capacity())
886             expandCapacity(size);
887         if (begin())
888             TypeOperations::initialize(end(), begin() + size);
889         m_size = size;
890     }
891
892     template<typename T, size_t inlineCapacity>
893     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
894     {
895         if (newCapacity <= capacity())
896             return;
897         T* oldBuffer = begin();
898         T* oldEnd = end();
899         m_buffer.allocateBuffer(newCapacity);
900         if (begin())
901             TypeOperations::move(oldBuffer, oldEnd, begin());
902         m_buffer.deallocateBuffer(oldBuffer);
903     }
904     
905     template<typename T, size_t inlineCapacity>
906     bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity)
907     {
908         if (newCapacity <= capacity())
909             return true;
910         T* oldBuffer = begin();
911         T* oldEnd = end();
912         if (!m_buffer.tryAllocateBuffer(newCapacity))
913             return false;
914         ASSERT(begin());
915         TypeOperations::move(oldBuffer, oldEnd, begin());
916         m_buffer.deallocateBuffer(oldBuffer);
917         return true;
918     }
919     
920     template<typename T, size_t inlineCapacity>
921     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
922     {
923         ASSERT(!m_size);
924         ASSERT(capacity() == inlineCapacity);
925         if (initialCapacity > inlineCapacity)
926             m_buffer.allocateBuffer(initialCapacity);
927     }
928     
929     template<typename T, size_t inlineCapacity>
930     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
931     {
932         if (newCapacity >= capacity())
933             return;
934
935         if (newCapacity < size()) 
936             shrink(newCapacity);
937
938         T* oldBuffer = begin();
939         if (newCapacity > 0) {
940             if (m_buffer.shouldReallocateBuffer(newCapacity)) {
941                 m_buffer.reallocateBuffer(newCapacity);
942                 return;
943             }
944
945             T* oldEnd = end();
946             m_buffer.allocateBuffer(newCapacity);
947             if (begin() != oldBuffer)
948                 TypeOperations::move(oldBuffer, oldEnd, begin());
949         }
950
951         m_buffer.deallocateBuffer(oldBuffer);
952         m_buffer.restoreInlineBufferIfNeeded();
953     }
954
955     // Templatizing these is better than just letting the conversion happen implicitly,
956     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
957     // without refcount thrash.
958
959     template<typename T, size_t inlineCapacity> template<typename U>
960     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
961     {
962         size_t newSize = m_size + dataSize;
963         if (newSize > capacity()) {
964             data = expandCapacity(newSize, data);
965             if (!begin())
966                 return;
967         }
968         if (newSize < m_size)
969             CRASH();
970         T* dest = end();
971         for (size_t i = 0; i < dataSize; ++i)
972             new (NotNull, &dest[i]) T(data[i]);
973         m_size = newSize;
974     }
975
976     template<typename T, size_t inlineCapacity> template<typename U>
977     bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize)
978     {
979         size_t newSize = m_size + dataSize;
980         if (newSize > capacity()) {
981             data = tryExpandCapacity(newSize, data);
982             if (!data)
983                 return false;
984             ASSERT(begin());
985         }
986         if (newSize < m_size)
987             return false;
988         T* dest = end();
989         for (size_t i = 0; i < dataSize; ++i)
990             new (NotNull, &dest[i]) T(data[i]);
991         m_size = newSize;
992         return true;
993     }
994
995     template<typename T, size_t inlineCapacity> template<typename U>
996     ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
997     {
998         if (size() != capacity()) {
999             new (NotNull, end()) T(val);
1000             ++m_size;
1001             return;
1002         }
1003
1004         appendSlowCase(val);
1005     }
1006
1007     template<typename T, size_t inlineCapacity> template<typename U>
1008     void Vector<T, inlineCapacity>::appendSlowCase(const U& val)
1009     {
1010         ASSERT(size() == capacity());
1011
1012         const U* ptr = &val;
1013         ptr = expandCapacity(size() + 1, ptr);
1014         if (!begin())
1015             return;
1016
1017         new (NotNull, end()) T(*ptr);
1018         ++m_size;
1019     }
1020
1021     // This version of append saves a branch in the case where you know that the
1022     // vector's capacity is large enough for the append to succeed.
1023
1024     template<typename T, size_t inlineCapacity> template<typename U>
1025     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
1026     {
1027         ASSERT(size() < capacity());
1028         const U* ptr = &val;
1029         new (NotNull, end()) T(*ptr);
1030         ++m_size;
1031     }
1032
1033     // This method should not be called append, a better name would be appendElements.
1034     // It could also be eliminated entirely, and call sites could just use
1035     // appendRange(val.begin(), val.end()).
1036     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
1037     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
1038     {
1039         append(val.begin(), val.size());
1040     }
1041
1042     template<typename T, size_t inlineCapacity> template<typename U, size_t otherCapacity>
1043     inline void Vector<T, inlineCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1044     {
1045         append(val.begin(), val.size());
1046     }
1047
1048     template<typename T, size_t inlineCapacity> template<typename U>
1049     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
1050     {
1051         ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1052         size_t newSize = m_size + dataSize;
1053         if (newSize > capacity()) {
1054             data = expandCapacity(newSize, data);
1055             if (!begin())
1056                 return;
1057         }
1058         if (newSize < m_size)
1059             CRASH();
1060         T* spot = begin() + position;
1061         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1062         for (size_t i = 0; i < dataSize; ++i)
1063             new (NotNull, &spot[i]) T(data[i]);
1064         m_size = newSize;
1065     }
1066      
1067     template<typename T, size_t inlineCapacity> template<typename U>
1068     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
1069     {
1070         ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1071         const U* data = &val;
1072         if (size() == capacity()) {
1073             data = expandCapacity(size() + 1, data);
1074             if (!begin())
1075                 return;
1076         }
1077         T* spot = begin() + position;
1078         TypeOperations::moveOverlapping(spot, end(), spot + 1);
1079         new (NotNull, spot) T(*data);
1080         ++m_size;
1081     }
1082    
1083     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1084     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
1085     {
1086         insert(position, val.begin(), val.size());
1087     }
1088
1089     template<typename T, size_t inlineCapacity> template<typename U>
1090     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
1091     {
1092         insert(0, data, dataSize);
1093     }
1094
1095     template<typename T, size_t inlineCapacity> template<typename U>
1096     inline void Vector<T, inlineCapacity>::prepend(const U& val)
1097     {
1098         insert(0, val);
1099     }
1100    
1101     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1102     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
1103     {
1104         insert(0, val.begin(), val.size());
1105     }
1106     
1107     template<typename T, size_t inlineCapacity>
1108     inline void Vector<T, inlineCapacity>::remove(size_t position)
1109     {
1110         ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1111         T* spot = begin() + position;
1112         spot->~T();
1113         TypeOperations::moveOverlapping(spot + 1, end(), spot);
1114         --m_size;
1115     }
1116
1117     template<typename T, size_t inlineCapacity>
1118     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
1119     {
1120         ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1121         ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1122         T* beginSpot = begin() + position;
1123         T* endSpot = beginSpot + length;
1124         TypeOperations::destruct(beginSpot, endSpot); 
1125         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1126         m_size -= length;
1127     }
1128
1129     template<typename T, size_t inlineCapacity>
1130     inline void Vector<T, inlineCapacity>::reverse()
1131     {
1132         for (size_t i = 0; i < m_size / 2; ++i)
1133             std::swap(at(i), at(m_size - 1 - i));
1134     }
1135
1136     template<typename T, size_t inlineCapacity>
1137     inline T* Vector<T, inlineCapacity>::releaseBuffer()
1138     {
1139         T* buffer = m_buffer.releaseBuffer();
1140         if (inlineCapacity && !buffer && m_size) {
1141             // If the vector had some data, but no buffer to release,
1142             // that means it was using the inline buffer. In that case,
1143             // we create a brand new buffer so the caller always gets one.
1144             size_t bytes = m_size * sizeof(T);
1145             buffer = static_cast<T*>(fastMalloc(bytes));
1146             memcpy(buffer, data(), bytes);
1147         }
1148         m_size = 0;
1149         return buffer;
1150     }
1151
1152     template<typename T, size_t inlineCapacity>
1153     inline void Vector<T, inlineCapacity>::checkConsistency()
1154     {
1155 #if !ASSERT_DISABLED
1156         for (size_t i = 0; i < size(); ++i)
1157             ValueCheck<T>::checkConsistency(at(i));
1158 #endif
1159     }
1160
1161     template<typename T, size_t inlineCapacity>
1162     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
1163     {
1164         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
1165         iterator end = collection.end();
1166         for (iterator it = collection.begin(); it != end; ++it)
1167             delete *it;
1168     }
1169
1170     template<typename T, size_t inlineCapacity>
1171     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
1172     {
1173         a.swap(b);
1174     }
1175
1176     template<typename T, size_t inlineCapacity>
1177     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1178     {
1179         if (a.size() != b.size())
1180             return false;
1181
1182         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1183     }
1184
1185     template<typename T, size_t inlineCapacity>
1186     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1187     {
1188         return !(a == b);
1189     }
1190
1191 #if !ASSERT_DISABLED
1192     template<typename T> struct ValueCheck<Vector<T> > {
1193         typedef Vector<T> TraitType;
1194         static void checkConsistency(const Vector<T>& v)
1195         {
1196             v.checkConsistency();
1197         }
1198     };
1199 #endif
1200
1201 } // namespace WTF
1202
1203 using WTF::Vector;
1204
1205 #endif // WTF_Vector_h