1// [Blend2D]
2// 2D Vector Graphics Powered by a JIT Compiler.
3//
4// [License]
5// Zlib - See LICENSE.md file in the package.
6
7#include "./blapi-build_p.h"
8#include "./blsupport_p.h"
9#include "./blzoneallocator_p.h"
10#include "./blzonetree_p.h"
11
12// ============================================================================
13// [BLZoneTree - Unit Tests]
14// ============================================================================
15
16#ifdef BL_TEST
17template<typename NodeT>
18struct ZoneTreeUnit {
19 typedef BLZoneTree<NodeT> Tree;
20
21 static void verifyTree(Tree& tree) noexcept {
22 EXPECT(checkHeight(static_cast<NodeT*>(tree._root)) > 0);
23 }
24
25 // Check whether the Red-Black tree is valid.
26 static int checkHeight(NodeT* node) noexcept {
27 if (!node) return 1;
28
29 NodeT* ln = node->left();
30 NodeT* rn = node->right();
31
32 // Invalid tree.
33 EXPECT(ln == nullptr || *ln < *node);
34 EXPECT(rn == nullptr || *rn > *node);
35
36 // Red violation.
37 EXPECT(!node->isRed() ||
38 (!BLZoneTreeNodeBase::_isValidRed(ln) && !BLZoneTreeNodeBase::_isValidRed(rn)));
39
40 // Black violation.
41 int lh = checkHeight(ln);
42 int rh = checkHeight(rn);
43 EXPECT(!lh || !rh || lh == rh);
44
45 // Only count black links.
46 return (lh && rh) ? lh + !node->isRed() : 0;
47 }
48};
49
50class MyTreeNode : public BLZoneTreeNode<MyTreeNode> {
51public:
52 BL_NONCOPYABLE(MyTreeNode)
53
54 BL_INLINE explicit MyTreeNode(uint32_t key) noexcept
55 : _key(key) {}
56
57 BL_INLINE bool operator<(const MyTreeNode& other) const noexcept { return _key < other._key; }
58 BL_INLINE bool operator>(const MyTreeNode& other) const noexcept { return _key > other._key; }
59
60 BL_INLINE bool operator<(uint32_t queryKey) const noexcept { return _key < queryKey; }
61 BL_INLINE bool operator>(uint32_t queryKey) const noexcept { return _key > queryKey; }
62
63 uint32_t _key;
64};
65
66UNIT(blend2d_zone_tree) {
67 constexpr uint32_t kCount = 2000;
68
69 BLZoneAllocator zone(4096);
70 BLZoneTree<MyTreeNode> rbTree;
71
72 uint32_t key;
73 INFO("Inserting %u elements to the tree and validating each operation", unsigned(kCount));
74 for (key = 0; key < kCount; key++) {
75 rbTree.insert(zone.newT<MyTreeNode>(key));
76 ZoneTreeUnit<MyTreeNode>::verifyTree(rbTree);
77 }
78
79 uint32_t count = kCount;
80 INFO("Removing %u elements from the tree and validating each operation", unsigned(kCount));
81 do {
82 MyTreeNode* node;
83
84 for (key = 0; key < count; key++) {
85 node = rbTree.get(key);
86 EXPECT(node != nullptr);
87 EXPECT(node->_key == key);
88 }
89
90 node = rbTree.get(--count);
91 rbTree.remove(node);
92 ZoneTreeUnit<MyTreeNode>::verifyTree(rbTree);
93 } while (count);
94
95 EXPECT(rbTree.empty());
96}
97#endif
98