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
56QT_BEGIN_NAMESPACE
57
58template <class T>
59struct QRBTree
60{
61 struct Node
62 {
63 inline Node() : parent(nullptr), left(nullptr), right(nullptr), red(true) { }
64 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
72 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
93private:
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
110public:
111 Node *root;
112private:
113 Node *freeList;
114};
115
116template <class T>
117inline 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
129template <class T>
130inline void QRBTree<T>::clear()
131{
132 if (root)
133 delete root;
134 root = nullptr;
135}
136
137template <class T>
138void 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
178template <class T>
179void 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
200template <class T>
201void 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
252template <class T>
253inline 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
261template <class T>
262inline 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
270template <class T>
271void 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
283template <class T>
284void 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
296template <class T>
297void 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
343template <class T>
344void 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.
366template <class T>
367void 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
441template <class T>
442inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
443{
444 while (node->left)
445 node = node->left;
446 return node;
447}
448
449template <class T>
450inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
451{
452 while (node->right)
453 node = node->right;
454 return node;
455}
456
457template <class T>
458typename 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
467template <class T>
468typename 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
477template <class T>
478int 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
491template <class T>
492bool 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
503template <class T>
504inline bool QRBTree<T>::validate() const
505{
506 return checkRedBlackProperty(root) && blackDepth(root) != -1;
507}
508
509template <class T>
510inline 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
519template <class T>
520inline 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.
534template <class T>
535int QRBTree<T>::order(Node *left, Node *right)
536{
537 Q_ASSERT(left && right);
538 if (left == right)
539 return 0;
540
541 QList<Node *> leftAncestors;
542 QList<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
569QT_END_NAMESPACE
570
571#endif
572