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 | #include "qv4sparsearray_p.h" |
41 | #include "qv4runtime_p.h" |
42 | #include "qv4object_p.h" |
43 | #include "qv4functionobject_p.h" |
44 | #include "qv4scopedvalue_p.h" |
45 | #include <stdlib.h> |
46 | |
47 | #ifdef QT_QMAP_DEBUG |
48 | # include <qstring.h> |
49 | # include <qvector.h> |
50 | #endif |
51 | |
52 | using namespace QV4; |
53 | |
54 | const SparseArrayNode *SparseArrayNode::nextNode() const |
55 | { |
56 | const SparseArrayNode *n = this; |
57 | if (n->right) { |
58 | n = n->right; |
59 | while (n->left) |
60 | n = n->left; |
61 | } else { |
62 | const SparseArrayNode *y = n->parent(); |
63 | while (y && n == y->right) { |
64 | n = y; |
65 | y = n->parent(); |
66 | } |
67 | n = y; |
68 | } |
69 | return n; |
70 | } |
71 | |
72 | const SparseArrayNode *SparseArrayNode::previousNode() const |
73 | { |
74 | const SparseArrayNode *n = this; |
75 | if (n->left) { |
76 | n = n->left; |
77 | while (n->right) |
78 | n = n->right; |
79 | } else { |
80 | const SparseArrayNode *y = n->parent(); |
81 | while (y && n == y->left) { |
82 | n = y; |
83 | y = n->parent(); |
84 | } |
85 | n = y; |
86 | } |
87 | return n; |
88 | } |
89 | |
90 | SparseArrayNode *SparseArrayNode::copy(SparseArray *d) const |
91 | { |
92 | SparseArrayNode *n = d->createNode(sl: size_left, parent: nullptr, left: false); |
93 | n->value = value; |
94 | n->setColor(color()); |
95 | if (left) { |
96 | n->left = left->copy(d); |
97 | n->left->setParent(n); |
98 | } else { |
99 | n->left = nullptr; |
100 | } |
101 | if (right) { |
102 | n->right = right->copy(d); |
103 | n->right->setParent(n); |
104 | } else { |
105 | n->right = nullptr; |
106 | } |
107 | return n; |
108 | } |
109 | |
110 | /* |
111 | x y |
112 | \ / \ |
113 | y --> x b |
114 | / \ \ |
115 | a b a |
116 | */ |
117 | void SparseArray::rotateLeft(SparseArrayNode *x) |
118 | { |
119 | SparseArrayNode *&root = header.left; |
120 | SparseArrayNode *y = x->right; |
121 | x->right = y->left; |
122 | if (y->left != nullptr) |
123 | y->left->setParent(x); |
124 | y->setParent(x->parent()); |
125 | if (x == root) |
126 | root = y; |
127 | else if (x == x->parent()->left) |
128 | x->parent()->left = y; |
129 | else |
130 | x->parent()->right = y; |
131 | y->left = x; |
132 | x->setParent(y); |
133 | y->size_left += x->size_left; |
134 | } |
135 | |
136 | |
137 | /* |
138 | x y |
139 | / / \ |
140 | y --> a x |
141 | / \ / |
142 | a b b |
143 | */ |
144 | void SparseArray::rotateRight(SparseArrayNode *x) |
145 | { |
146 | SparseArrayNode *&root = header.left; |
147 | SparseArrayNode *y = x->left; |
148 | x->left = y->right; |
149 | if (y->right != nullptr) |
150 | y->right->setParent(x); |
151 | y->setParent(x->parent()); |
152 | if (x == root) |
153 | root = y; |
154 | else if (x == x->parent()->right) |
155 | x->parent()->right = y; |
156 | else |
157 | x->parent()->left = y; |
158 | y->right = x; |
159 | x->setParent(y); |
160 | x->size_left -= y->size_left; |
161 | } |
162 | |
163 | |
164 | void SparseArray::rebalance(SparseArrayNode *x) |
165 | { |
166 | SparseArrayNode *&root = header.left; |
167 | x->setColor(SparseArrayNode::Red); |
168 | while (x != root && x->parent()->color() == SparseArrayNode::Red) { |
169 | if (x->parent() == x->parent()->parent()->left) { |
170 | SparseArrayNode *y = x->parent()->parent()->right; |
171 | if (y && y->color() == SparseArrayNode::Red) { |
172 | x->parent()->setColor(SparseArrayNode::Black); |
173 | y->setColor(SparseArrayNode::Black); |
174 | x->parent()->parent()->setColor(SparseArrayNode::Red); |
175 | x = x->parent()->parent(); |
176 | } else { |
177 | if (x == x->parent()->right) { |
178 | x = x->parent(); |
179 | rotateLeft(x); |
180 | } |
181 | x->parent()->setColor(SparseArrayNode::Black); |
182 | x->parent()->parent()->setColor(SparseArrayNode::Red); |
183 | rotateRight (x: x->parent()->parent()); |
184 | } |
185 | } else { |
186 | SparseArrayNode *y = x->parent()->parent()->left; |
187 | if (y && y->color() == SparseArrayNode::Red) { |
188 | x->parent()->setColor(SparseArrayNode::Black); |
189 | y->setColor(SparseArrayNode::Black); |
190 | x->parent()->parent()->setColor(SparseArrayNode::Red); |
191 | x = x->parent()->parent(); |
192 | } else { |
193 | if (x == x->parent()->left) { |
194 | x = x->parent(); |
195 | rotateRight(x); |
196 | } |
197 | x->parent()->setColor(SparseArrayNode::Black); |
198 | x->parent()->parent()->setColor(SparseArrayNode::Red); |
199 | rotateLeft(x: x->parent()->parent()); |
200 | } |
201 | } |
202 | } |
203 | root->setColor(SparseArrayNode::Black); |
204 | } |
205 | |
206 | void SparseArray::deleteNode(SparseArrayNode *z) |
207 | { |
208 | SparseArrayNode *&root = header.left; |
209 | SparseArrayNode *y = z; |
210 | SparseArrayNode *x; |
211 | SparseArrayNode *x_parent; |
212 | if (y->left == nullptr) { |
213 | x = y->right; |
214 | if (y == mostLeftNode) { |
215 | if (x) |
216 | mostLeftNode = x; // It cannot have (left) children due the red black invariant. |
217 | else |
218 | mostLeftNode = y->parent(); |
219 | } |
220 | } else if (y->right == nullptr) { |
221 | x = y->left; |
222 | } else { |
223 | y = y->right; |
224 | while (y->left != nullptr) |
225 | y = y->left; |
226 | x = y->right; |
227 | } |
228 | if (y != z) { |
229 | // move y into the position of z |
230 | // adjust size_left so the keys are ok. |
231 | z->size_left += y->size_left; |
232 | SparseArrayNode *n = y->parent(); |
233 | while (n != z) { |
234 | n->size_left -= y->size_left; |
235 | n = n->parent(); |
236 | } |
237 | y->size_left = 0; |
238 | z->value = y->value; |
239 | |
240 | if (y != z->right) { |
241 | x_parent = y->parent(); |
242 | y->parent()->left = x; |
243 | } else { |
244 | x_parent = z; |
245 | z->right = x; |
246 | } |
247 | if (x) |
248 | x->setParent(x_parent); |
249 | } else { |
250 | x_parent = y->parent(); |
251 | if (x) |
252 | x->setParent(y->parent()); |
253 | if (root == y) |
254 | root = x; |
255 | else if (y->parent()->left == y) |
256 | y->parent()->left = x; |
257 | else |
258 | y->parent()->right = x; |
259 | if (x && x == y->right) |
260 | x->size_left += y->size_left; |
261 | y->size_left = 0; |
262 | } |
263 | if (y->color() != SparseArrayNode::Red) { |
264 | while (x != root && (x == nullptr || x->color() == SparseArrayNode::Black)) { |
265 | if (x == x_parent->left) { |
266 | SparseArrayNode *w = x_parent->right; |
267 | if (w->color() == SparseArrayNode::Red) { |
268 | w->setColor(SparseArrayNode::Black); |
269 | x_parent->setColor(SparseArrayNode::Red); |
270 | rotateLeft(x: x_parent); |
271 | w = x_parent->right; |
272 | } |
273 | if ((w->left == nullptr || w->left->color() == SparseArrayNode::Black) && |
274 | (w->right == nullptr || w->right->color() == SparseArrayNode::Black)) { |
275 | w->setColor(SparseArrayNode::Red); |
276 | x = x_parent; |
277 | x_parent = x_parent->parent(); |
278 | } else { |
279 | if (w->right == nullptr || w->right->color() == SparseArrayNode::Black) { |
280 | if (w->left) |
281 | w->left->setColor(SparseArrayNode::Black); |
282 | w->setColor(SparseArrayNode::Red); |
283 | rotateRight(x: w); |
284 | w = x_parent->right; |
285 | } |
286 | w->setColor(x_parent->color()); |
287 | x_parent->setColor(SparseArrayNode::Black); |
288 | if (w->right) |
289 | w->right->setColor(SparseArrayNode::Black); |
290 | rotateLeft(x: x_parent); |
291 | break; |
292 | } |
293 | } else { |
294 | SparseArrayNode *w = x_parent->left; |
295 | if (w->color() == SparseArrayNode::Red) { |
296 | w->setColor(SparseArrayNode::Black); |
297 | x_parent->setColor(SparseArrayNode::Red); |
298 | rotateRight(x: x_parent); |
299 | w = x_parent->left; |
300 | } |
301 | if ((w->right == nullptr || w->right->color() == SparseArrayNode::Black) && |
302 | (w->left == nullptr || w->left->color() == SparseArrayNode::Black)) { |
303 | w->setColor(SparseArrayNode::Red); |
304 | x = x_parent; |
305 | x_parent = x_parent->parent(); |
306 | } else { |
307 | if (w->left == nullptr || w->left->color() == SparseArrayNode::Black) { |
308 | if (w->right) |
309 | w->right->setColor(SparseArrayNode::Black); |
310 | w->setColor(SparseArrayNode::Red); |
311 | rotateLeft(x: w); |
312 | w = x_parent->left; |
313 | } |
314 | w->setColor(x_parent->color()); |
315 | x_parent->setColor(SparseArrayNode::Black); |
316 | if (w->left) |
317 | w->left->setColor(SparseArrayNode::Black); |
318 | rotateRight(x: x_parent); |
319 | break; |
320 | } |
321 | } |
322 | } |
323 | if (x) |
324 | x->setColor(SparseArrayNode::Black); |
325 | } |
326 | free(ptr: y); |
327 | --numEntries; |
328 | } |
329 | |
330 | void SparseArray::recalcMostLeftNode() |
331 | { |
332 | mostLeftNode = &header; |
333 | while (mostLeftNode->left) |
334 | mostLeftNode = mostLeftNode->left; |
335 | } |
336 | |
337 | static inline int qMapAlignmentThreshold() |
338 | { |
339 | // malloc on 32-bit platforms should return pointers that are 8-byte |
340 | // aligned or more while on 64-bit platforms they should be 16-byte aligned |
341 | // or more |
342 | return 2 * sizeof(void*); |
343 | } |
344 | |
345 | static inline void *qMapAllocate(int alloc, int alignment) |
346 | { |
347 | return alignment > qMapAlignmentThreshold() |
348 | ? qMallocAligned(size: alloc, alignment) |
349 | : ::malloc(size: alloc); |
350 | } |
351 | |
352 | static inline void qMapDeallocate(SparseArrayNode *node, int alignment) |
353 | { |
354 | if (alignment > qMapAlignmentThreshold()) |
355 | qFreeAligned(ptr: node); |
356 | else |
357 | ::free(ptr: node); |
358 | } |
359 | |
360 | SparseArrayNode *SparseArray::createNode(uint sl, SparseArrayNode *parent, bool left) |
361 | { |
362 | SparseArrayNode *node = static_cast<SparseArrayNode *>(qMapAllocate(alloc: sizeof(SparseArrayNode), Q_ALIGNOF(SparseArrayNode))); |
363 | Q_CHECK_PTR(node); |
364 | |
365 | node->p = (quintptr)parent; |
366 | node->left = nullptr; |
367 | node->right = nullptr; |
368 | node->size_left = sl; |
369 | node->value = UINT_MAX; |
370 | ++numEntries; |
371 | |
372 | if (parent) { |
373 | if (left) { |
374 | parent->left = node; |
375 | if (parent == mostLeftNode) |
376 | mostLeftNode = node; |
377 | } else { |
378 | parent->right = node; |
379 | } |
380 | node->setParent(parent); |
381 | rebalance(x: node); |
382 | } |
383 | return node; |
384 | } |
385 | |
386 | void SparseArray::freeTree(SparseArrayNode *root, int alignment) |
387 | { |
388 | if (root->left) |
389 | freeTree(root: root->left, alignment); |
390 | if (root->right) |
391 | freeTree(root: root->right, alignment); |
392 | qMapDeallocate(node: root, alignment); |
393 | } |
394 | |
395 | SparseArray::SparseArray() |
396 | : numEntries(0) |
397 | { |
398 | freeList = Encode(-1); |
399 | header.p = 0; |
400 | header.left = nullptr; |
401 | header.right = nullptr; |
402 | mostLeftNode = &header; |
403 | } |
404 | |
405 | SparseArray::SparseArray(const SparseArray &other) |
406 | { |
407 | header.p = 0; |
408 | header.right = nullptr; |
409 | if (other.header.left) { |
410 | header.left = other.header.left->copy(d: this); |
411 | header.left->setParent(&header); |
412 | recalcMostLeftNode(); |
413 | } |
414 | freeList = other.freeList; |
415 | } |
416 | |
417 | SparseArrayNode *SparseArray::insert(uint akey) |
418 | { |
419 | SparseArrayNode *n = root(); |
420 | SparseArrayNode *y = end(); |
421 | bool left = true; |
422 | uint s = akey; |
423 | while (n) { |
424 | y = n; |
425 | if (s == n->size_left) { |
426 | return n; |
427 | } else if (s < n->size_left) { |
428 | left = true; |
429 | n = n->left; |
430 | } else { |
431 | left = false; |
432 | s -= n->size_left; |
433 | n = n->right; |
434 | } |
435 | } |
436 | |
437 | return createNode(sl: s, parent: y, left); |
438 | } |
439 | |