diff options
Diffstat (limited to '3rdparty/asmjit/src/asmjit/core/zonehash.h')
-rw-r--r-- | 3rdparty/asmjit/src/asmjit/core/zonehash.h | 186 |
1 files changed, 186 insertions, 0 deletions
diff --git a/3rdparty/asmjit/src/asmjit/core/zonehash.h b/3rdparty/asmjit/src/asmjit/core/zonehash.h new file mode 100644 index 00000000000..d6cd2e31cb9 --- /dev/null +++ b/3rdparty/asmjit/src/asmjit/core/zonehash.h @@ -0,0 +1,186 @@ +// 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 + +#ifndef ASMJIT_CORE_ZONEHASH_H_INCLUDED +#define ASMJIT_CORE_ZONEHASH_H_INCLUDED + +#include "../core/zone.h" + +ASMJIT_BEGIN_NAMESPACE + +//! \addtogroup asmjit_zone +//! \{ + +//! Node used by \ref ZoneHash template. +//! +//! You must provide function `bool eq(const Key& key)` in order to make `ZoneHash::get()` working. +class ZoneHashNode { +public: + ASMJIT_NONCOPYABLE(ZoneHashNode) + + inline ZoneHashNode(uint32_t hashCode = 0) noexcept + : _hashNext(nullptr), + _hashCode(hashCode), + _customData(0) {} + + //! Next node in the chain, null if it terminates the chain. + ZoneHashNode* _hashNext; + //! Precalculated hash-code of key. + uint32_t _hashCode; + //! Padding, can be reused by any Node that inherits `ZoneHashNode`. + uint32_t _customData; +}; + +//! Base class used by \ref ZoneHash template +class ZoneHashBase { +public: + ASMJIT_NONCOPYABLE(ZoneHashBase) + + //! Buckets data. + ZoneHashNode** _data; + //! Count of records inserted into the hash table. + size_t _size; + //! Count of hash buckets. + uint32_t _bucketsCount; + //! When buckets array should grow (only checked after insertion). + uint32_t _bucketsGrow; + //! Reciprocal value of `_bucketsCount`. + uint32_t _rcpValue; + //! How many bits to shift right when hash is multiplied with `_rcpValue`. + uint8_t _rcpShift; + //! Prime value index in internal prime array. + uint8_t _primeIndex; + + //! Embedded data, used by empty hash tables. + ZoneHashNode* _embedded[1]; + + //! \name Construction & Destruction + //! \{ + + ASMJIT_INLINE_NODEBUG ZoneHashBase() noexcept { + reset(); + } + + inline ZoneHashBase(ZoneHashBase&& other) noexcept { + _data = other._data; + _size = other._size; + _bucketsCount = other._bucketsCount; + _bucketsGrow = other._bucketsGrow; + _rcpValue = other._rcpValue; + _rcpShift = other._rcpShift; + _primeIndex = other._primeIndex; + _embedded[0] = other._embedded[0]; + + if (_data == other._embedded) _data = _embedded; + } + + inline void reset() noexcept { + _data = _embedded; + _size = 0; + _bucketsCount = 1; + _bucketsGrow = 1; + _rcpValue = 1; + _rcpShift = 0; + _primeIndex = 0; + _embedded[0] = nullptr; + } + + inline void release(ZoneAllocator* allocator) noexcept { + ZoneHashNode** oldData = _data; + if (oldData != _embedded) + allocator->release(oldData, _bucketsCount * sizeof(ZoneHashNode*)); + reset(); + } + + //! \} + + //! \name Accessors + //! \{ + + ASMJIT_INLINE_NODEBUG bool empty() const noexcept { return _size == 0; } + ASMJIT_INLINE_NODEBUG size_t size() const noexcept { return _size; } + + //! \} + + //! \name Utilities + //! \{ + + inline void _swap(ZoneHashBase& other) noexcept { + std::swap(_data, other._data); + std::swap(_size, other._size); + std::swap(_bucketsCount, other._bucketsCount); + std::swap(_bucketsGrow, other._bucketsGrow); + std::swap(_rcpValue, other._rcpValue); + std::swap(_rcpShift, other._rcpShift); + std::swap(_primeIndex, other._primeIndex); + std::swap(_embedded[0], other._embedded[0]); + + if (_data == other._embedded) _data = _embedded; + if (other._data == _embedded) other._data = other._embedded; + } + + //! \cond INTERNAL + inline uint32_t _calcMod(uint32_t hash) const noexcept { + uint32_t x = uint32_t((uint64_t(hash) * _rcpValue) >> _rcpShift); + return hash - x * _bucketsCount; + } + + ASMJIT_API void _rehash(ZoneAllocator* allocator, uint32_t newCount) noexcept; + ASMJIT_API ZoneHashNode* _insert(ZoneAllocator* allocator, ZoneHashNode* node) noexcept; + ASMJIT_API ZoneHashNode* _remove(ZoneAllocator* allocator, ZoneHashNode* node) noexcept; + //! \endcond + + //! \} +}; + +//! Low-level hash table specialized for storing string keys and POD values. +//! +//! This hash table allows duplicates to be inserted (the API is so low level that it's up to you if you allow it or +//! not, as you should first `get()` the node and then modify it or insert a new node by using `insert()`, depending +//! on the intention). +template<typename NodeT> +class ZoneHash : public ZoneHashBase { +public: + ASMJIT_NONCOPYABLE(ZoneHash) + + typedef NodeT Node; + + //! \name Construction & Destruction + //! \{ + + ASMJIT_INLINE_NODEBUG ZoneHash() noexcept + : ZoneHashBase() {} + + ASMJIT_INLINE_NODEBUG ZoneHash(ZoneHash&& other) noexcept + : ZoneHash(other) {} + + //! \} + + //! \name Utilities + //! \{ + + ASMJIT_INLINE_NODEBUG void swap(ZoneHash& other) noexcept { ZoneHashBase::_swap(other); } + + template<typename KeyT> + inline NodeT* get(const KeyT& key) const noexcept { + uint32_t hashMod = _calcMod(key.hashCode()); + NodeT* node = static_cast<NodeT*>(_data[hashMod]); + + while (node && !key.matches(node)) + node = static_cast<NodeT*>(node->_hashNext); + return node; + } + + ASMJIT_INLINE_NODEBUG NodeT* insert(ZoneAllocator* allocator, NodeT* node) noexcept { return static_cast<NodeT*>(_insert(allocator, node)); } + ASMJIT_INLINE_NODEBUG NodeT* remove(ZoneAllocator* allocator, NodeT* node) noexcept { return static_cast<NodeT*>(_remove(allocator, node)); } + + //! \} +}; + +//! \} + +ASMJIT_END_NAMESPACE + +#endif // ASMJIT_CORE_ZONEHASH_H_INCLUDED |