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