← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/javascriptcore/JavaScriptCore/wtf/Vector.h

  • Committer: Bazaar Package Importer
  • Author(s): Alessandro Ghersi
  • Date: 2009-11-02 18:30:08 UTC
  • mfrom: (1.2.2 upstream)
  • mto: (15.2.5 experimental)
  • mto: This revision was merged to the branch mainline in revision 88.
  • Revision ID: james.westby@ubuntu.com-20091102183008-b6a4gcs128mvfb3m
Tags: upstream-4.6.0~beta1
Import upstream version 4.6.0~beta1

Show diffs side-by-side

added added

removed removed

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