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