2006-11-20 Samuel Weinig <sam@webkit.org>
[WebKit-https.git] / JavaScriptCore / wtf / Vector.h
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  *  This file is part of the KDE libraries
4  *  Copyright (C) 2005, 2006 Apple Computer, Inc.
5  *
6  *  This library is free software; you can redistribute it and/or
7  *  modify it under the terms of the GNU Library General Public
8  *  License as published by the Free Software Foundation; either
9  *  version 2 of the License, or (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  *  Library General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Library General Public License
17  *  along with this library; see the file COPYING.LIB.  If not, write to
18  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  *  Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #ifndef WTF_Vector_h
24 #define WTF_Vector_h
25
26 #include "Assertions.h"
27 #include "FastMalloc.h"
28 #include "VectorTraits.h"
29 #include <limits>
30 #include <stdlib.h>
31 #include <utility>
32
33 // FIXME: For unknown reasons defining NOMINMAX is not preventing the
34 // min and max macros from being defined on Win32.
35 #ifdef max
36 #undef max
37 #endif
38
39 #ifdef min
40 #undef min
41 #endif
42
43 namespace WTF {
44
45     using std::min;
46     using std::max;
47     
48     template <bool needsDestruction, typename T>
49     class VectorDestructor;
50
51     template<typename T>
52     struct VectorDestructor<false, T>
53     {
54         static void destruct(T*, T*) {}
55     };
56
57     template<typename T>
58     struct VectorDestructor<true, T>
59     {
60         static void destruct(T* begin, T* end) 
61         {
62             for (T* cur = begin; cur != end; ++cur)
63                 cur->~T();
64         }
65     };
66
67     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
68     class VectorInitializer;
69
70     template<bool ignore, typename T>
71     struct VectorInitializer<false, ignore, T>
72     {
73         static void initialize(T*, T*) {}
74     };
75
76     template<typename T>
77     struct VectorInitializer<true, false, T>
78     {
79         static void initialize(T* begin, T* end) 
80         {
81             for (T* cur = begin; cur != end; ++cur)
82                 new (cur) T;
83         }
84     };
85
86     template<typename T>
87     struct VectorInitializer<true, true, T>
88     {
89         static void initialize(T* begin, T* end) 
90         {
91             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
92         }
93     };
94
95     template <bool canMoveWithMemcpy, typename T>
96     class VectorMover;
97
98     template<typename T>
99     struct VectorMover<false, T>
100     {
101         static void move(const T* src, const T* srcEnd, T* dst)
102         {
103             while (src != srcEnd) {
104                 new (dst) T(*src);
105                 src->~T();
106                 ++dst;
107                 ++src;
108             }
109         }
110         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
111         {
112             if (src > dst)
113                 move(src, srcEnd, dst);
114             else {
115                 T* dstEnd = dst + (srcEnd - src);
116                 while (src != srcEnd) {
117                     --srcEnd;
118                     --dstEnd;
119                     new (dstEnd) T(*srcEnd);
120                     srcEnd->~T();
121                 }
122             }
123         }
124     };
125
126     template<typename T>
127     struct VectorMover<true, T>
128     {
129         static void move(const T* src, const T* srcEnd, T* dst) 
130         {
131             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
132         }
133         static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
134         {
135             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
136         }
137     };
138
139     template <bool canCopyWithMemcpy, typename T>
140     class VectorCopier;
141
142     template<typename T>
143     struct VectorCopier<false, T>
144     {
145         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
146         {
147             while (src != srcEnd) {
148                 new (dst) T(*src);
149                 ++dst;
150                 ++src;
151             }
152         }
153     };
154
155     template<typename T>
156     struct VectorCopier<true, T>
157     {
158         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
159         {
160             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
161         }
162     };
163
164     template <bool canFillWithMemset, typename T>
165     class VectorFiller;
166
167     template<typename T>
168     struct VectorFiller<false, T>
169     {
170         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
171         {
172             while (dst != dstEnd) {
173                 new (dst) T(val);
174                 ++dst;
175             }
176         }
177     };
178
179     template<typename T>
180     struct VectorFiller<true, T>
181     {
182         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
183         {
184             ASSERT(sizeof(T) == sizeof(char));
185             memset(dst, val, dstEnd - dst);
186         }
187     };
188     
189     template<typename T>
190     struct VectorTypeOperations
191     {
192         static void destruct(T* begin, T* end)
193         {
194             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
195         }
196
197         static void initialize(T* begin, T* end)
198         {
199             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
200         }
201
202         static void move(const T* src, const T* srcEnd, T* dst)
203         {
204             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
205         }
206
207         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
208         {
209             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
210         }
211
212         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
213         {
214             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
215         }
216
217         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
218         {
219             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
220         }
221     };
222
223     template<typename T, size_t inlineCapacity>
224     class VectorBuffer;
225
226     template<typename T>
227     class VectorBuffer<T, 0> {
228     public:
229         VectorBuffer()
230             : m_buffer(0), m_capacity(0)
231         {
232         }
233         
234         VectorBuffer(size_t capacity)
235 #if !ASSERT_DISABLED
236             : m_capacity(0)
237 #endif
238         {
239             allocateBuffer(capacity);
240         }
241
242         ~VectorBuffer()
243         {
244             deallocateBuffer(m_buffer);
245         }
246         
247         static void deallocateBuffer(T* buffer)
248         {
249             fastFree(buffer);
250         }
251         
252         void allocateBuffer(size_t newCapacity)
253         {
254             ASSERT(newCapacity >= m_capacity);
255             m_capacity = newCapacity;
256             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
257                 abort();
258             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
259         }
260
261         T* buffer() { return m_buffer; }
262         const T* buffer() const { return m_buffer; }
263         size_t capacity() const { return m_capacity; }
264
265         void swap(VectorBuffer<T, 0>& other)
266         {
267             std::swap(m_capacity, other.m_capacity);
268             std::swap(m_buffer, other.m_buffer);
269         }
270
271         T* releaseBuffer()
272         {
273             T* buffer = m_buffer;
274             m_buffer = 0;
275             m_capacity = 0;
276             return buffer;
277         }
278
279     protected:
280         VectorBuffer(T* buffer, size_t capacity)
281             : m_buffer(buffer), m_capacity(capacity)
282         {
283         }
284
285         T* m_buffer;
286
287     private:
288         size_t m_capacity;
289     };
290
291     template<typename T, size_t inlineCapacity>
292     class VectorBuffer : private VectorBuffer<T, 0> {
293     private:
294         typedef VectorBuffer<T, 0> BaseBuffer;
295     public:
296         VectorBuffer()
297             : BaseBuffer(inlineBuffer(), inlineCapacity)
298         {
299         }
300
301         VectorBuffer(size_t capacity)
302             : BaseBuffer(inlineBuffer(), inlineCapacity)
303         {
304             if (capacity > inlineCapacity)
305                 allocateBuffer(capacity);
306         }
307
308         ~VectorBuffer()
309         {
310             if (buffer() == inlineBuffer())
311                 BaseBuffer::m_buffer = 0;
312         }
313
314         void deallocateBuffer(T* buffer)
315         {
316             if (buffer != inlineBuffer())
317                 BaseBuffer::deallocateBuffer(buffer);
318         }
319
320         using BaseBuffer::allocateBuffer;
321
322         using BaseBuffer::buffer;
323         using BaseBuffer::capacity;
324
325         T* releaseBuffer()
326         {
327             if (buffer() == inlineBuffer())
328                 return 0;
329             return BaseBuffer::releaseBuffer();
330         }
331
332         void swap(VectorBuffer<T, inlineCapacity>&);
333
334     private:
335         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
336         T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
337
338         // FIXME: Nothing guarantees this buffer is appropriately aligned to hold objects of type T.
339         char m_inlineBuffer[m_inlineBufferSize];
340     };
341
342     template<typename T, size_t inlineCapacity = 0>
343     class Vector {
344     private:
345         typedef VectorBuffer<T, inlineCapacity> Impl;
346         typedef VectorTypeOperations<T> TypeOperations;
347
348     public:
349         typedef T* iterator;
350         typedef const T* const_iterator;
351
352         Vector() 
353             : m_size(0)
354         {
355         }
356         
357         explicit Vector(size_t size) 
358             : m_size(0)
359         {
360             resize(size);
361         }
362
363         ~Vector()
364         {
365             clear();
366         }
367
368         Vector(const Vector&);
369         template<size_t otherCapacity> 
370         Vector(const Vector<T, otherCapacity>&);
371
372         Vector& operator=(const Vector&);
373         template<size_t otherCapacity> 
374         Vector& operator=(const Vector<T, otherCapacity>&);
375
376         size_t size() const { return m_size; }
377         size_t capacity() const { return m_impl.capacity(); }
378         bool isEmpty() const { return !size(); }
379
380         T& at(size_t i) 
381         { 
382             ASSERT(i < size());
383             return m_impl.buffer()[i]; 
384         }
385         const T& at(size_t i) const 
386         {
387             ASSERT(i < size());
388             return m_impl.buffer()[i]; 
389         }
390
391         T& operator[](long i) { return at(i); }
392         const T& operator[](long i) const { return at(i); }
393         T& operator[](unsigned long i) { return at(i); }
394         const T& operator[](unsigned long i) const { return at(i); }
395         T& operator[](int i) { return at(i); }
396         const T& operator[](int i) const { return at(i); }
397         T& operator[](unsigned i) { return at(i); }
398         const T& operator[](unsigned i) const { return at(i); }
399         T& operator[](short i) { return at(i); }
400         const T& operator[](short i) const { return at(i); }
401         T& operator[](unsigned short i) { return at(i); }
402         const T& operator[](unsigned short i) const { return at(i); }
403
404         T* data() { return m_impl.buffer(); }
405         const T* data() const { return m_impl.buffer(); }
406         operator T*() { return data(); }
407         operator const T*() const { return data(); }
408
409         iterator begin() { return data(); }
410         iterator end() { return begin() + m_size; }
411         const_iterator begin() const { return data(); }
412         const_iterator end() const { return begin() + m_size; }
413         
414         T& first() { return at(0); }
415         const T& first() const { return at(0); }
416         T& last() { return at(size() - 1); }
417         const T& last() const { return at(size() - 1); }
418
419         void resize(size_t size);
420         void reserveCapacity(size_t newCapacity);
421
422         void clear() { resize(0); }
423
424         template<typename U> void append(const U*, size_t);
425         template<typename U> void append(const U&);
426         template<typename U, size_t c> void append(const Vector<U, c>&);
427
428         template<typename U> void insert(size_t position, const U&);
429
430         void remove(size_t position);
431
432         void removeLast() 
433         {
434             ASSERT(!isEmpty());
435             resize(size() - 1); 
436         }
437
438         Vector(size_t size, const T& val)
439             : m_size(size)
440             , m_impl(size)
441         {
442             TypeOperations::uninitializedFill(begin(), end(), val);
443         }
444
445         void fill(const T&, size_t);
446         void fill(const T& val) { fill(val, size()); }
447
448         T* releaseBuffer();
449
450         void swap(Vector<T, inlineCapacity>& other)
451         {
452             std::swap(m_size, other.m_size);
453             m_impl.swap(other.m_impl);
454         }
455
456     private:
457         void expandCapacity(size_t newMinCapacity);
458         const T* expandCapacity(size_t newMinCapacity, const T*);
459         template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
460
461         size_t m_size;
462         Impl m_impl;
463     };
464
465     template<typename T, size_t inlineCapacity>
466     Vector<T, inlineCapacity>::Vector(const Vector& other)
467         : m_size(other.size())
468         , m_impl(other.capacity())
469     {
470         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
471     }
472
473     template<typename T, size_t inlineCapacity>
474     template<size_t otherCapacity> 
475     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
476         : m_size(other.size())
477         , m_impl(other.capacity())
478     {
479         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
480     }
481
482     template<typename T, size_t inlineCapacity>
483     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
484     {
485         if (&other == this)
486             return *this;
487         
488         if (size() > other.size())
489             resize(other.size());
490         else if (other.size() > capacity()) {
491             clear();
492             reserveCapacity(other.size());
493         }
494         
495         std::copy(other.begin(), other.begin() + size(), begin());
496         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
497         m_size = other.size();
498
499         return *this;
500     }
501
502     template<typename T, size_t inlineCapacity>
503     template<size_t otherCapacity> 
504     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
505     {
506         if (&other == this)
507             return *this;
508         
509         if (size() > other.size())
510             resize(other.size());
511         else if (other.size() > capacity()) {
512             clear();
513             reserveCapacity(other.size());
514         }
515         
516         std::copy(other.begin(), other.begin() + size(), begin());
517         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
518         m_size = other.size();
519
520         return *this;
521     }
522
523     template<typename T, size_t inlineCapacity>
524     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
525     {
526         if (size() > newSize)
527             resize(newSize);
528         else if (newSize > capacity()) {
529             clear();
530             reserveCapacity(newSize);
531         }
532         
533         std::fill(begin(), end(), val);
534         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
535         m_size = newSize;
536     }
537
538     template<typename T, size_t inlineCapacity>
539     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
540     {
541         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
542     }
543     
544     template<typename T, size_t inlineCapacity>
545     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
546     {
547         if (ptr < begin() || ptr >= end()) {
548             expandCapacity(newMinCapacity);
549             return ptr;
550         }
551         size_t index = ptr - begin();
552         expandCapacity(newMinCapacity);
553         return begin() + index;
554     }
555
556     template<typename T, size_t inlineCapacity> template<typename U>
557     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
558     {
559         expandCapacity(newMinCapacity);
560         return ptr;
561     }
562
563     template<typename T, size_t inlineCapacity>
564     void Vector<T, inlineCapacity>::resize(size_t size)
565     {
566         if (size <= m_size)
567             TypeOperations::destruct(begin() + size, end());
568         else {
569             if (size > capacity())
570                 expandCapacity(size);
571             TypeOperations::initialize(end(), begin() + size);
572         }
573         
574         m_size = size;
575     }
576
577     template<typename T, size_t inlineCapacity>
578     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
579     {
580         if (newCapacity < capacity())
581             return;
582         T* oldBuffer = begin();
583         T* oldEnd = end();
584         m_impl.allocateBuffer(newCapacity);
585         TypeOperations::move(oldBuffer, oldEnd, begin());
586         m_impl.deallocateBuffer(oldBuffer);
587     }
588
589     // Templatizing these is better than just letting the conversion happen implicitly,
590     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
591     // without refcount thrash.
592
593     template<typename T, size_t inlineCapacity> template<typename U>
594     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
595     {
596         size_t newSize = m_size + dataSize;
597         if (newSize > capacity())
598             data = expandCapacity(newSize, data);
599         T* dest = end();
600         for (size_t i = 0; i < dataSize; ++i)
601             new (&dest[i]) T(data[i]);
602         m_size = newSize;
603     }
604
605     template<typename T, size_t inlineCapacity> template<typename U>
606     inline void Vector<T, inlineCapacity>::append(const U& val)
607     {
608         const U* ptr = &val;
609         if (size() == capacity())
610             ptr = expandCapacity(size() + 1, ptr);
611         new (end()) T(*ptr);
612         ++m_size;
613     }
614
615     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
616     inline void Vector<T, inlineCapacity>::append(const Vector<U, c>& val)
617     {
618         append(val.begin(), val.size());
619     }
620     
621     template<typename T, size_t inlineCapacity> template<typename U>
622     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
623     {
624         ASSERT(position <= size());
625         const U* ptr = &val;
626         if (size() == capacity())
627             ptr = expandCapacity(size() + 1, ptr);
628         T* spot = begin() + position;
629         TypeOperations::moveOverlapping(spot, end(), spot + 1);
630         new (spot) T(*ptr);
631         ++m_size;
632     }
633
634     template<typename T, size_t inlineCapacity>
635     inline void Vector<T, inlineCapacity>::remove(size_t position)
636     {
637         ASSERT(position < size());
638         T* spot = begin() + position;
639         spot->~T();
640         TypeOperations::moveOverlapping(spot + 1, end(), spot);
641         --m_size;
642     }
643
644     template<typename T, size_t inlineCapacity>
645     T* Vector<T, inlineCapacity>::releaseBuffer()
646     {
647         T* buffer = m_impl.releaseBuffer();
648         if (!buffer && m_size) {
649             // If the vector had some data, but no buffer to release,
650             // that means it was using the inline buffer. In that case,
651             // we create a brand new buffer so the caller always gets one.
652             size_t bytes = m_size * sizeof(T);
653             buffer = static_cast<T*>(fastMalloc(bytes));
654             memcpy(buffer, data(), bytes);
655         }
656         m_size = 0;
657         return buffer;
658     }
659
660     template<typename T, size_t inlineCapacity>
661     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
662     {
663         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
664         iterator end = collection.end();
665         for (iterator it = collection.begin(); it != end; ++it)
666             delete *it;
667     }
668
669     template<typename T, size_t inlineCapacity>
670     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
671     {
672         a.swap(b);
673     }
674
675 } // namespace WTF
676
677 using WTF::Vector;
678
679 #endif // WTF_Vector_h