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
52using namespace QV4;
53
54const 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
72const 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
90SparseArrayNode *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*/
117void 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*/
144void 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
164void 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
206void 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
330void SparseArray::recalcMostLeftNode()
331{
332 mostLeftNode = &header;
333 while (mostLeftNode->left)
334 mostLeftNode = mostLeftNode->left;
335}
336
337static 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
345static inline void *qMapAllocate(int alloc, int alignment)
346{
347 return alignment > qMapAlignmentThreshold()
348 ? qMallocAligned(size: alloc, alignment)
349 : ::malloc(size: alloc);
350}
351
352static inline void qMapDeallocate(SparseArrayNode *node, int alignment)
353{
354 if (alignment > qMapAlignmentThreshold())
355 qFreeAligned(ptr: node);
356 else
357 ::free(ptr: node);
358}
359
360SparseArrayNode *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
386void 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
395SparseArray::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
405SparseArray::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
417SparseArrayNode *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

source code of qtdeclarative/src/qml/jsruntime/qv4sparsearray.cpp