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