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#ifndef BLEND2D_BLZONETREE_P_H
8#define BLEND2D_BLZONETREE_P_H
9
10#include "./blapi-internal_p.h"
11#include "./blarrayops_p.h"
12#include "./blsupport_p.h"
13
14//! \cond INTERNAL
15//! \addtogroup blend2d_internal
16//! \{
17
18// ============================================================================
19// [BLZoneTreeNodeBase]
20// ============================================================================
21
22//! Tree node.
23//!
24//! The color is stored in a least significant bit of the `left` node.
25//!
26//! \warning Always use accessors to access left and right nodes.
27class BLZoneTreeNodeBase {
28public:
29 BL_NONCOPYABLE(BLZoneTreeNodeBase)
30
31 static constexpr const uintptr_t kRedMask = 0x1;
32 static constexpr const uintptr_t kPtrMask = ~kRedMask;
33
34 uintptr_t _treeNodes[2];
35
36 BL_INLINE BLZoneTreeNodeBase() noexcept
37 : _treeNodes { 0, 0 } {}
38
39 // --------------------------------------------------------------------------
40 // [Accessors]
41 // --------------------------------------------------------------------------
42
43 BL_INLINE bool hasChild(size_t i) const noexcept { return _treeNodes[i] > kRedMask; }
44 BL_INLINE bool hasLeft() const noexcept { return _treeNodes[0] > kRedMask; }
45 BL_INLINE bool hasRight() const noexcept { return _treeNodes[1] != 0; }
46
47 BL_INLINE BLZoneTreeNodeBase* _getChild(size_t i) const noexcept { return (BLZoneTreeNodeBase*)(_treeNodes[i] & kPtrMask); }
48 BL_INLINE BLZoneTreeNodeBase* _getLeft() const noexcept { return (BLZoneTreeNodeBase*)(_treeNodes[0] & kPtrMask); }
49 BL_INLINE BLZoneTreeNodeBase* _getRight() const noexcept { return (BLZoneTreeNodeBase*)(_treeNodes[1]); }
50
51 BL_INLINE void _setChild(size_t i, BLZoneTreeNodeBase* node) noexcept { _treeNodes[i] = (_treeNodes[i] & kRedMask) | (uintptr_t)node; }
52 BL_INLINE void _setLeft(BLZoneTreeNodeBase* node) noexcept { _treeNodes[0] = (_treeNodes[0] & kRedMask) | (uintptr_t)node; }
53 BL_INLINE void _setRight(BLZoneTreeNodeBase* node) noexcept { _treeNodes[1] = (uintptr_t)node; }
54
55 template<typename T = BLZoneTreeNodeBase>
56 BL_INLINE T* child(size_t i) const noexcept { return static_cast<T*>(_getChild(i)); }
57 template<typename T = BLZoneTreeNodeBase>
58 BL_INLINE T* left() const noexcept { return static_cast<T*>(_getLeft()); }
59 template<typename T = BLZoneTreeNodeBase>
60 BL_INLINE T* right() const noexcept { return static_cast<T*>(_getRight()); }
61
62 BL_INLINE bool isRed() const noexcept { return static_cast<bool>(_treeNodes[0] & kRedMask); }
63 BL_INLINE void _makeRed() noexcept { _treeNodes[0] |= kRedMask; }
64 BL_INLINE void _makeBlack() noexcept { _treeNodes[0] &= kPtrMask; }
65
66 //! Tests whether the node is RED (RED node must be non-null and must have RED flag set).
67 static BL_INLINE bool _isValidRed(BLZoneTreeNodeBase* node) noexcept { return node && node->isRed(); }
68};
69
70template<typename NodeT>
71class BLZoneTreeNode : public BLZoneTreeNodeBase {
72public:
73 BL_NONCOPYABLE(BLZoneTreeNode)
74
75 BL_INLINE BLZoneTreeNode() noexcept
76 : BLZoneTreeNodeBase() {}
77
78 BL_INLINE NodeT* child(size_t i) const noexcept { return static_cast<NodeT*>(_getChild(i)); }
79 BL_INLINE NodeT* left() const noexcept { return static_cast<NodeT*>(_getLeft()); }
80 BL_INLINE NodeT* right() const noexcept { return static_cast<NodeT*>(_getRight()); }
81};
82
83// ============================================================================
84// [BLZoneTree]
85// ============================================================================
86
87//! A red-black tree that uses nodes allocated by `BLZoneAllocator`.
88template<typename NodeT>
89class BLZoneTree {
90public:
91 BL_NONCOPYABLE(BLZoneTree)
92
93 typedef NodeT Node;
94 NodeT* _root;
95
96 // --------------------------------------------------------------------------
97 // [Construction / Destruction]
98 // --------------------------------------------------------------------------
99
100 BL_INLINE BLZoneTree() noexcept
101 : _root(nullptr) {}
102
103 BL_INLINE BLZoneTree(BLZoneTree&& other) noexcept
104 : _root(other._root) {}
105
106 // --------------------------------------------------------------------------
107 // [Swap]
108 // --------------------------------------------------------------------------
109
110 BL_INLINE void swap(BLZoneTree& other) noexcept {
111 std::swap(_root, other._root);
112 }
113
114 // --------------------------------------------------------------------------
115 // [Accessors]
116 // --------------------------------------------------------------------------
117
118 BL_INLINE bool empty() const noexcept { return _root == nullptr; }
119 BL_INLINE NodeT* root() const noexcept { return static_cast<NodeT*>(_root); }
120
121 // --------------------------------------------------------------------------
122 // [Reset]
123 // --------------------------------------------------------------------------
124
125 BL_INLINE void reset() noexcept { _root = nullptr; }
126
127 // --------------------------------------------------------------------------
128 // [Operations]
129 // --------------------------------------------------------------------------
130
131 //! Insert a node into the tree.
132 template<typename CompareT = BLCompare<BL_SORT_ORDER_ASCENDING>>
133 void insert(NodeT* node, const CompareT& cmp = CompareT()) noexcept {
134 // Node to insert must not contain garbage.
135 BL_ASSERT(!node->hasLeft());
136 BL_ASSERT(!node->hasRight());
137 BL_ASSERT(!node->isRed());
138
139 if (!_root) {
140 _root = node;
141 return;
142 }
143
144 BLZoneTreeNodeBase head; // False root node,
145 head._setRight(_root); // having root on the right.
146
147 BLZoneTreeNodeBase* g = nullptr; // Grandparent.
148 BLZoneTreeNodeBase* p = nullptr; // Parent.
149 BLZoneTreeNodeBase* t = &head; // Iterator.
150 BLZoneTreeNodeBase* q = _root; // Query.
151
152 size_t dir = 0; // Direction for accessing child nodes.
153 size_t last = 0; // Not needed to initialize, but makes some tools happy.
154 node->_makeRed(); // New nodes are always red and violations fixed appropriately.
155
156 // Search down the tree.
157 for (;;) {
158 if (!q) {
159 // Insert new node at the bottom.
160 q = node;
161 p->_setChild(dir, node);
162 }
163 else if (_isValidRed(q->_getLeft()) && _isValidRed(q->_getRight())) {
164 // Color flip.
165 q->_makeRed();
166 q->_getLeft()->_makeBlack();
167 q->_getRight()->_makeBlack();
168 }
169
170 // Fix red violation.
171 if (_isValidRed(q) && _isValidRed(p))
172 t->_setChild(t->_getRight() == g,
173 q == p->_getChild(last) ? _singleRotate(g, !last) : _doubleRotate(g, !last));
174
175 // Stop if found.
176 if (q == node)
177 break;
178
179 last = dir;
180 dir = cmp(*static_cast<NodeT*>(q), *static_cast<NodeT*>(node)) < 0;
181
182 // Update helpers.
183 if (g) t = g;
184
185 g = p;
186 p = q;
187 q = q->_getChild(dir);
188 }
189
190 // Update root and make it black.
191 _root = static_cast<NodeT*>(head._getRight());
192 _root->_makeBlack();
193 }
194
195 //! Remove a node from the tree.
196 template<typename CompareT = BLCompare<BL_SORT_ORDER_ASCENDING>>
197 void remove(BLZoneTreeNodeBase* node, const CompareT& cmp = CompareT()) noexcept {
198 BLZoneTreeNodeBase head; // False root node,
199 head._setRight(_root); // having root on the right.
200
201 BLZoneTreeNodeBase* g = nullptr; // Grandparent.
202 BLZoneTreeNodeBase* p = nullptr; // Parent.
203 BLZoneTreeNodeBase* q = &head; // Query.
204
205 BLZoneTreeNodeBase* f = nullptr; // Found item.
206 BLZoneTreeNodeBase* gf = nullptr; // Found grandparent.
207 size_t dir = 1; // Direction (0 or 1).
208
209 // Search and push a red down.
210 while (q->hasChild(dir)) {
211 size_t last = dir;
212
213 // Update helpers.
214 g = p;
215 p = q;
216 q = q->_getChild(dir);
217 dir = cmp(*static_cast<NodeT*>(q), *static_cast<NodeT*>(node)) < 0;
218
219 // Save found node.
220 if (q == node) {
221 f = q;
222 gf = g;
223 }
224
225 // Push the red node down.
226 if (!_isValidRed(q) && !_isValidRed(q->_getChild(dir))) {
227 if (_isValidRed(q->_getChild(!dir))) {
228 BLZoneTreeNodeBase* child = _singleRotate(q, dir);
229 p->_setChild(last, child);
230 p = child;
231 }
232 else if (!_isValidRed(q->_getChild(!dir)) && p->_getChild(!last)) {
233 BLZoneTreeNodeBase* s = p->_getChild(!last);
234 if (!_isValidRed(s->_getChild(!last)) && !_isValidRed(s->_getChild(last))) {
235 // Color flip.
236 p->_makeBlack();
237 s->_makeRed();
238 q->_makeRed();
239 }
240 else {
241 size_t dir2 = g->_getRight() == p;
242 BLZoneTreeNodeBase* child = g->_getChild(dir2);
243
244 if (_isValidRed(s->_getChild(last))) {
245 child = _doubleRotate(p, last);
246 g->_setChild(dir2, child);
247 }
248 else if (_isValidRed(s->_getChild(!last))) {
249 child = _singleRotate(p, last);
250 g->_setChild(dir2, child);
251 }
252
253 // Ensure correct coloring.
254 q->_makeRed();
255 child->_makeRed();
256 child->_getLeft()->_makeBlack();
257 child->_getRight()->_makeBlack();
258 }
259 }
260 }
261 }
262
263 // Replace and remove.
264 BL_ASSERT(f != nullptr);
265 BL_ASSERT(f != &head);
266 BL_ASSERT(q != &head);
267
268 p->_setChild(p->_getRight() == q,
269 q->_getChild(q->_getLeft() == nullptr));
270
271 // NOTE: The original algorithm used a trick to just copy 'key/value' to
272 // `f` and mark `q` for deletion. But this is unacceptable here as we
273 // really want to destroy the passed `node`. So, we have to make sure that
274 // we have really removed `f` and not `q`.
275 if (f != q) {
276 BL_ASSERT(f != &head);
277 BL_ASSERT(f != gf);
278
279 BLZoneTreeNodeBase* n = gf ? gf : &head;
280 dir = (n == &head) ? 1 : cmp(*static_cast<NodeT*>(n), *static_cast<NodeT*>(node)) < 0;
281
282 for (;;) {
283 if (n->_getChild(dir) == f) {
284 n->_setChild(dir, q);
285 // RAW copy, including the color.
286 q->_treeNodes[0] = f->_treeNodes[0];
287 q->_treeNodes[1] = f->_treeNodes[1];
288 break;
289 }
290
291 n = n->_getChild(dir);
292
293 // Cannot be true as we know that it must reach `f` in few iterations.
294 BL_ASSERT(n != nullptr);
295 dir = cmp(*static_cast<NodeT*>(n), *static_cast<NodeT*>(node)) < 0;
296 }
297 }
298
299 // Update root and make it black.
300 _root = static_cast<NodeT*>(head._getRight());
301 if (_root) _root->_makeBlack();
302 }
303
304 template<typename KeyT, typename CompareT = BLCompare<BL_SORT_ORDER_ASCENDING>>
305 BL_INLINE NodeT* get(const KeyT& key, const CompareT& cmp = CompareT()) const noexcept {
306 BLZoneTreeNodeBase* node = _root;
307 while (node) {
308 auto result = cmp(*static_cast<const NodeT*>(node), key);
309 if (result == 0) break;
310
311 // Go left or right depending on the `result`.
312 node = node->_getChild(result < 0);
313 }
314 return static_cast<NodeT*>(node);
315 }
316
317 // --------------------------------------------------------------------------
318 // [Internal]
319 // --------------------------------------------------------------------------
320
321 static BL_INLINE bool _isValidRed(BLZoneTreeNodeBase* node) noexcept { return BLZoneTreeNodeBase::_isValidRed(node); }
322
323 //! Single rotation.
324 static BL_INLINE BLZoneTreeNodeBase* _singleRotate(BLZoneTreeNodeBase* root, size_t dir) noexcept {
325 BLZoneTreeNodeBase* save = root->_getChild(!dir);
326 root->_setChild(!dir, save->_getChild(dir));
327 save->_setChild( dir, root);
328 root->_makeRed();
329 save->_makeBlack();
330 return save;
331 }
332
333 //! Double rotation.
334 static BL_INLINE BLZoneTreeNodeBase* _doubleRotate(BLZoneTreeNodeBase* root, size_t dir) noexcept {
335 root->_setChild(!dir, _singleRotate(root->_getChild(!dir), !dir));
336 return _singleRotate(root, dir);
337 }
338};
339
340//! \}
341//! \endcond
342
343#endif // BLEND2D_BLZONETREE_P_H
344