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