Qt
Internal/Contributor docs for the Qt SDK. <b>Note:</b> These are NOT official API docs; those are found <a href='https://doc.qt.io/'>here</a>.
Loading...
Searching...
No Matches
qv4sparsearray_p.h
Go to the documentation of this file.
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
30
31namespace QV4 {
32
33struct SparseArray;
34
36{
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
68
71};
72
73
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
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();
113 if (SparseArrayNode *n = root())
114 freeTree(n, alignof(SparseArrayNode));
115 }
116
118
120private:
121 SparseArray &operator=(const SparseArray &other);
122
123 int numEntries;
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
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;
164
165 // STL compatibility
166 typedef uint key_type;
167 typedef int mapped_type;
169 typedef int size_type;
170
171#ifdef Q_MAP_DEBUG
172 void dump() const;
173#endif
174};
175
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
195{
196 uint idx = UINT_MAX ;
197
199 if (n) {
200 idx = n->value;
201 deleteNode(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
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(0);
221 n->value = value;
222}
223
225{
226 uint idx = UINT_MAX;
227 if (!len)
228 return idx;
229
231 if (n) {
232 idx = n->value;
233 deleteNode(n);
234 }
235 return idx;
236}
237
239{
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
267{
268 if (n == end())
269 return n;
270
271 SparseArrayNode *next = n->nextNode();
272 deleteNode(n);
273 return next;
274}
275
276inline QList<int> SparseArray::keys() const
277{
278 QList<int> res;
279 res.reserve(numEntries);
280 SparseArrayNode *n = mostLeftNode;
281 while (n != end()) {
282 res.append(n->key());
283 n = n->nextNode();
284 }
285 return res;
286}
287
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
300{
301 if (SparseArrayNode *n = root()) {
302 if (SparseArrayNode *lb = n->lowerBound(akey))
303 return lb;
304 }
305
306 return end();
307}
308
309
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
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
334
335#endif
\inmodule QtCore
Definition qbytearray.h:57
void reserve(qsizetype size)
Definition qlist.h:753
cache insert(employee->id(), employee)
QSet< QString >::iterator it
uint alignment
short next
Definition keywords.cpp:445
Combined button and popup list for selecting options.
qsizetype erase(QByteArray &ba, const T &t)
Definition qbytearray.h:782
static QString header(const QString &name)
EGLOutputLayerEXT EGLint EGLAttrib value
[5]
#define qDebug
[1]
Definition qlogging.h:164
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat z
GLint GLint GLint GLint GLint x
[0]
GLint GLenum GLsizei GLsizei GLsizei depth
GLuint64 key
GLuint index
[2]
GLuint GLuint end
GLint left
GLfloat n
GLuint res
const GLubyte * c
GLfloat GLfloat p
[1]
GLenum GLsizei len
static QString dump(const QByteArray &)
size_t quintptr
Definition qtypes.h:167
ptrdiff_t qptrdiff
Definition qtypes.h:164
unsigned int uint
Definition qtypes.h:34
QStringList keys
QSharedPointer< T > other(t)
[5]
QAction * at
SparseArrayNode * right
SparseArrayNode * left
SparseArrayNode * copy(SparseArray *d) const
SparseArrayNode * lowerBound(uint key)
const SparseArrayNode * previousNode() const
SparseArrayNode * parent() const
SparseArrayNode * nextNode()
SparseArrayNode * upperBound(uint key)
const SparseArrayNode * nextNode() const
SparseArrayNode * previousNode()
void setParent(SparseArrayNode *pp)
SparseArrayNode * upperBound(uint key)
SparseArrayNode * erase(SparseArrayNode *n)
void push_back(uint at, uint len)
SparseArrayNode * lowerBound(uint key)
const SparseArrayNode * begin() const
SparseArrayNode * insert(uint akey)
void push_front(uint at)
uint pop_back(uint len)
QList< int > keys() const
SparseArrayNode * findNode(uint akey) const
SparseArrayNode * begin()
const SparseArrayNode * end() const
SparseArrayNode * end()
uint nEntries() const