af91a641de2cb391390d9c9ec61bc16dff0d9e00
[WebKit.git] / 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 "Assertions.h"
25 #include "FastMalloc.h"
26 #include "Noncopyable.h"
27 #include "NotFound.h"
28 #include "VectorTraits.h"
29 #include <limits>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <utility>
33
34 namespace WTF {
35
36     using std::min;
37     using std::max;
38
39     // WTF_ALIGN_OF / WTF_ALIGNED
40     #if COMPILER(GCC) || COMPILER(MINGW) || COMPILER(RVCT) || COMPILER(WINSCW)
41         #define WTF_ALIGN_OF(type) __alignof__(type)
42         #define WTF_ALIGNED(variable_type, variable, n) variable_type variable __attribute__((__aligned__(n)))
43     #elif COMPILER(MSVC)
44         #define WTF_ALIGN_OF(type) __alignof(type)
45         #define WTF_ALIGNED(variable_type, variable, n) __declspec(align(n)) variable_type variable
46     #else
47         #error WTF_ALIGN macros need alignment control.
48     #endif
49
50     #if COMPILER(GCC) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 303)
51         typedef char __attribute__((__may_alias__)) AlignedBufferChar; 
52     #else
53         typedef char AlignedBufferChar; 
54     #endif
55
56     template <size_t size, size_t alignment> struct AlignedBuffer;
57     template <size_t size> struct AlignedBuffer<size, 1> { AlignedBufferChar buffer[size]; };
58     template <size_t size> struct AlignedBuffer<size, 2> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 2);  };
59     template <size_t size> struct AlignedBuffer<size, 4> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 4);  };
60     template <size_t size> struct AlignedBuffer<size, 8> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 8);  };
61     template <size_t size> struct AlignedBuffer<size, 16> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 16); };
62     template <size_t size> struct AlignedBuffer<size, 32> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 32); };
63     template <size_t size> struct AlignedBuffer<size, 64> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 64); };
64
65     template <bool needsDestruction, typename T>
66     class 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     class 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     class 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                 src->~T();
123                 ++dst;
124                 ++src;
125             }
126         }
127         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
128         {
129             if (src > dst)
130                 move(src, srcEnd, dst);
131             else {
132                 T* dstEnd = dst + (srcEnd - src);
133                 while (src != srcEnd) {
134                     --srcEnd;
135                     --dstEnd;
136                     new (dstEnd) T(*srcEnd);
137                     srcEnd->~T();
138                 }
139             }
140         }
141     };
142
143     template<typename T>
144     struct VectorMover<true, T>
145     {
146         static void move(const T* src, const T* srcEnd, T* dst) 
147         {
148             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
149         }
150         static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
151         {
152             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
153         }
154     };
155
156     template <bool canCopyWithMemcpy, typename T>
157     class VectorCopier;
158
159     template<typename T>
160     struct VectorCopier<false, T>
161     {
162         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
163         {
164             while (src != srcEnd) {
165                 new (dst) T(*src);
166                 ++dst;
167                 ++src;
168             }
169         }
170     };
171
172     template<typename T>
173     struct VectorCopier<true, T>
174     {
175         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
176         {
177             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
178         }
179     };
180
181     template <bool canFillWithMemset, typename T>
182     class VectorFiller;
183
184     template<typename T>
185     struct VectorFiller<false, T>
186     {
187         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
188         {
189             while (dst != dstEnd) {
190                 new (dst) T(val);
191                 ++dst;
192             }
193         }
194     };
195
196     template<typename T>
197     struct VectorFiller<true, T>
198     {
199         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
200         {
201             ASSERT(sizeof(T) == sizeof(char));
202             memset(dst, val, dstEnd - dst);
203         }
204     };
205     
206     template<bool canCompareWithMemcmp, typename T>
207     class VectorComparer;
208     
209     template<typename T>
210     struct VectorComparer<false, T>
211     {
212         static bool compare(const T* a, const T* b, size_t size)
213         {
214             for (size_t i = 0; i < size; ++i)
215                 if (a[i] != b[i])
216                     return false;
217             return true;
218         }
219     };
220
221     template<typename T>
222     struct VectorComparer<true, T>
223     {
224         static bool compare(const T* a, const T* b, size_t size)
225         {
226             return memcmp(a, b, sizeof(T) * size) == 0;
227         }
228     };
229     
230     template<typename T>
231     struct VectorTypeOperations
232     {
233         static void destruct(T* begin, T* end)
234         {
235             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
236         }
237
238         static void initialize(T* begin, T* end)
239         {
240             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
241         }
242
243         static void move(const T* src, const T* srcEnd, T* dst)
244         {
245             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
246         }
247
248         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
249         {
250             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
251         }
252
253         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
254         {
255             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
256         }
257
258         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
259         {
260             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
261         }
262         
263         static bool compare(const T* a, const T* b, size_t size)
264         {
265             return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
266         }
267     };
268
269     template<typename T>
270     class VectorBufferBase : Noncopyable {
271     public:
272         void allocateBuffer(size_t newCapacity)
273         {
274             m_capacity = newCapacity;
275             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
276                 CRASH();
277             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
278         }
279
280         void deallocateBuffer(T* bufferToDeallocate)
281         {
282             if (m_buffer == bufferToDeallocate) {
283                 m_buffer = 0;
284                 m_capacity = 0;
285             }
286             fastFree(bufferToDeallocate);
287         }
288
289         T* buffer() { return m_buffer; }
290         const T* buffer() const { return m_buffer; }
291         T** bufferSlot() { return &m_buffer; }
292         size_t capacity() const { return m_capacity; }
293
294         T* releaseBuffer()
295         {
296             T* buffer = m_buffer;
297             m_buffer = 0;
298             m_capacity = 0;
299             return buffer;
300         }
301
302     protected:
303         VectorBufferBase()
304             : m_buffer(0)
305             , m_capacity(0)
306         {
307         }
308
309         VectorBufferBase(T* buffer, size_t capacity)
310             : m_buffer(buffer)
311             , m_capacity(capacity)
312         {
313         }
314
315         ~VectorBufferBase()
316         {
317             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
318         }
319
320         T* m_buffer;
321         size_t m_capacity;
322     };
323
324     template<typename T, size_t inlineCapacity>
325     class VectorBuffer;
326
327     template<typename T>
328     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
329     private:
330         typedef VectorBufferBase<T> Base;
331     public:
332         VectorBuffer()
333         {
334         }
335
336         VectorBuffer(size_t capacity)
337         {
338             allocateBuffer(capacity);
339         }
340
341         ~VectorBuffer()
342         {
343             deallocateBuffer(buffer());
344         }
345         
346         void swap(VectorBuffer<T, 0>& other)
347         {
348             std::swap(m_buffer, other.m_buffer);
349             std::swap(m_capacity, other.m_capacity);
350         }
351         
352         void restoreInlineBufferIfNeeded() { }
353
354         using Base::allocateBuffer;
355         using Base::deallocateBuffer;
356
357         using Base::buffer;
358         using Base::bufferSlot;
359         using Base::capacity;
360
361         using Base::releaseBuffer;
362     private:
363         using Base::m_buffer;
364         using Base::m_capacity;
365     };
366
367     template<typename T, size_t inlineCapacity>
368     class VectorBuffer : private VectorBufferBase<T> {
369     private:
370         typedef VectorBufferBase<T> Base;
371     public:
372         VectorBuffer()
373             : Base(inlineBuffer(), inlineCapacity)
374         {
375         }
376
377         VectorBuffer(size_t capacity)
378             : Base(inlineBuffer(), inlineCapacity)
379         {
380             if (capacity > inlineCapacity)
381                 Base::allocateBuffer(capacity);
382         }
383
384         ~VectorBuffer()
385         {
386             deallocateBuffer(buffer());
387         }
388
389         void allocateBuffer(size_t newCapacity)
390         {
391             if (newCapacity > inlineCapacity)
392                 Base::allocateBuffer(newCapacity);
393             else {
394                 m_buffer = inlineBuffer();
395                 m_capacity = inlineCapacity;
396             }
397         }
398
399         void deallocateBuffer(T* bufferToDeallocate)
400         {
401             if (bufferToDeallocate == inlineBuffer())
402                 return;
403             Base::deallocateBuffer(bufferToDeallocate);
404         }
405         
406         void restoreInlineBufferIfNeeded()
407         {
408             if (m_buffer)
409                 return;
410             m_buffer = inlineBuffer();
411             m_capacity = inlineCapacity;
412         }
413
414         using Base::buffer;
415         using Base::bufferSlot;
416         using Base::capacity;
417
418         T* releaseBuffer()
419         {
420             if (buffer() == inlineBuffer())
421                 return 0;
422             return Base::releaseBuffer();
423         }
424
425     private:
426         using Base::m_buffer;
427         using Base::m_capacity;
428
429         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
430         T* inlineBuffer() { return reinterpret_cast<T*>(m_inlineBuffer.buffer); }
431
432         AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
433     };
434
435     template<typename T, size_t inlineCapacity = 0>
436     class Vector {
437     private:
438         typedef VectorBuffer<T, inlineCapacity> Buffer;
439         typedef VectorTypeOperations<T> TypeOperations;
440
441     public:
442         typedef T ValueType;
443
444         typedef T* iterator;
445         typedef const T* const_iterator;
446
447         Vector() 
448             : m_size(0)
449         {
450         }
451         
452         explicit Vector(size_t size) 
453             : m_size(size)
454             , m_buffer(size)
455         {
456             if (begin())
457                 TypeOperations::initialize(begin(), end());
458         }
459
460         ~Vector()
461         {
462             if (m_size) shrink(0);
463         }
464
465         Vector(const Vector&);
466         template<size_t otherCapacity> 
467         Vector(const Vector<T, otherCapacity>&);
468
469         Vector& operator=(const Vector&);
470         template<size_t otherCapacity> 
471         Vector& operator=(const Vector<T, otherCapacity>&);
472
473         size_t size() const { return m_size; }
474         size_t capacity() const { return m_buffer.capacity(); }
475         bool isEmpty() const { return !size(); }
476
477         T& at(size_t i) 
478         { 
479             ASSERT(i < size());
480             return m_buffer.buffer()[i]; 
481         }
482         const T& at(size_t i) const 
483         {
484             ASSERT(i < size());
485             return m_buffer.buffer()[i]; 
486         }
487
488         T& operator[](size_t i) { return at(i); }
489         const T& operator[](size_t i) const { return at(i); }
490
491         T* data() { return m_buffer.buffer(); }
492         const T* data() const { return m_buffer.buffer(); }
493         T** dataSlot() { return m_buffer.bufferSlot(); }
494
495         iterator begin() { return data(); }
496         iterator end() { return begin() + m_size; }
497         const_iterator begin() const { return data(); }
498         const_iterator end() const { return begin() + m_size; }
499         
500         T& first() { return at(0); }
501         const T& first() const { return at(0); }
502         T& last() { return at(size() - 1); }
503         const T& last() const { return at(size() - 1); }
504
505         template<typename U> size_t find(const U&) const;
506
507         void shrink(size_t size);
508         void grow(size_t size);
509         void resize(size_t size);
510         void reserveCapacity(size_t newCapacity);
511         void reserveInitialCapacity(size_t initialCapacity);
512         void shrinkCapacity(size_t newCapacity);
513         void shrinkToFit() { shrinkCapacity(size()); }
514
515         void clear() { shrinkCapacity(0); }
516
517         template<typename U> void append(const U*, size_t);
518         template<typename U> void append(const U&);
519         template<typename U> void uncheckedAppend(const U& val);
520         template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
521
522         template<typename U> void insert(size_t position, const U*, size_t);
523         template<typename U> void insert(size_t position, const U&);
524         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
525
526         template<typename U> void prepend(const U*, size_t);
527         template<typename U> void prepend(const U&);
528         template<typename U, size_t c> void prepend(const Vector<U, c>&);
529
530         void remove(size_t position);
531         void remove(size_t position, size_t length);
532
533         void removeLast() 
534         {
535             ASSERT(!isEmpty());
536             shrink(size() - 1); 
537         }
538
539         Vector(size_t size, const T& val)
540             : m_size(size)
541             , m_buffer(size)
542         {
543             if (begin())
544                 TypeOperations::uninitializedFill(begin(), end(), val);
545         }
546
547         void fill(const T&, size_t);
548         void fill(const T& val) { fill(val, size()); }
549
550         template<typename Iterator> void appendRange(Iterator start, Iterator end);
551
552         T* releaseBuffer();
553
554         void swap(Vector<T, inlineCapacity>& other)
555         {
556             std::swap(m_size, other.m_size);
557             m_buffer.swap(other.m_buffer);
558         }
559
560     private:
561         void expandCapacity(size_t newMinCapacity);
562         const T* expandCapacity(size_t newMinCapacity, const T*);
563         template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
564
565         size_t m_size;
566         Buffer m_buffer;
567     };
568
569     template<typename T, size_t inlineCapacity>
570     Vector<T, inlineCapacity>::Vector(const Vector& other)
571         : m_size(other.size())
572         , m_buffer(other.capacity())
573     {
574         if (begin())
575             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
576     }
577
578     template<typename T, size_t inlineCapacity>
579     template<size_t otherCapacity> 
580     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
581         : m_size(other.size())
582         , m_buffer(other.capacity())
583     {
584         if (begin())
585             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
586     }
587
588     template<typename T, size_t inlineCapacity>
589     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
590     {
591         if (&other == this)
592             return *this;
593         
594         if (size() > other.size())
595             shrink(other.size());
596         else if (other.size() > capacity()) {
597             clear();
598             reserveCapacity(other.size());
599             if (!begin())
600                 return *this;
601         }
602         
603         std::copy(other.begin(), other.begin() + size(), begin());
604         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
605         m_size = other.size();
606
607         return *this;
608     }
609
610     template<typename T, size_t inlineCapacity>
611     template<size_t otherCapacity> 
612     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
613     {
614         if (&other == this)
615             return *this;
616         
617         if (size() > other.size())
618             shrink(other.size());
619         else if (other.size() > capacity()) {
620             clear();
621             reserveCapacity(other.size());
622             if (!begin())
623                 return *this;
624         }
625         
626         std::copy(other.begin(), other.begin() + size(), begin());
627         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
628         m_size = other.size();
629
630         return *this;
631     }
632
633     template<typename T, size_t inlineCapacity>
634     template<typename U>
635     size_t Vector<T, inlineCapacity>::find(const U& value) const
636     {
637         for (size_t i = 0; i < size(); ++i) {
638             if (at(i) == value)
639                 return i;
640         }
641         return notFound;
642     }
643
644     template<typename T, size_t inlineCapacity>
645     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
646     {
647         if (size() > newSize)
648             shrink(newSize);
649         else if (newSize > capacity()) {
650             clear();
651             reserveCapacity(newSize);
652             if (!begin())
653                 return;
654         }
655         
656         std::fill(begin(), end(), val);
657         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
658         m_size = newSize;
659     }
660
661     template<typename T, size_t inlineCapacity>
662     template<typename Iterator>
663     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
664     {
665         for (Iterator it = start; it != end; ++it)
666             append(*it);
667     }
668
669     template<typename T, size_t inlineCapacity>
670     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
671     {
672         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
673     }
674     
675     template<typename T, size_t inlineCapacity>
676     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
677     {
678         if (ptr < begin() || ptr >= end()) {
679             expandCapacity(newMinCapacity);
680             return ptr;
681         }
682         size_t index = ptr - begin();
683         expandCapacity(newMinCapacity);
684         return begin() + index;
685     }
686
687     template<typename T, size_t inlineCapacity> template<typename U>
688     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
689     {
690         expandCapacity(newMinCapacity);
691         return ptr;
692     }
693
694     template<typename T, size_t inlineCapacity>
695     void Vector<T, inlineCapacity>::resize(size_t size)
696     {
697         if (size <= m_size)
698             TypeOperations::destruct(begin() + size, end());
699         else {
700             if (size > capacity())
701                 expandCapacity(size);
702             if (begin())
703                 TypeOperations::initialize(end(), begin() + size);
704         }
705         
706         m_size = size;
707     }
708
709     template<typename T, size_t inlineCapacity>
710     void Vector<T, inlineCapacity>::shrink(size_t size)
711     {
712         ASSERT(size <= m_size);
713         TypeOperations::destruct(begin() + size, end());
714         m_size = size;
715     }
716
717     template<typename T, size_t inlineCapacity>
718     void Vector<T, inlineCapacity>::grow(size_t size)
719     {
720         ASSERT(size >= m_size);
721         if (size > capacity())
722             expandCapacity(size);
723         if (begin())
724             TypeOperations::initialize(end(), begin() + size);
725         m_size = size;
726     }
727
728     template<typename T, size_t inlineCapacity>
729     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
730     {
731         if (newCapacity <= capacity())
732             return;
733         T* oldBuffer = begin();
734         T* oldEnd = end();
735         m_buffer.allocateBuffer(newCapacity);
736         if (begin())
737             TypeOperations::move(oldBuffer, oldEnd, begin());
738         m_buffer.deallocateBuffer(oldBuffer);
739     }
740     
741     template<typename T, size_t inlineCapacity>
742     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
743     {
744         ASSERT(!m_size);
745         ASSERT(capacity() == inlineCapacity);
746         if (initialCapacity > inlineCapacity)
747             m_buffer.allocateBuffer(initialCapacity);
748     }
749     
750     template<typename T, size_t inlineCapacity>
751     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
752     {
753         if (newCapacity >= capacity())
754             return;
755
756         if (newCapacity < size()) 
757             shrink(newCapacity);
758
759         T* oldBuffer = begin();
760         if (newCapacity > 0) {
761             T* oldEnd = end();
762             m_buffer.allocateBuffer(newCapacity);
763             if (begin() != oldBuffer)
764                 TypeOperations::move(oldBuffer, oldEnd, begin());
765         }
766
767         m_buffer.deallocateBuffer(oldBuffer);
768         m_buffer.restoreInlineBufferIfNeeded();
769     }
770
771     // Templatizing these is better than just letting the conversion happen implicitly,
772     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
773     // without refcount thrash.
774
775     template<typename T, size_t inlineCapacity> template<typename U>
776     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
777     {
778         size_t newSize = m_size + dataSize;
779         if (newSize > capacity()) {
780             data = expandCapacity(newSize, data);
781             if (!begin())
782                 return;
783         }
784         if (newSize < m_size)
785             CRASH();
786         T* dest = end();
787         for (size_t i = 0; i < dataSize; ++i)
788             new (&dest[i]) T(data[i]);
789         m_size = newSize;
790     }
791
792     template<typename T, size_t inlineCapacity> template<typename U>
793     ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
794     {
795         const U* ptr = &val;
796         if (size() == capacity()) {
797             ptr = expandCapacity(size() + 1, ptr);
798             if (!begin())
799                 return;
800         }
801             
802 #if COMPILER(MSVC7)
803         // FIXME: MSVC7 generates compilation errors when trying to assign
804         // a pointer to a Vector of its base class (i.e. can't downcast). So far
805         // I've been unable to determine any logical reason for this, so I can
806         // only assume it is a bug with the compiler. Casting is a bad solution,
807         // however, because it subverts implicit conversions, so a better 
808         // one is needed. 
809         new (end()) T(static_cast<T>(*ptr));
810 #else
811         new (end()) T(*ptr);
812 #endif
813         ++m_size;
814     }
815
816     // This version of append saves a branch in the case where you know that the
817     // vector's capacity is large enough for the append to succeed.
818
819     template<typename T, size_t inlineCapacity> template<typename U>
820     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
821     {
822         ASSERT(size() < capacity());
823         const U* ptr = &val;
824         new (end()) T(*ptr);
825         ++m_size;
826     }
827
828     // This method should not be called append, a better name would be appendElements.
829     // It could also be eliminated entirely, and call sites could just use
830     // appendRange(val.begin(), val.end()).
831     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
832     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
833     {
834         append(val.begin(), val.size());
835     }
836
837     template<typename T, size_t inlineCapacity> template<typename U>
838     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
839     {
840         ASSERT(position <= size());
841         size_t newSize = m_size + dataSize;
842         if (newSize > capacity()) {
843             data = expandCapacity(newSize, data);
844             if (!begin())
845                 return;
846         }
847         if (newSize < m_size)
848             CRASH();
849         T* spot = begin() + position;
850         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
851         for (size_t i = 0; i < dataSize; ++i)
852             new (&spot[i]) T(data[i]);
853         m_size = newSize;
854     }
855      
856     template<typename T, size_t inlineCapacity> template<typename U>
857     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
858     {
859         ASSERT(position <= size());
860         const U* data = &val;
861         if (size() == capacity()) {
862             data = expandCapacity(size() + 1, data);
863             if (!begin())
864                 return;
865         }
866         T* spot = begin() + position;
867         TypeOperations::moveOverlapping(spot, end(), spot + 1);
868         new (spot) T(*data);
869         ++m_size;
870     }
871    
872     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
873     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
874     {
875         insert(position, val.begin(), val.size());
876     }
877
878     template<typename T, size_t inlineCapacity> template<typename U>
879     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
880     {
881         insert(0, data, dataSize);
882     }
883
884     template<typename T, size_t inlineCapacity> template<typename U>
885     inline void Vector<T, inlineCapacity>::prepend(const U& val)
886     {
887         insert(0, val);
888     }
889    
890     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
891     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
892     {
893         insert(0, val.begin(), val.size());
894     }
895     
896     template<typename T, size_t inlineCapacity>
897     inline void Vector<T, inlineCapacity>::remove(size_t position)
898     {
899         ASSERT(position < size());
900         T* spot = begin() + position;
901         spot->~T();
902         TypeOperations::moveOverlapping(spot + 1, end(), spot);
903         --m_size;
904     }
905
906     template<typename T, size_t inlineCapacity>
907     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
908     {
909         ASSERT(position < size());
910         ASSERT(position + length < size());
911         T* beginSpot = begin() + position;
912         T* endSpot = beginSpot + length;
913         TypeOperations::destruct(beginSpot, endSpot); 
914         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
915         m_size -= length;
916     }
917
918     template<typename T, size_t inlineCapacity>
919     inline T* Vector<T, inlineCapacity>::releaseBuffer()
920     {
921         T* buffer = m_buffer.releaseBuffer();
922         if (inlineCapacity && !buffer && m_size) {
923             // If the vector had some data, but no buffer to release,
924             // that means it was using the inline buffer. In that case,
925             // we create a brand new buffer so the caller always gets one.
926             size_t bytes = m_size * sizeof(T);
927             buffer = static_cast<T*>(fastMalloc(bytes));
928             memcpy(buffer, data(), bytes);
929         }
930         m_size = 0;
931         return buffer;
932     }
933
934     template<typename T, size_t inlineCapacity>
935     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
936     {
937         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
938         iterator end = collection.end();
939         for (iterator it = collection.begin(); it != end; ++it)
940             delete *it;
941     }
942
943     template<typename T, size_t inlineCapacity>
944     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
945     {
946         a.swap(b);
947     }
948
949     template<typename T, size_t inlineCapacity>
950     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
951     {
952         if (a.size() != b.size())
953             return false;
954
955         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
956     }
957
958     template<typename T, size_t inlineCapacity>
959     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
960     {
961         return !(a == b);
962     }
963
964
965 } // namespace WTF
966
967 using WTF::Vector;
968
969 #endif // WTF_Vector_h