1/*
2 * Copyright (C) 2005-2017 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#pragma once
22
23#include <initializer_list>
24#include <limits>
25#include <string.h>
26#include <type_traits>
27#include <utility>
28#include <wtf/CheckedArithmetic.h>
29#include <wtf/FastMalloc.h>
30#include <wtf/Forward.h>
31#include <wtf/MallocPtr.h>
32#include <wtf/MathExtras.h>
33#include <wtf/Noncopyable.h>
34#include <wtf/NotFound.h>
35#include <wtf/StdLibExtras.h>
36#include <wtf/ValueCheck.h>
37#include <wtf/VectorTraits.h>
38
39#if ASAN_ENABLED
40extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid);
41#endif
42
43namespace JSC {
44class LLIntOffsetsExtractor;
45}
46
47namespace WTF {
48
49template <bool needsDestruction, typename T>
50struct VectorDestructor;
51
52template<typename T>
53struct VectorDestructor<false, T>
54{
55 static void destruct(T*, T*) {}
56};
57
58template<typename T>
59struct VectorDestructor<true, T>
60{
61 static void destruct(T* begin, T* end)
62 {
63 for (T* cur = begin; cur != end; ++cur)
64 cur->~T();
65 }
66};
67
68template <bool needsInitialization, bool canInitializeWithMemset, typename T>
69struct VectorInitializer;
70
71template<bool canInitializeWithMemset, typename T>
72struct VectorInitializer<false, canInitializeWithMemset, T>
73{
74 static void initializeIfNonPOD(T*, T*) { }
75
76 static void initialize(T* begin, T* end)
77 {
78 VectorInitializer<true, canInitializeWithMemset, T>::initialize(begin, end);
79 }
80};
81
82template<typename T>
83struct VectorInitializer<true, false, T>
84{
85 static void initializeIfNonPOD(T* begin, T* end)
86 {
87 for (T* cur = begin; cur != end; ++cur)
88 new (NotNull, cur) T();
89 }
90
91 static void initialize(T* begin, T* end)
92 {
93 initializeIfNonPOD(begin, end);
94 }
95};
96
97template<typename T>
98struct VectorInitializer<true, true, T>
99{
100 static void initializeIfNonPOD(T* begin, T* end)
101 {
102 memset(static_cast<void*>(begin), 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
103 }
104
105 static void initialize(T* begin, T* end)
106 {
107 initializeIfNonPOD(begin, end);
108 }
109};
110
111template <bool canMoveWithMemcpy, typename T>
112struct VectorMover;
113
114template<typename T>
115struct VectorMover<false, T>
116{
117 static void move(T* src, T* srcEnd, T* dst)
118 {
119 while (src != srcEnd) {
120 new (NotNull, dst) T(WTFMove(*src));
121 src->~T();
122 ++dst;
123 ++src;
124 }
125 }
126 static void moveOverlapping(T* src, T* srcEnd, T* dst)
127 {
128 if (src > dst)
129 move(src, srcEnd, dst);
130 else {
131 T* dstEnd = dst + (srcEnd - src);
132 while (src != srcEnd) {
133 --srcEnd;
134 --dstEnd;
135 new (NotNull, dstEnd) T(WTFMove(*srcEnd));
136 srcEnd->~T();
137 }
138 }
139 }
140};
141
142template<typename T>
143struct VectorMover<true, T>
144{
145 static void move(const T* src, const T* srcEnd, T* dst)
146 {
147 memcpy(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
148 }
149 static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
150 {
151 memmove(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
152 }
153};
154
155template <bool canCopyWithMemcpy, typename T>
156struct VectorCopier;
157
158template<typename T>
159struct VectorCopier<false, T>
160{
161 template<typename U>
162 static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
163 {
164 while (src != srcEnd) {
165 new (NotNull, dst) U(*src);
166 ++dst;
167 ++src;
168 }
169 }
170};
171
172template<typename T>
173struct VectorCopier<true, T>
174{
175 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
176 {
177 memcpy(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
178 }
179 template<typename U>
180 static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
181 {
182 VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst);
183 }
184};
185
186template <bool canFillWithMemset, typename T>
187struct VectorFiller;
188
189template<typename T>
190struct VectorFiller<false, T>
191{
192 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
193 {
194 while (dst != dstEnd) {
195 new (NotNull, dst) T(val);
196 ++dst;
197 }
198 }
199};
200
201template<typename T>
202struct VectorFiller<true, T>
203{
204 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
205 {
206 static_assert(sizeof(T) == 1, "Size of type T should be equal to one!");
207#if COMPILER(GCC_COMPATIBLE) && defined(_FORTIFY_SOURCE)
208 if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst)))
209#endif
210 memset(dst, val, dstEnd - dst);
211 }
212};
213
214template<bool canCompareWithMemcmp, typename T>
215struct VectorComparer;
216
217template<typename T>
218struct VectorComparer<false, T>
219{
220 static bool compare(const T* a, const T* b, size_t size)
221 {
222 for (size_t i = 0; i < size; ++i)
223 if (!(a[i] == b[i]))
224 return false;
225 return true;
226 }
227};
228
229template<typename T>
230struct VectorComparer<true, T>
231{
232 static bool compare(const T* a, const T* b, size_t size)
233 {
234 return memcmp(a, b, sizeof(T) * size) == 0;
235 }
236};
237
238template<typename T>
239struct VectorTypeOperations
240{
241 static void destruct(T* begin, T* end)
242 {
243 VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end);
244 }
245
246 static void initializeIfNonPOD(T* begin, T* end)
247 {
248 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initializeIfNonPOD(begin, end);
249 }
250
251 static void initialize(T* begin, T* end)
252 {
253 VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
254 }
255
256 static void move(T* src, T* srcEnd, T* dst)
257 {
258 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
259 }
260
261 static void moveOverlapping(T* src, T* srcEnd, T* dst)
262 {
263 VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
264 }
265
266 static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
267 {
268 VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
269 }
270
271 static void uninitializedFill(T* dst, T* dstEnd, const T& val)
272 {
273 VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
274 }
275
276 static bool compare(const T* a, const T* b, size_t size)
277 {
278 return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
279 }
280};
281
282template<typename T>
283class VectorBufferBase {
284 WTF_MAKE_NONCOPYABLE(VectorBufferBase);
285public:
286 void allocateBuffer(size_t newCapacity)
287 {
288 ASSERT(newCapacity);
289 if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
290 CRASH();
291 size_t sizeToAllocate = newCapacity * sizeof(T);
292 m_capacity = sizeToAllocate / sizeof(T);
293 m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate));
294 }
295
296 bool tryAllocateBuffer(size_t newCapacity)
297 {
298 ASSERT(newCapacity);
299 if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
300 return false;
301
302 size_t sizeToAllocate = newCapacity * sizeof(T);
303 T* newBuffer;
304 if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) {
305 m_capacity = sizeToAllocate / sizeof(T);
306 m_buffer = newBuffer;
307 return true;
308 }
309 return false;
310 }
311
312 bool shouldReallocateBuffer(size_t newCapacity) const
313 {
314 return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
315 }
316
317 void reallocateBuffer(size_t newCapacity)
318 {
319 ASSERT(shouldReallocateBuffer(newCapacity));
320 if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
321 CRASH();
322 size_t sizeToAllocate = newCapacity * sizeof(T);
323 m_capacity = sizeToAllocate / sizeof(T);
324 m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate));
325 }
326
327 void deallocateBuffer(T* bufferToDeallocate)
328 {
329 if (!bufferToDeallocate)
330 return;
331
332 if (m_buffer == bufferToDeallocate) {
333 m_buffer = 0;
334 m_capacity = 0;
335 }
336
337 fastFree(bufferToDeallocate);
338 }
339
340 T* buffer() { return m_buffer; }
341 const T* buffer() const { return m_buffer; }
342 static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
343 size_t capacity() const { return m_capacity; }
344
345 MallocPtr<T> releaseBuffer()
346 {
347 T* buffer = m_buffer;
348 m_buffer = 0;
349 m_capacity = 0;
350 return adoptMallocPtr(buffer);
351 }
352
353protected:
354 VectorBufferBase()
355 : m_buffer(0)
356 , m_capacity(0)
357 , m_size(0)
358 {
359 }
360
361 VectorBufferBase(T* buffer, size_t capacity, size_t size)
362 : m_buffer(buffer)
363 , m_capacity(capacity)
364 , m_size(size)
365 {
366 }
367
368 ~VectorBufferBase()
369 {
370 // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
371 }
372
373 T* m_buffer;
374 unsigned m_capacity;
375 unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
376};
377
378template<typename T, size_t inlineCapacity>
379class VectorBuffer;
380
381template<typename T>
382class VectorBuffer<T, 0> : private VectorBufferBase<T> {
383private:
384 typedef VectorBufferBase<T> Base;
385public:
386 VectorBuffer()
387 {
388 }
389
390 VectorBuffer(size_t capacity, size_t size = 0)
391 {
392 m_size = size;
393 // Calling malloc(0) might take a lock and may actually do an
394 // allocation on some systems.
395 if (capacity)
396 allocateBuffer(capacity);
397 }
398
399 ~VectorBuffer()
400 {
401 deallocateBuffer(buffer());
402 }
403
404 void swap(VectorBuffer<T, 0>& other, size_t, size_t)
405 {
406 std::swap(m_buffer, other.m_buffer);
407 std::swap(m_capacity, other.m_capacity);
408 }
409
410 void restoreInlineBufferIfNeeded() { }
411
412#if ASAN_ENABLED
413 void* endOfBuffer()
414 {
415 return buffer() + capacity();
416 }
417#endif
418
419 using Base::allocateBuffer;
420 using Base::tryAllocateBuffer;
421 using Base::shouldReallocateBuffer;
422 using Base::reallocateBuffer;
423 using Base::deallocateBuffer;
424
425 using Base::buffer;
426 using Base::capacity;
427 using Base::bufferMemoryOffset;
428
429 using Base::releaseBuffer;
430
431protected:
432 using Base::m_size;
433
434private:
435 friend class JSC::LLIntOffsetsExtractor;
436 using Base::m_buffer;
437 using Base::m_capacity;
438};
439
440template<typename T, size_t inlineCapacity>
441class VectorBuffer : private VectorBufferBase<T> {
442 WTF_MAKE_NONCOPYABLE(VectorBuffer);
443private:
444 typedef VectorBufferBase<T> Base;
445public:
446 VectorBuffer()
447 : Base(inlineBuffer(), inlineCapacity, 0)
448 {
449 }
450
451 VectorBuffer(size_t capacity, size_t size = 0)
452 : Base(inlineBuffer(), inlineCapacity, size)
453 {
454 if (capacity > inlineCapacity)
455 Base::allocateBuffer(capacity);
456 }
457
458 ~VectorBuffer()
459 {
460 deallocateBuffer(buffer());
461 }
462
463 void allocateBuffer(size_t newCapacity)
464 {
465 // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
466 if (newCapacity > inlineCapacity)
467 Base::allocateBuffer(newCapacity);
468 else {
469 m_buffer = inlineBuffer();
470 m_capacity = inlineCapacity;
471 }
472 }
473
474 bool tryAllocateBuffer(size_t newCapacity)
475 {
476 if (newCapacity > inlineCapacity)
477 return Base::tryAllocateBuffer(newCapacity);
478 m_buffer = inlineBuffer();
479 m_capacity = inlineCapacity;
480 return true;
481 }
482
483 void deallocateBuffer(T* bufferToDeallocate)
484 {
485 if (bufferToDeallocate == inlineBuffer())
486 return;
487 Base::deallocateBuffer(bufferToDeallocate);
488 }
489
490 bool shouldReallocateBuffer(size_t newCapacity) const
491 {
492 // We cannot reallocate the inline buffer.
493 return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
494 }
495
496 void reallocateBuffer(size_t newCapacity)
497 {
498 ASSERT(shouldReallocateBuffer(newCapacity));
499 Base::reallocateBuffer(newCapacity);
500 }
501
502 void swap(VectorBuffer& other, size_t mySize, size_t otherSize)
503 {
504 if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
505 swapInlineBuffer(other, mySize, otherSize);
506 std::swap(m_capacity, other.m_capacity);
507 } else if (buffer() == inlineBuffer()) {
508 m_buffer = other.m_buffer;
509 other.m_buffer = other.inlineBuffer();
510 swapInlineBuffer(other, mySize, 0);
511 std::swap(m_capacity, other.m_capacity);
512 } else if (other.buffer() == other.inlineBuffer()) {
513 other.m_buffer = m_buffer;
514 m_buffer = inlineBuffer();
515 swapInlineBuffer(other, 0, otherSize);
516 std::swap(m_capacity, other.m_capacity);
517 } else {
518 std::swap(m_buffer, other.m_buffer);
519 std::swap(m_capacity, other.m_capacity);
520 }
521 }
522
523 void restoreInlineBufferIfNeeded()
524 {
525 if (m_buffer)
526 return;
527 m_buffer = inlineBuffer();
528 m_capacity = inlineCapacity;
529 }
530
531#if ASAN_ENABLED
532 void* endOfBuffer()
533 {
534 ASSERT(buffer());
535
536 IGNORE_GCC_WARNINGS_BEGIN("invalid-offsetof")
537 static_assert((offsetof(VectorBuffer, m_inlineBuffer) + sizeof(m_inlineBuffer)) % 8 == 0, "Inline buffer end needs to be on 8 byte boundary for ASan annotations to work.");
538 IGNORE_GCC_WARNINGS_END
539
540 if (buffer() == inlineBuffer())
541 return reinterpret_cast<char*>(m_inlineBuffer) + sizeof(m_inlineBuffer);
542
543 return buffer() + capacity();
544 }
545#endif
546
547 using Base::buffer;
548 using Base::capacity;
549 using Base::bufferMemoryOffset;
550
551 MallocPtr<T> releaseBuffer()
552 {
553 if (buffer() == inlineBuffer())
554 return nullptr;
555 return Base::releaseBuffer();
556 }
557
558protected:
559 using Base::m_size;
560
561private:
562 using Base::m_buffer;
563 using Base::m_capacity;
564
565 void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize)
566 {
567 // FIXME: We could make swap part of VectorTypeOperations
568 // https://bugs.webkit.org/show_bug.cgi?id=128863
569 swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
570 }
571
572 static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
573 {
574 if (left == right)
575 return;
576
577 ASSERT(leftSize <= inlineCapacity);
578 ASSERT(rightSize <= inlineCapacity);
579
580 size_t swapBound = std::min(leftSize, rightSize);
581 for (unsigned i = 0; i < swapBound; ++i)
582 std::swap(left[i], right[i]);
583 VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
584 VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
585 }
586
587 T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
588 const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
589
590#if ASAN_ENABLED
591 // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work.
592 // FIXME: Add a redzone before the buffer to catch off by one accesses. We don't need a guard after, because the buffer is the last member variable.
593 static const size_t asanInlineBufferAlignment = std::alignment_of<T>::value >= 8 ? std::alignment_of<T>::value : 8;
594 static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T);
595 typename std::aligned_storage<sizeof(T), asanInlineBufferAlignment>::type m_inlineBuffer[asanAdjustedInlineCapacity];
596#else
597 typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
598#endif
599};
600
601struct UnsafeVectorOverflow {
602 static NO_RETURN_DUE_TO_ASSERT void overflowed()
603 {
604 ASSERT_NOT_REACHED();
605 }
606};
607
608// Template default values are in Forward.h.
609template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
610class Vector : private VectorBuffer<T, inlineCapacity> {
611 WTF_MAKE_FAST_ALLOCATED;
612private:
613 typedef VectorBuffer<T, inlineCapacity> Base;
614 typedef VectorTypeOperations<T> TypeOperations;
615 friend class JSC::LLIntOffsetsExtractor;
616
617public:
618 typedef T ValueType;
619
620 typedef T* iterator;
621 typedef const T* const_iterator;
622 typedef std::reverse_iterator<iterator> reverse_iterator;
623 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
624
625 Vector()
626 {
627 }
628
629 // Unlike in std::vector, this constructor does not initialize POD types.
630 explicit Vector(size_t size)
631 : Base(size, size)
632 {
633 asanSetInitialBufferSizeTo(size);
634
635 if (begin())
636 TypeOperations::initializeIfNonPOD(begin(), end());
637 }
638
639 Vector(size_t size, const T& val)
640 : Base(size, size)
641 {
642 asanSetInitialBufferSizeTo(size);
643
644 if (begin())
645 TypeOperations::uninitializedFill(begin(), end(), val);
646 }
647
648 Vector(std::initializer_list<T> initializerList)
649 {
650 reserveInitialCapacity(initializerList.size());
651
652 asanSetInitialBufferSizeTo(initializerList.size());
653
654 for (const auto& element : initializerList)
655 uncheckedAppend(element);
656 }
657
658 template<typename... Items>
659 static Vector from(Items&&... items)
660 {
661 Vector result;
662 auto size = sizeof...(items);
663
664 result.reserveInitialCapacity(size);
665 result.asanSetInitialBufferSizeTo(size);
666 result.m_size = size;
667
668 result.uncheckedInitialize<0>(std::forward<Items>(items)...);
669 return result;
670 }
671
672 ~Vector()
673 {
674 if (m_size)
675 TypeOperations::destruct(begin(), end());
676
677 asanSetBufferSizeToFullCapacity(0);
678 }
679
680 Vector(const Vector&);
681 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
682 explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
683
684 Vector& operator=(const Vector&);
685 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
686 Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
687
688 Vector(Vector&&);
689 Vector& operator=(Vector&&);
690
691 size_t size() const { return m_size; }
692 static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
693 size_t capacity() const { return Base::capacity(); }
694 bool isEmpty() const { return !size(); }
695
696 T& at(size_t i)
697 {
698 if (UNLIKELY(i >= size()))
699 OverflowHandler::overflowed();
700 return Base::buffer()[i];
701 }
702 const T& at(size_t i) const
703 {
704 if (UNLIKELY(i >= size()))
705 OverflowHandler::overflowed();
706 return Base::buffer()[i];
707 }
708 T& at(Checked<size_t> i)
709 {
710 RELEASE_ASSERT(i < size());
711 return Base::buffer()[i];
712 }
713 const T& at(Checked<size_t> i) const
714 {
715 RELEASE_ASSERT(i < size());
716 return Base::buffer()[i];
717 }
718
719 T& operator[](size_t i) { return at(i); }
720 const T& operator[](size_t i) const { return at(i); }
721 T& operator[](Checked<size_t> i) { return at(i); }
722 const T& operator[](Checked<size_t> i) const { return at(i); }
723
724 T* data() { return Base::buffer(); }
725 const T* data() const { return Base::buffer(); }
726 static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
727
728 iterator begin() { return data(); }
729 iterator end() { return begin() + m_size; }
730 const_iterator begin() const { return data(); }
731 const_iterator end() const { return begin() + m_size; }
732
733 reverse_iterator rbegin() { return reverse_iterator(end()); }
734 reverse_iterator rend() { return reverse_iterator(begin()); }
735 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
736 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
737
738 T& first() { return at(0); }
739 const T& first() const { return at(0); }
740 T& last() { return at(size() - 1); }
741 const T& last() const { return at(size() - 1); }
742
743 T takeLast()
744 {
745 T result = WTFMove(last());
746 removeLast();
747 return result;
748 }
749
750 template<typename U> bool contains(const U&) const;
751 template<typename U> size_t find(const U&) const;
752 template<typename MatchFunction> size_t findMatching(const MatchFunction&) const;
753 template<typename U> size_t reverseFind(const U&) const;
754
755 template<typename U> bool appendIfNotContains(const U&);
756
757 void shrink(size_t size);
758 void grow(size_t size);
759 void resize(size_t size);
760 void resizeToFit(size_t size);
761 void reserveCapacity(size_t newCapacity);
762 bool tryReserveCapacity(size_t newCapacity);
763 void reserveInitialCapacity(size_t initialCapacity);
764 void shrinkCapacity(size_t newCapacity);
765 void shrinkToFit() { shrinkCapacity(size()); }
766
767 void clear() { shrinkCapacity(0); }
768
769 template<typename U = T> Vector<U> isolatedCopy() const;
770
771 ALWAYS_INLINE void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
772 template<typename U> void append(U&&);
773 template<typename... Args> void constructAndAppend(Args&&...);
774 template<typename... Args> bool tryConstructAndAppend(Args&&...);
775
776 void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
777 template<typename U> void uncheckedAppend(U&&);
778 template<typename... Args> void uncheckedConstructAndAppend(Args&&...);
779
780 template<typename U> void append(const U*, size_t);
781 template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
782 template<typename U> bool tryAppend(const U*, size_t);
783
784 template<typename U> void insert(size_t position, const U*, size_t);
785 template<typename U> void insert(size_t position, U&&);
786 template<typename U, size_t c, typename OH> void insertVector(size_t position, const Vector<U, c, OH>&);
787
788 void remove(size_t position);
789 void remove(size_t position, size_t length);
790 template<typename U> bool removeFirst(const U&);
791 template<typename MatchFunction> bool removeFirstMatching(const MatchFunction&, size_t startIndex = 0);
792 template<typename U> unsigned removeAll(const U&);
793 template<typename MatchFunction> unsigned removeAllMatching(const MatchFunction&, size_t startIndex = 0);
794
795 void removeLast()
796 {
797 if (UNLIKELY(isEmpty()))
798 OverflowHandler::overflowed();
799 shrink(size() - 1);
800 }
801
802 void fill(const T&, size_t);
803 void fill(const T& val) { fill(val, size()); }
804
805 template<typename Iterator> void appendRange(Iterator start, Iterator end);
806
807 MallocPtr<T> releaseBuffer();
808
809 void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
810 {
811#if ASAN_ENABLED
812 if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
813 return;
814#endif
815
816 // Make it possible to copy inline buffers.
817 asanSetBufferSizeToFullCapacity();
818 other.asanSetBufferSizeToFullCapacity();
819
820 Base::swap(other, m_size, other.m_size);
821 std::swap(m_size, other.m_size);
822
823 asanSetInitialBufferSizeTo(m_size);
824 other.asanSetInitialBufferSizeTo(other.m_size);
825 }
826
827 void reverse();
828
829 void checkConsistency();
830
831 template<typename MapFunction, typename R = typename std::result_of<MapFunction(const T&)>::type> Vector<R> map(MapFunction) const;
832
833private:
834 void expandCapacity(size_t newMinCapacity);
835 T* expandCapacity(size_t newMinCapacity, T*);
836 bool tryExpandCapacity(size_t newMinCapacity);
837 const T* tryExpandCapacity(size_t newMinCapacity, const T*);
838 template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
839 template<typename U> void appendSlowCase(U&&);
840 template<typename... Args> void constructAndAppendSlowCase(Args&&...);
841 template<typename... Args> bool tryConstructAndAppendSlowCase(Args&&...);
842
843 template<size_t position, typename U, typename... Items>
844 void uncheckedInitialize(U&& item, Items&&... items)
845 {
846 uncheckedInitialize<position>(std::forward<U>(item));
847 uncheckedInitialize<position + 1>(std::forward<Items>(items)...);
848 }
849 template<size_t position, typename U>
850 void uncheckedInitialize(U&& value)
851 {
852 ASSERT(position < size());
853 ASSERT(position < capacity());
854 new (NotNull, begin() + position) T(std::forward<U>(value));
855 }
856
857 void asanSetInitialBufferSizeTo(size_t);
858 void asanSetBufferSizeToFullCapacity(size_t);
859 void asanSetBufferSizeToFullCapacity() { asanSetBufferSizeToFullCapacity(size()); }
860
861 void asanBufferSizeWillChangeTo(size_t);
862
863 using Base::m_size;
864 using Base::buffer;
865 using Base::capacity;
866 using Base::swap;
867 using Base::allocateBuffer;
868 using Base::deallocateBuffer;
869 using Base::tryAllocateBuffer;
870 using Base::shouldReallocateBuffer;
871 using Base::reallocateBuffer;
872 using Base::restoreInlineBufferIfNeeded;
873 using Base::releaseBuffer;
874#if ASAN_ENABLED
875 using Base::endOfBuffer;
876#endif
877};
878
879template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
880Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
881 : Base(other.capacity(), other.size())
882{
883 asanSetInitialBufferSizeTo(other.size());
884
885 if (begin())
886 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
887}
888
889template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
890template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
891Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
892 : Base(other.capacity(), other.size())
893{
894 asanSetInitialBufferSizeTo(other.size());
895
896 if (begin())
897 TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
898}
899
900template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
901Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
902{
903 if (&other == this)
904 return *this;
905
906 if (size() > other.size())
907 shrink(other.size());
908 else if (other.size() > capacity()) {
909 clear();
910 reserveCapacity(other.size());
911 ASSERT(begin());
912 }
913
914 asanBufferSizeWillChangeTo(other.size());
915
916 std::copy(other.begin(), other.begin() + size(), begin());
917 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
918 m_size = other.size();
919
920 return *this;
921}
922
923inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
924
925template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
926template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
927Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
928{
929 // If the inline capacities match, we should call the more specific
930 // template. If the inline capacities don't match, the two objects
931 // shouldn't be allocated the same address.
932 ASSERT(!typelessPointersAreEqual(&other, this));
933
934 if (size() > other.size())
935 shrink(other.size());
936 else if (other.size() > capacity()) {
937 clear();
938 reserveCapacity(other.size());
939 ASSERT(begin());
940 }
941
942 asanBufferSizeWillChangeTo(other.size());
943
944 std::copy(other.begin(), other.begin() + size(), begin());
945 TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
946 m_size = other.size();
947
948 return *this;
949}
950
951template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
952inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
953{
954 swap(other);
955}
956
957template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
958inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
959{
960 swap(other);
961 return *this;
962}
963
964template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
965template<typename U>
966bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
967{
968 return find(value) != notFound;
969}
970
971template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
972template<typename MatchFunction>
973size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::findMatching(const MatchFunction& matches) const
974{
975 for (size_t i = 0; i < size(); ++i) {
976 if (matches(at(i)))
977 return i;
978 }
979 return notFound;
980}
981
982template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
983template<typename U>
984size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
985{
986 return findMatching([&](auto& item) {
987 return item == value;
988 });
989}
990
991template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
992template<typename U>
993size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
994{
995 for (size_t i = 1; i <= size(); ++i) {
996 const size_t index = size() - i;
997 if (at(index) == value)
998 return index;
999 }
1000 return notFound;
1001}
1002
1003template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1004template<typename U>
1005bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendIfNotContains(const U& value)
1006{
1007 if (contains(value))
1008 return false;
1009 append(value);
1010 return true;
1011}
1012
1013template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1014void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
1015{
1016 if (size() > newSize)
1017 shrink(newSize);
1018 else if (newSize > capacity()) {
1019 clear();
1020 reserveCapacity(newSize);
1021 ASSERT(begin());
1022 }
1023
1024 asanBufferSizeWillChangeTo(newSize);
1025
1026 std::fill(begin(), end(), val);
1027 TypeOperations::uninitializedFill(end(), begin() + newSize, val);
1028 m_size = newSize;
1029}
1030
1031template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1032template<typename Iterator>
1033void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
1034{
1035 for (Iterator it = start; it != end; ++it)
1036 append(*it);
1037}
1038
1039template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1040void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
1041{
1042 reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1043}
1044
1045template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1046NEVER_INLINE T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
1047{
1048 if (ptr < begin() || ptr >= end()) {
1049 expandCapacity(newMinCapacity);
1050 return ptr;
1051 }
1052 size_t index = ptr - begin();
1053 expandCapacity(newMinCapacity);
1054 return begin() + index;
1055}
1056
1057template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1058bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
1059{
1060 return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1061}
1062
1063template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1064const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
1065{
1066 if (ptr < begin() || ptr >= end()) {
1067 if (!tryExpandCapacity(newMinCapacity))
1068 return 0;
1069 return ptr;
1070 }
1071 size_t index = ptr - begin();
1072 if (!tryExpandCapacity(newMinCapacity))
1073 return 0;
1074 return begin() + index;
1075}
1076
1077template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1078template<typename U>
1079inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
1080{
1081 expandCapacity(newMinCapacity);
1082 return ptr;
1083}
1084
1085template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1086inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
1087{
1088 if (size <= m_size) {
1089 TypeOperations::destruct(begin() + size, end());
1090 asanBufferSizeWillChangeTo(size);
1091 } else {
1092 if (size > capacity())
1093 expandCapacity(size);
1094 asanBufferSizeWillChangeTo(size);
1095 if (begin())
1096 TypeOperations::initializeIfNonPOD(end(), begin() + size);
1097 }
1098
1099 m_size = size;
1100}
1101
1102template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1103void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
1104{
1105 reserveCapacity(size);
1106 resize(size);
1107}
1108
1109template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1110void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
1111{
1112 ASSERT(size <= m_size);
1113 TypeOperations::destruct(begin() + size, end());
1114 asanBufferSizeWillChangeTo(size);
1115 m_size = size;
1116}
1117
1118template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1119void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
1120{
1121 ASSERT(size >= m_size);
1122 if (size > capacity())
1123 expandCapacity(size);
1124 asanBufferSizeWillChangeTo(size);
1125 if (begin())
1126 TypeOperations::initializeIfNonPOD(end(), begin() + size);
1127 m_size = size;
1128}
1129
1130template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1131inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
1132{
1133#if ASAN_ENABLED
1134 if (!buffer())
1135 return;
1136
1137 // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1138 // when accessing elements in [end(), endOfBuffer()) range.
1139 // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1140 __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1141#else
1142 UNUSED_PARAM(size);
1143#endif
1144}
1145
1146template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1147inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity(size_t size)
1148{
1149#if ASAN_ENABLED
1150 if (!buffer())
1151 return;
1152
1153 // ASan requires that the annotation is returned to its initial state before deallocation.
1154 __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size, endOfBuffer());
1155#else
1156 UNUSED_PARAM(size);
1157#endif
1158}
1159
1160template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1161inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
1162{
1163#if ASAN_ENABLED
1164 if (!buffer())
1165 return;
1166
1167 // Change allowed range.
1168 __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1169#else
1170 UNUSED_PARAM(newSize);
1171#endif
1172}
1173
1174template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1175void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
1176{
1177 if (newCapacity <= capacity())
1178 return;
1179 T* oldBuffer = begin();
1180 T* oldEnd = end();
1181
1182 asanSetBufferSizeToFullCapacity();
1183
1184 Base::allocateBuffer(newCapacity);
1185 ASSERT(begin());
1186
1187 asanSetInitialBufferSizeTo(size());
1188
1189 TypeOperations::move(oldBuffer, oldEnd, begin());
1190 Base::deallocateBuffer(oldBuffer);
1191}
1192
1193template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1194bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
1195{
1196 if (newCapacity <= capacity())
1197 return true;
1198 T* oldBuffer = begin();
1199 T* oldEnd = end();
1200
1201 asanSetBufferSizeToFullCapacity();
1202
1203 if (!Base::tryAllocateBuffer(newCapacity)) {
1204 asanSetInitialBufferSizeTo(size());
1205 return false;
1206 }
1207 ASSERT(begin());
1208
1209 asanSetInitialBufferSizeTo(size());
1210
1211 TypeOperations::move(oldBuffer, oldEnd, begin());
1212 Base::deallocateBuffer(oldBuffer);
1213 return true;
1214}
1215
1216template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1217inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
1218{
1219 ASSERT(!m_size);
1220 ASSERT(capacity() == inlineCapacity);
1221 if (initialCapacity > inlineCapacity)
1222 Base::allocateBuffer(initialCapacity);
1223}
1224
1225template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1226void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
1227{
1228 if (newCapacity >= capacity())
1229 return;
1230
1231 if (newCapacity < size())
1232 shrink(newCapacity);
1233
1234 asanSetBufferSizeToFullCapacity();
1235
1236 T* oldBuffer = begin();
1237 if (newCapacity > 0) {
1238 if (Base::shouldReallocateBuffer(newCapacity)) {
1239 Base::reallocateBuffer(newCapacity);
1240 asanSetInitialBufferSizeTo(size());
1241 return;
1242 }
1243
1244 T* oldEnd = end();
1245 Base::allocateBuffer(newCapacity);
1246 if (begin() != oldBuffer)
1247 TypeOperations::move(oldBuffer, oldEnd, begin());
1248 }
1249
1250 Base::deallocateBuffer(oldBuffer);
1251 Base::restoreInlineBufferIfNeeded();
1252
1253 asanSetInitialBufferSizeTo(size());
1254}
1255
1256template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1257template<typename U>
1258ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
1259{
1260 size_t newSize = m_size + dataSize;
1261 if (newSize > capacity()) {
1262 data = expandCapacity(newSize, data);
1263 ASSERT(begin());
1264 }
1265 if (newSize < m_size)
1266 CRASH();
1267 asanBufferSizeWillChangeTo(newSize);
1268 T* dest = end();
1269 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1270 m_size = newSize;
1271}
1272
1273template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1274template<typename U>
1275ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
1276{
1277 size_t newSize = m_size + dataSize;
1278 if (newSize > capacity()) {
1279 data = tryExpandCapacity(newSize, data);
1280 if (!data)
1281 return false;
1282 ASSERT(begin());
1283 }
1284 if (newSize < m_size)
1285 return false;
1286 asanBufferSizeWillChangeTo(newSize);
1287 T* dest = end();
1288 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1289 m_size = newSize;
1290 return true;
1291}
1292
1293template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1294template<typename U>
1295ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
1296{
1297 if (size() != capacity()) {
1298 asanBufferSizeWillChangeTo(m_size + 1);
1299 new (NotNull, end()) T(std::forward<U>(value));
1300 ++m_size;
1301 return;
1302 }
1303
1304 appendSlowCase(std::forward<U>(value));
1305}
1306
1307template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1308template<typename... Args>
1309ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend(Args&&... args)
1310{
1311 if (size() != capacity()) {
1312 asanBufferSizeWillChangeTo(m_size + 1);
1313 new (NotNull, end()) T(std::forward<Args>(args)...);
1314 ++m_size;
1315 return;
1316 }
1317
1318 constructAndAppendSlowCase(std::forward<Args>(args)...);
1319}
1320
1321template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1322template<typename... Args>
1323ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppend(Args&&... args)
1324{
1325 if (size() != capacity()) {
1326 asanBufferSizeWillChangeTo(m_size + 1);
1327 new (NotNull, end()) T(std::forward<Args>(args)...);
1328 ++m_size;
1329 return true;
1330 }
1331
1332 return tryConstructAndAppendSlowCase(std::forward<Args>(args)...);
1333}
1334
1335template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1336template<typename U>
1337void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
1338{
1339 ASSERT(size() == capacity());
1340
1341 auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1342 ptr = expandCapacity(size() + 1, ptr);
1343 ASSERT(begin());
1344
1345 asanBufferSizeWillChangeTo(m_size + 1);
1346 new (NotNull, end()) T(std::forward<U>(*ptr));
1347 ++m_size;
1348}
1349
1350template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1351template<typename... Args>
1352void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppendSlowCase(Args&&... args)
1353{
1354 ASSERT(size() == capacity());
1355
1356 expandCapacity(size() + 1);
1357 ASSERT(begin());
1358
1359 asanBufferSizeWillChangeTo(m_size + 1);
1360 new (NotNull, end()) T(std::forward<Args>(args)...);
1361 ++m_size;
1362}
1363
1364template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1365template<typename... Args>
1366bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppendSlowCase(Args&&... args)
1367{
1368 ASSERT(size() == capacity());
1369
1370 if (UNLIKELY(!tryExpandCapacity(size() + 1)))
1371 return false;
1372 ASSERT(begin());
1373
1374 asanBufferSizeWillChangeTo(m_size + 1);
1375 new (NotNull, end()) T(std::forward<Args>(args)...);
1376 ++m_size;
1377 return true;
1378}
1379
1380// This version of append saves a branch in the case where you know that the
1381// vector's capacity is large enough for the append to succeed.
1382
1383template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1384template<typename U>
1385ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
1386{
1387 ASSERT(size() < capacity());
1388
1389 asanBufferSizeWillChangeTo(m_size + 1);
1390
1391 new (NotNull, end()) T(std::forward<U>(value));
1392 ++m_size;
1393}
1394
1395template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1396template<typename... Args>
1397ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedConstructAndAppend(Args&&... args)
1398{
1399 ASSERT(size() < capacity());
1400
1401 asanBufferSizeWillChangeTo(m_size + 1);
1402
1403 new (NotNull, end()) T(std::forward<Args>(args)...);
1404 ++m_size;
1405}
1406
1407template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1408template<typename U, size_t otherCapacity>
1409inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1410{
1411 append(val.begin(), val.size());
1412}
1413
1414template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1415template<typename U>
1416void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
1417{
1418 ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1419 size_t newSize = m_size + dataSize;
1420 if (newSize > capacity()) {
1421 data = expandCapacity(newSize, data);
1422 ASSERT(begin());
1423 }
1424 if (newSize < m_size)
1425 CRASH();
1426 asanBufferSizeWillChangeTo(newSize);
1427 T* spot = begin() + position;
1428 TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1429 VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1430 m_size = newSize;
1431}
1432
1433template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1434template<typename U>
1435inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
1436{
1437 ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1438
1439 auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1440 if (size() == capacity()) {
1441 ptr = expandCapacity(size() + 1, ptr);
1442 ASSERT(begin());
1443 }
1444
1445 asanBufferSizeWillChangeTo(m_size + 1);
1446
1447 T* spot = begin() + position;
1448 TypeOperations::moveOverlapping(spot, end(), spot + 1);
1449 new (NotNull, spot) T(std::forward<U>(*ptr));
1450 ++m_size;
1451}
1452
1453template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1454template<typename U, size_t c, typename OH>
1455inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c, OH>& val)
1456{
1457 insert(position, val.begin(), val.size());
1458}
1459
1460template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1461inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
1462{
1463 ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1464 T* spot = begin() + position;
1465 spot->~T();
1466 TypeOperations::moveOverlapping(spot + 1, end(), spot);
1467 asanBufferSizeWillChangeTo(m_size - 1);
1468 --m_size;
1469}
1470
1471template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1472inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
1473{
1474 ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1475 ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1476 T* beginSpot = begin() + position;
1477 T* endSpot = beginSpot + length;
1478 TypeOperations::destruct(beginSpot, endSpot);
1479 TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1480 asanBufferSizeWillChangeTo(m_size - length);
1481 m_size -= length;
1482}
1483
1484template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1485template<typename U>
1486inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
1487{
1488 return removeFirstMatching([&value] (const T& current) {
1489 return current == value;
1490 });
1491}
1492
1493template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1494template<typename MatchFunction>
1495inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches, size_t startIndex)
1496{
1497 for (size_t i = startIndex; i < size(); ++i) {
1498 if (matches(at(i))) {
1499 remove(i);
1500 return true;
1501 }
1502 }
1503 return false;
1504}
1505
1506template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1507template<typename U>
1508inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
1509{
1510 return removeAllMatching([&value] (const T& current) {
1511 return current == value;
1512 });
1513}
1514
1515template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1516template<typename MatchFunction>
1517inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches, size_t startIndex)
1518{
1519 iterator holeBegin = end();
1520 iterator holeEnd = end();
1521 unsigned matchCount = 0;
1522 for (auto it = begin() + startIndex, itEnd = end(); it < itEnd; ++it) {
1523 if (matches(*it)) {
1524 if (holeBegin == end())
1525 holeBegin = it;
1526 else if (holeEnd != it) {
1527 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1528 holeBegin += it - holeEnd;
1529 }
1530 holeEnd = it + 1;
1531 it->~T();
1532 ++matchCount;
1533 }
1534 }
1535 if (holeEnd != end())
1536 TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1537 asanBufferSizeWillChangeTo(m_size - matchCount);
1538 m_size -= matchCount;
1539 return matchCount;
1540}
1541
1542template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1543inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
1544{
1545 for (size_t i = 0; i < m_size / 2; ++i)
1546 std::swap(at(i), at(m_size - 1 - i));
1547}
1548
1549template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1550template<typename MapFunction, typename R>
1551inline Vector<R> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::map(MapFunction mapFunction) const
1552{
1553 Vector<R> result;
1554 result.reserveInitialCapacity(size());
1555 for (size_t i = 0; i < size(); ++i)
1556 result.uncheckedAppend(mapFunction(at(i)));
1557 return result;
1558}
1559
1560template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1561inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
1562{
1563 // FIXME: Find a way to preserve annotations on the returned buffer.
1564 // ASan requires that all annotations are removed before deallocation,
1565 // and MallocPtr doesn't implement that.
1566 asanSetBufferSizeToFullCapacity();
1567
1568 auto buffer = Base::releaseBuffer();
1569 if (inlineCapacity && !buffer && m_size) {
1570 // If the vector had some data, but no buffer to release,
1571 // that means it was using the inline buffer. In that case,
1572 // we create a brand new buffer so the caller always gets one.
1573 size_t bytes = m_size * sizeof(T);
1574 buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1575 memcpy(buffer.get(), data(), bytes);
1576 }
1577 m_size = 0;
1578 // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1579 return buffer;
1580}
1581
1582template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1583inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
1584{
1585#if !ASSERT_DISABLED
1586 for (size_t i = 0; i < size(); ++i)
1587 ValueCheck<T>::checkConsistency(at(i));
1588#endif
1589}
1590
1591template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1592inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1593{
1594 a.swap(b);
1595}
1596
1597template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1598bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1599{
1600 if (a.size() != b.size())
1601 return false;
1602
1603 return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1604}
1605
1606template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1607inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1608{
1609 return !(a == b);
1610}
1611
1612#if !ASSERT_DISABLED
1613template<typename T> struct ValueCheck<Vector<T>> {
1614 typedef Vector<T> TraitType;
1615 static void checkConsistency(const Vector<T>& v)
1616 {
1617 v.checkConsistency();
1618 }
1619};
1620#endif
1621
1622template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1623template<typename U>
1624inline Vector<U> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::isolatedCopy() const
1625{
1626 Vector<U> copy;
1627 copy.reserveInitialCapacity(size());
1628 for (const auto& element : *this)
1629 copy.uncheckedAppend(element.isolatedCopy());
1630 return copy;
1631}
1632
1633template<typename VectorType, typename Func>
1634size_t removeRepeatedElements(VectorType& vector, const Func& func)
1635{
1636 auto end = std::unique(vector.begin(), vector.end(), func);
1637 size_t newSize = end - vector.begin();
1638 vector.shrink(newSize);
1639 return newSize;
1640}
1641
1642template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1643size_t removeRepeatedElements(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
1644{
1645 return removeRepeatedElements(vector, [] (T& a, T& b) { return a == b; });
1646}
1647
1648template<typename SourceType>
1649struct CollectionInspector {
1650 using RealSourceType = typename std::remove_reference<SourceType>::type;
1651 using IteratorType = decltype(std::begin(std::declval<RealSourceType>()));
1652 using SourceItemType = typename std::iterator_traits<IteratorType>::value_type;
1653};
1654
1655template<typename MapFunction, typename SourceType, typename Enable = void>
1656struct Mapper {
1657 using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1658 using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&)>::type;
1659
1660 static Vector<DestinationItemType> map(SourceType source, const MapFunction& mapFunction)
1661 {
1662 Vector<DestinationItemType> result;
1663 // FIXME: Use std::size when available on all compilers.
1664 result.reserveInitialCapacity(source.size());
1665 for (auto& item : source)
1666 result.uncheckedAppend(mapFunction(item));
1667 return result;
1668 }
1669};
1670
1671template<typename MapFunction, typename SourceType>
1672struct Mapper<MapFunction, SourceType, typename std::enable_if<std::is_rvalue_reference<SourceType&&>::value>::type> {
1673 using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1674 using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&&)>::type;
1675
1676 static Vector<DestinationItemType> map(SourceType&& source, const MapFunction& mapFunction)
1677 {
1678 Vector<DestinationItemType> result;
1679 // FIXME: Use std::size when available on all compilers.
1680 result.reserveInitialCapacity(source.size());
1681 for (auto& item : source)
1682 result.uncheckedAppend(mapFunction(WTFMove(item)));
1683 return result;
1684 }
1685};
1686
1687template<typename MapFunction, typename SourceType>
1688Vector<typename Mapper<MapFunction, SourceType>::DestinationItemType> map(SourceType&& source, MapFunction&& mapFunction)
1689{
1690 return Mapper<MapFunction, SourceType>::map(std::forward<SourceType>(source), std::forward<MapFunction>(mapFunction));
1691}
1692
1693template<typename DestinationVector, typename Collection>
1694inline auto copyToVectorSpecialization(const Collection& collection) -> DestinationVector
1695{
1696 DestinationVector result;
1697 // FIXME: Use std::size when available on all compilers.
1698 result.reserveInitialCapacity(collection.size());
1699 for (auto& item : collection)
1700 result.uncheckedAppend(item);
1701 return result;
1702}
1703
1704template<typename DestinationItemType, typename Collection>
1705inline auto copyToVectorOf(const Collection& collection) -> Vector<DestinationItemType>
1706{
1707 return WTF::map(collection, [] (const auto& v) -> DestinationItemType { return v; });
1708}
1709
1710template<typename Collection>
1711struct CopyToVectorResult {
1712 using Type = typename std::remove_cv<typename CollectionInspector<Collection>::SourceItemType>::type;
1713};
1714
1715template<typename Collection>
1716inline auto copyToVector(const Collection& collection) -> Vector<typename CopyToVectorResult<Collection>::Type>
1717{
1718 return copyToVectorOf<typename CopyToVectorResult<Collection>::Type>(collection);
1719}
1720
1721} // namespace WTF
1722
1723using WTF::UnsafeVectorOverflow;
1724using WTF::Vector;
1725using WTF::copyToVector;
1726using WTF::copyToVectorOf;
1727using WTF::copyToVectorSpecialization;
1728using WTF::removeRepeatedElements;
1729