Source/JavaScriptCore: Add Vector::reverse()
[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 reverse();
623
624         void checkConsistency();
625
626     private:
627         void expandCapacity(size_t newMinCapacity);
628         const T* expandCapacity(size_t newMinCapacity, const T*);
629         bool tryExpandCapacity(size_t newMinCapacity);
630         const T* tryExpandCapacity(size_t newMinCapacity, const T*);
631         template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
632
633         size_t m_size;
634         Buffer m_buffer;
635     };
636
637 #if PLATFORM(QT)
638     template<typename T>
639     QDataStream& operator<<(QDataStream& stream, const Vector<T>& data)
640     {
641         stream << qint64(data.size());
642         foreach (const T& i, data)
643             stream << i;
644         return stream;
645     }
646
647     template<typename T>
648     QDataStream& operator>>(QDataStream& stream, Vector<T>& data)
649     {
650         data.clear();
651         qint64 count;
652         T item;
653         stream >> count;
654         data.reserveCapacity(count);
655         for (qint64 i = 0; i < count; ++i) {
656             stream >> item;
657             data.append(item);
658         }
659         return stream;
660     }
661 #endif
662
663     template<typename T, size_t inlineCapacity>
664     Vector<T, inlineCapacity>::Vector(const Vector& other)
665         : m_size(other.size())
666         , m_buffer(other.capacity())
667     {
668         if (begin())
669             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
670     }
671
672     template<typename T, size_t inlineCapacity>
673     template<size_t otherCapacity> 
674     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
675         : m_size(other.size())
676         , m_buffer(other.capacity())
677     {
678         if (begin())
679             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
680     }
681
682     template<typename T, size_t inlineCapacity>
683     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
684     {
685         if (&other == this)
686             return *this;
687         
688         if (size() > other.size())
689             shrink(other.size());
690         else if (other.size() > capacity()) {
691             clear();
692             reserveCapacity(other.size());
693             if (!begin())
694                 return *this;
695         }
696         
697 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
698 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
699         if (!begin())
700             return *this;
701 #endif
702
703         std::copy(other.begin(), other.begin() + size(), begin());
704         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
705         m_size = other.size();
706
707         return *this;
708     }
709
710     inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
711
712     template<typename T, size_t inlineCapacity>
713     template<size_t otherCapacity> 
714     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
715     {
716         // If the inline capacities match, we should call the more specific
717         // template.  If the inline capacities don't match, the two objects
718         // shouldn't be allocated the same address.
719         ASSERT(!typelessPointersAreEqual(&other, this));
720
721         if (size() > other.size())
722             shrink(other.size());
723         else if (other.size() > capacity()) {
724             clear();
725             reserveCapacity(other.size());
726             if (!begin())
727                 return *this;
728         }
729         
730 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
731 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
732         if (!begin())
733             return *this;
734 #endif
735
736         std::copy(other.begin(), other.begin() + size(), begin());
737         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
738         m_size = other.size();
739
740         return *this;
741     }
742
743     template<typename T, size_t inlineCapacity>
744     template<typename U>
745     bool Vector<T, inlineCapacity>::contains(const U& value) const
746     {
747         return find(value) != notFound;
748     }
749  
750     template<typename T, size_t inlineCapacity>
751     template<typename U>
752     size_t Vector<T, inlineCapacity>::find(const U& value) const
753     {
754         for (size_t i = 0; i < size(); ++i) {
755             if (at(i) == value)
756                 return i;
757         }
758         return notFound;
759     }
760
761     template<typename T, size_t inlineCapacity>
762     template<typename U>
763     size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
764     {
765         for (size_t i = 1; i <= size(); ++i) {
766             const size_t index = size() - i;
767             if (at(index) == value)
768                 return index;
769         }
770         return notFound;
771     }
772
773     template<typename T, size_t inlineCapacity>
774     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
775     {
776         if (size() > newSize)
777             shrink(newSize);
778         else if (newSize > capacity()) {
779             clear();
780             reserveCapacity(newSize);
781             if (!begin())
782                 return;
783         }
784         
785         std::fill(begin(), end(), val);
786         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
787         m_size = newSize;
788     }
789
790     template<typename T, size_t inlineCapacity>
791     template<typename Iterator>
792     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
793     {
794         for (Iterator it = start; it != end; ++it)
795             append(*it);
796     }
797
798     template<typename T, size_t inlineCapacity>
799     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
800     {
801         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
802     }
803     
804     template<typename T, size_t inlineCapacity>
805     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
806     {
807         if (ptr < begin() || ptr >= end()) {
808             expandCapacity(newMinCapacity);
809             return ptr;
810         }
811         size_t index = ptr - begin();
812         expandCapacity(newMinCapacity);
813         return begin() + index;
814     }
815
816     template<typename T, size_t inlineCapacity>
817     bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity)
818     {
819         return tryReserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
820     }
821     
822     template<typename T, size_t inlineCapacity>
823     const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
824     {
825         if (ptr < begin() || ptr >= end()) {
826             if (!tryExpandCapacity(newMinCapacity))
827                 return 0;
828             return ptr;
829         }
830         size_t index = ptr - begin();
831         if (!tryExpandCapacity(newMinCapacity))
832             return 0;
833         return begin() + index;
834     }
835
836     template<typename T, size_t inlineCapacity> template<typename U>
837     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
838     {
839         expandCapacity(newMinCapacity);
840         return ptr;
841     }
842
843     template<typename T, size_t inlineCapacity>
844     inline void Vector<T, inlineCapacity>::resize(size_t size)
845     {
846         if (size <= m_size)
847             TypeOperations::destruct(begin() + size, end());
848         else {
849             if (size > capacity())
850                 expandCapacity(size);
851             if (begin())
852                 TypeOperations::initialize(end(), begin() + size);
853         }
854         
855         m_size = size;
856     }
857
858     template<typename T, size_t inlineCapacity>
859     void Vector<T, inlineCapacity>::shrink(size_t size)
860     {
861         ASSERT(size <= m_size);
862         TypeOperations::destruct(begin() + size, end());
863         m_size = size;
864     }
865
866     template<typename T, size_t inlineCapacity>
867     void Vector<T, inlineCapacity>::grow(size_t size)
868     {
869         ASSERT(size >= m_size);
870         if (size > capacity())
871             expandCapacity(size);
872         if (begin())
873             TypeOperations::initialize(end(), begin() + size);
874         m_size = size;
875     }
876
877     template<typename T, size_t inlineCapacity>
878     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
879     {
880         if (newCapacity <= capacity())
881             return;
882         T* oldBuffer = begin();
883         T* oldEnd = end();
884         m_buffer.allocateBuffer(newCapacity);
885         if (begin())
886             TypeOperations::move(oldBuffer, oldEnd, begin());
887         m_buffer.deallocateBuffer(oldBuffer);
888     }
889     
890     template<typename T, size_t inlineCapacity>
891     bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity)
892     {
893         if (newCapacity <= capacity())
894             return true;
895         T* oldBuffer = begin();
896         T* oldEnd = end();
897         if (!m_buffer.tryAllocateBuffer(newCapacity))
898             return false;
899         ASSERT(begin());
900         TypeOperations::move(oldBuffer, oldEnd, begin());
901         m_buffer.deallocateBuffer(oldBuffer);
902         return true;
903     }
904     
905     template<typename T, size_t inlineCapacity>
906     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
907     {
908         ASSERT(!m_size);
909         ASSERT(capacity() == inlineCapacity);
910         if (initialCapacity > inlineCapacity)
911             m_buffer.allocateBuffer(initialCapacity);
912     }
913     
914     template<typename T, size_t inlineCapacity>
915     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
916     {
917         if (newCapacity >= capacity())
918             return;
919
920         if (newCapacity < size()) 
921             shrink(newCapacity);
922
923         T* oldBuffer = begin();
924         if (newCapacity > 0) {
925             T* oldEnd = end();
926             m_buffer.allocateBuffer(newCapacity);
927             if (begin() != oldBuffer)
928                 TypeOperations::move(oldBuffer, oldEnd, begin());
929         }
930
931         m_buffer.deallocateBuffer(oldBuffer);
932         m_buffer.restoreInlineBufferIfNeeded();
933     }
934
935     // Templatizing these is better than just letting the conversion happen implicitly,
936     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
937     // without refcount thrash.
938
939     template<typename T, size_t inlineCapacity> template<typename U>
940     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
941     {
942         size_t newSize = m_size + dataSize;
943         if (newSize > capacity()) {
944             data = expandCapacity(newSize, data);
945             if (!begin())
946                 return;
947         }
948         if (newSize < m_size)
949             CRASH();
950         T* dest = end();
951         for (size_t i = 0; i < dataSize; ++i)
952             new (&dest[i]) T(data[i]);
953         m_size = newSize;
954     }
955
956     template<typename T, size_t inlineCapacity> template<typename U>
957     bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize)
958     {
959         size_t newSize = m_size + dataSize;
960         if (newSize > capacity()) {
961             data = tryExpandCapacity(newSize, data);
962             if (!data)
963                 return false;
964             ASSERT(begin());
965         }
966         if (newSize < m_size)
967             return false;
968         T* dest = end();
969         for (size_t i = 0; i < dataSize; ++i)
970             new (&dest[i]) T(data[i]);
971         m_size = newSize;
972         return true;
973     }
974
975     template<typename T, size_t inlineCapacity> template<typename U>
976     ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
977     {
978         const U* ptr = &val;
979         if (size() == capacity()) {
980             ptr = expandCapacity(size() + 1, ptr);
981             if (!begin())
982                 return;
983         }
984             
985 #if COMPILER(MSVC7_OR_LOWER)
986         // FIXME: MSVC7 generates compilation errors when trying to assign
987         // a pointer to a Vector of its base class (i.e. can't downcast). So far
988         // I've been unable to determine any logical reason for this, so I can
989         // only assume it is a bug with the compiler. Casting is a bad solution,
990         // however, because it subverts implicit conversions, so a better 
991         // one is needed. 
992         new (end()) T(static_cast<T>(*ptr));
993 #else
994         new (end()) T(*ptr);
995 #endif
996         ++m_size;
997     }
998
999     // This version of append saves a branch in the case where you know that the
1000     // vector's capacity is large enough for the append to succeed.
1001
1002     template<typename T, size_t inlineCapacity> template<typename U>
1003     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
1004     {
1005         ASSERT(size() < capacity());
1006         const U* ptr = &val;
1007         new (end()) T(*ptr);
1008         ++m_size;
1009     }
1010
1011     // This method should not be called append, a better name would be appendElements.
1012     // It could also be eliminated entirely, and call sites could just use
1013     // appendRange(val.begin(), val.end()).
1014     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
1015     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
1016     {
1017         append(val.begin(), val.size());
1018     }
1019
1020     template<typename T, size_t inlineCapacity> template<typename U>
1021     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
1022     {
1023         ASSERT(position <= size());
1024         size_t newSize = m_size + dataSize;
1025         if (newSize > capacity()) {
1026             data = expandCapacity(newSize, data);
1027             if (!begin())
1028                 return;
1029         }
1030         if (newSize < m_size)
1031             CRASH();
1032         T* spot = begin() + position;
1033         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1034         for (size_t i = 0; i < dataSize; ++i)
1035             new (&spot[i]) T(data[i]);
1036         m_size = newSize;
1037     }
1038      
1039     template<typename T, size_t inlineCapacity> template<typename U>
1040     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
1041     {
1042         ASSERT(position <= size());
1043         const U* data = &val;
1044         if (size() == capacity()) {
1045             data = expandCapacity(size() + 1, data);
1046             if (!begin())
1047                 return;
1048         }
1049         T* spot = begin() + position;
1050         TypeOperations::moveOverlapping(spot, end(), spot + 1);
1051         new (spot) T(*data);
1052         ++m_size;
1053     }
1054    
1055     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1056     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
1057     {
1058         insert(position, val.begin(), val.size());
1059     }
1060
1061     template<typename T, size_t inlineCapacity> template<typename U>
1062     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
1063     {
1064         insert(0, data, dataSize);
1065     }
1066
1067     template<typename T, size_t inlineCapacity> template<typename U>
1068     inline void Vector<T, inlineCapacity>::prepend(const U& val)
1069     {
1070         insert(0, val);
1071     }
1072    
1073     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1074     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
1075     {
1076         insert(0, val.begin(), val.size());
1077     }
1078     
1079     template<typename T, size_t inlineCapacity>
1080     inline void Vector<T, inlineCapacity>::remove(size_t position)
1081     {
1082         ASSERT(position < size());
1083         T* spot = begin() + position;
1084         spot->~T();
1085         TypeOperations::moveOverlapping(spot + 1, end(), spot);
1086         --m_size;
1087     }
1088
1089     template<typename T, size_t inlineCapacity>
1090     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
1091     {
1092         ASSERT(position < size());
1093         ASSERT(position + length <= size());
1094         T* beginSpot = begin() + position;
1095         T* endSpot = beginSpot + length;
1096         TypeOperations::destruct(beginSpot, endSpot); 
1097         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1098         m_size -= length;
1099     }
1100
1101     template<typename T, size_t inlineCapacity>
1102     inline void Vector<T, inlineCapacity>::reverse()
1103     {
1104         for (size_t i = 0; i < m_size / 2; ++i)
1105             std::swap(at(i), at(m_size - 1 - i));
1106     }
1107
1108     template<typename T, size_t inlineCapacity>
1109     inline T* Vector<T, inlineCapacity>::releaseBuffer()
1110     {
1111         T* buffer = m_buffer.releaseBuffer();
1112         if (inlineCapacity && !buffer && m_size) {
1113             // If the vector had some data, but no buffer to release,
1114             // that means it was using the inline buffer. In that case,
1115             // we create a brand new buffer so the caller always gets one.
1116             size_t bytes = m_size * sizeof(T);
1117             buffer = static_cast<T*>(fastMalloc(bytes));
1118             memcpy(buffer, data(), bytes);
1119         }
1120         m_size = 0;
1121         return buffer;
1122     }
1123
1124     template<typename T, size_t inlineCapacity>
1125     inline void Vector<T, inlineCapacity>::checkConsistency()
1126     {
1127 #if !ASSERT_DISABLED
1128         for (size_t i = 0; i < size(); ++i)
1129             ValueCheck<T>::checkConsistency(at(i));
1130 #endif
1131     }
1132
1133     template<typename T, size_t inlineCapacity>
1134     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
1135     {
1136         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
1137         iterator end = collection.end();
1138         for (iterator it = collection.begin(); it != end; ++it)
1139             delete *it;
1140     }
1141
1142     template<typename T, size_t inlineCapacity>
1143     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
1144     {
1145         a.swap(b);
1146     }
1147
1148     template<typename T, size_t inlineCapacity>
1149     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1150     {
1151         if (a.size() != b.size())
1152             return false;
1153
1154         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1155     }
1156
1157     template<typename T, size_t inlineCapacity>
1158     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1159     {
1160         return !(a == b);
1161     }
1162
1163 #if !ASSERT_DISABLED
1164     template<typename T> struct ValueCheck<Vector<T> > {
1165         typedef Vector<T> TraitType;
1166         static void checkConsistency(const Vector<T>& v)
1167         {
1168             v.checkConsistency();
1169         }
1170     };
1171 #endif
1172
1173 } // namespace WTF
1174
1175 using WTF::Vector;
1176
1177 #endif // WTF_Vector_h