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