diff options
Diffstat (limited to '3rdparty/asmjit/src/asmjit/core/zonevector.cpp')
-rw-r--r-- | 3rdparty/asmjit/src/asmjit/core/zonevector.cpp | 369 |
1 files changed, 369 insertions, 0 deletions
diff --git a/3rdparty/asmjit/src/asmjit/core/zonevector.cpp b/3rdparty/asmjit/src/asmjit/core/zonevector.cpp new file mode 100644 index 00000000000..24860219de2 --- /dev/null +++ b/3rdparty/asmjit/src/asmjit/core/zonevector.cpp @@ -0,0 +1,369 @@ +// This file is part of AsmJit project <https://asmjit.com> +// +// See asmjit.h or LICENSE.md for license and copyright information +// SPDX-License-Identifier: Zlib + +#include "../core/api-build_p.h" +#include "../core/support.h" +#include "../core/zone.h" +#include "../core/zonevector.h" + +ASMJIT_BEGIN_NAMESPACE + +// ZoneVectorBase - Helpers +// ======================== + +Error ZoneVectorBase::_grow(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept { + uint32_t threshold = Globals::kGrowThreshold / sizeOfT; + uint32_t capacity = _capacity; + uint32_t after = _size; + + if (ASMJIT_UNLIKELY(std::numeric_limits<uint32_t>::max() - n < after)) + return DebugUtils::errored(kErrorOutOfMemory); + + after += n; + if (capacity >= after) + return kErrorOk; + + // ZoneVector is used as an array to hold short-lived data structures used + // during code generation. The growing strategy is simple - use small capacity + // at the beginning (very good for ZoneAllocator) and then grow quicker to + // prevent successive reallocations. + if (capacity < 4) + capacity = 4; + else if (capacity < 8) + capacity = 8; + else if (capacity < 16) + capacity = 16; + else if (capacity < 64) + capacity = 64; + else if (capacity < 256) + capacity = 256; + + while (capacity < after) { + if (capacity < threshold) + capacity *= 2; + else + capacity += threshold; + } + + return _reserve(allocator, sizeOfT, capacity); +} + +Error ZoneVectorBase::_reserve(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept { + uint32_t oldCapacity = _capacity; + if (oldCapacity >= n) + return kErrorOk; + + uint32_t nBytes = n * sizeOfT; + if (ASMJIT_UNLIKELY(nBytes < n)) + return DebugUtils::errored(kErrorOutOfMemory); + + size_t allocatedBytes; + uint8_t* newData = static_cast<uint8_t*>(allocator->alloc(nBytes, allocatedBytes)); + + if (ASMJIT_UNLIKELY(!newData)) + return DebugUtils::errored(kErrorOutOfMemory); + + void* oldData = _data; + if (oldData && _size) { + memcpy(newData, oldData, size_t(_size) * sizeOfT); + allocator->release(oldData, size_t(oldCapacity) * sizeOfT); + } + + _capacity = uint32_t(allocatedBytes / sizeOfT); + ASMJIT_ASSERT(_capacity >= n); + + _data = newData; + return kErrorOk; +} + +Error ZoneVectorBase::_resize(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept { + uint32_t size = _size; + + if (_capacity < n) { + ASMJIT_PROPAGATE(_grow(allocator, sizeOfT, n - size)); + ASMJIT_ASSERT(_capacity >= n); + } + + if (size < n) + memset(static_cast<uint8_t*>(_data) + size_t(size) * sizeOfT, 0, size_t(n - size) * sizeOfT); + + _size = n; + return kErrorOk; +} + +// ZoneBitVector - Operations +// ========================== + +Error ZoneBitVector::copyFrom(ZoneAllocator* allocator, const ZoneBitVector& other) noexcept { + BitWord* data = _data; + uint32_t newSize = other.size(); + + if (!newSize) { + _size = 0; + return kErrorOk; + } + + if (newSize > _capacity) { + // Realloc needed... Calculate the minimum capacity (in bytes) required. + uint32_t minimumCapacityInBits = Support::alignUp<uint32_t>(newSize, kBitWordSizeInBits); + if (ASMJIT_UNLIKELY(minimumCapacityInBits < newSize)) + return DebugUtils::errored(kErrorOutOfMemory); + + // Normalize to bytes. + uint32_t minimumCapacity = minimumCapacityInBits / 8; + size_t allocatedCapacity; + + BitWord* newData = static_cast<BitWord*>(allocator->alloc(minimumCapacity, allocatedCapacity)); + if (ASMJIT_UNLIKELY(!newData)) + return DebugUtils::errored(kErrorOutOfMemory); + + // `allocatedCapacity` now contains number in bytes, we need bits. + size_t allocatedCapacityInBits = allocatedCapacity * 8; + + // Arithmetic overflow should normally not happen. If it happens we just + // change the `allocatedCapacityInBits` to the `minimumCapacityInBits` as + // this value is still safe to be used to call `_allocator->release(...)`. + if (ASMJIT_UNLIKELY(allocatedCapacityInBits < allocatedCapacity)) + allocatedCapacityInBits = minimumCapacityInBits; + + if (data) + allocator->release(data, _capacity / 8); + data = newData; + + _data = data; + _capacity = uint32_t(allocatedCapacityInBits); + } + + _size = newSize; + _copyBits(data, other.data(), _wordsPerBits(newSize)); + + return kErrorOk; +} + +Error ZoneBitVector::_resize(ZoneAllocator* allocator, uint32_t newSize, uint32_t idealCapacity, bool newBitsValue) noexcept { + ASMJIT_ASSERT(idealCapacity >= newSize); + + if (newSize <= _size) { + // The size after the resize is lesser than or equal to the current size. + uint32_t idx = newSize / kBitWordSizeInBits; + uint32_t bit = newSize % kBitWordSizeInBits; + + // Just set all bits outside of the new size in the last word to zero. + // There is a case that there are not bits to set if `bit` is zero. This + // happens when `newSize` is a multiply of `kBitWordSizeInBits` like 64, 128, + // and so on. In that case don't change anything as that would mean settings + // bits outside of the `_size`. + if (bit) + _data[idx] &= (BitWord(1) << bit) - 1u; + + _size = newSize; + return kErrorOk; + } + + uint32_t oldSize = _size; + BitWord* data = _data; + + if (newSize > _capacity) { + // Realloc needed, calculate the minimum capacity (in bytes) required. + uint32_t minimumCapacityInBits = Support::alignUp<uint32_t>(idealCapacity, kBitWordSizeInBits); + + if (ASMJIT_UNLIKELY(minimumCapacityInBits < newSize)) + return DebugUtils::errored(kErrorOutOfMemory); + + // Normalize to bytes. + uint32_t minimumCapacity = minimumCapacityInBits / 8; + size_t allocatedCapacity; + + BitWord* newData = static_cast<BitWord*>(allocator->alloc(minimumCapacity, allocatedCapacity)); + if (ASMJIT_UNLIKELY(!newData)) + return DebugUtils::errored(kErrorOutOfMemory); + + // `allocatedCapacity` now contains number in bytes, we need bits. + size_t allocatedCapacityInBits = allocatedCapacity * 8; + + // Arithmetic overflow should normally not happen. If it happens we just + // change the `allocatedCapacityInBits` to the `minimumCapacityInBits` as + // this value is still safe to be used to call `_allocator->release(...)`. + if (ASMJIT_UNLIKELY(allocatedCapacityInBits < allocatedCapacity)) + allocatedCapacityInBits = minimumCapacityInBits; + + _copyBits(newData, data, _wordsPerBits(oldSize)); + + if (data) + allocator->release(data, _capacity / 8); + data = newData; + + _data = data; + _capacity = uint32_t(allocatedCapacityInBits); + } + + // Start (of the old size) and end (of the new size) bits + uint32_t idx = oldSize / kBitWordSizeInBits; + uint32_t startBit = oldSize % kBitWordSizeInBits; + uint32_t endBit = newSize % kBitWordSizeInBits; + + // Set new bits to either 0 or 1. The `pattern` is used to set multiple + // bits per bit-word and contains either all zeros or all ones. + BitWord pattern = Support::bitMaskFromBool<BitWord>(newBitsValue); + + // First initialize the last bit-word of the old size. + if (startBit) { + uint32_t nBits = 0; + + if (idx == (newSize / kBitWordSizeInBits)) { + // The number of bit-words is the same after the resize. In that case + // we need to set only bits necessary in the current last bit-word. + ASMJIT_ASSERT(startBit < endBit); + nBits = endBit - startBit; + } + else { + // There is be more bit-words after the resize. In that case we don't + // have to be extra careful about the last bit-word of the old size. + nBits = kBitWordSizeInBits - startBit; + } + + data[idx++] |= pattern << nBits; + } + + // Initialize all bit-words after the last bit-word of the old size. + uint32_t endIdx = _wordsPerBits(newSize); + while (idx < endIdx) data[idx++] = pattern; + + // Clear unused bits of the last bit-word. + if (endBit) + data[endIdx - 1] = pattern & ((BitWord(1) << endBit) - 1); + + _size = newSize; + return kErrorOk; +} + +Error ZoneBitVector::_append(ZoneAllocator* allocator, bool value) noexcept { + uint32_t kThreshold = Globals::kGrowThreshold * 8; + uint32_t newSize = _size + 1; + uint32_t idealCapacity = _capacity; + + if (idealCapacity < 128) + idealCapacity = 128; + else if (idealCapacity <= kThreshold) + idealCapacity *= 2; + else + idealCapacity += kThreshold; + + if (ASMJIT_UNLIKELY(idealCapacity < _capacity)) { + if (ASMJIT_UNLIKELY(_size == std::numeric_limits<uint32_t>::max())) + return DebugUtils::errored(kErrorOutOfMemory); + idealCapacity = newSize; + } + + return _resize(allocator, newSize, idealCapacity, value); +} + +// ZoneVector / ZoneBitVector - Tests +// ================================== + +#if defined(ASMJIT_TEST) +template<typename T> +static void test_zone_vector(ZoneAllocator* allocator, const char* typeName) { + int i; + int kMax = 100000; + + ZoneVector<T> vec; + + INFO("ZoneVector<%s> basic tests", typeName); + EXPECT_EQ(vec.append(allocator, 0), kErrorOk); + EXPECT_FALSE(vec.empty()); + EXPECT_EQ(vec.size(), 1u); + EXPECT_GE(vec.capacity(), 1u); + EXPECT_EQ(vec.indexOf(0), 0u); + EXPECT_EQ(vec.indexOf(-11), Globals::kNotFound); + + vec.clear(); + EXPECT_TRUE(vec.empty()); + EXPECT_EQ(vec.size(), 0u); + EXPECT_EQ(vec.indexOf(0), Globals::kNotFound); + + for (i = 0; i < kMax; i++) { + EXPECT_EQ(vec.append(allocator, T(i)), kErrorOk); + } + EXPECT_FALSE(vec.empty()); + EXPECT_EQ(vec.size(), uint32_t(kMax)); + EXPECT_EQ(vec.indexOf(T(0)), uint32_t(0)); + EXPECT_EQ(vec.indexOf(T(kMax - 1)), uint32_t(kMax - 1)); + + EXPECT_EQ(vec.begin()[0], 0); + EXPECT_EQ(vec.end()[-1], kMax - 1); + + EXPECT_EQ(vec.rbegin()[0], kMax - 1); + EXPECT_EQ(vec.rend()[-1], 0); + + int64_t fsum = 0; + int64_t rsum = 0; + + for (const T& item : vec) { fsum += item; } + for (auto it = vec.rbegin(); it != vec.rend(); ++it) { rsum += *it; } + + EXPECT_EQ(fsum, rsum); + + vec.release(allocator); +} + +static void test_zone_bitvector(ZoneAllocator* allocator) { + Zone zone(8096 - Zone::kBlockOverhead); + + uint32_t i, count; + uint32_t kMaxCount = 100; + + ZoneBitVector vec; + EXPECT_TRUE(vec.empty()); + EXPECT_EQ(vec.size(), 0u); + + INFO("ZoneBitVector::resize()"); + for (count = 1; count < kMaxCount; count++) { + vec.clear(); + EXPECT_EQ(vec.resize(allocator, count, false), kErrorOk); + EXPECT_EQ(vec.size(), count); + + for (i = 0; i < count; i++) + EXPECT_FALSE(vec.bitAt(i)); + + vec.clear(); + EXPECT_EQ(vec.resize(allocator, count, true), kErrorOk); + EXPECT_EQ(vec.size(), count); + + for (i = 0; i < count; i++) + EXPECT_TRUE(vec.bitAt(i)); + } + + INFO("ZoneBitVector::fillBits() / clearBits()"); + for (count = 1; count < kMaxCount; count += 2) { + vec.clear(); + EXPECT_EQ(vec.resize(allocator, count), kErrorOk); + EXPECT_EQ(vec.size(), count); + + for (i = 0; i < (count + 1) / 2; i++) { + bool value = bool(i & 1); + if (value) + vec.fillBits(i, count - i * 2); + else + vec.clearBits(i, count - i * 2); + } + + for (i = 0; i < count; i++) { + EXPECT_EQ(vec.bitAt(i), bool(i & 1)); + } + } +} + +UNIT(zone_vector) { + Zone zone(8096 - Zone::kBlockOverhead); + ZoneAllocator allocator(&zone); + + test_zone_vector<int>(&allocator, "int"); + test_zone_vector<int64_t>(&allocator, "int64_t"); + test_zone_bitvector(&allocator); +} +#endif + +ASMJIT_END_NAMESPACE |