Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qmap.cpp

Source at commit 1406 created 12 years 10 months ago.
By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too.
1/****************************************************************************␊
2** ␊
3**␊
4** Implementation of QMap␊
5**␊
6** Created : 990406␊
7**␊
8** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.␊
9**␊
10** This file is part of the tools module of the Qt GUI Toolkit.␊
11**␊
12** This file may be distributed under the terms of the Q Public License␊
13** as defined by Trolltech AS of Norway and appearing in the file␊
14** LICENSE.QPL included in the packaging of this file.␊
15**␊
16** This file may be distributed and/or modified under the terms of the␊
17** GNU General Public License version 2 as published by the Free Software␊
18** Foundation and appearing in the file LICENSE.GPL included in the␊
19** packaging of this file.␊
20**␊
21** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition␊
22** licenses may use this file in accordance with the Qt Commercial License␊
23** Agreement provided with the Software.␊
24**␊
25** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE␊
26** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.␊
27**␊
28** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for␊
29** information about Qt Commercial License Agreements.␊
30** See http://www.trolltech.com/qpl/ for QPL licensing information.␊
31** See http://www.trolltech.com/gpl/ for GPL licensing information.␊
32**␊
33** Contact info@trolltech.com if any conditions of this licensing are␊
34** not clear to you.␊
35**␊
36**********************************************************************/␊
37␊
38#include "qmap.h"␊
39␊
40typedef QMapNodeBase* NodePtr;␊
41typedef QMapNodeBase Node;␊
42␊
43␊
44void QMapPrivateBase::rotateLeft( NodePtr x, NodePtr& root)␊
45{␊
46 NodePtr y = x->right;␊
47 x->right = y->left;␊
48 if (y->left !=0)␊
49␉y->left->parent = x;␊
50 y->parent = x->parent;␊
51 if (x == root)␊
52␉root = y;␊
53 else if (x == x->parent->left)␊
54␉x->parent->left = y;␊
55 else␊
56␉x->parent->right = y;␊
57 y->left = x;␊
58 x->parent = y;␊
59}␊
60␊
61␊
62void QMapPrivateBase::rotateRight( NodePtr x, NodePtr& root )␊
63{␊
64 NodePtr y = x->left;␊
65 x->left = y->right;␊
66 if (y->right != 0)␊
67␉y->right->parent = x;␊
68 y->parent = x->parent;␊
69 if (x == root)␊
70␉root = y;␊
71 else if (x == x->parent->right)␊
72␉x->parent->right = y;␊
73 else␊
74␉x->parent->left = y;␊
75 y->right = x;␊
76 x->parent = y;␊
77}␊
78␊
79␊
80void QMapPrivateBase::rebalance( NodePtr x, NodePtr& root)␊
81{␊
82 x->color = Node::Red;␊
83 while ( x != root && x->parent->color == Node::Red ) {␊
84␉if ( x->parent == x->parent->parent->left ) {␊
85␉ NodePtr y = x->parent->parent->right;␊
86␉ if (y && y->color == Node::Red) {␊
87␉␉x->parent->color = Node::Black;␊
88␉␉y->color = Node::Black;␊
89␉␉x->parent->parent->color = Node::Red;␊
90␉␉x = x->parent->parent;␊
91␉ } else {␊
92␉␉if (x == x->parent->right) {␊
93␉␉ x = x->parent;␊
94␉␉ rotateLeft( x, root );␊
95␉␉}␊
96␉␉x->parent->color = Node::Black;␊
97␉␉x->parent->parent->color = Node::Red;␊
98␉␉rotateRight (x->parent->parent, root );␊
99␉ }␊
100␉} else {␊
101␉ NodePtr y = x->parent->parent->left;␊
102␉ if ( y && y->color == Node::Red ) {␊
103␉␉x->parent->color = Node::Black;␊
104␉␉y->color = Node::Black;␊
105␉␉x->parent->parent->color = Node::Red;␊
106␉␉x = x->parent->parent;␊
107␉ } else {␊
108␉␉if (x == x->parent->left) { ␊
109␉␉ x = x->parent;␊
110␉␉ rotateRight( x, root );␊
111␉␉}␊
112␉␉x->parent->color = Node::Black;␊
113␉␉x->parent->parent->color = Node::Red;␊
114␉␉rotateLeft( x->parent->parent, root );␊
115␉ }␊
116␉}␊
117 }␊
118 root->color = Node::Black;␊
119}␊
120␊
121␊
122NodePtr QMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,␊
123␉␉␉␉␉ NodePtr& leftmost,␊
124␉␉␉␉␉ NodePtr& rightmost )␊
125{␊
126 NodePtr y = z;␊
127 NodePtr x;␊
128 NodePtr x_parent;␊
129 if (y->left == 0) {␊
130␉x = y->right;␊
131 } else {␊
132␉if (y->right == 0)␊
133␉ x = y->left;␊
134␉else␊
135␉ {␊
136␉␉y = y->right;␊
137␉␉while (y->left != 0)␊
138␉␉ y = y->left;␊
139␉␉x = y->right;␊
140␉ }␊
141 }␊
142 if (y != z) {␊
143␉z->left->parent = y; ␊
144␉y->left = z->left;␊
145␉if (y != z->right) {␊
146␉ x_parent = y->parent;␊
147␉ if (x)␊
148␉␉x->parent = y->parent;␊
149␉ y->parent->left = x;␊
150␉ y->right = z->right;␊
151␉ z->right->parent = y;␊
152␉} else {␊
153␉ x_parent = y; ␊
154␉}␊
155␉if (root == z)␊
156␉ root = y;␊
157␉else if (z->parent->left == z)␊
158␉ z->parent->left = y;␊
159␉else ␊
160␉ z->parent->right = y;␊
161␉y->parent = z->parent;␊
162␉// Swap the colors␊
163␉Node::Color c = y->color;␊
164␉y->color = z->color;␊
165␉z->color = c;␊
166␉y = z;␊
167 } else { ␊
168␉x_parent = y->parent;␊
169␉if (x)␊
170␉ x->parent = y->parent; ␊
171␉if (root == z)␊
172␉ root = x;␊
173␉else if (z->parent->left == z)␊
174␉ z->parent->left = x;␊
175␉else␊
176␉ z->parent->right = x;␊
177␉if ( leftmost == z ) {␊
178␉ if (z->right == 0)␊
179␉␉leftmost = z->parent;␊
180␉ else␊
181␉␉leftmost = x->minimum();␊
182␉}␊
183␉if (rightmost == z) {␊
184␉ if (z->left == 0)␊
185␉␉rightmost = z->parent; ␊
186␉ else␊
187␉␉rightmost = x->maximum();␊
188␉}␊
189 }␊
190 if (y->color != Node::Red) { ␊
191␉while (x != root && (x == 0 || x->color == Node::Black)) {␊
192␉ if (x == x_parent->left) {␊
193␉␉NodePtr w = x_parent->right;␊
194␉␉if (w->color == Node::Red) {␊
195␉␉ w->color = Node::Black;␊
196␉␉ x_parent->color = Node::Red;␊
197␉␉ rotateLeft(x_parent, root);␊
198␉␉ w = x_parent->right;␊
199␉␉}␊
200␉␉if ((w->left == 0 || w->left->color == Node::Black) &&␊
201␉␉ (w->right == 0 || w->right->color == Node::Black)) {␊
202␉␉ w->color = Node::Red;␊
203␉␉ x = x_parent;␊
204␉␉ x_parent = x_parent->parent;␊
205␉␉} else {␊
206␉␉ if (w->right == 0 || w->right->color == Node::Black) {␊
207␉␉␉if (w->left)␊
208␉␉␉ w->left->color = Node::Black;␊
209␉␉␉w->color = Node::Red;␊
210␉␉␉rotateRight(w, root);␊
211␉␉␉w = x_parent->right;␊
212␉␉ }␊
213␉␉ w->color = x_parent->color;␊
214␉␉ x_parent->color = Node::Black;␊
215␉␉ if (w->right)␊
216␉␉␉w->right->color = Node::Black;␊
217␉␉ rotateLeft(x_parent, root);␊
218␉␉ break;␊
219␉␉}␊
220␉ } else {␊
221␉␉NodePtr w = x_parent->left;␊
222␉␉if (w->color == Node::Red) {␊
223␉␉ w->color = Node::Black;␊
224␉␉ x_parent->color = Node::Red;␊
225␉␉ rotateRight(x_parent, root);␊
226␉␉ w = x_parent->left;␊
227␉␉}␊
228␉␉if ((w->right == 0 || w->right->color == Node::Black) &&␊
229␉␉ (w->left == 0 || w->left->color == Node::Black)) {␊
230␉␉ w->color = Node::Red;␊
231␉␉ x = x_parent;␊
232␉␉ x_parent = x_parent->parent;␊
233␉␉} else {␊
234␉␉ if (w->left == 0 || w->left->color == Node::Black) {␊
235␉␉␉if (w->right) ␊
236␉␉␉ w->right->color = Node::Black;␊
237␉␉␉w->color = Node::Red;␊
238␉␉␉rotateLeft(w, root);␊
239␉␉␉w = x_parent->left;␊
240␉␉ }␊
241␉␉ w->color = x_parent->color;␊
242␉␉ x_parent->color = Node::Black;␊
243␉␉ if (w->left)␊
244␉␉␉w->left->color = Node::Black;␊
245␉␉ rotateRight(x_parent, root);␊
246␉␉ break;␊
247␉␉}␊
248␉ }␊
249␉}␊
250␉if (x)␊
251␉ x->color = Node::Black;␊
252 }␊
253 return y;␊
254}␊
255

Archive Download this file

Revision: 1406