diff options
Diffstat (limited to '3rdparty/asmjit/src/asmjit/core/zonetree.h')
-rw-r--r-- | 3rdparty/asmjit/src/asmjit/core/zonetree.h | 163 |
1 files changed, 77 insertions, 86 deletions
diff --git a/3rdparty/asmjit/src/asmjit/core/zonetree.h b/3rdparty/asmjit/src/asmjit/core/zonetree.h index 1877919d67b..ffeb674cfe2 100644 --- a/3rdparty/asmjit/src/asmjit/core/zonetree.h +++ b/3rdparty/asmjit/src/asmjit/core/zonetree.h @@ -1,25 +1,7 @@ -// AsmJit - Machine code generation for C++ +// This file is part of AsmJit project <https://asmjit.com> // -// * Official AsmJit Home Page: https://asmjit.com -// * Official Github Repository: https://github.com/asmjit/asmjit -// -// Copyright (c) 2008-2020 The AsmJit Authors -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. +// See asmjit.h or LICENSE.md for license and copyright information +// SPDX-License-Identifier: Zlib #ifndef ASMJIT_CORE_ZONETREE_H_INCLUDED #define ASMJIT_CORE_ZONETREE_H_INCLUDED @@ -31,10 +13,6 @@ ASMJIT_BEGIN_NAMESPACE //! \addtogroup asmjit_zone //! \{ -// ============================================================================ -// [asmjit::ZoneTreeNode] -// ============================================================================ - //! RB-Tree node. //! //! The color is stored in a least significant bit of the `left` node. @@ -44,36 +22,45 @@ class ZoneTreeNode { public: ASMJIT_NONCOPYABLE(ZoneTreeNode) + //! \name Constants + //! \{ + enum : uintptr_t { kRedMask = 0x1, kPtrMask = ~kRedMask }; - uintptr_t _rbNodeData[Globals::kLinkCount]; + //! \} + + //! \name Members + //! \{ + + uintptr_t _rbNodeData[2] {}; + + //! \} //! \name Construction & Destruction //! \{ - inline ZoneTreeNode() noexcept - : _rbNodeData { 0, 0 } {} + ASMJIT_INLINE_NODEBUG ZoneTreeNode() noexcept {} //! \} //! \name Accessors //! \{ - inline bool isRed() const noexcept { return static_cast<bool>(_rbNodeData[0] & kRedMask); } + ASMJIT_INLINE_NODEBUG bool isRed() const noexcept { return static_cast<bool>(_rbNodeData[0] & kRedMask); } - inline bool hasChild(size_t i) const noexcept { return _rbNodeData[i] > kRedMask; } - inline bool hasLeft() const noexcept { return _rbNodeData[0] > kRedMask; } - inline bool hasRight() const noexcept { return _rbNodeData[1] != 0; } + ASMJIT_INLINE_NODEBUG bool hasChild(size_t i) const noexcept { return _rbNodeData[i] > kRedMask; } + ASMJIT_INLINE_NODEBUG bool hasLeft() const noexcept { return _rbNodeData[0] > kRedMask; } + ASMJIT_INLINE_NODEBUG bool hasRight() const noexcept { return _rbNodeData[1] != 0; } template<typename T = ZoneTreeNode> - inline T* child(size_t i) const noexcept { return static_cast<T*>(_getChild(i)); } + ASMJIT_INLINE_NODEBUG T* child(size_t i) const noexcept { return static_cast<T*>(_getChild(i)); } template<typename T = ZoneTreeNode> - inline T* left() const noexcept { return static_cast<T*>(_getLeft()); } + ASMJIT_INLINE_NODEBUG T* left() const noexcept { return static_cast<T*>(_getLeft()); } template<typename T = ZoneTreeNode> - inline T* right() const noexcept { return static_cast<T*>(_getRight()); } + ASMJIT_INLINE_NODEBUG T* right() const noexcept { return static_cast<T*>(_getRight()); } //! \} @@ -81,19 +68,19 @@ public: //! \name Internal //! \{ - inline ZoneTreeNode* _getChild(size_t i) const noexcept { return (ZoneTreeNode*)(_rbNodeData[i] & kPtrMask); } - inline ZoneTreeNode* _getLeft() const noexcept { return (ZoneTreeNode*)(_rbNodeData[0] & kPtrMask); } - inline ZoneTreeNode* _getRight() const noexcept { return (ZoneTreeNode*)(_rbNodeData[1]); } + ASMJIT_INLINE_NODEBUG ZoneTreeNode* _getChild(size_t i) const noexcept { return (ZoneTreeNode*)(_rbNodeData[i] & kPtrMask); } + ASMJIT_INLINE_NODEBUG ZoneTreeNode* _getLeft() const noexcept { return (ZoneTreeNode*)(_rbNodeData[0] & kPtrMask); } + ASMJIT_INLINE_NODEBUG ZoneTreeNode* _getRight() const noexcept { return (ZoneTreeNode*)(_rbNodeData[1]); } - inline void _setChild(size_t i, ZoneTreeNode* node) noexcept { _rbNodeData[i] = (_rbNodeData[i] & kRedMask) | (uintptr_t)node; } - inline void _setLeft(ZoneTreeNode* node) noexcept { _rbNodeData[0] = (_rbNodeData[0] & kRedMask) | (uintptr_t)node; } - inline void _setRight(ZoneTreeNode* node) noexcept { _rbNodeData[1] = (uintptr_t)node; } + ASMJIT_INLINE_NODEBUG void _setChild(size_t i, ZoneTreeNode* node) noexcept { _rbNodeData[i] = (_rbNodeData[i] & kRedMask) | (uintptr_t)node; } + ASMJIT_INLINE_NODEBUG void _setLeft(ZoneTreeNode* node) noexcept { _rbNodeData[0] = (_rbNodeData[0] & kRedMask) | (uintptr_t)node; } + ASMJIT_INLINE_NODEBUG void _setRight(ZoneTreeNode* node) noexcept { _rbNodeData[1] = (uintptr_t)node; } - inline void _makeRed() noexcept { _rbNodeData[0] |= kRedMask; } - inline void _makeBlack() noexcept { _rbNodeData[0] &= kPtrMask; } + ASMJIT_INLINE_NODEBUG void _makeRed() noexcept { _rbNodeData[0] |= kRedMask; } + ASMJIT_INLINE_NODEBUG void _makeBlack() noexcept { _rbNodeData[0] &= kPtrMask; } //! Tests whether the node is RED (RED node must be non-null and must have RED flag set). - static inline bool _isValidRed(ZoneTreeNode* node) noexcept { return node && node->isRed(); } + static ASMJIT_INLINE_NODEBUG bool _isValidRed(ZoneTreeNode* node) noexcept { return node && node->isRed(); } //! \} //! \endcond @@ -108,7 +95,7 @@ public: //! \name Construction & Destruction //! \{ - inline ZoneTreeNodeT() noexcept + ASMJIT_INLINE_NODEBUG ZoneTreeNodeT() noexcept : ZoneTreeNode() {} //! \} @@ -116,17 +103,13 @@ public: //! \name Accessors //! \{ - inline NodeT* child(size_t i) const noexcept { return static_cast<NodeT*>(_getChild(i)); } - inline NodeT* left() const noexcept { return static_cast<NodeT*>(_getLeft()); } - inline NodeT* right() const noexcept { return static_cast<NodeT*>(_getRight()); } + ASMJIT_INLINE_NODEBUG NodeT* child(size_t i) const noexcept { return static_cast<NodeT*>(_getChild(i)); } + ASMJIT_INLINE_NODEBUG NodeT* left() const noexcept { return static_cast<NodeT*>(_getLeft()); } + ASMJIT_INLINE_NODEBUG NodeT* right() const noexcept { return static_cast<NodeT*>(_getRight()); } //! \} }; -// ============================================================================ -// [asmjit::ZoneTree] -// ============================================================================ - //! RB-Tree. template<typename NodeT> class ZoneTree { @@ -134,38 +117,35 @@ public: ASMJIT_NONCOPYABLE(ZoneTree) typedef NodeT Node; - NodeT* _root; + NodeT* _root {}; //! \name Construction & Destruction //! \{ - inline ZoneTree() noexcept - : _root(nullptr) {} - - inline ZoneTree(ZoneTree&& other) noexcept + ASMJIT_INLINE_NODEBUG ZoneTree() noexcept {} + ASMJIT_INLINE_NODEBUG ZoneTree(ZoneTree&& other) noexcept : _root(other._root) {} - - inline void reset() noexcept { _root = nullptr; } + ASMJIT_INLINE_NODEBUG void reset() noexcept { _root = nullptr; } //! \} //! \name Accessors //! \{ - inline bool empty() const noexcept { return _root == nullptr; } - inline NodeT* root() const noexcept { return static_cast<NodeT*>(_root); } + ASMJIT_INLINE_NODEBUG bool empty() const noexcept { return _root == nullptr; } + ASMJIT_INLINE_NODEBUG NodeT* root() const noexcept { return static_cast<NodeT*>(_root); } //! \} //! \name Utilities //! \{ - inline void swap(ZoneTree& other) noexcept { + ASMJIT_INLINE_NODEBUG void swap(ZoneTree& other) noexcept { std::swap(_root, other._root); } - template<typename CompareT = Support::Compare<Support::kSortAscending>> - void insert(NodeT* node, const CompareT& cmp = CompareT()) noexcept { + template<typename CompareT = Support::Compare<Support::SortOrder::kAscending>> + void insert(NodeT* ASMJIT_NONNULL(node), const CompareT& cmp = CompareT()) noexcept { // Node to insert must not contain garbage. ASMJIT_ASSERT(!node->hasLeft()); ASMJIT_ASSERT(!node->hasRight()); @@ -176,18 +156,18 @@ public: return; } - ZoneTreeNode head; // False root node, - head._setRight(_root); // having root on the right. + ZoneTreeNode head; // False root node, + head._setRight(_root); // having root on the right. - ZoneTreeNode* g = nullptr; // Grandparent. - ZoneTreeNode* p = nullptr; // Parent. - ZoneTreeNode* t = &head; // Iterator. - ZoneTreeNode* q = _root; // Query. + ZoneTreeNode* g = nullptr; // Grandparent. + ZoneTreeNode* p = nullptr; // Parent. + ZoneTreeNode* t = &head; // Iterator. + ZoneTreeNode* q = _root; // Query. - size_t dir = 0; // Direction for accessing child nodes. - size_t last = 0; // Not needed to initialize, but makes some tools happy. + size_t dir = 0; // Direction for accessing child nodes. + size_t last = 0; // Not needed to initialize, but makes some tools happy. - node->_makeRed(); // New nodes are always red and violations fixed appropriately. + node->_makeRed(); // New nodes are always red and violations fixed appropriately. // Search down the tree. for (;;) { @@ -204,9 +184,12 @@ public: } // Fix red violation. - if (_isValidRed(q) && _isValidRed(p)) + if (_isValidRed(q) && _isValidRed(p)) { + ASMJIT_ASSUME(g != nullptr); + ASMJIT_ASSUME(p != nullptr); t->_setChild(t->_getRight() == g, q == p->_getChild(last) ? _singleRotate(g, !last) : _doubleRotate(g, !last)); + } // Stop if found. if (q == node) @@ -229,8 +212,8 @@ public: } //! Remove node from RBTree. - template<typename CompareT = Support::Compare<Support::kSortAscending>> - void remove(ZoneTreeNode* node, const CompareT& cmp = CompareT()) noexcept { + template<typename CompareT = Support::Compare<Support::SortOrder::kAscending>> + void remove(ZoneTreeNode* ASMJIT_NONNULL(node), const CompareT& cmp = CompareT()) noexcept { ZoneTreeNode head; // False root node, head._setRight(_root); // having root on the right. @@ -274,6 +257,9 @@ public: q->_makeRed(); } else { + ASMJIT_ASSUME(g != nullptr); + ASMJIT_ASSUME(s != nullptr); + size_t dir2 = g->_getRight() == p; ZoneTreeNode* child = g->_getChild(dir2); @@ -304,10 +290,9 @@ public: p->_setChild(p->_getRight() == q, q->_getChild(q->_getLeft() == nullptr)); - // NOTE: The original algorithm used a trick to just copy 'key/value' to - // `f` and mark `q` for deletion. But this is unacceptable here as we - // really want to destroy the passed `node`. So, we have to make sure that - // we have really removed `f` and not `q`. + // NOTE: The original algorithm used a trick to just copy 'key/value' to `f` and mark `q` for deletion. But this + // is unacceptable here as we really want to destroy the passed `node`. So, we have to make sure that we have + // really removed `f` and not `q`. if (f != q) { ASMJIT_ASSERT(f != &head); ASMJIT_ASSERT(f != gf); @@ -337,8 +322,8 @@ public: if (_root) _root->_makeBlack(); } - template<typename KeyT, typename CompareT = Support::Compare<Support::kSortAscending>> - ASMJIT_INLINE NodeT* get(const KeyT& key, const CompareT& cmp = CompareT()) const noexcept { + template<typename KeyT, typename CompareT = Support::Compare<Support::SortOrder::kAscending>> + inline NodeT* get(const KeyT& key, const CompareT& cmp = CompareT()) const noexcept { ZoneTreeNode* node = _root; while (node) { auto result = cmp(*static_cast<const NodeT*>(node), key); @@ -359,9 +344,12 @@ public: static inline bool _isValidRed(ZoneTreeNode* node) noexcept { return ZoneTreeNode::_isValidRed(node); } //! Single rotation. - static ASMJIT_INLINE ZoneTreeNode* _singleRotate(ZoneTreeNode* root, size_t dir) noexcept { + static inline ZoneTreeNode* _singleRotate(ZoneTreeNode* ASMJIT_NONNULL(root), size_t dir) noexcept { ZoneTreeNode* save = root->_getChild(!dir); - root->_setChild(!dir, save->_getChild(dir)); + ASMJIT_ASSUME(save != nullptr); + + ZoneTreeNode* saveChild = save->_getChild(dir); + root->_setChild(!dir, saveChild); save->_setChild( dir, root); root->_makeRed(); save->_makeBlack(); @@ -369,8 +357,11 @@ public: } //! Double rotation. - static ASMJIT_INLINE ZoneTreeNode* _doubleRotate(ZoneTreeNode* root, size_t dir) noexcept { - root->_setChild(!dir, _singleRotate(root->_getChild(!dir), !dir)); + static inline ZoneTreeNode* _doubleRotate(ZoneTreeNode* ASMJIT_NONNULL(root), size_t dir) noexcept { + ZoneTreeNode* child = root->_getChild(!dir); + ASMJIT_ASSUME(child != nullptr); + + root->_setChild(!dir, _singleRotate(child, !dir)); return _singleRotate(root, dir); } |