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; |
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 | |
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 | |
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(); |
148 | ~SparseArray() { |
149 | if (root()) |
150 | freeTree(root: 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 ; |
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 | |
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 | |
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 | |
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 | |
230 | inline 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 | |
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(akey: 0); |
257 | n->value = value; |
258 | } |
259 | |
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(akey: len - 1); |
267 | if (n) { |
268 | idx = n->value; |
269 | deleteNode(z: n); |
270 | } |
271 | return idx; |
272 | } |
273 | |
274 | inline 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 |
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 | |
302 | inline 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 | |
312 | inline 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 | |
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 | |
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 | |
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 | |
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 | |