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
65 QT_BEGIN_NAMESPACE
66
67 namespace QV4 {
68
69 struct SparseArray;
70
71 struct 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;
nextNodeSparseArrayNode83 SparseArrayNode *nextNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->nextNode()); }
84 const SparseArrayNode *previousNode() const;
previousNodeSparseArrayNode85 SparseArrayNode *previousNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode()); }
86
colorSparseArrayNode87 Color color() const { return Color(p & 1); }
setColorSparseArrayNode88 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
parentSparseArrayNode89 SparseArrayNode *parent() const { return reinterpret_cast<SparseArrayNode *>(p & ~Mask); }
setParentSparseArrayNode90 void setParent(SparseArrayNode *pp) { p = (p & Mask) | quintptr(pp); }
91
keySparseArrayNode92 uint key() const {
93 uint k = size_left;
94 const SparseArrayNode *n = this;
95 while (SparseArrayNode *p = n->parent()) {
96 if (p && p->right == n)
97 k += p->size_left;
98 n = p;
99 }
100 return k;
101 }
102
103 SparseArrayNode *copy(SparseArray *d) const;
104
105 SparseArrayNode *lowerBound(uint key);
106 SparseArrayNode *upperBound(uint key);
107 };
108
109
lowerBound(uint akey)110 inline SparseArrayNode *SparseArrayNode::lowerBound(uint akey)
111 {
112 SparseArrayNode *n = this;
113 SparseArrayNode *last = nullptr;
114 while (n) {
115 if (akey <= n->size_left) {
116 last = n;
117 n = n->left;
118 } else {
119 akey -= n->size_left;
120 n = n->right;
121 }
122 }
123 return last;
124 }
125
126
upperBound(uint akey)127 inline SparseArrayNode *SparseArrayNode::upperBound(uint akey)
128 {
129 SparseArrayNode *n = this;
130 SparseArrayNode *last = nullptr;
131 while (n) {
132 if (akey < n->size_left) {
133 last = n;
134 n = n->left;
135 } else {
136 akey -= n->size_left;
137 n = n->right;
138 }
139 }
140 return last;
141 }
142
143
144
145 struct Q_QML_EXPORT SparseArray
146 {
147 SparseArray();
~SparseArraySparseArray148 ~SparseArray() {
149 if (root())
150 freeTree(header.left, Q_ALIGNOF(SparseArrayNode));
151 }
152
153 SparseArray(const SparseArray &other);
154
155 Value freeList;
156 private:
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
rootSparseArray168 SparseArrayNode *root() const { return header.left; }
169
170 void deleteNode(SparseArrayNode *z);
171
172
173 public:
174 SparseArrayNode *createNode(uint sl, SparseArrayNode *parent, bool left);
175 void freeTree(SparseArrayNode *root, int alignment);
176
177 SparseArrayNode *findNode(uint akey) const;
178
nEntriesSparseArray179 uint nEntries() const { return numEntries; }
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
endSparseArray188 const SparseArrayNode *end() const { return &header; }
endSparseArray189 SparseArrayNode *end() { return &header; }
beginSparseArray190 const SparseArrayNode *begin() const { if (root()) return mostLeftNode; return end(); }
beginSparseArray191 SparseArrayNode *begin() { if (root()) return mostLeftNode; return end(); }
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
findNode(uint akey)212 inline SparseArrayNode *SparseArray::findNode(uint akey) const
213 {
214 SparseArrayNode *n = root();
215
216 while (n) {
217 if (akey == n->size_left) {
218 return n;
219 } else if (akey < n->size_left) {
220 n = n->left;
221 } else {
222 akey -= n->size_left;
223 n = n->right;
224 }
225 }
226
227 return nullptr;
228 }
229
pop_front()230 inline uint SparseArray::pop_front()
231 {
232 uint idx = UINT_MAX ;
233
234 SparseArrayNode *n = findNode(0);
235 if (n) {
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) {
241 n->size_left -= 1;
242 n = n->left;
243 }
244 }
245 return idx;
246 }
247
push_front(uint value)248 inline 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) {
253 n->size_left += 1;
254 n = n->left;
255 }
256 n = insert(0);
257 n->value = value;
258 }
259
pop_back(uint len)260 inline uint SparseArray::pop_back(uint len)
261 {
262 uint idx = UINT_MAX;
263 if (!len)
264 return idx;
265
266 SparseArrayNode *n = findNode(len - 1);
267 if (n) {
268 idx = n->value;
269 deleteNode(n);
270 }
271 return idx;
272 }
273
push_back(uint index,uint len)274 inline void SparseArray::push_back(uint index, uint len)
275 {
276 SparseArrayNode *n = insert(len);
277 n->value = index;
278 }
279
280 #ifdef Q_MAP_DEBUG
dump()281 inline 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
erase(SparseArrayNode * n)302 inline SparseArrayNode *SparseArray::erase(SparseArrayNode *n)
303 {
304 if (n == end())
305 return n;
306
307 SparseArrayNode *next = n->nextNode();
308 deleteNode(n);
309 return next;
310 }
311
keys()312 inline QList<int> SparseArray::keys() const
313 {
314 QList<int> res;
315 res.reserve(numEntries);
316 SparseArrayNode *n = mostLeftNode;
317 while (n != end()) {
318 res.append(n->key());
319 n = n->nextNode();
320 }
321 return res;
322 }
323
lowerBound(uint akey)324 inline const SparseArrayNode *SparseArray::lowerBound(uint akey) const
325 {
326 const SparseArrayNode *lb = root()->lowerBound(akey);
327 if (!lb)
328 lb = end();
329 return lb;
330 }
331
332
lowerBound(uint akey)333 inline SparseArrayNode *SparseArray::lowerBound(uint akey)
334 {
335 SparseArrayNode *lb = root()->lowerBound(akey);
336 if (!lb)
337 lb = end();
338 return lb;
339 }
340
341
upperBound(uint akey)342 inline const SparseArrayNode *SparseArray::upperBound(uint akey) const
343 {
344 const SparseArrayNode *ub = root()->upperBound(akey);
345 if (!ub)
346 ub = end();
347 return ub;
348 }
349
350
upperBound(uint akey)351 inline SparseArrayNode *SparseArray::upperBound(uint akey)
352 {
353 SparseArrayNode *ub = root()->upperBound(akey);
354 if (!ub)
355 ub = end();
356 return ub;
357 }
358
359 }
360
361 QT_END_NAMESPACE
362
363 #endif
364