* kxmlcore/Vector.h: Quick fix to try to get Windows compiling again.
[WebKit-https.git] / JavaScriptCore / kxmlcore / 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 KXMLCORE_VECTOR_H
24 #define KXMLCORE_VECTOR_H
25
26 #include "Assertions.h"
27 #include "VectorTraits.h"
28 #include <limits>
29 #include <stdlib.h>
30 #include <utility>
31
32 // Temporary workaround for Win32.
33 // We should use NOMINMAX instead.
34 #undef max
35
36 namespace KXMLCore {
37
38     using std::min;
39     using std::max;
40     
41     template <bool needsDestruction, typename T>
42     class VectorDestructor;
43
44     template<typename T>
45     struct VectorDestructor<false, T>
46     {
47         static void destruct(T*, T*) {}
48     };
49
50     template<typename T>
51     struct VectorDestructor<true, T>
52     {
53         static void destruct(T* begin, T* end) 
54         {
55             for (T* cur = begin; cur != end; ++cur)
56                 cur->~T();
57         }
58     };
59
60     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
61     class VectorInitializer;
62
63     template<bool ignore, typename T>
64     struct VectorInitializer<false, ignore, T>
65     {
66         static void initialize(T*, T*) {}
67     };
68
69     template<typename T>
70     struct VectorInitializer<true, false, T>
71     {
72         static void initialize(T* begin, T* end) 
73         {
74             for (T* cur = begin; cur != end; ++cur)
75                 new (cur) T;
76         }
77     };
78
79     template<typename T>
80     struct VectorInitializer<true, true, T>
81     {
82         static void initialize(T* begin, T* end) 
83         {
84             memset(begin, 0, reinterpret_cast<char *>(end) - reinterpret_cast<char *>(begin));
85         }
86     };
87
88     template <bool canMoveWithMemcpy, typename T>
89     class VectorMover;
90
91     template<typename T>
92     struct VectorMover<false, T>
93     {
94         static void move(const T* src, const T* srcEnd, T* dst)
95         {
96             while (src != srcEnd) {
97                 new (dst) T(*src);
98                 src->~T();
99                 ++dst;
100                 ++src;
101             }
102         }
103         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
104         {
105             if (src > dst)
106                 move(src, srcEnd, dst);
107             else {
108                 T* dstEnd = dst + (srcEnd - src);
109                 while (src != srcEnd) {
110                     --srcEnd;
111                     --dstEnd;
112                     new (dstEnd) T(*srcEnd);
113                     srcEnd->~T();
114                 }
115             }
116         }
117     };
118
119     template<typename T>
120     struct VectorMover<true, T>
121     {
122         static void move(const T* src, const T* srcEnd, T* dst) 
123         {
124             memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
125         }
126         static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
127         {
128             memmove(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
129         }
130     };
131
132     template <bool canCopyWithMemcpy, typename T>
133     class VectorCopier;
134
135     template<typename T>
136     struct VectorCopier<false, T>
137     {
138         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
139         {
140             while (src != srcEnd) {
141                 new (dst) T(*src);
142                 ++dst;
143                 ++src;
144             }
145         }
146     };
147
148     template<typename T>
149     struct VectorCopier<true, T>
150     {
151         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
152         {
153             memcpy(dst, src, reinterpret_cast<const char *>(srcEnd) - reinterpret_cast<const char *>(src));
154         }
155     };
156
157     template <bool canFillWithMemset, typename T>
158     class VectorFiller;
159
160     template<typename T>
161     struct VectorFiller<false, T>
162     {
163         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
164         {
165             while (dst != dstEnd) {
166                 new (dst) T(val);
167                 ++dst;
168             }
169         }
170     };
171
172     template<typename T>
173     struct VectorFiller<true, T>
174     {
175         static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
176         {
177             ASSERT(sizeof(T) == sizeof(char));
178             memset(dst, val, dstEnd - dst);
179         }
180     };
181     
182     template<typename T>
183     struct VectorTypeOperations
184     {
185         static void destruct(T* begin, T* end)
186         {
187             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
188         }
189
190         static void initialize(T* begin, T* end)
191         {
192             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
193         }
194
195         static void move(const T* src, const T* srcEnd, T* dst)
196         {
197             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
198         }
199
200         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
201         {
202             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
203         }
204
205         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
206         {
207             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
208         }
209
210         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
211         {
212             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
213         }
214     };
215
216     template<typename T, size_t inlineCapacity>
217     class VectorBuffer;
218
219     template<typename T>
220     class VectorBuffer<T, 0> 
221     {
222     public:
223         VectorBuffer()
224             : m_capacity(0)
225             , m_buffer(0)
226         {
227         }
228         
229         VectorBuffer(size_t capacity)
230             : m_capacity(0)
231         {
232             allocateBuffer(capacity);
233         }
234
235         ~VectorBuffer()
236         {
237             deallocateBuffer(m_buffer);
238         }
239         
240         void deallocateBuffer(T* buffer)
241         {
242             fastFree(buffer);
243         }
244         
245         void allocateBuffer(size_t newCapacity)
246         {
247             ASSERT(newCapacity >= m_capacity);
248             m_capacity = newCapacity;
249             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
250                 abort();
251             m_buffer = reinterpret_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
252         }
253
254         T* buffer() { return m_buffer; }
255         const T* buffer() const { return m_buffer; }
256         size_t capacity() const { return m_capacity; }
257
258     protected:
259         VectorBuffer(T* buffer, size_t capacity)
260             : m_capacity(capacity)
261             , m_buffer(buffer)
262         {
263         }
264
265         size_t m_capacity;
266         T *m_buffer;
267     };
268
269     template<typename T, size_t inlineCapacity>
270     class VectorBuffer : public VectorBuffer<T, 0> {
271     private:
272         typedef VectorBuffer<T, 0> BaseBuffer;
273     public:
274         VectorBuffer() 
275             : BaseBuffer(inlineBuffer(), inlineCapacity)
276         {
277         }
278
279         VectorBuffer(size_t capacity)
280             : BaseBuffer(inlineBuffer(), inlineCapacity)
281         {
282             if (capacity > inlineCapacity)
283                 BaseBuffer::allocateBuffer(capacity);
284         }
285
286         ~VectorBuffer()
287         {
288             if (BaseBuffer::buffer() == inlineBuffer())
289                 BaseBuffer::m_buffer = 0;
290         }
291
292         void deallocateBuffer(T* buffer)
293         {
294             if (buffer != inlineBuffer())
295                 BaseBuffer::deallocateBuffer(buffer);
296         }
297
298     private:
299         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
300         T *inlineBuffer() { return reinterpret_cast<T *>(&m_inlineBuffer); }
301         char m_inlineBuffer[m_inlineBufferSize];
302     };
303
304     template<typename T, size_t inlineCapacity = 0>
305     class Vector {
306     private:
307         typedef VectorBuffer<T, inlineCapacity> Impl;
308         typedef VectorTypeOperations<T> TypeOperations;
309
310     public:
311         typedef T* iterator;
312         typedef const T* const_iterator;
313
314         Vector() 
315             : m_size(0)
316         {
317         }
318         
319         explicit Vector(size_t size) 
320             : m_size(0)
321         {
322             resize(size);
323         }
324
325         ~Vector()
326         {
327             clear();
328         }
329
330         Vector(const Vector&);
331         template<size_t otherCapacity> 
332         Vector(const Vector<T, otherCapacity>&);
333
334         Vector& operator=(const Vector&);
335         template<size_t otherCapacity> 
336         Vector& operator=(const Vector<T, otherCapacity>&);
337
338         size_t size() const { return m_size; }
339         size_t capacity() const { return m_impl.capacity(); }
340         bool isEmpty() const { return !size(); }
341
342         T& at(size_t i) 
343         { 
344             ASSERT(i < size());
345             return m_impl.buffer()[i]; 
346         }
347         const T& at(size_t i) const 
348         {
349             ASSERT(i < size());
350             return m_impl.buffer()[i]; 
351         }
352
353         T& operator[](unsigned long i) { return at(i); }
354         const T& operator[](unsigned long i) const { return at(i); }
355         T& operator[](int i) { return at(i); }
356         const T& operator[](int i) const { return at(i); }
357         T& operator[](unsigned i) { return at(i); }
358         const T& operator[](unsigned i) const { return at(i); }
359
360         T* data() { return m_impl.buffer(); }
361         const T* data() const { return m_impl.buffer(); }
362         operator T*() { return data(); }
363         operator const T*() const { return data(); }
364
365         iterator begin() { return data(); }
366         iterator end() { return begin() + m_size; }
367         const_iterator begin() const { return data(); }
368         const_iterator end() const { return begin() + m_size; }
369         
370         T& first() { return at(0); }
371         const T& first() const { return at(0); }
372         T& last() { return at(size() - 1); }
373         const T& last() const { return at(size() - 1); }
374
375         void resize(size_t size);
376         void reserveCapacity(size_t newCapacity);
377
378         void clear() { resize(0); }
379
380         template<typename U> void append(const U&);
381         template<typename U> void insert(size_t position, const U&);
382         void remove(size_t position);
383
384         void removeLast() 
385         {
386             ASSERT(!isEmpty());
387             resize(size() - 1); 
388         }
389
390         Vector(size_t size, const T& val)
391             : m_size(size)
392             , m_impl(size)
393         {
394             TypeOperations::uninitializedFill(begin(), end(), val);
395         }
396
397         void fill(const T& val, size_t size);
398         void fill(const T& val) { fill(val, size()); }
399
400     private:
401         void expandCapacity(size_t newMinCapacity);
402
403         size_t m_size;
404         Impl m_impl;
405     };
406
407     template<typename T, size_t inlineCapacity>
408     Vector<T, inlineCapacity>::Vector(const Vector& other)
409         : m_size(other.size())
410         , m_impl(other.capacity())
411     {
412         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
413     }
414
415     template<typename T, size_t inlineCapacity>
416     template<size_t otherCapacity> 
417     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
418         : m_size(other.size())
419         , m_impl(other.capacity())
420     {
421         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
422     }
423
424     template<typename T, size_t inlineCapacity>
425     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
426     {
427         if (&other == this)
428             return *this;
429         
430         if (size() > other.size())
431             resize(other.size());
432         else if (other.size() > capacity()) {
433             clear();
434             reserveCapacity(other.size());
435         }
436         
437         std::copy(other.begin(), other.begin() + size(), begin());
438         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
439         m_size = other.size();
440
441         return *this;
442     }
443
444     template<typename T, size_t inlineCapacity>
445     template<size_t otherCapacity> 
446     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
447     {
448         if (&other == this)
449             return *this;
450         
451         if (size() > other.size())
452             resize(other.size());
453         else if (other.size() > capacity()) {
454             clear();
455             reserveCapacity(other.size());
456         }
457         
458         std::copy(other.begin(), other.begin() + size(), begin());
459         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
460         m_size = other.size();
461
462         return *this;
463     }
464
465     template<typename T, size_t inlineCapacity>
466     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
467     {
468         if (size() > newSize)
469             resize(newSize);
470         else if (newSize > capacity()) {
471             clear();
472             reserveCapacity(newSize);
473         }
474         
475         std::fill(begin(), end(), val);
476         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
477         m_size = newSize;
478     }
479
480     template<typename T, size_t inlineCapacity>
481     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
482     {
483         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
484     }
485     
486     template<typename T, size_t inlineCapacity>
487     void Vector<T, inlineCapacity>::resize(size_t size)
488     {
489         if (size <= m_size)
490             TypeOperations::destruct(begin() + size, end());
491         else {
492             if (size > capacity())
493                 expandCapacity(size);
494             TypeOperations::initialize(end(), begin() + size);
495         }
496         
497         m_size = size;
498     }
499
500     template<typename T, size_t inlineCapacity>
501     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
502     {
503         if (newCapacity < capacity())
504             return;
505         T* oldBuffer = begin();
506         T* oldEnd = end();
507         m_impl.allocateBuffer(newCapacity);
508         TypeOperations::move(oldBuffer, oldEnd, begin());
509         m_impl.deallocateBuffer(oldBuffer);
510     }
511
512     // templatizing these is better than just letting the conversion happen implicitly,
513     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
514     // without refcount thrash.
515
516     template<typename T, size_t inlineCapacity> template<typename U>
517     inline void Vector<T, inlineCapacity>::append(const U& val)
518     {
519         if (size() == capacity())
520             expandCapacity(size() + 1);
521         new (end()) T(val);
522         ++m_size;
523     }
524
525     template<typename T, size_t inlineCapacity> template<typename U>
526     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
527     {
528         ASSERT(position <= size());
529         if (size() == capacity())
530             expandCapacity(size() + 1);
531         T* spot = begin() + position;
532         TypeOperations::moveOverlapping(spot, end(), spot + 1);
533         new (spot) T(val);
534         ++m_size;
535     }
536
537     template<typename T, size_t inlineCapacity>
538     inline void Vector<T, inlineCapacity>::remove(size_t position)
539     {
540         ASSERT(position < size());
541         T* spot = begin() + position;
542         spot->~T();
543         TypeOperations::moveOverlapping(spot + 1, end(), spot);
544         --m_size;
545     }
546
547     template<typename T, size_t inlineCapacity>
548     void deleteAllValues(Vector<T, inlineCapacity>& collection)
549     {
550         typedef Vector<T, inlineCapacity> Vec;
551         typename Vec::iterator end = collection.end();
552         for (typename Vec::iterator it = collection.begin(); it != end; ++it)
553             delete *it;
554     }
555
556 } // namespace KXMLCore
557
558 using KXMLCore::Vector;
559
560 #endif // KXMLCORE_VECTOR_H