1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QV4SPARSEARRAY_H
5#define QV4SPARSEARRAY_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include "qv4global_p.h"
19#include "qv4value_p.h"
20#include <QtCore/qlist.h>
21
22//#define Q_MAP_DEBUG
23#ifdef Q_MAP_DEBUG
24#include <QtCore/qdebug.h>
25#endif
26
27#include <new>
28
29QT_BEGIN_NAMESPACE
30
31namespace QV4 {
32
33struct SparseArray;
34
35struct SparseArrayNode
36{
37 quintptr p;
38 SparseArrayNode *left;
39 SparseArrayNode *right;
40 uint size_left;
41 uint value;
42
43 enum Color { Red = 0, Black = 1 };
44 enum { Mask = 3 }; // reserve the second bit as well
45
46 const SparseArrayNode *nextNode() const;
47 SparseArrayNode *nextNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->nextNode()); }
48 const SparseArrayNode *previousNode() const;
49 SparseArrayNode *previousNode() { return const_cast<SparseArrayNode *>(const_cast<const SparseArrayNode *>(this)->previousNode()); }
50
51 Color color() const { return Color(p & 1); }
52 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
53 SparseArrayNode *parent() const { return reinterpret_cast<SparseArrayNode *>(p & ~Mask); }
54 void setParent(SparseArrayNode *pp) { p = (p & Mask) | quintptr(pp); }
55
56 uint key() const {
57 uint k = size_left;
58 const SparseArrayNode *n = this;
59 while (SparseArrayNode *p = n->parent()) {
60 if (p && p->right == n)
61 k += p->size_left;
62 n = p;
63 }
64 return k;
65 }
66
67 SparseArrayNode *copy(SparseArray *d) const;
68
69 SparseArrayNode *lowerBound(uint key);
70 SparseArrayNode *upperBound(uint key);
71};
72
73
74inline SparseArrayNode *SparseArrayNode::lowerBound(uint akey)
75{
76 SparseArrayNode *n = this;
77 SparseArrayNode *last = nullptr;
78 while (n) {
79 if (akey <= n->size_left) {
80 last = n;
81 n = n->left;
82 } else {
83 akey -= n->size_left;
84 n = n->right;
85 }
86 }
87 return last;
88}
89
90
91inline SparseArrayNode *SparseArrayNode::upperBound(uint akey)
92{
93 SparseArrayNode *n = this;
94 SparseArrayNode *last = nullptr;
95 while (n) {
96 if (akey < n->size_left) {
97 last = n;
98 n = n->left;
99 } else {
100 akey -= n->size_left;
101 n = n->right;
102 }
103 }
104 return last;
105}
106
107
108
109struct Q_QML_EXPORT SparseArray
110{
111 SparseArray();
112 ~SparseArray() {
113 if (SparseArrayNode *n = root())
114 freeTree(root: n, alignment: alignof(SparseArrayNode));
115 }
116
117 SparseArray(const SparseArray &other);
118
119 Value freeList;
120private:
121 SparseArray &operator=(const SparseArray &other);
122
123 int numEntries;
124 SparseArrayNode header;
125 SparseArrayNode *mostLeftNode;
126
127 void rotateLeft(SparseArrayNode *x);
128 void rotateRight(SparseArrayNode *x);
129 void rebalance(SparseArrayNode *x);
130 void recalcMostLeftNode();
131
132 SparseArrayNode *root() const { return header.left; }
133
134 void deleteNode(SparseArrayNode *z);
135
136
137public:
138 SparseArrayNode *createNode(uint sl, SparseArrayNode *parent, bool left);
139 void freeTree(SparseArrayNode *root, int alignment);
140
141 SparseArrayNode *findNode(uint akey) const;
142
143 uint nEntries() const { return numEntries; }
144
145 uint pop_front();
146 void push_front(uint at);
147 uint pop_back(uint len);
148 void push_back(uint at, uint len);
149
150 QList<int> keys() const;
151
152 const SparseArrayNode *end() const { return &header; }
153 SparseArrayNode *end() { return &header; }
154 const SparseArrayNode *begin() const { if (root()) return mostLeftNode; return end(); }
155 SparseArrayNode *begin() { if (root()) return mostLeftNode; return end(); }
156
157 SparseArrayNode *erase(SparseArrayNode *n);
158
159 SparseArrayNode *lowerBound(uint key);
160 const SparseArrayNode *lowerBound(uint key) const;
161 SparseArrayNode *upperBound(uint key);
162 const SparseArrayNode *upperBound(uint key) const;
163 SparseArrayNode *insert(uint akey);
164
165 // STL compatibility
166 typedef uint key_type;
167 typedef int mapped_type;
168 typedef qptrdiff difference_type;
169 typedef int size_type;
170
171#ifdef Q_MAP_DEBUG
172 void dump() const;
173#endif
174};
175
176inline SparseArrayNode *SparseArray::findNode(uint akey) const
177{
178 SparseArrayNode *n = root();
179
180 while (n) {
181 if (akey == n->size_left) {
182 return n;
183 } else if (akey < n->size_left) {
184 n = n->left;
185 } else {
186 akey -= n->size_left;
187 n = n->right;
188 }
189 }
190
191 return nullptr;
192}
193
194inline uint SparseArray::pop_front()
195{
196 uint idx = UINT_MAX ;
197
198 SparseArrayNode *n = findNode(akey: 0);
199 if (n) {
200 idx = n->value;
201 deleteNode(z: n);
202 // adjust all size_left indices on the path to leftmost item by 1
203 SparseArrayNode *rootNode = root();
204 while (rootNode) {
205 rootNode->size_left -= 1;
206 rootNode = rootNode->left;
207 }
208 }
209 return idx;
210}
211
212inline void SparseArray::push_front(uint value)
213{
214 // adjust all size_left indices on the path to leftmost item by 1
215 SparseArrayNode *n = root();
216 while (n) {
217 n->size_left += 1;
218 n = n->left;
219 }
220 n = insert(akey: 0);
221 n->value = value;
222}
223
224inline uint SparseArray::pop_back(uint len)
225{
226 uint idx = UINT_MAX;
227 if (!len)
228 return idx;
229
230 SparseArrayNode *n = findNode(akey: len - 1);
231 if (n) {
232 idx = n->value;
233 deleteNode(z: n);
234 }
235 return idx;
236}
237
238inline void SparseArray::push_back(uint index, uint len)
239{
240 SparseArrayNode *n = insert(akey: len);
241 n->value = index;
242}
243
244#ifdef Q_MAP_DEBUG
245inline void SparseArray::dump() const
246{
247 const SparseArrayNode *it = begin();
248 qDebug() << "map dump:";
249 while (it != end()) {
250 const SparseArrayNode *n = it;
251 int depth = 0;
252 while (n && n != root()) {
253 ++depth;
254 n = n->parent();
255 }
256 QByteArray space(4*depth, ' ');
257 qDebug() << space << (it->color() == SparseArrayNode::Red ? "Red " : "Black") << it << it->size_left << it->left << it->right
258 << it->key() << it->value;
259 it = it->nextNode();
260 }
261 qDebug() << "---------";
262}
263#endif
264
265
266inline SparseArrayNode *SparseArray::erase(SparseArrayNode *n)
267{
268 if (n == end())
269 return n;
270
271 SparseArrayNode *next = n->nextNode();
272 deleteNode(z: n);
273 return next;
274}
275
276inline QList<int> SparseArray::keys() const
277{
278 QList<int> res;
279 res.reserve(asize: numEntries);
280 SparseArrayNode *n = mostLeftNode;
281 while (n != end()) {
282 res.append(t: n->key());
283 n = n->nextNode();
284 }
285 return res;
286}
287
288inline const SparseArrayNode *SparseArray::lowerBound(uint akey) const
289{
290 if (SparseArrayNode *n = root()) {
291 if (const SparseArrayNode *lb = n->lowerBound(akey))
292 return lb;
293 }
294
295 return end();
296}
297
298
299inline SparseArrayNode *SparseArray::lowerBound(uint akey)
300{
301 if (SparseArrayNode *n = root()) {
302 if (SparseArrayNode *lb = n->lowerBound(akey))
303 return lb;
304 }
305
306 return end();
307}
308
309
310inline const SparseArrayNode *SparseArray::upperBound(uint akey) const
311{
312 if (SparseArrayNode *n = root()) {
313 if (const SparseArrayNode *ub = n->upperBound(akey))
314 return ub;
315 }
316
317 return end();
318}
319
320
321inline SparseArrayNode *SparseArray::upperBound(uint akey)
322{
323 if (SparseArrayNode *n = root()) {
324 if (SparseArrayNode *ub = n->upperBound(akey))
325 return ub;
326 }
327
328 return end();
329}
330
331}
332
333QT_END_NAMESPACE
334
335#endif
336

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