tools/qmap.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3const QMapDataBase QMapDataBase::shared_null = { { { (-1) } }, 0, { 0, 0, 0 }, 0 }; -
4 -
5const QMapNodeBase *QMapNodeBase::nextNode() const -
6{ -
7 const QMapNodeBase *n = this; -
8 if (n->right) {
evaluated: n->right
TRUEFALSE
yes
Evaluation Count:323112
yes
Evaluation Count:1047878
323112-1047878
9 n = n->right; -
10 while (n->left)
evaluated: n->left
TRUEFALSE
yes
Evaluation Count:123762
yes
Evaluation Count:323112
123762-323112
11 n = n->left;
executed: n = n->left;
Execution Count:123762
123762
12 } else {
executed: }
Execution Count:323112
323112
13 const QMapNodeBase *y = n->parent(); -
14 while (y && n == y->right) {
partially evaluated: y
TRUEFALSE
yes
Evaluation Count:1437464
no
Evaluation Count:0
evaluated: n == y->right
TRUEFALSE
yes
Evaluation Count:389693
yes
Evaluation Count:1047712
0-1437464
15 n = y; -
16 y = n->parent(); -
17 }
executed: }
Execution Count:389693
389693
18 n = y; -
19 }
executed: }
Execution Count:1047604
1047604
20 return n;
executed: return n;
Execution Count:1370793
1370793
21} -
22 -
23const QMapNodeBase *QMapNodeBase::previousNode() const -
24{ -
25 const QMapNodeBase *n = this; -
26 if (n->left) {
evaluated: n->left
TRUEFALSE
yes
Evaluation Count:282332
yes
Evaluation Count:22735
22735-282332
27 n = n->left; -
28 while (n->right)
evaluated: n->right
TRUEFALSE
yes
Evaluation Count:42957
yes
Evaluation Count:282240
42957-282240
29 n = n->right;
executed: n = n->right;
Execution Count:42957
42957
30 } else {
executed: }
Execution Count:281930
281930
31 const QMapNodeBase *y = n->parent(); -
32 while (y && n == y->left) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:41233
yes
Evaluation Count:24
evaluated: n == y->left
TRUEFALSE
yes
Evaluation Count:18522
yes
Evaluation Count:22711
24-41233
33 n = y; -
34 y = n->parent(); -
35 }
executed: }
Execution Count:18522
18522
36 n = y; -
37 }
executed: }
Execution Count:22735
22735
38 return n;
executed: return n;
Execution Count:304627
304627
39} -
40 -
41 -
42void QMapDataBase::rotateLeft(QMapNodeBase *x) -
43{ -
44 QMapNodeBase *&root = header.left; -
45 QMapNodeBase *y = x->right; -
46 x->right = y->left; -
47 if (y->left != 0)
evaluated: y->left != 0
TRUEFALSE
yes
Evaluation Count:91961
yes
Evaluation Count:286110
91961-286110
48 y->left->setParent(x);
executed: y->left->setParent(x);
Execution Count:91961
91961
49 y->setParent(x->parent()); -
50 if (x == root)
evaluated: x == root
TRUEFALSE
yes
Evaluation Count:178422
yes
Evaluation Count:199649
178422-199649
51 root = y;
executed: root = y;
Execution Count:178422
178422
52 else if (x == x->parent()->left)
evaluated: x == x->parent()->left
TRUEFALSE
yes
Evaluation Count:43337
yes
Evaluation Count:156312
43337-156312
53 x->parent()->left = y;
executed: x->parent()->left = y;
Execution Count:43337
43337
54 else -
55 x->parent()->right = y;
executed: x->parent()->right = y;
Execution Count:156312
156312
56 y->left = x; -
57 x->setParent(y); -
58}
executed: }
Execution Count:378071
378071
59 -
60 -
61void QMapDataBase::rotateRight(QMapNodeBase *x) -
62{ -
63 QMapNodeBase *&root = header.left; -
64 QMapNodeBase *y = x->left; -
65 x->left = y->right; -
66 if (y->right != 0)
evaluated: y->right != 0
TRUEFALSE
yes
Evaluation Count:69313
yes
Evaluation Count:80197
69313-80197
67 y->right->setParent(x);
executed: y->right->setParent(x);
Execution Count:69313
69313
68 y->setParent(x->parent()); -
69 if (x == root)
evaluated: x == root
TRUEFALSE
yes
Evaluation Count:2996
yes
Evaluation Count:146514
2996-146514
70 root = y;
executed: root = y;
Execution Count:2996
2996
71 else if (x == x->parent()->right)
evaluated: x == x->parent()->right
TRUEFALSE
yes
Evaluation Count:28369
yes
Evaluation Count:118145
28369-118145
72 x->parent()->right = y;
executed: x->parent()->right = y;
Execution Count:28369
28369
73 else -
74 x->parent()->left = y;
executed: x->parent()->left = y;
Execution Count:118145
118145
75 y->right = x; -
76 x->setParent(y); -
77}
executed: }
Execution Count:149510
149510
78 -
79 -
80void QMapDataBase::rebalance(QMapNodeBase *x) -
81{ -
82 QMapNodeBase *&root = header.left; -
83 x->setColor(QMapNodeBase::Red); -
84 while (x != root && x->parent()->color() == QMapNodeBase::Red) {
evaluated: x != root
TRUEFALSE
yes
Evaluation Count:1537306
yes
Evaluation Count:672316
evaluated: x->parent()->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:808628
yes
Evaluation Count:728679
672316-1537306
85 if (x->parent() == x->parent()->parent()->left) {
evaluated: x->parent() == x->parent()->parent()->left
TRUEFALSE
yes
Evaluation Count:268665
yes
Evaluation Count:539963
268665-539963
86 QMapNodeBase *y = x->parent()->parent()->right; -
87 if (y && y->color() == QMapNodeBase::Red) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:197888
yes
Evaluation Count:70777
evaluated: y->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:130424
yes
Evaluation Count:67464
67464-197888
88 x->parent()->setColor(QMapNodeBase::Black); -
89 y->setColor(QMapNodeBase::Black); -
90 x->parent()->parent()->setColor(QMapNodeBase::Red); -
91 x = x->parent()->parent(); -
92 } else {
executed: }
Execution Count:130424
130424
93 if (x == x->parent()->right) {
evaluated: x == x->parent()->right
TRUEFALSE
yes
Evaluation Count:16119
yes
Evaluation Count:122122
16119-122122
94 x = x->parent(); -
95 rotateLeft(x); -
96 }
executed: }
Execution Count:16119
16119
97 x->parent()->setColor(QMapNodeBase::Black); -
98 x->parent()->parent()->setColor(QMapNodeBase::Red); -
99 rotateRight (x->parent()->parent()); -
100 }
executed: }
Execution Count:138241
138241
101 } else { -
102 QMapNodeBase *y = x->parent()->parent()->left; -
103 if (y && y->color() == QMapNodeBase::Red) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:266304
yes
Evaluation Count:273659
evaluated: y->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:192172
yes
Evaluation Count:74132
74132-273659
104 x->parent()->setColor(QMapNodeBase::Black); -
105 y->setColor(QMapNodeBase::Black); -
106 x->parent()->parent()->setColor(QMapNodeBase::Red); -
107 x = x->parent()->parent(); -
108 } else {
executed: }
Execution Count:192172
192172
109 if (x == x->parent()->left) {
evaluated: x == x->parent()->left
TRUEFALSE
yes
Evaluation Count:9432
yes
Evaluation Count:338359
9432-338359
110 x = x->parent(); -
111 rotateRight(x); -
112 }
executed: }
Execution Count:9432
9432
113 x->parent()->setColor(QMapNodeBase::Black); -
114 x->parent()->parent()->setColor(QMapNodeBase::Red); -
115 rotateLeft(x->parent()->parent()); -
116 }
executed: }
Execution Count:347791
347791
117 } -
118 } -
119 root->setColor(QMapNodeBase::Black); -
120}
executed: }
Execution Count:1400731
1400731
121 -
122void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) -
123{ -
124 QMapNodeBase *&root = header.left; -
125 QMapNodeBase *y = z; -
126 QMapNodeBase *x; -
127 QMapNodeBase *x_parent; -
128 if (y->left == 0) {
evaluated: y->left == 0
TRUEFALSE
yes
Evaluation Count:66761
yes
Evaluation Count:1773
1773-66761
129 x = y->right; -
130 if (y == mostLeftNode) {
evaluated: y == mostLeftNode
TRUEFALSE
yes
Evaluation Count:64961
yes
Evaluation Count:1800
1800-64961
131 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:13600
yes
Evaluation Count:51361
13600-51361
132 mostLeftNode = x;
executed: mostLeftNode = x;
Execution Count:13600
13600
133 else -
134 mostLeftNode = y->parent();
executed: mostLeftNode = y->parent();
Execution Count:51361
51361
135 } -
136 } else {
executed: }
Execution Count:66761
66761
137 if (y->right == 0) {
evaluated: y->right == 0
TRUEFALSE
yes
Evaluation Count:879
yes
Evaluation Count:894
879-894
138 x = y->left; -
139 } else {
executed: }
Execution Count:879
879
140 y = y->right; -
141 while (y->left != 0)
evaluated: y->left != 0
TRUEFALSE
yes
Evaluation Count:184
yes
Evaluation Count:894
184-894
142 y = y->left;
executed: y = y->left;
Execution Count:184
184
143 x = y->right; -
144 }
executed: }
Execution Count:894
894
145 } -
146 if (y != z) {
evaluated: y != z
TRUEFALSE
yes
Evaluation Count:894
yes
Evaluation Count:67640
894-67640
147 z->left->setParent(y); -
148 y->left = z->left; -
149 if (y != z->right) {
evaluated: y != z->right
TRUEFALSE
yes
Evaluation Count:178
yes
Evaluation Count:716
178-716
150 x_parent = y->parent(); -
151 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:16
yes
Evaluation Count:162
16-162
152 x->setParent(y->parent());
executed: x->setParent(y->parent());
Execution Count:16
16
153 y->parent()->left = x; -
154 y->right = z->right; -
155 z->right->setParent(y); -
156 } else {
executed: }
Execution Count:178
178
157 x_parent = y; -
158 }
executed: }
Execution Count:716
716
159 if (root == z)
evaluated: root == z
TRUEFALSE
yes
Evaluation Count:611
yes
Evaluation Count:283
283-611
160 root = y;
executed: root = y;
Execution Count:611
611
161 else if (z->parent()->left == z)
evaluated: z->parent()->left == z
TRUEFALSE
yes
Evaluation Count:80
yes
Evaluation Count:203
80-203
162 z->parent()->left = y;
executed: z->parent()->left = y;
Execution Count:80
80
163 else -
164 z->parent()->right = y;
executed: z->parent()->right = y;
Execution Count:203
203
165 y->setParent(z->parent()); -
166 -
167 QMapNodeBase::Color c = y->color(); -
168 y->setColor(z->color()); -
169 z->setColor(c); -
170 y = z; -
171 } else {
executed: }
Execution Count:894
894
172 x_parent = y->parent(); -
173 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:14669
yes
Evaluation Count:52971
14669-52971
174 x->setParent(y->parent());
executed: x->setParent(y->parent());
Execution Count:14669
14669
175 if (root == z)
evaluated: root == z
TRUEFALSE
yes
Evaluation Count:36466
yes
Evaluation Count:31174
31174-36466
176 root = x;
executed: root = x;
Execution Count:36466
36466
177 else if (z->parent()->left == z)
evaluated: z->parent()->left == z
TRUEFALSE
yes
Evaluation Count:29500
yes
Evaluation Count:1674
1674-29500
178 z->parent()->left = x;
executed: z->parent()->left = x;
Execution Count:29500
29500
179 else -
180 z->parent()->right = x;
executed: z->parent()->right = x;
Execution Count:1674
1674
181 } -
182 if (y->color() != QMapNodeBase::Red) {
evaluated: y->color() != QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:64795
yes
Evaluation Count:3739
3739-64795
183 while (x != root && (x == 0 || x->color() == QMapNodeBase::Black)) {
evaluated: x != root
TRUEFALSE
yes
Evaluation Count:43111
yes
Evaluation Count:39162
evaluated: x == 0
TRUEFALSE
yes
Evaluation Count:17293
yes
Evaluation Count:25818
evaluated: x->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:7337
yes
Evaluation Count:18481
7337-43111
184 if (x == x_parent->left) {
evaluated: x == x_parent->left
TRUEFALSE
yes
Evaluation Count:24001
yes
Evaluation Count:629
629-24001
185 QMapNodeBase *w = x_parent->right; -
186 if (w->color() == QMapNodeBase::Red) {
evaluated: w->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:7093
yes
Evaluation Count:16908
7093-16908
187 w->setColor(QMapNodeBase::Black); -
188 x_parent->setColor(QMapNodeBase::Red); -
189 rotateLeft(x_parent); -
190 w = x_parent->right; -
191 }
executed: }
Execution Count:7093
7093
192 if ((w->left == 0 || w->left->color() == QMapNodeBase::Black) &&
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:13573
yes
Evaluation Count:10428
evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:6877
yes
Evaluation Count:3551
3551-13573
193 (w->right == 0 || w->right->color() == QMapNodeBase::Black)) {
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:10561
yes
Evaluation Count:9889
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:6426
yes
Evaluation Count:3463
3463-10561
194 w->setColor(QMapNodeBase::Red); -
195 x = x_parent; -
196 x_parent = x_parent->parent(); -
197 } else {
executed: }
Execution Count:16987
16987
198 if (w->right == 0 || w->right->color() == QMapNodeBase::Black) {
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:1526
yes
Evaluation Count:5488
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:161
yes
Evaluation Count:5327
161-5488
199 if (w->left)
partially evaluated: w->left
TRUEFALSE
yes
Evaluation Count:1687
no
Evaluation Count:0
0-1687
200 w->left->setColor(QMapNodeBase::Black);
executed: w->left->setColor(QMapNodeBase::Black);
Execution Count:1687
1687
201 w->setColor(QMapNodeBase::Red); -
202 rotateRight(w); -
203 w = x_parent->right; -
204 }
executed: }
Execution Count:1687
1687
205 w->setColor(x_parent->color()); -
206 x_parent->setColor(QMapNodeBase::Black); -
207 if (w->right)
partially evaluated: w->right
TRUEFALSE
yes
Evaluation Count:7014
no
Evaluation Count:0
0-7014
208 w->right->setColor(QMapNodeBase::Black);
executed: w->right->setColor(QMapNodeBase::Black);
Execution Count:7014
7014
209 rotateLeft(x_parent); -
210 break;
executed: break;
Execution Count:7014
7014
211 } -
212 } else { -
213 QMapNodeBase *w = x_parent->left; -
214 if (w->color() == QMapNodeBase::Red) {
evaluated: w->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:12
yes
Evaluation Count:617
12-617
215 w->setColor(QMapNodeBase::Black); -
216 x_parent->setColor(QMapNodeBase::Red); -
217 rotateRight(x_parent); -
218 w = x_parent->left; -
219 }
executed: }
Execution Count:12
12
220 if ((w->right == 0 || w->right->color() == QMapNodeBase::Black) &&
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:526
yes
Evaluation Count:103
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:13
yes
Evaluation Count:90
13-526
221 (w->left == 0 || w->left->color() == QMapNodeBase::Black)) {
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:478
yes
Evaluation Count:61
evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:13
yes
Evaluation Count:48
13-478
222 w->setColor(QMapNodeBase::Red); -
223 x = x_parent; -
224 x_parent = x_parent->parent(); -
225 } else {
executed: }
Execution Count:491
491
226 if (w->left == 0 || w->left->color() == QMapNodeBase::Black) {
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:54
yes
Evaluation Count:84
partially evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:84
0-84
227 if (w->right)
partially evaluated: w->right
TRUEFALSE
yes
Evaluation Count:54
no
Evaluation Count:0
0-54
228 w->right->setColor(QMapNodeBase::Black);
executed: w->right->setColor(QMapNodeBase::Black);
Execution Count:54
54
229 w->setColor(QMapNodeBase::Red); -
230 rotateLeft(w); -
231 w = x_parent->left; -
232 }
executed: }
Execution Count:54
54
233 w->setColor(x_parent->color()); -
234 x_parent->setColor(QMapNodeBase::Black); -
235 if (w->left)
partially evaluated: w->left
TRUEFALSE
yes
Evaluation Count:138
no
Evaluation Count:0
0-138
236 w->left->setColor(QMapNodeBase::Black);
executed: w->left->setColor(QMapNodeBase::Black);
Execution Count:138
138
237 rotateRight(x_parent); -
238 break;
executed: break;
Execution Count:138
138
239 } -
240 } -
241 } -
242 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:25824
yes
Evaluation Count:38971
25824-38971
243 x->setColor(QMapNodeBase::Black);
executed: x->setColor(QMapNodeBase::Black);
Execution Count:25824
25824
244 }
executed: }
Execution Count:64795
64795
245 free(y); -
246 --size; -
247}
executed: }
Execution Count:68534
68534
248 -
249void QMapDataBase::recalcMostLeftNode() -
250{ -
251 mostLeftNode = &header; -
252 while (mostLeftNode->left)
evaluated: mostLeftNode->left
TRUEFALSE
yes
Evaluation Count:1304
yes
Evaluation Count:914553
1304-914553
253 mostLeftNode = mostLeftNode->left;
executed: mostLeftNode = mostLeftNode->left;
Execution Count:1304
1304
254}
executed: }
Execution Count:914272
914272
255 -
256static inline int qMapAlignmentThreshold() -
257{ -
258 -
259 -
260 -
261 return 2 * sizeof(void*);
executed: return 2 * sizeof(void*);
Execution Count:2751836
2751836
262} -
263 -
264static inline void *qMapAllocate(int alloc, int alignment) -
265{ -
266 return alignment > qMapAlignmentThreshold() 1408382
267 ? qMallocAligned(alloc, alignment) 1408382
268 : ::malloc(alloc);
executed: return alignment > qMapAlignmentThreshold() ? qMallocAligned(alloc, alignment) : ::malloc(alloc);
Execution Count:1408382
1408382
269} -
270 -
271static inline void qMapDeallocate(QMapNodeBase *node, int alignment) -
272{ -
273 if (alignment > qMapAlignmentThreshold())
evaluated: alignment > qMapAlignmentThreshold()
TRUEFALSE
yes
Evaluation Count:600
yes
Evaluation Count:1344540
600-1344540
274 qFreeAligned(node);
executed: qFreeAligned(node);
Execution Count:600
600
275 else -
276 ::free(node);
executed: ::free(node);
Execution Count:1344308
1344308
277} -
278 -
279QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left) -
280{ -
281 QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment)); -
282 do { if (!(node)) qBadAlloc(); } while (0);
partially evaluated: 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:1408498
never executed: qBadAlloc();
executed: }
Execution Count:1408884
partially evaluated: !(node)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:1409177
0-1409177
283 -
284 memset(node, 0, alloc); -
285 ++size; -
286 -
287 if (parent) {
evaluated: parent
TRUEFALSE
yes
Evaluation Count:1401954
yes
Evaluation Count:6590
6590-1401954
288 if (left) {
evaluated: left
TRUEFALSE
yes
Evaluation Count:816356
yes
Evaluation Count:585344
585344-816356
289 parent->left = node; -
290 if (parent == mostLeftNode)
evaluated: parent == mostLeftNode
TRUEFALSE
yes
Evaluation Count:773125
yes
Evaluation Count:42950
42950-773125
291 mostLeftNode = node;
executed: mostLeftNode = node;
Execution Count:773026
773026
292 } else {
executed: }
Execution Count:816215
816215
293 parent->right = node; -
294 }
executed: }
Execution Count:585344
585344
295 node->setParent(parent); -
296 rebalance(node); -
297 }
executed: }
Execution Count:1400839
1400839
298 return node;
executed: return node;
Execution Count:1407535
1407535
299} -
300 -
301void QMapDataBase::freeTree(QMapNodeBase *root, int alignment) -
302{ -
303 if (root->left)
evaluated: root->left
TRUEFALSE
yes
Evaluation Count:354179
yes
Evaluation Count:991468
354179-991468
304 freeTree(root->left, alignment);
executed: freeTree(root->left, alignment);
Execution Count:354179
354179
305 if (root->right)
evaluated: root->right
TRUEFALSE
yes
Evaluation Count:369062
yes
Evaluation Count:976640
369062-976640
306 freeTree(root->right, alignment);
executed: freeTree(root->right, alignment);
Execution Count:369062
369062
307 qMapDeallocate(root, alignment); -
308}
executed: }
Execution Count:1345114
1345114
309 -
310QMapDataBase *QMapDataBase::createData() -
311{ -
312 QMapDataBase *d = new QMapDataBase; -
313 -
314 d->ref.initializeOwned(); -
315 d->size = 0; -
316 -
317 d->header.p = 0; -
318 d->header.left = 0; -
319 d->header.right = 0; -
320 d->mostLeftNode = &(d->header); -
321 -
322 return d;
executed: return d;
Execution Count:914551
914551
323} -
324 -
325void QMapDataBase::freeData(QMapDataBase *d) -
326{ -
327 delete d; -
328}
executed: }
Execution Count:916805
916805
329 -
330 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial