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. |
27 | class BLZoneTreeNodeBase { |
28 | public: |
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 | |
70 | template<typename NodeT> |
71 | class BLZoneTreeNode : public BLZoneTreeNodeBase { |
72 | public: |
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`. |
88 | template<typename NodeT> |
89 | class BLZoneTree { |
90 | public: |
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 | |