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