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

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