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()); }
84 const SparseArrayNode *previousNode() const;
85 SparseArrayNode *previousNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode()); }
86
87 Color color() const { return Color(p & 1); }
88 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
89 SparseArrayNode *parent() const { return reinterpret_cast<SparseArrayNode *>(p & ~Mask); }
90 void setParent(SparseArrayNode *pp) { p = (p & Mask) | quintptr(pp); }
91
92 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
110inline 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
127inline 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
145struct Q_QML_EXPORT SparseArray
146{
147 SparseArray();
148 ~SparseArray() {
149 if (root())
150 freeTree(root: header.left, Q_ALIGNOF(SparseArrayNode));
151 }
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; }
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; }
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; }
189 SparseArrayNode *end() { return &header; }
190 const SparseArrayNode *begin() const { if (root()) return mostLeftNode; return end(); }
191 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
212inline 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
230inline uint SparseArray::pop_front()
231{
232 uint idx = UINT_MAX ;
233
234 SparseArrayNode *n = findNode(akey: 0);
235 if (n) {
236 idx = n->value;
237 deleteNode(z: 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
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) {
253 n->size_left += 1;
254 n = n->left;
255 }
256 n = insert(akey: 0);
257 n->value = value;
258}
259
260inline uint SparseArray::pop_back(uint len)
261{
262 uint idx = UINT_MAX;
263 if (!len)
264 return idx;
265
266 SparseArrayNode *n = findNode(akey: len - 1);
267 if (n) {
268 idx = n->value;
269 deleteNode(z: n);
270 }
271 return idx;
272}
273
274inline void SparseArray::push_back(uint index, uint len)
275{
276 SparseArrayNode *n = insert(akey: len);
277 n->value = index;
278}
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())
305 return n;
306
307 SparseArrayNode *next = n->nextNode();
308 deleteNode(z: n);
309 return next;
310}
311
312inline QList<int> SparseArray::keys() const
313{
314 QList<int> res;
315 res.reserve(size: numEntries);
316 SparseArrayNode *n = mostLeftNode;
317 while (n != end()) {
318 res.append(t: n->key());
319 n = n->nextNode();
320 }
321 return res;
322}
323
324inline 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
333inline SparseArrayNode *SparseArray::lowerBound(uint akey)
334{
335 SparseArrayNode *lb = root()->lowerBound(akey);
336 if (!lb)
337 lb = end();
338 return lb;
339}
340
341
342inline 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
351inline 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
361QT_END_NAMESPACE
362
363#endif
364

source code of qtdeclarative/src/qml/jsruntime/qv4sparsearray_p.h