summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/asmjit/src/asmjit/core/zonehash.h
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/asmjit/src/asmjit/core/zonehash.h')
-rw-r--r--3rdparty/asmjit/src/asmjit/core/zonehash.h186
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