blob: 8c42af8c02ff44fcb4140f6a40026716af1355b4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
// 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/zonetree.h"
ASMJIT_BEGIN_NAMESPACE
// ZoneTreeBase - Tests
// ====================
#if defined(ASMJIT_TEST)
template<typename NodeT>
struct ZoneRBUnit {
typedef ZoneTree<NodeT> Tree;
static void verifyTree(Tree& tree) noexcept {
EXPECT(checkHeight(static_cast<NodeT*>(tree._root)) > 0);
}
// Check whether the Red-Black tree is valid.
static int checkHeight(NodeT* node) noexcept {
if (!node) return 1;
NodeT* ln = node->left();
NodeT* rn = node->right();
// Invalid tree.
EXPECT(ln == nullptr || *ln < *node);
EXPECT(rn == nullptr || *rn > *node);
// Red violation.
EXPECT(!node->isRed() ||
(!ZoneTreeNode::_isValidRed(ln) && !ZoneTreeNode::_isValidRed(rn)));
// Black violation.
int lh = checkHeight(ln);
int rh = checkHeight(rn);
EXPECT(!lh || !rh || lh == rh);
// Only count black links.
return (lh && rh) ? lh + !node->isRed() : 0;
}
};
class MyRBNode : public ZoneTreeNodeT<MyRBNode> {
public:
ASMJIT_NONCOPYABLE(MyRBNode)
inline explicit MyRBNode(uint32_t key) noexcept
: _key(key) {}
inline bool operator<(const MyRBNode& other) const noexcept { return _key < other._key; }
inline bool operator>(const MyRBNode& other) const noexcept { return _key > other._key; }
inline bool operator<(uint32_t queryKey) const noexcept { return _key < queryKey; }
inline bool operator>(uint32_t queryKey) const noexcept { return _key > queryKey; }
uint32_t _key;
};
UNIT(zone_rbtree) {
uint32_t kCount = BrokenAPI::hasArg("--quick") ? 1000 : 10000;
Zone zone(4096);
ZoneTree<MyRBNode> rbTree;
uint32_t key;
INFO("Inserting %u elements to RBTree and validating each operation", unsigned(kCount));
for (key = 0; key < kCount; key++) {
rbTree.insert(zone.newT<MyRBNode>(key));
ZoneRBUnit<MyRBNode>::verifyTree(rbTree);
}
uint32_t count = kCount;
INFO("Removing %u elements from RBTree and validating each operation", unsigned(kCount));
do {
MyRBNode* node;
for (key = 0; key < count; key++) {
node = rbTree.get(key);
EXPECT(node != nullptr);
EXPECT(node->_key == key);
}
node = rbTree.get(--count);
rbTree.remove(node);
ZoneRBUnit<MyRBNode>::verifyTree(rbTree);
} while (count);
EXPECT(rbTree.empty());
}
#endif
ASMJIT_END_NAMESPACE
|
