From 1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c Mon Sep 17 00:00:00 2001 From: Lorry Tar Creator Date: Tue, 27 Jun 2017 06:07:23 +0000 Subject: webkitgtk-2.16.5 --- Source/WTF/wtf/Vector.h | 575 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 431 insertions(+), 144 deletions(-) (limited to 'Source/WTF/wtf/Vector.h') diff --git a/Source/WTF/wtf/Vector.h b/Source/WTF/wtf/Vector.h index 964fe5577..6fdd19ad4 100644 --- a/Source/WTF/wtf/Vector.h +++ b/Source/WTF/wtf/Vector.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. + * Copyright (C) 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -30,11 +30,14 @@ #include #include #include -#include #include #include #include +#if ASAN_ENABLED +extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid); +#endif + namespace WTF { const size_t notFound = static_cast(-1); @@ -95,7 +98,7 @@ struct VectorMover static void move(T* src, T* srcEnd, T* dst) { while (src != srcEnd) { - new (NotNull, dst) T(std::move(*src)); + new (NotNull, dst) T(WTFMove(*src)); src->~T(); ++dst; ++src; @@ -110,7 +113,7 @@ struct VectorMover while (src != srcEnd) { --srcEnd; --dstEnd; - new (NotNull, dstEnd) T(std::move(*srcEnd)); + new (NotNull, dstEnd) T(WTFMove(*srcEnd)); srcEnd->~T(); } } @@ -136,10 +139,11 @@ struct VectorCopier; template struct VectorCopier { - static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) + template + static void uninitializedCopy(const T* src, const T* srcEnd, U* dst) { while (src != srcEnd) { - new (NotNull, dst) T(*src); + new (NotNull, dst) U(*src); ++dst; ++src; } @@ -149,10 +153,15 @@ struct VectorCopier template struct VectorCopier { - static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) + static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) { memcpy(dst, src, reinterpret_cast(srcEnd) - reinterpret_cast(src)); } + template + static void uninitializedCopy(const T* src, const T* srcEnd, U* dst) + { + VectorCopier::uninitializedCopy(src, srcEnd, dst); + } }; template @@ -176,7 +185,7 @@ struct VectorFiller static void uninitializedFill(T* dst, T* dstEnd, const T& val) { static_assert(sizeof(T) == 1, "Size of type T should be equal to one!"); -#if COMPILER(GCC) && defined(_FORTIFY_SOURCE) +#if COMPILER(GCC_OR_CLANG) && defined(_FORTIFY_SOURCE) if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst))) #endif memset(dst, val, dstEnd - dst); @@ -255,7 +264,7 @@ public: ASSERT(newCapacity); if (newCapacity > std::numeric_limits::max() / sizeof(T)) CRASH(); - size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); + size_t sizeToAllocate = newCapacity * sizeof(T); m_capacity = sizeToAllocate / sizeof(T); m_buffer = static_cast(fastMalloc(sizeToAllocate)); } @@ -266,7 +275,7 @@ public: if (newCapacity > std::numeric_limits::max() / sizeof(T)) return false; - size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); + size_t sizeToAllocate = newCapacity * sizeof(T); T* newBuffer; if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) { m_capacity = sizeToAllocate / sizeof(T); @@ -286,7 +295,7 @@ public: ASSERT(shouldReallocateBuffer(newCapacity)); if (newCapacity > std::numeric_limits::max() / sizeof(T)) CRASH(); - size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T)); + size_t sizeToAllocate = newCapacity * sizeof(T); m_capacity = sizeToAllocate / sizeof(T); m_buffer = static_cast(fastRealloc(m_buffer, sizeToAllocate)); } @@ -306,6 +315,7 @@ public: T* buffer() { return m_buffer; } const T* buffer() const { return m_buffer; } + static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); } size_t capacity() const { return m_capacity; } MallocPtr releaseBuffer() @@ -367,7 +377,7 @@ public: deallocateBuffer(buffer()); } - void swap(VectorBuffer& other) + void swap(VectorBuffer& other, size_t, size_t) { std::swap(m_buffer, other.m_buffer); std::swap(m_capacity, other.m_capacity); @@ -375,6 +385,13 @@ public: void restoreInlineBufferIfNeeded() { } +#if ASAN_ENABLED + void* endOfBuffer() + { + return buffer() + capacity(); + } +#endif + using Base::allocateBuffer; using Base::tryAllocateBuffer; using Base::shouldReallocateBuffer; @@ -383,6 +400,7 @@ public: using Base::buffer; using Base::capacity; + using Base::bufferMemoryOffset; using Base::releaseBuffer; @@ -456,20 +474,20 @@ public: Base::reallocateBuffer(newCapacity); } - void swap(VectorBuffer& other) + void swap(VectorBuffer& other, size_t mySize, size_t otherSize) { if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) { - std::swap(m_inlineBuffer, other.m_inlineBuffer); + swapInlineBuffer(other, mySize, otherSize); std::swap(m_capacity, other.m_capacity); } else if (buffer() == inlineBuffer()) { m_buffer = other.m_buffer; other.m_buffer = other.inlineBuffer(); - std::swap(m_inlineBuffer, other.m_inlineBuffer); + swapInlineBuffer(other, mySize, 0); std::swap(m_capacity, other.m_capacity); } else if (other.buffer() == other.inlineBuffer()) { other.m_buffer = m_buffer; m_buffer = inlineBuffer(); - std::swap(m_inlineBuffer, other.m_inlineBuffer); + swapInlineBuffer(other, 0, otherSize); std::swap(m_capacity, other.m_capacity); } else { std::swap(m_buffer, other.m_buffer); @@ -485,8 +503,22 @@ public: m_capacity = inlineCapacity; } +#if ASAN_ENABLED + void* endOfBuffer() + { + ASSERT(buffer()); + 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."); + + if (buffer() == inlineBuffer()) + return reinterpret_cast(m_inlineBuffer) + sizeof(m_inlineBuffer); + + return buffer() + capacity(); + } +#endif + using Base::buffer; using Base::capacity; + using Base::bufferMemoryOffset; MallocPtr releaseBuffer() { @@ -501,11 +533,41 @@ protected: private: using Base::m_buffer; using Base::m_capacity; + + void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize) + { + // FIXME: We could make swap part of VectorTypeOperations + // https://bugs.webkit.org/show_bug.cgi?id=128863 + swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize); + } + + static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize) + { + if (left == right) + return; + + ASSERT(leftSize <= inlineCapacity); + ASSERT(rightSize <= inlineCapacity); + + size_t swapBound = std::min(leftSize, rightSize); + for (unsigned i = 0; i < swapBound; ++i) + std::swap(left[i], right[i]); + VectorTypeOperations::move(left + swapBound, left + leftSize, right + swapBound); + VectorTypeOperations::move(right + swapBound, right + rightSize, left + swapBound); + } T* inlineBuffer() { return reinterpret_cast_ptr(m_inlineBuffer); } const T* inlineBuffer() const { return reinterpret_cast_ptr(m_inlineBuffer); } +#if ASAN_ENABLED + // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work. + // 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. + static const size_t asanInlineBufferAlignment = std::alignment_of::value >= 8 ? std::alignment_of::value : 8; + static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T); + typename std::aligned_storage::type m_inlineBuffer[asanAdjustedInlineCapacity]; +#else typename std::aligned_storage::value>::type m_inlineBuffer[inlineCapacity]; +#endif }; struct UnsafeVectorOverflow { @@ -515,7 +577,7 @@ struct UnsafeVectorOverflow { } }; -template +template class Vector : private VectorBuffer { WTF_MAKE_FAST_ALLOCATED; private: @@ -538,6 +600,8 @@ public: explicit Vector(size_t size) : Base(size, size) { + asanSetInitialBufferSizeTo(size); + if (begin()) TypeOperations::initialize(begin(), end()); } @@ -545,6 +609,8 @@ public: Vector(size_t size, const T& val) : Base(size, size) { + asanSetInitialBufferSizeTo(size); + if (begin()) TypeOperations::uninitializedFill(begin(), end(), val); } @@ -552,6 +618,9 @@ public: Vector(std::initializer_list initializerList) { reserveInitialCapacity(initializerList.size()); + + asanSetInitialBufferSizeTo(initializerList.size()); + for (const auto& element : initializerList) uncheckedAppend(element); } @@ -559,21 +628,24 @@ public: ~Vector() { if (m_size) - shrink(0); + TypeOperations::destruct(begin(), end()); + + asanSetBufferSizeToFullCapacity(0); } Vector(const Vector&); - template - Vector(const Vector&); + template + explicit Vector(const Vector&); Vector& operator=(const Vector&); - template - Vector& operator=(const Vector&); + template + Vector& operator=(const Vector&); Vector(Vector&&); Vector& operator=(Vector&&); size_t size() const { return m_size; } + static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); } size_t capacity() const { return Base::capacity(); } bool isEmpty() const { return !size(); } @@ -607,6 +679,7 @@ public: T* data() { return Base::buffer(); } const T* data() const { return Base::buffer(); } + static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); } iterator begin() { return data(); } iterator end() { return begin() + m_size; } @@ -625,7 +698,7 @@ public: T takeLast() { - T result = last(); + T result = WTFMove(last()); removeLast(); return result; } @@ -646,9 +719,15 @@ public: void clear() { shrinkCapacity(0); } - template void append(const U*, size_t); + void append(ValueType&& value) { append(std::forward(value)); } template void append(U&&); - template void uncheckedAppend(U&& val); + template void constructAndAppend(Args&&...); + template bool tryConstructAndAppend(Args&&...); + + void uncheckedAppend(ValueType&& value) { uncheckedAppend(std::forward(value)); } + template void uncheckedAppend(U&&); + + template void append(const U*, size_t); template void appendVector(const Vector&); template bool tryAppend(const U*, size_t); @@ -658,6 +737,10 @@ public: void remove(size_t position); void remove(size_t position, size_t length); + template bool removeFirst(const U&); + template bool removeFirstMatching(const MatchFunction&); + template unsigned removeAll(const U&); + template unsigned removeAllMatching(const MatchFunction&); void removeLast() { @@ -673,10 +756,22 @@ public: MallocPtr releaseBuffer(); - void swap(Vector& other) + void swap(Vector& other) { +#if ASAN_ENABLED + if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice. + return; +#endif + + // Make it possible to copy inline buffers. + asanSetBufferSizeToFullCapacity(); + other.asanSetBufferSizeToFullCapacity(); + + Base::swap(other, m_size, other.m_size); std::swap(m_size, other.m_size); - Base::swap(other); + + asanSetInitialBufferSizeTo(m_size); + other.asanSetInitialBufferSizeTo(other.m_size); } void reverse(); @@ -690,6 +785,14 @@ private: const T* tryExpandCapacity(size_t newMinCapacity, const T*); template U* expandCapacity(size_t newMinCapacity, U*); template void appendSlowCase(U&&); + template void constructAndAppendSlowCase(Args&&...); + template bool tryConstructAndAppendSlowCase(Args&&...); + + void asanSetInitialBufferSizeTo(size_t); + void asanSetBufferSizeToFullCapacity(size_t); + void asanSetBufferSizeToFullCapacity() { asanSetBufferSizeToFullCapacity(size()); } + + void asanBufferSizeWillChangeTo(size_t); using Base::m_size; using Base::buffer; @@ -702,27 +805,34 @@ private: using Base::reallocateBuffer; using Base::restoreInlineBufferIfNeeded; using Base::releaseBuffer; +#if ASAN_ENABLED + using Base::endOfBuffer; +#endif }; -template -Vector::Vector(const Vector& other) +template +Vector::Vector(const Vector& other) : Base(other.capacity(), other.size()) { + asanSetInitialBufferSizeTo(other.size()); + if (begin()) TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); } -template -template -Vector::Vector(const Vector& other) +template +template +Vector::Vector(const Vector& other) : Base(other.capacity(), other.size()) { + asanSetInitialBufferSizeTo(other.size()); + if (begin()) TypeOperations::uninitializedCopy(other.begin(), other.end(), begin()); } -template -Vector& Vector::operator=(const Vector& other) +template +Vector& Vector::operator=(const Vector& other) { if (&other == this) return *this; @@ -734,12 +844,8 @@ Vector& Vector& Vector -template -Vector& Vector::operator=(const Vector& other) +template +template +Vector& Vector::operator=(const Vector& other) { // If the inline capacities match, we should call the more specific // template. If the inline capacities don't match, the two objects @@ -767,11 +873,7 @@ Vector& Vector& Vector -inline Vector::Vector(Vector&& other) +template +inline Vector::Vector(Vector&& other) { swap(other); } -template -inline Vector& Vector::operator=(Vector&& other) +template +inline Vector& Vector::operator=(Vector&& other) { swap(other); return *this; } -template +template template -bool Vector::contains(const U& value) const +bool Vector::contains(const U& value) const { return find(value) != notFound; } -template +template template -size_t Vector::find(const U& value) const +size_t Vector::find(const U& value) const { for (size_t i = 0; i < size(); ++i) { if (at(i) == value) @@ -811,9 +913,9 @@ size_t Vector::find(const U& value) const return notFound; } -template +template template -size_t Vector::reverseFind(const U& value) const +size_t Vector::reverseFind(const U& value) const { for (size_t i = 1; i <= size(); ++i) { const size_t index = size() - i; @@ -823,8 +925,8 @@ size_t Vector::reverseFind(const U& value) c return notFound; } -template -void Vector::fill(const T& val, size_t newSize) +template +void Vector::fill(const T& val, size_t newSize) { if (size() > newSize) shrink(newSize); @@ -833,28 +935,30 @@ void Vector::fill(const T& val, size_t newSi reserveCapacity(newSize); ASSERT(begin()); } - + + asanBufferSizeWillChangeTo(newSize); + std::fill(begin(), end(), val); TypeOperations::uninitializedFill(end(), begin() + newSize, val); m_size = newSize; } -template +template template -void Vector::appendRange(Iterator start, Iterator end) +void Vector::appendRange(Iterator start, Iterator end) { for (Iterator it = start; it != end; ++it) append(*it); } -template -void Vector::expandCapacity(size_t newMinCapacity) +template +void Vector::expandCapacity(size_t newMinCapacity) { - reserveCapacity(std::max(newMinCapacity, std::max(static_cast(16), capacity() + capacity() / 4 + 1))); + reserveCapacity(std::max(newMinCapacity, std::max(static_cast(minCapacity), capacity() + capacity() / 4 + 1))); } -template -T* Vector::expandCapacity(size_t newMinCapacity, T* ptr) +template +T* Vector::expandCapacity(size_t newMinCapacity, T* ptr) { if (ptr < begin() || ptr >= end()) { expandCapacity(newMinCapacity); @@ -865,14 +969,14 @@ T* Vector::expandCapacity(size_t newMinCapac return begin() + index; } -template -bool Vector::tryExpandCapacity(size_t newMinCapacity) +template +bool Vector::tryExpandCapacity(size_t newMinCapacity) { - return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast(16), capacity() + capacity() / 4 + 1))); + return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast(minCapacity), capacity() + capacity() / 4 + 1))); } -template -const T* Vector::tryExpandCapacity(size_t newMinCapacity, const T* ptr) +template +const T* Vector::tryExpandCapacity(size_t newMinCapacity, const T* ptr) { if (ptr < begin() || ptr >= end()) { if (!tryExpandCapacity(newMinCapacity)) @@ -885,21 +989,23 @@ const T* Vector::tryExpandCapacity(size_t ne return begin() + index; } -template template -inline U* Vector::expandCapacity(size_t newMinCapacity, U* ptr) +template template +inline U* Vector::expandCapacity(size_t newMinCapacity, U* ptr) { expandCapacity(newMinCapacity); return ptr; } -template -inline void Vector::resize(size_t size) +template +inline void Vector::resize(size_t size) { - if (size <= m_size) + if (size <= m_size) { TypeOperations::destruct(begin() + size, end()); - else { + asanBufferSizeWillChangeTo(size); + } else { if (size > capacity()) expandCapacity(size); + asanBufferSizeWillChangeTo(size); if (begin()) TypeOperations::initialize(end(), begin() + size); } @@ -907,62 +1013,122 @@ inline void Vector::resize(size_t size) m_size = size; } -template -void Vector::resizeToFit(size_t size) +template +void Vector::resizeToFit(size_t size) { reserveCapacity(size); resize(size); } -template -void Vector::shrink(size_t size) +template +void Vector::shrink(size_t size) { ASSERT(size <= m_size); TypeOperations::destruct(begin() + size, end()); + asanBufferSizeWillChangeTo(size); m_size = size; } -template -void Vector::grow(size_t size) +template +void Vector::grow(size_t size) { ASSERT(size >= m_size); if (size > capacity()) expandCapacity(size); + asanBufferSizeWillChangeTo(size); if (begin()) TypeOperations::initialize(end(), begin() + size); m_size = size; } -template -void Vector::reserveCapacity(size_t newCapacity) +template +inline void Vector::asanSetInitialBufferSizeTo(size_t size) +{ +#if ASAN_ENABLED + if (!buffer()) + return; + + // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error + // when accessing elements in [end(), endOfBuffer()) range. + // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument. + __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size); +#else + UNUSED_PARAM(size); +#endif +} + +template +inline void Vector::asanSetBufferSizeToFullCapacity(size_t size) +{ +#if ASAN_ENABLED + if (!buffer()) + return; + + // ASan requires that the annotation is returned to its initial state before deallocation. + __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size, endOfBuffer()); +#else + UNUSED_PARAM(size); +#endif +} + +template +inline void Vector::asanBufferSizeWillChangeTo(size_t newSize) +{ +#if ASAN_ENABLED + if (!buffer()) + return; + + // Change allowed range. + __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize); +#else + UNUSED_PARAM(newSize); +#endif +} + +template +void Vector::reserveCapacity(size_t newCapacity) { if (newCapacity <= capacity()) return; T* oldBuffer = begin(); T* oldEnd = end(); + + asanSetBufferSizeToFullCapacity(); + Base::allocateBuffer(newCapacity); ASSERT(begin()); + + asanSetInitialBufferSizeTo(size()); + TypeOperations::move(oldBuffer, oldEnd, begin()); Base::deallocateBuffer(oldBuffer); } -template -bool Vector::tryReserveCapacity(size_t newCapacity) +template +bool Vector::tryReserveCapacity(size_t newCapacity) { if (newCapacity <= capacity()) return true; T* oldBuffer = begin(); T* oldEnd = end(); - if (!Base::tryAllocateBuffer(newCapacity)) + + asanSetBufferSizeToFullCapacity(); + + if (!Base::tryAllocateBuffer(newCapacity)) { + asanSetInitialBufferSizeTo(size()); return false; + } ASSERT(begin()); + + asanSetInitialBufferSizeTo(size()); + TypeOperations::move(oldBuffer, oldEnd, begin()); Base::deallocateBuffer(oldBuffer); return true; } -template -inline void Vector::reserveInitialCapacity(size_t initialCapacity) +template +inline void Vector::reserveInitialCapacity(size_t initialCapacity) { ASSERT(!m_size); ASSERT(capacity() == inlineCapacity); @@ -970,8 +1136,8 @@ inline void Vector::reserveInitialCapacity(s Base::allocateBuffer(initialCapacity); } -template -void Vector::shrinkCapacity(size_t newCapacity) +template +void Vector::shrinkCapacity(size_t newCapacity) { if (newCapacity >= capacity()) return; @@ -979,10 +1145,13 @@ void Vector::shrinkCapacity(size_t newCapaci if (newCapacity < size()) shrink(newCapacity); + asanSetBufferSizeToFullCapacity(); + T* oldBuffer = begin(); if (newCapacity > 0) { if (Base::shouldReallocateBuffer(newCapacity)) { Base::reallocateBuffer(newCapacity); + asanSetInitialBufferSizeTo(size()); return; } @@ -994,14 +1163,15 @@ void Vector::shrinkCapacity(size_t newCapaci Base::deallocateBuffer(oldBuffer); Base::restoreInlineBufferIfNeeded(); + + asanSetInitialBufferSizeTo(size()); } // Templatizing these is better than just letting the conversion happen implicitly, // because for instance it allows a PassRefPtr to be appended to a RefPtr vector // without refcount thrash. - -template template -void Vector::append(const U* data, size_t dataSize) +template template +void Vector::append(const U* data, size_t dataSize) { size_t newSize = m_size + dataSize; if (newSize > capacity()) { @@ -1010,14 +1180,14 @@ void Vector::append(const U* data, size_t da } if (newSize < m_size) CRASH(); + asanBufferSizeWillChangeTo(newSize); T* dest = end(); - for (size_t i = 0; i < dataSize; ++i) - new (NotNull, &dest[i]) T(data[i]); + VectorCopier::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest); m_size = newSize; } -template template -bool Vector::tryAppend(const U* data, size_t dataSize) +template template +bool Vector::tryAppend(const U* data, size_t dataSize) { size_t newSize = m_size + dataSize; if (newSize > capacity()) { @@ -1028,17 +1198,18 @@ bool Vector::tryAppend(const U* data, size_t } if (newSize < m_size) return false; + asanBufferSizeWillChangeTo(newSize); T* dest = end(); - for (size_t i = 0; i < dataSize; ++i) - new (NotNull, &dest[i]) T(data[i]); + VectorCopier::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest); m_size = newSize; return true; } -template template -ALWAYS_INLINE void Vector::append(U&& value) +template template +ALWAYS_INLINE void Vector::append(U&& value) { if (size() != capacity()) { + asanBufferSizeWillChangeTo(m_size + 1); new (NotNull, end()) T(std::forward(value)); ++m_size; return; @@ -1047,8 +1218,34 @@ ALWAYS_INLINE void Vector::append(U&& value) appendSlowCase(std::forward(value)); } -template template -void Vector::appendSlowCase(U&& value) +template template +ALWAYS_INLINE void Vector::constructAndAppend(Args&&... args) +{ + if (size() != capacity()) { + asanBufferSizeWillChangeTo(m_size + 1); + new (NotNull, end()) T(std::forward(args)...); + ++m_size; + return; + } + + constructAndAppendSlowCase(std::forward(args)...); +} + +template template +ALWAYS_INLINE bool Vector::tryConstructAndAppend(Args&&... args) +{ + if (size() != capacity()) { + asanBufferSizeWillChangeTo(m_size + 1); + new (NotNull, end()) T(std::forward(args)...); + ++m_size; + return true; + } + + return tryConstructAndAppendSlowCase(std::forward(args)...); +} + +template template +void Vector::appendSlowCase(U&& value) { ASSERT(size() == capacity()); @@ -1056,31 +1253,62 @@ void Vector::appendSlowCase(U&& value) ptr = expandCapacity(size() + 1, ptr); ASSERT(begin()); + asanBufferSizeWillChangeTo(m_size + 1); new (NotNull, end()) T(std::forward(*ptr)); ++m_size; } +template template +void Vector::constructAndAppendSlowCase(Args&&... args) +{ + ASSERT(size() == capacity()); + + expandCapacity(size() + 1); + ASSERT(begin()); + + asanBufferSizeWillChangeTo(m_size + 1); + new (NotNull, end()) T(std::forward(args)...); + ++m_size; +} + +template template +bool Vector::tryConstructAndAppendSlowCase(Args&&... args) +{ + ASSERT(size() == capacity()); + + if (UNLIKELY(!tryExpandCapacity(size() + 1))) + return false; + ASSERT(begin()); + + asanBufferSizeWillChangeTo(m_size + 1); + new (NotNull, end()) T(std::forward(args)...); + ++m_size; + return true; +} + // This version of append saves a branch in the case where you know that the // vector's capacity is large enough for the append to succeed. -template template -inline void Vector::uncheckedAppend(U&& value) +template template +inline void Vector::uncheckedAppend(U&& value) { ASSERT(size() < capacity()); + asanBufferSizeWillChangeTo(m_size + 1); + auto ptr = std::addressof(value); new (NotNull, end()) T(std::forward(*ptr)); ++m_size; } -template template -inline void Vector::appendVector(const Vector& val) +template template +inline void Vector::appendVector(const Vector& val) { append(val.begin(), val.size()); } -template template -void Vector::insert(size_t position, const U* data, size_t dataSize) +template template +void Vector::insert(size_t position, const U* data, size_t dataSize) { ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); size_t newSize = m_size + dataSize; @@ -1090,15 +1318,15 @@ void Vector::insert(size_t position, const U } if (newSize < m_size) CRASH(); + asanBufferSizeWillChangeTo(newSize); T* spot = begin() + position; TypeOperations::moveOverlapping(spot, end(), spot + dataSize); - for (size_t i = 0; i < dataSize; ++i) - new (NotNull, &spot[i]) T(data[i]); + VectorCopier::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot); m_size = newSize; } -template template -inline void Vector::insert(size_t position, U&& value) +template template +inline void Vector::insert(size_t position, U&& value) { ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); @@ -1108,30 +1336,33 @@ inline void Vector::insert(size_t position, ASSERT(begin()); } + asanBufferSizeWillChangeTo(m_size + 1); + T* spot = begin() + position; TypeOperations::moveOverlapping(spot, end(), spot + 1); new (NotNull, spot) T(std::forward(*ptr)); ++m_size; } -template template -inline void Vector::insertVector(size_t position, const Vector& val) +template template +inline void Vector::insertVector(size_t position, const Vector& val) { insert(position, val.begin(), val.size()); } -template -inline void Vector::remove(size_t position) +template +inline void Vector::remove(size_t position) { ASSERT_WITH_SECURITY_IMPLICATION(position < size()); T* spot = begin() + position; spot->~T(); TypeOperations::moveOverlapping(spot + 1, end(), spot); + asanBufferSizeWillChangeTo(m_size - 1); --m_size; } -template -inline void Vector::remove(size_t position, size_t length) +template +inline void Vector::remove(size_t position, size_t length) { ASSERT_WITH_SECURITY_IMPLICATION(position <= size()); ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size()); @@ -1139,19 +1370,83 @@ inline void Vector::remove(size_t position, T* endSpot = beginSpot + length; TypeOperations::destruct(beginSpot, endSpot); TypeOperations::moveOverlapping(endSpot, end(), beginSpot); + asanBufferSizeWillChangeTo(m_size - length); m_size -= length; } -template -inline void Vector::reverse() +template +template +inline bool Vector::removeFirst(const U& value) +{ + return removeFirstMatching([&value] (const T& current) { + return current == value; + }); +} + +template +template +inline bool Vector::removeFirstMatching(const MatchFunction& matches) +{ + for (size_t i = 0; i < size(); ++i) { + if (matches(at(i))) { + remove(i); + return true; + } + } + return false; +} + +template +template +inline unsigned Vector::removeAll(const U& value) +{ + return removeAllMatching([&value] (const T& current) { + return current == value; + }); +} + +template +template +inline unsigned Vector::removeAllMatching(const MatchFunction& matches) +{ + iterator holeBegin = end(); + iterator holeEnd = end(); + unsigned matchCount = 0; + for (auto it = begin(), itEnd = end(); it != itEnd; ++it) { + if (matches(*it)) { + if (holeBegin == end()) + holeBegin = it; + else if (holeEnd != it) { + TypeOperations::moveOverlapping(holeEnd, it, holeBegin); + holeBegin += it - holeEnd; + } + holeEnd = it + 1; + it->~T(); + ++matchCount; + } + } + if (holeEnd != end()) + TypeOperations::moveOverlapping(holeEnd, end(), holeBegin); + asanBufferSizeWillChangeTo(m_size - matchCount); + m_size -= matchCount; + return matchCount; +} + +template +inline void Vector::reverse() { for (size_t i = 0; i < m_size / 2; ++i) std::swap(at(i), at(m_size - 1 - i)); } -template -inline MallocPtr Vector::releaseBuffer() +template +inline MallocPtr Vector::releaseBuffer() { + // FIXME: Find a way to preserve annotations on the returned buffer. + // ASan requires that all annotations are removed before deallocation, + // and MallocPtr doesn't implement that. + asanSetBufferSizeToFullCapacity(); + auto buffer = Base::releaseBuffer(); if (inlineCapacity && !buffer && m_size) { // If the vector had some data, but no buffer to release, @@ -1162,11 +1457,12 @@ inline MallocPtr Vector::releaseBuffer() memcpy(buffer.get(), data(), bytes); } m_size = 0; + // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here? return buffer; } -template -inline void Vector::checkConsistency() +template +inline void Vector::checkConsistency() { #if !ASSERT_DISABLED for (size_t i = 0; i < size(); ++i) @@ -1174,23 +1470,14 @@ inline void Vector::checkConsistency() #endif } -template -void deprecatedDeleteAllValues(const Vector& collection) -{ - typedef typename Vector::const_iterator iterator; - iterator end = collection.end(); - for (iterator it = collection.begin(); it != end; ++it) - delete *it; -} - -template -inline void swap(Vector& a, Vector& b) +template +inline void swap(Vector& a, Vector& b) { a.swap(b); } -template -bool operator==(const Vector& a, const Vector& b) +template +bool operator==(const Vector& a, const Vector& b) { if (a.size() != b.size()) return false; @@ -1198,8 +1485,8 @@ bool operator==(const Vector& a, const Vecto return VectorTypeOperations::compare(a.data(), b.data(), a.size()); } -template -inline bool operator!=(const Vector& a, const Vector& b) +template +inline bool operator!=(const Vector& a, const Vector& b) { return !(a == b); } -- cgit v1.2.1