1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QRBTREE_P_H
5#define QRBTREE_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtGui/private/qtguiglobal_p.h>
19
20QT_BEGIN_NAMESPACE
21
22template <class T>
23struct QRBTree
24{
25 struct Node
26 {
27 inline Node() : parent(nullptr), left(nullptr), right(nullptr), red(true) { }
28 inline ~Node() {if (left) delete left; if (right) delete right;}
29 T data;
30 Node *parent;
31 Node *left;
32 Node *right;
33 bool red;
34 };
35
36 inline QRBTree() : root(nullptr), freeList(nullptr) { }
37 inline ~QRBTree();
38
39 inline void clear();
40
41 void attachBefore(Node *parent, Node *child);
42 void attachAfter(Node *parent, Node *child);
43
44 inline Node *front(Node *node) const;
45 inline Node *back(Node *node) const;
46 Node *next(Node *node) const;
47 Node *previous(Node *node) const;
48
49 inline void deleteNode(Node *&node);
50 inline Node *newNode();
51
52 // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
53 // 'left' and 'right' cannot be null.
54 int order(Node *left, Node *right);
55 inline bool validate() const;
56
57private:
58 void rotateLeft(Node *node);
59 void rotateRight(Node *node);
60 void update(Node *node);
61
62 inline void attachLeft(Node *parent, Node *child);
63 inline void attachRight(Node *parent, Node *child);
64
65 int blackDepth(Node *top) const;
66 bool checkRedBlackProperty(Node *top) const;
67
68 void swapNodes(Node *n1, Node *n2);
69 void detach(Node *node);
70
71 // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
72 void rebalance(Node *node);
73
74public:
75 Node *root;
76private:
77 Node *freeList;
78};
79
80template <class T>
81inline QRBTree<T>::~QRBTree()
82{
83 clear();
84 while (freeList) {
85 // Avoid recursively calling the destructor, as this list may become large.
86 Node *next = freeList->right;
87 freeList->right = nullptr;
88 delete freeList;
89 freeList = next;
90 }
91}
92
93template <class T>
94inline void QRBTree<T>::clear()
95{
96 if (root)
97 delete root;
98 root = nullptr;
99}
100
101template <class T>
102void QRBTree<T>::rotateLeft(Node *node)
103{
104 // | | //
105 // N B //
106 // / \ / \ //
107 // A B ---> N D //
108 // / \ / \ //
109 // C D A C //
110
111 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
112 ref = node->right;
113 node->right->parent = node->parent;
114
115 // : //
116 // N //
117 // / :| //
118 // A B //
119 // / \ //
120 // C D //
121
122 node->right = ref->left;
123 if (ref->left)
124 ref->left->parent = node;
125
126 // : | //
127 // N B //
128 // / \ : \ //
129 // A C D //
130
131 ref->left = node;
132 node->parent = ref;
133
134 // | //
135 // B //
136 // / \ //
137 // N D //
138 // / \ //
139 // A C //
140}
141
142template <class T>
143void QRBTree<T>::rotateRight(Node *node)
144{
145 // | | //
146 // N A //
147 // / \ / \ //
148 // A B ---> C N //
149 // / \ / \ //
150 // C D D B //
151
152 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
153 ref = node->left;
154 node->left->parent = node->parent;
155
156 node->left = ref->right;
157 if (ref->right)
158 ref->right->parent = node;
159
160 ref->right = node;
161 node->parent = ref;
162}
163
164template <class T>
165void QRBTree<T>::update(Node *node) // call this after inserting a node
166{
167 for (;;) {
168 Node *parent = node->parent;
169
170 // if the node is the root, color it black
171 if (!parent) {
172 node->red = false;
173 return;
174 }
175
176 // if the parent is black, the node can be left red
177 if (!parent->red)
178 return;
179
180 // at this point, the parent is red and cannot be the root
181 Node *grandpa = parent->parent;
182 Q_ASSERT(grandpa);
183
184 Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
185 if (uncle && uncle->red) {
186 // grandpa's black, parent and uncle are red.
187 // let parent and uncle be black, grandpa red and recursively update grandpa.
188 Q_ASSERT(!grandpa->red);
189 parent->red = false;
190 uncle->red = false;
191 grandpa->red = true;
192 node = grandpa;
193 continue;
194 }
195
196 // at this point, uncle is black
197 if (node == parent->right && parent == grandpa->left)
198 rotateLeft(node: node = parent);
199 else if (node == parent->left && parent == grandpa->right)
200 rotateRight(node: node = parent);
201 parent = node->parent;
202
203 if (parent == grandpa->left) {
204 rotateRight(node: grandpa);
205 parent->red = false;
206 grandpa->red = true;
207 } else {
208 rotateLeft(node: grandpa);
209 parent->red = false;
210 grandpa->red = true;
211 }
212 return;
213 }
214}
215
216template <class T>
217inline void QRBTree<T>::attachLeft(Node *parent, Node *child)
218{
219 Q_ASSERT(!parent->left);
220 parent->left = child;
221 child->parent = parent;
222 update(node: child);
223}
224
225template <class T>
226inline void QRBTree<T>::attachRight(Node *parent, Node *child)
227{
228 Q_ASSERT(!parent->right);
229 parent->right = child;
230 child->parent = parent;
231 update(node: child);
232}
233
234template <class T>
235void QRBTree<T>::attachBefore(Node *parent, Node *child)
236{
237 if (!root)
238 update(node: root = child);
239 else if (!parent)
240 attachRight(parent: back(node: root), child);
241 else if (parent->left)
242 attachRight(parent: back(node: parent->left), child);
243 else
244 attachLeft(parent, child);
245}
246
247template <class T>
248void QRBTree<T>::attachAfter(Node *parent, Node *child)
249{
250 if (!root)
251 update(node: root = child);
252 else if (!parent)
253 attachLeft(parent: front(node: root), child);
254 else if (parent->right)
255 attachLeft(parent: front(node: parent->right), child);
256 else
257 attachRight(parent, child);
258}
259
260template <class T>
261void QRBTree<T>::swapNodes(Node *n1, Node *n2)
262{
263 // Since iterators must not be invalidated, it is not sufficient to only swap the data.
264 if (n1->parent == n2) {
265 n1->parent = n2->parent;
266 n2->parent = n1;
267 } else if (n2->parent == n1) {
268 n2->parent = n1->parent;
269 n1->parent = n2;
270 } else {
271 qSwap(n1->parent, n2->parent);
272 }
273
274 qSwap(n1->left, n2->left);
275 qSwap(n1->right, n2->right);
276 qSwap(n1->red, n2->red);
277
278 if (n1->parent) {
279 if (n1->parent->left == n2)
280 n1->parent->left = n1;
281 else
282 n1->parent->right = n1;
283 } else {
284 root = n1;
285 }
286
287 if (n2->parent) {
288 if (n2->parent->left == n1)
289 n2->parent->left = n2;
290 else
291 n2->parent->right = n2;
292 } else {
293 root = n2;
294 }
295
296 if (n1->left)
297 n1->left->parent = n1;
298 if (n1->right)
299 n1->right->parent = n1;
300
301 if (n2->left)
302 n2->left->parent = n2;
303 if (n2->right)
304 n2->right->parent = n2;
305}
306
307template <class T>
308void QRBTree<T>::detach(Node *node) // call this before removing a node.
309{
310 if (node->right)
311 swapNodes(n1: node, n2: front(node: node->right));
312
313 Node *child = (node->left ? node->left : node->right);
314
315 if (!node->red) {
316 if (child && child->red)
317 child->red = false;
318 else
319 rebalance(node);
320 }
321
322 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
323 ref = child;
324 if (child)
325 child->parent = node->parent;
326 node->left = node->right = node->parent = nullptr;
327}
328
329// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
330template <class T>
331void QRBTree<T>::rebalance(Node *node)
332{
333 Q_ASSERT(!node->red);
334 for (;;) {
335 if (!node->parent)
336 return;
337
338 // at this point, node is not a parent, it is black, thus it must have a sibling.
339 Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
340 Q_ASSERT(sibling);
341
342 if (sibling->red) {
343 sibling->red = false;
344 node->parent->red = true;
345 if (node == node->parent->left)
346 rotateLeft(node: node->parent);
347 else
348 rotateRight(node: node->parent);
349 sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
350 Q_ASSERT(sibling);
351 }
352
353 // at this point, the sibling is black.
354 Q_ASSERT(!sibling->red);
355
356 if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
357 bool parentWasRed = node->parent->red;
358 sibling->red = true;
359 node->parent->red = false;
360 if (parentWasRed)
361 return;
362 node = node->parent;
363 continue;
364 }
365
366 // at this point, at least one of the sibling's children is red.
367
368 if (node == node->parent->left) {
369 if (!sibling->right || !sibling->right->red) {
370 Q_ASSERT(sibling->left);
371 sibling->red = true;
372 sibling->left->red = false;
373 rotateRight(node: sibling);
374
375 sibling = sibling->parent;
376 Q_ASSERT(sibling);
377 }
378 sibling->red = node->parent->red;
379 node->parent->red = false;
380
381 Q_ASSERT(sibling->right->red);
382 sibling->right->red = false;
383 rotateLeft(node: node->parent);
384 } else {
385 if (!sibling->left || !sibling->left->red) {
386 Q_ASSERT(sibling->right);
387 sibling->red = true;
388 sibling->right->red = false;
389 rotateLeft(node: sibling);
390
391 sibling = sibling->parent;
392 Q_ASSERT(sibling);
393 }
394 sibling->red = node->parent->red;
395 node->parent->red = false;
396
397 Q_ASSERT(sibling->left->red);
398 sibling->left->red = false;
399 rotateRight(node: node->parent);
400 }
401 return;
402 }
403}
404
405template <class T>
406inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
407{
408 while (node->left)
409 node = node->left;
410 return node;
411}
412
413template <class T>
414inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
415{
416 while (node->right)
417 node = node->right;
418 return node;
419}
420
421template <class T>
422typename QRBTree<T>::Node *QRBTree<T>::next(Node *node) const
423{
424 if (node->right)
425 return front(node: node->right);
426 while (node->parent && node == node->parent->right)
427 node = node->parent;
428 return node->parent;
429}
430
431template <class T>
432typename QRBTree<T>::Node *QRBTree<T>::previous(Node *node) const
433{
434 if (node->left)
435 return back(node: node->left);
436 while (node->parent && node == node->parent->left)
437 node = node->parent;
438 return node->parent;
439}
440
441template <class T>
442int QRBTree<T>::blackDepth(Node *top) const
443{
444 if (!top)
445 return 0;
446 int leftDepth = blackDepth(top: top->left);
447 int rightDepth = blackDepth(top: top->right);
448 if (leftDepth != rightDepth)
449 return -1;
450 if (!top->red)
451 ++leftDepth;
452 return leftDepth;
453}
454
455template <class T>
456bool QRBTree<T>::checkRedBlackProperty(Node *top) const
457{
458 if (!top)
459 return true;
460 if (top->left && !checkRedBlackProperty(top: top->left))
461 return false;
462 if (top->right && !checkRedBlackProperty(top: top->right))
463 return false;
464 return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
465}
466
467template <class T>
468inline bool QRBTree<T>::validate() const
469{
470 return checkRedBlackProperty(top: root) && blackDepth(top: root) != -1;
471}
472
473template <class T>
474inline void QRBTree<T>::deleteNode(Node *&node)
475{
476 Q_ASSERT(node);
477 detach(node);
478 node->right = freeList;
479 freeList = node;
480 node = nullptr;
481}
482
483template <class T>
484inline typename QRBTree<T>::Node *QRBTree<T>::newNode()
485{
486 if (freeList) {
487 Node *node = freeList;
488 freeList = freeList->right;
489 node->parent = node->left = node->right = nullptr;
490 node->red = true;
491 return node;
492 }
493 return new Node;
494}
495
496// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
497// 'left' and 'right' cannot be null.
498template <class T>
499int QRBTree<T>::order(Node *left, Node *right)
500{
501 Q_ASSERT(left && right);
502 if (left == right)
503 return 0;
504
505 QList<Node *> leftAncestors;
506 QList<Node *> rightAncestors;
507 while (left) {
508 leftAncestors.push_back(left);
509 left = left->parent;
510 }
511 while (right) {
512 rightAncestors.push_back(right);
513 right = right->parent;
514 }
515 Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
516
517 while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
518 leftAncestors.pop_back();
519 rightAncestors.pop_back();
520 }
521
522 if (!leftAncestors.empty())
523 return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
524
525 if (!rightAncestors.empty())
526 return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
527
528 // The code should never reach this point.
529 Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
530 return 0;
531}
532
533QT_END_NAMESPACE
534
535#endif
536

source code of qtbase/src/gui/painting/qrbtree_p.h