OpenCoverage

qv4sparsearray_p.h

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/qtdeclarative/src/qtdeclarative/src/qml/jsruntime/qv4sparsearray_p.h
Source codeSwitch to Preprocessed file
LineSourceCount
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#ifndef QV4SPARSEARRAY_H-
41#define QV4SPARSEARRAY_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 "qv4global_p.h"-
55#include "qv4value_p.h"-
56#include <QtCore/qlist.h>-
57-
58//#define Q_MAP_DEBUG-
59#ifdef Q_MAP_DEBUG-
60#include <QtCore/qdebug.h>-
61#endif-
62-
63#include <new>-
64-
65QT_BEGIN_NAMESPACE-
66-
67namespace QV4 {-
68-
69struct SparseArray;-
70-
71struct SparseArrayNode-
72{-
73 quintptr p;-
74 SparseArrayNode *left;-
75 SparseArrayNode *right;-
76 uint size_left;-
77 uint value;-
78-
79 enum Color { Red = 0, Black = 1 };-
80 enum { Mask = 3 }; // reserve the second bit as well-
81-
82 const SparseArrayNode *nextNode() const;-
83 SparseArrayNode *nextNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->nextNode()); }
executed 1549 times by 2 tests: return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->nextNode());
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
1549
84 const SparseArrayNode *previousNode() const;-
85 SparseArrayNode *previousNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode()); }
executed 362 times by 1 test: return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode());
Executed by:
  • tst_ecmascripttests
