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 | |
12 | using namespace QV4; |
13 | |
14 | const 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 | |
32 | const 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 | |
50 | SparseArrayNode *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 | */ |
77 | void 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 | */ |
104 | void 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 | |
124 | void 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 | |
166 | void 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 | |
290 | void SparseArray::recalcMostLeftNode() |
291 | { |
292 | mostLeftNode = &header; |
293 | while (mostLeftNode->left) |
294 | mostLeftNode = mostLeftNode->left; |
295 | } |
296 | |
297 | static 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 | |
305 | static inline void *qMapAllocate(int alloc, int alignment) |
306 | { |
307 | return alignment > qMapAlignmentThreshold() |
308 | ? qMallocAligned(size: alloc, alignment) |
309 | : ::malloc(size: alloc); |
310 | } |
311 | |
312 | static inline void qMapDeallocate(SparseArrayNode *node, int alignment) |
313 | { |
314 | if (alignment > qMapAlignmentThreshold()) |
315 | qFreeAligned(ptr: node); |
316 | else |
317 | ::free(ptr: node); |
318 | } |
319 | |
320 | SparseArrayNode *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 | |
346 | void 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 | |
355 | SparseArray::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 | |
365 | SparseArray::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 | |
377 | SparseArrayNode *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 | |