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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/Vector.h