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:315975
yes
Evaluation Count:941080
315975-941080
9 n = n->right; -
10 while (n->left)
evaluated: n->left
TRUEFALSE
yes
Evaluation Count:120028
yes
Evaluation Count:315975
120028-315975
11 n = n->left;
executed: n = n->left;
Execution Count:120028
120028
12 } else {
executed: }
Execution Count:315975
315975
13 const QMapNodeBase *y = n->parent(); -
14 while (y && n == y->right) {
partially evaluated: y
TRUEFALSE
yes
Evaluation Count:1292876
no
Evaluation Count:0
evaluated: n == y->right
TRUEFALSE
yes
Evaluation Count:351850
yes
Evaluation Count:940957
0-1292876
15 n = y; -
16 y = n->parent(); -
17 }
executed: }
Execution Count:351850
351850
18 n = y; -
19 }
executed: }
Execution Count:940866
940866
20 return n;
executed: return n;
Execution Count:1256960
1256960
21} -
22 -
23const QMapNodeBase *QMapNodeBase::previousNode() const -
24{ -
25 const QMapNodeBase *n = this; -
26 if (n->left) {
evaluated: n->left
TRUEFALSE
yes
Evaluation Count:281802
yes
Evaluation Count:22110
22110-281802
27 n = n->left; -
28 while (n->right)
evaluated: n->right
TRUEFALSE
yes
Evaluation Count:42415
yes
Evaluation Count:281700
42415-281700
29 n = n->right;
executed: n = n->right;
Execution Count:42415
42415
30 } else {
executed: }
Execution Count:281402
281402
31 const QMapNodeBase *y = n->parent(); -
32 while (y && n == y->left) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:40651
yes
Evaluation Count:24
evaluated: n == y->left
TRUEFALSE
yes
Evaluation Count:18565
yes
Evaluation Count:22086
24-40651
33 n = y; -
34 y = n->parent(); -
35 }
executed: }
Execution Count:18565
18565
36 n = y; -
37 }
executed: }
Execution Count:22110
22110
38 return n;
executed: return n;
Execution Count:303437
303437
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:82888
yes
Evaluation Count:269134
82888-269134
48 y->left->setParent(x);
executed: y->left->setParent(x);
Execution Count:82888
82888
49 y->setParent(x->parent()); -
50 if (x == root)
evaluated: x == root
TRUEFALSE
yes
Evaluation Count:175980
yes
Evaluation Count:176042
175980-176042
51 root = y;
executed: root = y;
Execution Count:175980
175980
52 else if (x == x->parent()->left)
evaluated: x == x->parent()->left
TRUEFALSE
yes
Evaluation Count:32066
yes
Evaluation Count:143976
32066-143976
53 x->parent()->left = y;
executed: x->parent()->left = y;
Execution Count:32066
32066
54 else -
55 x->parent()->right = y;
executed: x->parent()->right = y;
Execution Count:143976
143976
56 y->left = x; -
57 x->setParent(y); -
58}
executed: }
Execution Count:352022
352022
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:63061
yes
Evaluation Count:75724
63061-75724
67 y->right->setParent(x);
executed: y->right->setParent(x);
Execution Count:63061
63061
68 y->setParent(x->parent()); -
69 if (x == root)
evaluated: x == root
TRUEFALSE
yes
Evaluation Count:2413
yes
Evaluation Count:136372
2413-136372
70 root = y;
executed: root = y;
Execution Count:2413
2413
71 else if (x == x->parent()->right)
evaluated: x == x->parent()->right
TRUEFALSE
yes
Evaluation Count:19975
yes
Evaluation Count:116397
19975-116397
72 x->parent()->right = y;
executed: x->parent()->right = y;
Execution Count:19975
19975
73 else -
74 x->parent()->left = y;
executed: x->parent()->left = y;
Execution Count:116397
116397
75 y->right = x; -
76 x->setParent(y); -
77}
executed: }
Execution Count:138785
138785
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:1434133
yes
Evaluation Count:597631
evaluated: x->parent()->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:750547
yes
Evaluation Count:683586
597631-1434133
85 if (x->parent() == x->parent()->parent()->left) {
evaluated: x->parent() == x->parent()->parent()->left
TRUEFALSE
yes
Evaluation Count:254821
yes
Evaluation Count:495726
254821-495726
86 QMapNodeBase *y = x->parent()->parent()->right; -
87 if (y && y->color() == QMapNodeBase::Red) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:186945
yes
Evaluation Count:67876
evaluated: y->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:125234
yes
Evaluation Count:61711
61711-186945
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:125234
125234
93 if (x == x->parent()->right) {
evaluated: x == x->parent()->right
TRUEFALSE
yes
Evaluation Count:11589
yes
Evaluation Count:117998
11589-117998
94 x = x->parent(); -
95 rotateLeft(x); -
96 }
executed: }
Execution Count:11589
11589
97 x->parent()->setColor(QMapNodeBase::Black); -
98 x->parent()->parent()->setColor(QMapNodeBase::Red); -
99 rotateRight (x->parent()->parent()); -
100 }
executed: }
Execution Count:129587
129587
101 } else { -
102 QMapNodeBase *y = x->parent()->parent()->left; -
103 if (y && y->color() == QMapNodeBase::Red) {
evaluated: y
TRUEFALSE
yes
Evaluation Count:238581
yes
Evaluation Count:257145
evaluated: y->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:169519
yes
Evaluation Count:69062
69062-257145
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:169519
169519
109 if (x == x->parent()->left) {
evaluated: x == x->parent()->left
TRUEFALSE
yes
Evaluation Count:7320
yes
Evaluation Count:318887
7320-318887
110 x = x->parent(); -
111 rotateRight(x); -
112 }
executed: }
Execution Count:7320
7320
113 x->parent()->setColor(QMapNodeBase::Black); -
114 x->parent()->parent()->setColor(QMapNodeBase::Red); -
115 rotateLeft(x->parent()->parent()); -
116 }
executed: }
Execution Count:326207
326207
117 } -
118 } -
119 root->setColor(QMapNodeBase::Black); -
120}
executed: }
Execution Count:1280794
1280794
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:63696
yes
Evaluation Count:1688
1688-63696
129 x = y->right; -
130 if (y == mostLeftNode) {
evaluated: y == mostLeftNode
TRUEFALSE
yes
Evaluation Count:62078
yes
Evaluation Count:1618
1618-62078
131 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:13508
yes
Evaluation Count:48570
13508-48570
132 mostLeftNode = x;
executed: mostLeftNode = x;
Execution Count:13508
13508
133 else -
134 mostLeftNode = y->parent();
executed: mostLeftNode = y->parent();
Execution Count:48570
48570
135 } -
136 } else {
executed: }
Execution Count:63696
63696
137 if (y->right == 0) {
evaluated: y->right == 0
TRUEFALSE
yes
Evaluation Count:865
yes
Evaluation Count:823
823-865
138 x = y->left; -
139 } else {
executed: }
Execution Count:865
865
140 y = y->right; -
141 while (y->left != 0)
evaluated: y->left != 0
TRUEFALSE
yes
Evaluation Count:179
yes
Evaluation Count:823
179-823
142 y = y->left;
executed: y = y->left;
Execution Count:179
179
143 x = y->right; -
144 }
executed: }
Execution Count:823
823
145 } -
146 if (y != z) {
evaluated: y != z
TRUEFALSE
yes
Evaluation Count:823
yes
Evaluation Count:64561
823-64561
147 z->left->setParent(y); -
148 y->left = z->left; -
149 if (y != z->right) {
evaluated: y != z->right
TRUEFALSE
yes
Evaluation Count:174
yes
Evaluation Count:649
174-649
150 x_parent = y->parent(); -
151 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:17
yes
Evaluation Count:157
17-157
152 x->setParent(y->parent());
executed: x->setParent(y->parent());
Execution Count:17
17
153 y->parent()->left = x; -
154 y->right = z->right; -
155 z->right->setParent(y); -
156 } else {
executed: }
Execution Count:174
174
157 x_parent = y; -
158 }
executed: }
Execution Count:649
649
159 if (root == z)
evaluated: root == z
TRUEFALSE
yes
Evaluation Count:560
yes
Evaluation Count:263
263-560
160 root = y;
executed: root = y;
Execution Count:560
560
161 else if (z->parent()->left == z)
evaluated: z->parent()->left == z
TRUEFALSE
yes
Evaluation Count:82
yes
Evaluation Count:181
82-181
162 z->parent()->left = y;
executed: z->parent()->left = y;
Execution Count:82
82
163 else -
164 z->parent()->right = y;
executed: z->parent()->right = y;
Execution Count:181
181
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:823
823
172 x_parent = y->parent(); -
173 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:14565
yes
Evaluation Count:49996
14565-49996
174 x->setParent(y->parent());
executed: x->setParent(y->parent());
Execution Count:14565
14565
175 if (root == z)
evaluated: root == z
TRUEFALSE
yes
Evaluation Count:33645
yes
Evaluation Count:30916
30916-33645
176 root = x;
executed: root = x;
Execution Count:33645
33645
177 else if (z->parent()->left == z)
evaluated: z->parent()->left == z
TRUEFALSE
yes
Evaluation Count:29379
yes
Evaluation Count:1537
1537-29379
178 z->parent()->left = x;
executed: z->parent()->left = x;
Execution Count:29379
29379
179 else -
180 z->parent()->right = x;
executed: z->parent()->right = x;
Execution Count:1537
1537
181 } -
182 if (y->color() != QMapNodeBase::Red) {
evaluated: y->color() != QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:61940
yes
Evaluation Count:3444
3444-61940
183 while (x != root && (x == 0 || x->color() == QMapNodeBase::Black)) {
evaluated: x != root
TRUEFALSE
yes
Evaluation Count:43069
yes
Evaluation Count:36306
evaluated: x == 0
TRUEFALSE
yes
Evaluation Count:17258
yes
Evaluation Count:25811
evaluated: x->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:7380
yes
Evaluation Count:18431
7380-43069
184 if (x == x_parent->left) {
evaluated: x == x_parent->left
TRUEFALSE
yes
Evaluation Count:24049
yes
Evaluation Count:589
589-24049
185 QMapNodeBase *w = x_parent->right; -
186 if (w->color() == QMapNodeBase::Red) {
evaluated: w->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:7095
yes
Evaluation Count:16954
7095-16954
187 w->setColor(QMapNodeBase::Black); -
188 x_parent->setColor(QMapNodeBase::Red); -
189 rotateLeft(x_parent); -
190 w = x_parent->right; -
191 }
executed: }
Execution Count:7095
7095
192 if ((w->left == 0 || w->left->color() == QMapNodeBase::Black) &&
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:13557
yes
Evaluation Count:10492
evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:6910
yes
Evaluation Count:3582
3582-13557
193 (w->right == 0 || w->right->color() == QMapNodeBase::Black)) {
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:10562
yes
Evaluation Count:9905
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:6400
yes
Evaluation Count:3505
3505-10562
194 w->setColor(QMapNodeBase::Red); -
195 x = x_parent; -
196 x_parent = x_parent->parent(); -
197 } else {
executed: }
Execution Count:16962
16962
198 if (w->right == 0 || w->right->color() == QMapNodeBase::Black) {
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:1587
yes
Evaluation Count:5500
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:165
yes
Evaluation Count:5335
165-5500
199 if (w->left)
partially evaluated: w->left
TRUEFALSE
yes
Evaluation Count:1752
no
Evaluation Count:0
0-1752
200 w->left->setColor(QMapNodeBase::Black);
executed: w->left->setColor(QMapNodeBase::Black);
Execution Count:1752
1752
201 w->setColor(QMapNodeBase::Red); -
202 rotateRight(w); -
203 w = x_parent->right; -
204 }
executed: }
Execution Count:1752
1752
205 w->setColor(x_parent->color()); -
206 x_parent->setColor(QMapNodeBase::Black); -
207 if (w->right)
partially evaluated: w->right
TRUEFALSE
yes
Evaluation Count:7087
no
Evaluation Count:0
0-7087
208 w->right->setColor(QMapNodeBase::Black);
executed: w->right->setColor(QMapNodeBase::Black);
Execution Count:7087
7087
209 rotateLeft(x_parent); -
210 break;
executed: break;
Execution Count:7087
7087
211 } -
212 } else { -
213 QMapNodeBase *w = x_parent->left; -
214 if (w->color() == QMapNodeBase::Red) {
evaluated: w->color() == QMapNodeBase::Red
TRUEFALSE
yes
Evaluation Count:10
yes
Evaluation Count:579
10-579
215 w->setColor(QMapNodeBase::Black); -
216 x_parent->setColor(QMapNodeBase::Red); -
217 rotateRight(x_parent); -
218 w = x_parent->left; -
219 }
executed: }
Execution Count:10
10
220 if ((w->right == 0 || w->right->color() == QMapNodeBase::Black) &&
evaluated: w->right == 0
TRUEFALSE
yes
Evaluation Count:513
yes
Evaluation Count:76
evaluated: w->right->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:10
yes
Evaluation Count:66
10-513
221 (w->left == 0 || w->left->color() == QMapNodeBase::Black)) {
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:464
yes
Evaluation Count:59
evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
yes
Evaluation Count:9
yes
Evaluation Count:50
9-464
222 w->setColor(QMapNodeBase::Red); -
223 x = x_parent; -
224 x_parent = x_parent->parent(); -
225 } else {
executed: }
Execution Count:473
473
226 if (w->left == 0 || w->left->color() == QMapNodeBase::Black) {
evaluated: w->left == 0
TRUEFALSE
yes
Evaluation Count:44
yes
Evaluation Count:72
partially evaluated: w->left->color() == QMapNodeBase::Black
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:72
0-72
227 if (w->right)
partially evaluated: w->right
TRUEFALSE
yes
Evaluation Count:44
no
Evaluation Count:0
0-44
228 w->right->setColor(QMapNodeBase::Black);
executed: w->right->setColor(QMapNodeBase::Black);
Execution Count:44
44
229 w->setColor(QMapNodeBase::Red); -
230 rotateLeft(w); -
231 w = x_parent->left; -
232 }
executed: }
Execution Count:44
44
233 w->setColor(x_parent->color()); -
234 x_parent->setColor(QMapNodeBase::Black); -
235 if (w->left)
partially evaluated: w->left
TRUEFALSE
yes
Evaluation Count:116
no
Evaluation Count:0
0-116
236 w->left->setColor(QMapNodeBase::Black);
executed: w->left->setColor(QMapNodeBase::Black);
Execution Count:116
116
237 rotateRight(x_parent); -
238 break;
executed: break;
Execution Count:116
116
239 } -
240 } -
241 } -
242 if (x)
evaluated: x
TRUEFALSE
yes
Evaluation Count:25707
yes
Evaluation Count:36233
25707-36233
243 x->setColor(QMapNodeBase::Black);
executed: x->setColor(QMapNodeBase::Black);
Execution Count:25707
25707
244 }
executed: }
Execution Count:61940
61940
245 free(y); -
246 --size; -
247}
executed: }
Execution Count:65384
65384
248 -
249void QMapDataBase::recalcMostLeftNode() -
250{ -
251 mostLeftNode = &header; -
252 while (mostLeftNode->left)
evaluated: mostLeftNode->left
TRUEFALSE
yes
Evaluation Count:1175
yes
Evaluation Count:842432
1175-842432
253 mostLeftNode = mostLeftNode->left;
executed: mostLeftNode = mostLeftNode->left;
Execution Count:1175
1175
254}
executed: }
Execution Count:842087
842087
255 -
256static inline int qMapAlignmentThreshold() -
257{ -
258 -
259 -
260 -
261 return 2 * sizeof(void*);
executed: return 2 * sizeof(void*);
Execution Count:2513924
2513924
262} -
263 -
264static inline void *qMapAllocate(int alloc, int alignment) -
265{ -
266 return alignment > qMapAlignmentThreshold() 1288035
267 ? qMallocAligned(alloc, alignment) 1288035
268 : ::malloc(alloc);
executed: return alignment > qMapAlignmentThreshold() ? qMallocAligned(alloc, alignment) : ::malloc(alloc);
Execution Count:1288035
1288035
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:1226791
600-1226791
274 qFreeAligned(node);
executed: qFreeAligned(node);
Execution Count:600
600
275 else -
276 ::free(node);
executed: ::free(node);
Execution Count:1226618
1226618
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:1288173
never executed: qBadAlloc();
executed: }
Execution Count:1288540
partially evaluated: !(node)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:1288810
0-1288810
283 -
284 memset(node, 0, alloc); -
285 ++size; -
286 -
287 if (parent) {
evaluated: parent
TRUEFALSE
yes
Evaluation Count:1282084
yes
Evaluation Count:5864
5864-1282084
288 if (left) {
evaluated: left
TRUEFALSE
yes
Evaluation Count:735642
yes
Evaluation Count:546120
546120-735642
289 parent->left = node; -
290 if (parent == mostLeftNode)
evaluated: parent == mostLeftNode
TRUEFALSE
yes
Evaluation Count:701109
yes
Evaluation Count:34389
34389-701109
291 mostLeftNode = node;
executed: mostLeftNode = node;
Execution Count:701083
701083
292 } else {
executed: }
Execution Count:735587
735587
293 parent->right = node; -
294 }
executed: }
Execution Count:546120
546120
295 node->setParent(parent); -
296 rebalance(node); -
297 }
executed: }
Execution Count:1281063
1281063
298 return node;
executed: return node;
Execution Count:1287032
1287032
299} -
300 -
301void QMapDataBase::freeTree(QMapNodeBase *root, int alignment) -
302{ -
303 if (root->left)
evaluated: root->left
TRUEFALSE
yes
Evaluation Count:332712
yes
Evaluation Count:895207
332712-895207
304 freeTree(root->left, alignment);
executed: freeTree(root->left, alignment);
Execution Count:332712
332712
305 if (root->right)
evaluated: root->right
TRUEFALSE
yes
Evaluation Count:342061
yes
Evaluation Count:886002
342061-886002
306 freeTree(root->right, alignment);
executed: freeTree(root->right, alignment);
Execution Count:342061
342061
307 qMapDeallocate(root, alignment); -
308}
executed: }
Execution Count:1227399
1227399
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:842445
842445
323} -
324 -
325void QMapDataBase::freeData(QMapDataBase *d) -
326{ -
327 delete d; -
328}
executed: }
Execution Count:844594
844594
329 -
330 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial