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