Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/qtdeclarative/src/qtdeclarative/src/qml/jsruntime/qv4sparsearray.cpp |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 QtCore 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 | #include "qv4sparsearray_p.h" | - | ||||||||||||||||||
41 | #include "qv4runtime_p.h" | - | ||||||||||||||||||
42 | #include "qv4object_p.h" | - | ||||||||||||||||||
43 | #include "qv4functionobject_p.h" | - | ||||||||||||||||||
44 | #include "qv4scopedvalue_p.h" | - | ||||||||||||||||||
45 | #include <stdlib.h> | - | ||||||||||||||||||
46 | - | |||||||||||||||||||
47 | #ifdef QT_QMAP_DEBUG | - | ||||||||||||||||||
48 | # include <qstring.h> | - | ||||||||||||||||||
49 | # include <qvector.h> | - | ||||||||||||||||||
50 | #endif | - | ||||||||||||||||||
51 | - | |||||||||||||||||||
52 | using namespace QV4; | - | ||||||||||||||||||
53 | - | |||||||||||||||||||
54 | const SparseArrayNode *SparseArrayNode::nextNode() const | - | ||||||||||||||||||
55 | { | - | ||||||||||||||||||
56 | const SparseArrayNode *n = this; | - | ||||||||||||||||||
57 | if (n->right) {
| 293-1253 | ||||||||||||||||||
58 | n = n->right; | - | ||||||||||||||||||
59 | while (n->left)
| 4-294 | ||||||||||||||||||
60 | n = n->left; executed 4 times by 1 test: n = n->left; Executed by:
| 4 | ||||||||||||||||||
61 | } else { executed 293 times by 2 tests: end of block Executed by:
| 293 | ||||||||||||||||||
62 | const SparseArrayNode *y = n->parent(); | - | ||||||||||||||||||
63 | while (y && n == y->right) {
| 0-1747 | ||||||||||||||||||
64 | n = y; | - | ||||||||||||||||||
65 | y = n->parent(); | - | ||||||||||||||||||
66 | } executed 494 times by 2 tests: end of block Executed by:
| 494 | ||||||||||||||||||
67 | n = y; | - | ||||||||||||||||||
68 | } executed 1254 times by 2 tests: end of block Executed by:
| 1254 | ||||||||||||||||||
69 | return n; executed 1548 times by 2 tests: return n; Executed by:
| 1548 | ||||||||||||||||||
70 | } | - | ||||||||||||||||||
71 | - | |||||||||||||||||||
72 | const SparseArrayNode *SparseArrayNode::previousNode() const | - | ||||||||||||||||||
73 | { | - | ||||||||||||||||||
74 | const SparseArrayNode *n = this; | - | ||||||||||||||||||
75 | if (n->left) {
| 180-182 | ||||||||||||||||||
76 | n = n->left; | - | ||||||||||||||||||
77 | while (n->right)
| 182-256 | ||||||||||||||||||
78 | n = n->right; executed 256 times by 1 test: n = n->right; Executed by:
| 256 | ||||||||||||||||||
79 | } else { executed 182 times by 1 test: end of block Executed by:
| 182 | ||||||||||||||||||
80 | const SparseArrayNode *y = n->parent(); | - | ||||||||||||||||||
81 | while (y && n == y->left) {
| 4-178 | ||||||||||||||||||
82 | n = y; | - | ||||||||||||||||||
83 | y = n->parent(); | - | ||||||||||||||||||
84 | } executed 4 times by 1 test: end of block Executed by:
| 4 | ||||||||||||||||||
85 | n = y; | - | ||||||||||||||||||
86 | } executed 180 times by 1 test: end of block Executed by:
| 180 | ||||||||||||||||||
87 | return n; executed 362 times by 1 test: return n; Executed by:
| 362 | ||||||||||||||||||
88 | } | - | ||||||||||||||||||
89 | - | |||||||||||||||||||
90 | SparseArrayNode *SparseArrayNode::copy(SparseArray *d) const | - | ||||||||||||||||||
91 | { | - | ||||||||||||||||||
92 | SparseArrayNode *n = d->createNode(size_left, nullptr, false); | - | ||||||||||||||||||
93 | n->value = value; | - | ||||||||||||||||||
94 | n->setColor(color()); | - | ||||||||||||||||||
95 | if (left) {
| 0 | ||||||||||||||||||
96 | n->left = left->copy(d); | - | ||||||||||||||||||
97 | n->left->setParent(n); | - | ||||||||||||||||||
98 | } else { never executed: end of block | 0 | ||||||||||||||||||
99 | n->left = nullptr; | - | ||||||||||||||||||
100 | } never executed: end of block | 0 | ||||||||||||||||||
101 | if (right) {
| 0 | ||||||||||||||||||
102 | n->right = right->copy(d); | - | ||||||||||||||||||
103 | n->right->setParent(n); | - | ||||||||||||||||||
104 | } else { never executed: end of block | 0 | ||||||||||||||||||
105 | n->right = nullptr; | - | ||||||||||||||||||
106 | } never executed: end of block | 0 | ||||||||||||||||||
107 | return n; never executed: return n; | 0 | ||||||||||||||||||
108 | } | - | ||||||||||||||||||
109 | - | |||||||||||||||||||
110 | /* | - | ||||||||||||||||||
111 | x y | - | ||||||||||||||||||
112 | \ / \ | - | ||||||||||||||||||
113 | y --> x b | - | ||||||||||||||||||
114 | / \ \ | - | ||||||||||||||||||
115 | a b a | - | ||||||||||||||||||
116 | */ | - | ||||||||||||||||||
117 | void SparseArray::rotateLeft(SparseArrayNode *x) | - | ||||||||||||||||||
118 | { | - | ||||||||||||||||||
119 | SparseArrayNode *&root = header.left; | - | ||||||||||||||||||
120 | SparseArrayNode *y = x->right; | - | ||||||||||||||||||
121 | x->right = y->left; | - | ||||||||||||||||||
122 | if (y->left != nullptr)
| 36-1081 | ||||||||||||||||||
123 | y->left->setParent(x); executed 36 times by 1 test: y->left->setParent(x); Executed by:
| 36 | ||||||||||||||||||
124 | y->setParent(x->parent()); | - | ||||||||||||||||||
125 | if (x == root)
| 177-942 | ||||||||||||||||||
126 | root = y; executed 939 times by 1 test: root = y; Executed by:
| 939 | ||||||||||||||||||
127 | else if (x == x->parent()->left)
| 23-154 | ||||||||||||||||||
128 | x->parent()->left = y; executed 23 times by 1 test: x->parent()->left = y; Executed by:
| 23 | ||||||||||||||||||
129 | else | - | ||||||||||||||||||
130 | x->parent()->right = y; executed 154 times by 1 test: x->parent()->right = y; Executed by:
| 154 | ||||||||||||||||||
131 | y->left = x; | - | ||||||||||||||||||
132 | x->setParent(y); | - | ||||||||||||||||||
133 | y->size_left += x->size_left; | - | ||||||||||||||||||
134 | } executed 1119 times by 1 test: end of block Executed by:
| 1119 | ||||||||||||||||||
135 | - | |||||||||||||||||||
136 | - | |||||||||||||||||||
137 | /* | - | ||||||||||||||||||
138 | x y | - | ||||||||||||||||||
139 | / / \ | - | ||||||||||||||||||
140 | y --> a x | - | ||||||||||||||||||
141 | / \ / | - | ||||||||||||||||||
142 | a b b | - | ||||||||||||||||||
143 | */ | - | ||||||||||||||||||
144 | void SparseArray::rotateRight(SparseArrayNode *x) | - | ||||||||||||||||||
145 | { | - | ||||||||||||||||||
146 | SparseArrayNode *&root = header.left; | - | ||||||||||||||||||
147 | SparseArrayNode *y = x->left; | - | ||||||||||||||||||
148 | x->left = y->right; | - | ||||||||||||||||||
149 | if (y->right != nullptr)
| 0-179 | ||||||||||||||||||
150 | y->right->setParent(x); never executed: y->right->setParent(x); | 0 | ||||||||||||||||||
151 | y->setParent(x->parent()); | - | ||||||||||||||||||
152 | if (x == root)
| 20-160 | ||||||||||||||||||
153 | root = y; executed 20 times by 1 test: root = y; Executed by:
| 20 | ||||||||||||||||||
154 | else if (x == x->parent()->right)
| 0-160 | ||||||||||||||||||
155 | x->parent()->right = y; executed 160 times by 1 test: x->parent()->right = y; Executed by:
| 160 | ||||||||||||||||||
156 | else | - | ||||||||||||||||||
157 | x->parent()->left = y; never executed: x->parent()->left = y; | 0 | ||||||||||||||||||
158 | y->right = x; | - | ||||||||||||||||||
159 | x->setParent(y); | - | ||||||||||||||||||
160 | x->size_left -= y->size_left; | - | ||||||||||||||||||
161 | } executed 180 times by 1 test: end of block Executed by:
| 180 | ||||||||||||||||||
162 | - | |||||||||||||||||||
163 | - | |||||||||||||||||||
164 | void SparseArray::rebalance(SparseArrayNode *x) | - | ||||||||||||||||||
165 | { | - | ||||||||||||||||||
166 | SparseArrayNode *&root = header.left; | - | ||||||||||||||||||
167 | x->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
168 | while (x != root && x->parent()->color() == SparseArrayNode::Red) {
| 1518-4389 | ||||||||||||||||||
169 | if (x->parent() == x->parent()->parent()->left) {
| 50-1468 | ||||||||||||||||||
170 | SparseArrayNode *y = x->parent()->parent()->right; | - | ||||||||||||||||||
171 | if (y && y->color() == SparseArrayNode::Red) {
| 0-26 | ||||||||||||||||||
172 | x->parent()->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
173 | y->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
174 | x->parent()->parent()->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
175 | x = x->parent()->parent(); | - | ||||||||||||||||||
176 | } else { executed 26 times by 2 tests: end of block Executed by:
| 26 | ||||||||||||||||||
177 | if (x == x->parent()->right) {
| 8-15 | ||||||||||||||||||
178 | x = x->parent(); | - | ||||||||||||||||||
179 | rotateLeft(x); | - | ||||||||||||||||||
180 | } executed 14 times by 1 test: end of block Executed by:
| 14 | ||||||||||||||||||
181 | x->parent()->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
182 | x->parent()->parent()->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
183 | rotateRight (x->parent()->parent()); | - | ||||||||||||||||||
184 | } executed 24 times by 1 test: end of block Executed by:
| 24 | ||||||||||||||||||
185 | } else { | - | ||||||||||||||||||
186 | SparseArrayNode *y = x->parent()->parent()->left; | - | ||||||||||||||||||
187 | if (y && y->color() == SparseArrayNode::Red) {
| 36-1059 | ||||||||||||||||||
188 | x->parent()->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
189 | y->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
190 | x->parent()->parent()->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
191 | x = x->parent()->parent(); | - | ||||||||||||||||||
192 | } else { executed 370 times by 1 test: end of block Executed by:
| 370 | ||||||||||||||||||
193 | if (x == x->parent()->left) {
| 156-939 | ||||||||||||||||||
194 | x = x->parent(); | - | ||||||||||||||||||
195 | rotateRight(x); | - | ||||||||||||||||||
196 | } executed 156 times by 1 test: end of block Executed by:
| 156 | ||||||||||||||||||
197 | x->parent()->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
198 | x->parent()->parent()->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
199 | rotateLeft(x->parent()->parent()); | - | ||||||||||||||||||
200 | } executed 1096 times by 1 test: end of block Executed by:
| 1096 | ||||||||||||||||||
201 | } | - | ||||||||||||||||||
202 | } | - | ||||||||||||||||||
203 | root->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
204 | } executed 6260 times by 2 tests: end of block Executed by:
| 6260 | ||||||||||||||||||
205 | - | |||||||||||||||||||
206 | void SparseArray::deleteNode(SparseArrayNode *z) | - | ||||||||||||||||||
207 | { | - | ||||||||||||||||||
208 | SparseArrayNode *&root = header.left; | - | ||||||||||||||||||
209 | SparseArrayNode *y = z; | - | ||||||||||||||||||
210 | SparseArrayNode *x; | - | ||||||||||||||||||
211 | SparseArrayNode *x_parent; | - | ||||||||||||||||||
212 | if (y->left == nullptr) {
| 152-447 | ||||||||||||||||||
213 | x = y->right; | - | ||||||||||||||||||
214 | if (y == mostLeftNode) {
| 216-231 | ||||||||||||||||||
215 | if (x)
| 10-221 | ||||||||||||||||||
216 | mostLeftNode = x; // It cannot have (left) children due the red black invariant. executed 10 times by 2 tests: mostLeftNode = x; Executed by:
| 10 | ||||||||||||||||||
217 | else | - | ||||||||||||||||||
218 | mostLeftNode = y->parent(); executed 221 times by 1 test: mostLeftNode = y->parent(); Executed by:
| 221 | ||||||||||||||||||
219 | } | - | ||||||||||||||||||
220 | } else if (y->right == nullptr) { executed 448 times by 2 tests: end of block Executed by:
| 42-448 | ||||||||||||||||||
221 | x = y->left; | - | ||||||||||||||||||
222 | } else { executed 42 times by 2 tests: end of block Executed by:
| 42 | ||||||||||||||||||
223 | y = y->right; | - | ||||||||||||||||||
224 | while (y->left != nullptr)
| 0-112 | ||||||||||||||||||
225 | y = y->left; never executed: y = y->left; | 0 | ||||||||||||||||||
226 | x = y->right; | - | ||||||||||||||||||
227 | } executed 112 times by 1 test: end of block Executed by:
| 112 | ||||||||||||||||||
228 | if (y != z) {
| 112-489 | ||||||||||||||||||
229 | // move y into the position of z | - | ||||||||||||||||||
230 | // adjust size_left so the keys are ok. | - | ||||||||||||||||||
231 | z->size_left += y->size_left; | - | ||||||||||||||||||
232 | SparseArrayNode *n = y->parent(); | - | ||||||||||||||||||
233 | while (n != z) {
| 0-110 | ||||||||||||||||||
234 | n->size_left -= y->size_left; | - | ||||||||||||||||||
235 | n = n->parent(); | - | ||||||||||||||||||
236 | } never executed: end of block | 0 | ||||||||||||||||||
237 | y->size_left = 0; | - | ||||||||||||||||||
238 | z->value = y->value; | - | ||||||||||||||||||
239 | - | |||||||||||||||||||
240 | if (y != z->right) {
| 0-112 | ||||||||||||||||||
241 | x_parent = y->parent(); | - | ||||||||||||||||||
242 | y->parent()->left = x; | - | ||||||||||||||||||
243 | } else { never executed: end of block | 0 | ||||||||||||||||||
244 | x_parent = z; | - | ||||||||||||||||||
245 | z->right = x; | - | ||||||||||||||||||
246 | } executed 112 times by 1 test: end of block Executed by:
| 112 | ||||||||||||||||||
247 | if (x)
| 8-102 | ||||||||||||||||||
248 | x->setParent(x_parent); executed 8 times by 1 test: x->setParent(x_parent); Executed by:
| 8 | ||||||||||||||||||
249 | } else { executed 110 times by 1 test: end of block Executed by:
| 110 | ||||||||||||||||||
250 | x_parent = y->parent(); | - | ||||||||||||||||||
251 | if (x)
| 52-437 | ||||||||||||||||||
252 | x->setParent(y->parent()); executed 52 times by 2 tests: x->setParent(y->parent()); Executed by:
| 52 | ||||||||||||||||||
253 | if (root == y)
| 197-292 | ||||||||||||||||||
254 | root = x; executed 197 times by 2 tests: root = x; Executed by:
| 197 | ||||||||||||||||||
255 | else if (y->parent()->left == y)
| 60-232 | ||||||||||||||||||
256 | y->parent()->left = x; executed 60 times by 2 tests: y->parent()->left = x; Executed by:
| 60 | ||||||||||||||||||
257 | else | - | ||||||||||||||||||
258 | y->parent()->right = x; executed 232 times by 1 test: y->parent()->right = x; Executed by:
| 232 | ||||||||||||||||||
259 | if (x && x == y->right)
| 10-437 | ||||||||||||||||||
260 | x->size_left += y->size_left; executed 10 times by 2 tests: x->size_left += y->size_left; Executed by:
| 10 | ||||||||||||||||||
261 | y->size_left = 0; | - | ||||||||||||||||||
262 | } executed 490 times by 2 tests: end of block Executed by:
| 490 | ||||||||||||||||||
263 | if (y->color() != SparseArrayNode::Red) {
| 286-314 | ||||||||||||||||||
264 | while (x != root && (x == nullptr || x->color() == SparseArrayNode::Black)) {
| 0-251 | ||||||||||||||||||
265 | if (x == x_parent->left) {
| 10-52 | ||||||||||||||||||
266 | SparseArrayNode *w = x_parent->right; | - | ||||||||||||||||||
267 | if (w->color() == SparseArrayNode::Red) {
| 0-10 | ||||||||||||||||||
268 | w->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
269 | x_parent->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
270 | rotateLeft(x_parent); | - | ||||||||||||||||||
271 | w = x_parent->right; | - | ||||||||||||||||||
272 | } never executed: end of block | 0 | ||||||||||||||||||
273 | if ((w->left == nullptr || w->left->color() == SparseArrayNode::Black) &&
| 0-10 | ||||||||||||||||||
274 | (w->right == nullptr || w->right->color() == SparseArrayNode::Black)) {
| 0-6 | ||||||||||||||||||
275 | w->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
276 | x = x_parent; | - | ||||||||||||||||||
277 | x_parent = x_parent->parent(); | - | ||||||||||||||||||
278 | } else { executed 4 times by 1 test: end of block Executed by:
| 4 | ||||||||||||||||||
279 | if (w->right == nullptr || w->right->color() == SparseArrayNode::Black) {
| 0-6 | ||||||||||||||||||
280 | if (w->left)
| 0 | ||||||||||||||||||
281 | w->left->setColor(SparseArrayNode::Black); never executed: w->left->setColor(SparseArrayNode::Black); | 0 | ||||||||||||||||||
282 | w->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
283 | rotateRight(w); | - | ||||||||||||||||||
284 | w = x_parent->right; | - | ||||||||||||||||||
285 | } never executed: end of block | 0 | ||||||||||||||||||
286 | w->setColor(x_parent->color()); | - | ||||||||||||||||||
287 | x_parent->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
288 | if (w->right)
| 0-6 | ||||||||||||||||||
289 | w->right->setColor(SparseArrayNode::Black); executed 6 times by 1 test: w->right->setColor(SparseArrayNode::Black); Executed by:
| 6 | ||||||||||||||||||
290 | rotateLeft(x_parent); | - | ||||||||||||||||||
291 | break; executed 6 times by 1 test: break; Executed by:
| 6 | ||||||||||||||||||
292 | } | - | ||||||||||||||||||
293 | } else { | - | ||||||||||||||||||
294 | SparseArrayNode *w = x_parent->left; | - | ||||||||||||||||||
295 | if (w->color() == SparseArrayNode::Red) {
| 0-52 | ||||||||||||||||||
296 | w->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
297 | x_parent->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
298 | rotateRight(x_parent); | - | ||||||||||||||||||
299 | w = x_parent->left; | - | ||||||||||||||||||
300 | } never executed: end of block | 0 | ||||||||||||||||||
301 | if ((w->right == nullptr || w->right->color() == SparseArrayNode::Black) &&
| 0-52 | ||||||||||||||||||
302 | (w->left == nullptr || w->left->color() == SparseArrayNode::Black)) {
| 0-52 | ||||||||||||||||||
303 | w->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
304 | x = x_parent; | - | ||||||||||||||||||
305 | x_parent = x_parent->parent(); | - | ||||||||||||||||||
306 | } else { executed 52 times by 1 test: end of block Executed by:
| 52 | ||||||||||||||||||
307 | if (w->left == nullptr || w->left->color() == SparseArrayNode::Black) {
| 0 | ||||||||||||||||||
308 | if (w->right)
| 0 | ||||||||||||||||||
309 | w->right->setColor(SparseArrayNode::Black); never executed: w->right->setColor(SparseArrayNode::Black); | 0 | ||||||||||||||||||
310 | w->setColor(SparseArrayNode::Red); | - | ||||||||||||||||||
311 | rotateLeft(w); | - | ||||||||||||||||||
312 | w = x_parent->left; | - | ||||||||||||||||||
313 | } never executed: end of block | 0 | ||||||||||||||||||
314 | w->setColor(x_parent->color()); | - | ||||||||||||||||||
315 | x_parent->setColor(SparseArrayNode::Black); | - | ||||||||||||||||||
316 | if (w->left)
| 0 | ||||||||||||||||||
317 | w->left->setColor(SparseArrayNode::Black); never executed: w->left->setColor(SparseArrayNode::Black); | 0 | ||||||||||||||||||
318 | rotateRight(x_parent); | - | ||||||||||||||||||
319 | break; never executed: break; | 0 | ||||||||||||||||||
320 | } | - | ||||||||||||||||||
321 | } | - | ||||||||||||||||||
322 | } | - | ||||||||||||||||||
323 | if (x)
| 116-168 | ||||||||||||||||||
324 | x->setColor(SparseArrayNode::Black); executed 116 times by 2 tests: x->setColor(SparseArrayNode::Black); Executed by:
| 116 | ||||||||||||||||||
325 | } executed 284 times by 2 tests: end of block Executed by:
| 284 | ||||||||||||||||||
326 | free(y); | - | ||||||||||||||||||
327 | --numEntries; | - | ||||||||||||||||||
328 | } executed 601 times by 2 tests: end of block Executed by:
| 601 | ||||||||||||||||||
329 | - | |||||||||||||||||||
330 | void SparseArray::recalcMostLeftNode() | - | ||||||||||||||||||
331 | { | - | ||||||||||||||||||
332 | mostLeftNode = &header; | - | ||||||||||||||||||
333 | while (mostLeftNode->left)
| 0 | ||||||||||||||||||
334 | mostLeftNode = mostLeftNode->left; never executed: mostLeftNode = mostLeftNode->left; | 0 | ||||||||||||||||||
335 | } never executed: end of block | 0 | ||||||||||||||||||
336 | - | |||||||||||||||||||
337 | static inline int qMapAlignmentThreshold() | - | ||||||||||||||||||
338 | { | - | ||||||||||||||||||
339 | // malloc on 32-bit platforms should return pointers that are 8-byte | - | ||||||||||||||||||
340 | // aligned or more while on 64-bit platforms they should be 16-byte aligned | - | ||||||||||||||||||
341 | // or more | - | ||||||||||||||||||
342 | return 2 * sizeof(void*); executed 11918 times by 2 tests: return 2 * sizeof(void*); Executed by:
| 11918 | ||||||||||||||||||
343 | } | - | ||||||||||||||||||
344 | - | |||||||||||||||||||
345 | static inline void *qMapAllocate(int alloc, int alignment) | - | ||||||||||||||||||
346 | { | - | ||||||||||||||||||
347 | return alignment > qMapAlignmentThreshold() executed 6243 times by 2 tests: return alignment > qMapAlignmentThreshold() ? qMallocAligned(alloc, alignment) : ::malloc(alloc); Executed by:
| 6243 | ||||||||||||||||||
348 | ? qMallocAligned(alloc, alignment) executed 6243 times by 2 tests: return alignment > qMapAlignmentThreshold() ? qMallocAligned(alloc, alignment) : ::malloc(alloc); Executed by:
| 6243 | ||||||||||||||||||
349 | : ::malloc(alloc); executed 6243 times by 2 tests: return alignment > qMapAlignmentThreshold() ? qMallocAligned(alloc, alignment) : ::malloc(alloc); Executed by:
| 6243 | ||||||||||||||||||
350 | } | - | ||||||||||||||||||
351 | - | |||||||||||||||||||
352 | static inline void qMapDeallocate(SparseArrayNode *node, int alignment) | - | ||||||||||||||||||
353 | { | - | ||||||||||||||||||
354 | if (alignment > qMapAlignmentThreshold())
| 0-5673 | ||||||||||||||||||
355 | qFreeAligned(node); never executed: qFreeAligned(node); | 0 | ||||||||||||||||||
356 | else | - | ||||||||||||||||||
357 | ::free(node); executed 5673 times by 2 tests: ::free(node); Executed by:
| 5673 | ||||||||||||||||||
358 | } | - | ||||||||||||||||||
359 | - | |||||||||||||||||||
360 | SparseArrayNode *SparseArray::createNode(uint sl, SparseArrayNode *parent, bool left) | - | ||||||||||||||||||
361 | { | - | ||||||||||||||||||
362 | SparseArrayNode *node = static_cast<SparseArrayNode *>(qMapAllocate(sizeof(SparseArrayNode), Q_ALIGNOF(SparseArrayNode))); | - | ||||||||||||||||||
363 | Q_CHECK_PTR(node); never executed: qt_check_pointer(__FILE__,363);
| 0-6261 | ||||||||||||||||||
364 | - | |||||||||||||||||||
365 | node->p = (quintptr)parent; | - | ||||||||||||||||||
366 | node->left = nullptr; | - | ||||||||||||||||||
367 | node->right = nullptr; | - | ||||||||||||||||||
368 | node->size_left = sl; | - | ||||||||||||||||||
369 | node->value = UINT_MAX; | - | ||||||||||||||||||
370 | ++numEntries; | - | ||||||||||||||||||
371 | - | |||||||||||||||||||
372 | if (parent) {
| 0-6265 | ||||||||||||||||||
373 | if (left) {
| 2596-3668 | ||||||||||||||||||
374 | parent->left = node; | - | ||||||||||||||||||
375 | if (parent == mostLeftNode)
| 220-3445 | ||||||||||||||||||
376 | mostLeftNode = node; executed 3441 times by 2 tests: mostLeftNode = node; Executed by:
| 3441 | ||||||||||||||||||
377 | } else { executed 3670 times by 2 tests: end of block Executed by:
| 3670 | ||||||||||||||||||
378 | parent->right = node; | - | ||||||||||||||||||
379 | } executed 2595 times by 2 tests: end of block Executed by:
| 2595 | ||||||||||||||||||
380 | node->setParent(parent); | - | ||||||||||||||||||
381 | rebalance(node); | - | ||||||||||||||||||
382 | } executed 6254 times by 2 tests: end of block Executed by:
| 6254 | ||||||||||||||||||
383 | return node; executed 6260 times by 2 tests: return node; Executed by:
| 6260 | ||||||||||||||||||
384 | } | - | ||||||||||||||||||
385 | - | |||||||||||||||||||
386 | void SparseArray::freeTree(SparseArrayNode *root, int alignment) | - | ||||||||||||||||||
387 | { | - | ||||||||||||||||||
388 | if (root->left)
| 1376-4298 | ||||||||||||||||||
389 | freeTree(root->left, alignment); executed 1376 times by 2 tests: freeTree(root->left, alignment); Executed by:
| 1376 | ||||||||||||||||||
390 | if (root->right)
| 1354-4319 | ||||||||||||||||||
391 | freeTree(root->right, alignment); executed 1354 times by 2 tests: freeTree(root->right, alignment); Executed by:
| 1354 | ||||||||||||||||||
392 | qMapDeallocate(root, alignment); | - | ||||||||||||||||||
393 | } executed 5674 times by 2 tests: end of block Executed by:
| 5674 | ||||||||||||||||||
394 | - | |||||||||||||||||||
395 | SparseArray::SparseArray() | - | ||||||||||||||||||
396 | : numEntries(0) | - | ||||||||||||||||||
397 | { | - | ||||||||||||||||||
398 | freeList = Encode(-1); | - | ||||||||||||||||||
399 | header.p = 0; | - | ||||||||||||||||||
400 | header.left = nullptr; | - | ||||||||||||||||||
401 | header.right = nullptr; | - | ||||||||||||||||||
402 | mostLeftNode = &header; | - | ||||||||||||||||||
403 | } executed 3171 times by 2 tests: end of block Executed by:
| 3171 | ||||||||||||||||||
404 | - | |||||||||||||||||||
405 | SparseArray::SparseArray(const SparseArray &other) | - | ||||||||||||||||||
406 | { | - | ||||||||||||||||||
407 | header.p = 0; | - | ||||||||||||||||||
408 | header.right = nullptr; | - | ||||||||||||||||||
409 | if (other.header.left) {
| 0 | ||||||||||||||||||
410 | header.left = other.header.left->copy(this); | - | ||||||||||||||||||
411 | header.left->setParent(&header); | - | ||||||||||||||||||
412 | recalcMostLeftNode(); | - | ||||||||||||||||||
413 | } never executed: end of block | 0 | ||||||||||||||||||
414 | freeList = other.freeList; | - | ||||||||||||||||||
415 | } never executed: end of block | 0 | ||||||||||||||||||
416 | - | |||||||||||||||||||
417 | SparseArrayNode *SparseArray::insert(uint akey) | - | ||||||||||||||||||
418 | { | - | ||||||||||||||||||
419 | SparseArrayNode *n = root(); | - | ||||||||||||||||||
420 | SparseArrayNode *y = end(); | - | ||||||||||||||||||
421 | bool left = true; | - | ||||||||||||||||||
422 | uint s = akey; | - | ||||||||||||||||||
423 | while (n) {
| 6235-12552 | ||||||||||||||||||
424 | y = n; | - | ||||||||||||||||||
425 | if (s == n->size_left) {
| 5093-7458 | ||||||||||||||||||
426 | return n; executed 5095 times by 1 test: return n; Executed by:
| 5095 | ||||||||||||||||||
427 | } else if (s < n->size_left) {
| 1693-5768 | ||||||||||||||||||
428 | left = true; | - | ||||||||||||||||||
429 | n = n->left; | - | ||||||||||||||||||
430 | } else { executed 1693 times by 2 tests: end of block Executed by:
| 1693 | ||||||||||||||||||
431 | left = false; | - | ||||||||||||||||||
432 | s -= n->size_left; | - | ||||||||||||||||||
433 | n = n->right; | - | ||||||||||||||||||
434 | } executed 5768 times by 2 tests: end of block Executed by:
| 5768 | ||||||||||||||||||
435 | } | - | ||||||||||||||||||
436 | - | |||||||||||||||||||
437 | return createNode(s, y, left); executed 6247 times by 2 tests: return createNode(s, y, left); Executed by:
| 6247 | ||||||||||||||||||
438 | } | - | ||||||||||||||||||
Source code | Switch to Preprocessed file |