362
86-
87 Color color() const { return Color(p & 1); }
executed 5531 times by 2 tests: return Color(p & 1);
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
5531
88 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
executed 8308 times by 2 tests: p |= Black;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
executed 7823 times by 2 tests: p &= ~Black;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
c == BlackDescription
TRUEevaluated 8309 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 7821 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
7821-8309
89 SparseArrayNode *parent() const { return reinterpret_cast<SparseArrayNode *>(p & ~Mask); }
executed 28724 times by 2 tests: return reinterpret_cast<SparseArrayNode *>(p & ~Mask);
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
28724
90 void setParent(SparseArrayNode *pp) { p = (p & Mask) | quintptr(pp); }
executed 8948 times by 2 tests: end of block
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
8948
91-
92 uint key() const {-
93 uint k = size_left;-
94 const SparseArrayNode *n = this;-
95 while (SparseArrayNode *p = n->parent()) {
SparseArrayNod... = n->parent()Description
TRUEevaluated 1459 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 1004 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
1004-1459
96 if (p && p->right == n)
pDescription
TRUEevaluated 1459 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEnever evaluated
p->right == nDescription
TRUEevaluated 240 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 1219 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
0-1459
97 k += p->size_left;
executed 240 times by 2 tests: k += p->size_left;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
240
98 n = p;-
99 }
executed 1460 times by 2 tests: end of block
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
1460
100 return k;
executed 1005 times by 2 tests: return k;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
1005
101 }-
102-
103 SparseArrayNode *copy(SparseArray *d) const;-
104-
105 SparseArrayNode *lowerBound(uint key);-
106 SparseArrayNode *upperBound(uint key);-
107};-
108-
109-
110inline SparseArrayNode *SparseArrayNode::lowerBound(uint akey)-
111{-
112 SparseArrayNode *n = this;-
113 SparseArrayNode *last = nullptr;-
114 while (n) {
nDescription
TRUEevaluated 352 times by 1 test
Evaluated by:
  • tst_ecmascripttests
FALSEevaluated 158 times by 1 test
Evaluated by:
  • tst_ecmascripttests
158-352
115 if (akey <= n->size_left) {
akey <= n->size_leftDescription
TRUEevaluated 170 times by 1 test
Evaluated by:
  • tst_ecmascripttests
FALSEevaluated 182 times by 1 test
Evaluated by:
  • tst_ecmascripttests
170-182
116 last = n;-
117 n = n->left;-
118 } else {
executed 170 times by 1 test: end of block
Executed by:
  • tst_ecmascripttests
170
119 akey -= n->size_left;-
120 n = n->right;-
121 }
executed 182 times by 1 test: end of block
Executed by:
  • tst_ecmascripttests
182
122 }-
123 return last;
executed 158 times by 1 test: return last;
Executed by:
  • tst_ecmascripttests
158
124}-
125-
126-
127inline SparseArrayNode *SparseArrayNode::upperBound(uint akey)-
128{-
129 SparseArrayNode *n = this;-
130 SparseArrayNode *last = nullptr;-
131 while (n) {
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
132 if (akey < n->size_left) {
akey < n->size_leftDescription
TRUEnever evaluated
FALSEnever evaluated
0
133 last = n;-
134 n = n->left;-
135 } else {
never executed: end of block
0
136 akey -= n->size_left;-
137 n = n->right;-
138 }
never executed: end of block
0
139 }-
140 return last;
never executed: return last;
0
141}-
142-
143-
144-
145struct Q_QML_EXPORT SparseArray-
146{-
147 SparseArray();-
148 ~SparseArray() {-
149 if (root())
root()Description
TRUEevaluated 2944 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 262 times by 1 test
Evaluated by:
  • tst_ecmascripttests
262-2944
150 freeTree(header.left, Q_ALIGNOF(SparseArrayNode));
executed 2944 times by 2 tests: freeTree(header.left, alignof(SparseArrayNode));
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
2944
151 }
executed 3206 times by 2 tests: end of block
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
3206
152-
153 SparseArray(const SparseArray &other);-
154-
155 Value freeList;-
156private:-
157 SparseArray &operator=(const SparseArray &other);-
158-
159 int numEntries;-
160 SparseArrayNode header;-
161 SparseArrayNode *mostLeftNode;-
162-
163 void rotateLeft(SparseArrayNode *x);-
164 void rotateRight(SparseArrayNode *x);-
165 void rebalance(SparseArrayNode *x);-
166 void recalcMostLeftNode();-
167-
168 SparseArrayNode *root() const { return header.left; }
executed 27376298 times by 2 tests: return header.left;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
27376298
169-
170 void deleteNode(SparseArrayNode *z);-
171-
172-
173public:-
174 SparseArrayNode *createNode(uint sl, SparseArrayNode *parent, bool left);-
175 void freeTree(SparseArrayNode *root, int alignment);-
176-
177 SparseArrayNode *findNode(uint akey) const;-
178-
179 uint nEntries() const { return numEntries; }
never executed: return numEntries;
0
180-
181 uint pop_front();-
182 void push_front(uint at);-
183 uint pop_back(uint len);-
184 void push_back(uint at, uint len);-
185-
186 QList<int> keys() const;-
187-
188 const SparseArrayNode *end() const { return &header; }
never executed: return &header;
0
189 SparseArrayNode *end() { return &header; }
executed 13756 times by 2 tests: return &header;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
13756
190 const SparseArrayNode *begin() const { if (root()) return mostLeftNode; return end(); }
never executed: return mostLeftNode;
never executed: return end();
root()Description
TRUEnever evaluated
FALSEnever evaluated
0
191 SparseArrayNode *begin() { if (root()) return mostLeftNode; return end(); }
executed 613 times by 2 tests: return mostLeftNode;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
executed 38 times by 1 test: return end();
Executed by:
  • tst_ecmascripttests
root()Description
TRUEevaluated 613 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 38 times by 1 test
Evaluated by:
  • tst_ecmascripttests
38-613
192-
193 SparseArrayNode *erase(SparseArrayNode *n);-
194-
195 SparseArrayNode *lowerBound(uint key);-
196 const SparseArrayNode *lowerBound(uint key) const;-
197 SparseArrayNode *upperBound(uint key);-
198 const SparseArrayNode *upperBound(uint key) const;-
199 SparseArrayNode *insert(uint akey);-
200-
201 // STL compatibility-
202 typedef uint key_type;-
203 typedef int mapped_type;-
204 typedef qptrdiff difference_type;-
205 typedef int size_type;-
206-
207#ifdef Q_MAP_DEBUG-
208 void dump() const;-
209#endif-
210};-
211-
212inline SparseArrayNode *SparseArray::findNode(uint akey) const-
213{-
214 SparseArrayNode *n = root();-
215-
216 while (n) {
nDescription
TRUEevaluated 101893349 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 27363093 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
27363093-101893349
217 if (akey == n->size_left) {
akey == n->size_leftDescription
TRUEevaluated 23275 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 101877363 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
23275-101877363
218 return n;
executed 23278 times by 2 tests: return n;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
23278
219 } else if (akey < n->size_left) {
akey < n->size_leftDescription
TRUEevaluated 27676901 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
FALSEevaluated 74260435 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
27676901-74260435
220 n = n->left;-
221 } else {
executed 27679471 times by 2 tests: end of block
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
27679471
222 akey -= n->size_left;-
223 n = n->right;-
224 }
executed 74263779 times by 2 tests: end of block
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
74263779
225 }-
226-
227 return nullptr;
executed 27369006 times by 2 tests: return nullptr;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
27369006
228}-
229-
230inline uint SparseArray::pop_front()-
231{-
232 uint idx = UINT_MAX ;-
233-
234 SparseArrayNode *n = findNode(0);-
235 if (n) {
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
236 idx = n->value;-
237 deleteNode(n);-
238 // adjust all size_left indices on the path to leftmost item by 1-
239 SparseArrayNode *n = root();-
240 while (n) {
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
241 n->size_left -= 1;-
242 n = n->left;-
243 }
never executed: end of block
0
244 }
never executed: end of block
0
245 return idx;
never executed: return idx;
0
246}-
247-
248inline void SparseArray::push_front(uint value)-
249{-
250 // adjust all size_left indices on the path to leftmost item by 1-
251 SparseArrayNode *n = root();-
252 while (n) {
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
253 n->size_left += 1;-
254 n = n->left;-
255 }
never executed: end of block
0
256 n = insert(0);-
257 n->value = value;-
258}
never executed: end of block
0
259-
260inline uint SparseArray::pop_back(uint len)-
261{-
262 uint idx = UINT_MAX;-
263 if (!len)
!lenDescription
TRUEnever evaluated
FALSEnever evaluated
0
264 return idx;
never executed: return idx;
0
265-
266 SparseArrayNode *n = findNode(len - 1);-
267 if (n) {
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
268 idx = n->value;-
269 deleteNode(n);-
270 }
never executed: end of block
0
271 return idx;
never executed: return idx;
0
272}-
273-
274inline void SparseArray::push_back(uint index, uint len)-
275{-
276 SparseArrayNode *n = insert(len);-
277 n->value = index;-
278}
never executed: end of block
0
279-
280#ifdef Q_MAP_DEBUG-
281inline void SparseArray::dump() const-
282{-
283 const SparseArrayNode *it = begin();-
284 qDebug() << "map dump:";-
285 while (it != end()) {-
286 const SparseArrayNode *n = it;-
287 int depth = 0;-
288 while (n && n != root()) {-
289 ++depth;-
290 n = n->parent();-
291 }-
292 QByteArray space(4*depth, ' ');-
293 qDebug() << space << (it->color() == SparseArrayNode::Red ? "Red " : "Black") << it << it->size_left << it->left << it->right-
294 << it->key() << it->value;-
295 it = it->nextNode();-
296 }-
297 qDebug() << "---------";-
298}-
299#endif-
300-
301-
302inline SparseArrayNode *SparseArray::erase(SparseArrayNode *n)-
303{-
304 if (n == end())
n == end()Description
TRUEnever evaluated
FALSEevaluated 600 times by 2 tests
Evaluated by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
0-600
305 return n;
never executed: return n;
0
306-
307 SparseArrayNode *next = n->nextNode();-
308 deleteNode(n);-
309 return next;
executed 599 times by 2 tests: return next;
Executed by:
  • tst_ecmascripttests
  • tst_qqmlecmascript
599
310}-
311-
312inline QList<int> SparseArray::keys() const-
313{-
314 QList<int> res;-
315 res.reserve(numEntries);-
316 SparseArrayNode *n = mostLeftNode;-
317 while (n != end()) {
n != end()Description
TRUEnever evaluated
FALSEnever evaluated
0
318 res.append(n->key());-
319 n = n->nextNode();-
320 }
never executed: end of block
0
321 return res;
never executed: return res;
0
322}-
323-
324inline const SparseArrayNode *SparseArray::lowerBound(uint akey) const-
325{-
326 const SparseArrayNode *lb = root()->lowerBound(akey);-
327 if (!lb)
!lbDescription
TRUEnever evaluated
FALSEnever evaluated
0
328 lb = end();
never executed: lb = end();
0
329 return lb;
never executed: return lb;
0
330}-
331-
332-
333inline SparseArrayNode *SparseArray::lowerBound(uint akey)-
334{-
335 SparseArrayNode *lb = root()->lowerBound(akey);-
336 if (!lb)
!lbDescription
TRUEnever evaluated
FALSEevaluated 158 times by 1 test
Evaluated by:
  • tst_ecmascripttests
0-158
337 lb = end();
never executed: lb = end();
0
338 return lb;
executed 158 times by 1 test: return lb;
Executed by:
  • tst_ecmascripttests
158
339}-
340-
341-
342inline const SparseArrayNode *SparseArray::upperBound(uint akey) const-
343{-
344 const SparseArrayNode *ub = root()->upperBound(akey);-
345 if (!ub)
!ubDescription
TRUEnever evaluated
FALSEnever evaluated
0
346 ub = end();
never executed: ub = end();
0
347 return ub;
never executed: return ub;
0
348}-
349-
350-
351inline SparseArrayNode *SparseArray::upperBound(uint akey)-
352{-
353 SparseArrayNode *ub = root()->upperBound(akey);-
354 if (!ub)
!ubDescription
TRUEnever evaluated
FALSEnever evaluated
0
355 ub = end();
never executed: ub = end();
0
356 return ub;
never executed: return ub;
0
357}-
358-
359}-
360-
361QT_END_NAMESPACE-
362-
363#endif-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.0