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