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 |
17 | template<typename NodeT> |
18 | struct 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 | |
50 | class MyTreeNode : public BLZoneTreeNode<MyTreeNode> { |
51 | public: |
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 | |
66 | UNIT(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 |