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 | |
29 | QT_BEGIN_NAMESPACE |
30 | |
31 | namespace QV4 { |
32 | |
33 | struct SparseArray; |
34 | |
35 | struct 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 | |
74 | inline 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 | |
91 | inline 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 | |
109 | struct Q_QML_EXPORT SparseArray |
110 | { |
111 | SparseArray(); |
112 | ~SparseArray() { |
113 | if (root()) |
114 | freeTree(root: header.left, alignment: alignof(SparseArrayNode)); |
115 | } |
116 | |
117 | SparseArray(const SparseArray &other); |
118 | |
119 | Value freeList; |
120 | private: |
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 | |
137 | public: |
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 | |
176 | inline 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 | |
194 | inline 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 | |
212 | inline 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 | |
224 | inline 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 | |
238 | inline 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 |
245 | inline 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 | |
266 | inline 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 | |
276 | inline 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 | |
288 | inline const SparseArrayNode *SparseArray::lowerBound(uint akey) const |
289 | { |
290 | const SparseArrayNode *lb = root()->lowerBound(akey); |
291 | if (!lb) |
292 | lb = end(); |
293 | return lb; |
294 | } |
295 | |
296 | |
297 | inline SparseArrayNode *SparseArray::lowerBound(uint akey) |
298 | { |
299 | SparseArrayNode *lb = root()->lowerBound(akey); |
300 | if (!lb) |
301 | lb = end(); |
302 | return lb; |
303 | } |
304 | |
305 | |
306 | inline const SparseArrayNode *SparseArray::upperBound(uint akey) const |
307 | { |
308 | const SparseArrayNode *ub = root()->upperBound(akey); |
309 | if (!ub) |
310 | ub = end(); |
311 | return ub; |
312 | } |
313 | |
314 | |
315 | inline SparseArrayNode *SparseArray::upperBound(uint akey) |
316 | { |
317 | SparseArrayNode *ub = root()->upperBound(akey); |
318 | if (!ub) |
319 | ub = end(); |
320 | return ub; |
321 | } |
322 | |
323 | } |
324 | |
325 | QT_END_NAMESPACE |
326 | |
327 | #endif |
328 |