Qt
Internal/Contributor docs for the Qt SDK. Note: These are NOT official API docs; those are found at https://doc.qt.io/
Loading...
Searching...
No Matches
qv4arraydata.cpp
Go to the documentation of this file.
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// Qt-Security score:significant
4#include "qv4arraydata_p.h"
5#include "qv4object_p.h"
6#include "qv4functionobject_p.h"
7#include <private/qv4mm_p.h>
8#include "qv4runtime_p.h"
9#include "qv4argumentsobject_p.h"
10#include "qv4string_p.h"
11#include "qv4jscall_p.h"
12
13using namespace QV4;
14
15DEFINE_MANAGED_VTABLE(ArrayData);
16
17const ArrayVTable SimpleArrayData::static_vtbl =
18{
19 DEFINE_MANAGED_VTABLE_INT(SimpleArrayData, nullptr),
20 Heap::ArrayData::Simple,
21 SimpleArrayData::reallocate,
22 SimpleArrayData::get,
23 SimpleArrayData::put,
24 SimpleArrayData::putArray,
25 SimpleArrayData::del,
26 SimpleArrayData::setAttribute,
27 SimpleArrayData::push_front,
28 SimpleArrayData::pop_front,
29 SimpleArrayData::truncate,
30 SimpleArrayData::length
31};
32
33const ArrayVTable SparseArrayData::static_vtbl =
34{
35 DEFINE_MANAGED_VTABLE_INT(SparseArrayData, nullptr),
36 Heap::ArrayData::Sparse,
37 SparseArrayData::reallocate,
38 SparseArrayData::get,
39 SparseArrayData::put,
40 SparseArrayData::putArray,
41 SparseArrayData::del,
42 SparseArrayData::setAttribute,
43 SparseArrayData::push_front,
44 SparseArrayData::pop_front,
45 SparseArrayData::truncate,
46 SparseArrayData::length
47};
48
49Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SimpleArrayData));
50Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SparseArrayData));
51
52void Heap::ArrayData::markObjects(Heap::Base *base, MarkStack *stack)
53{
54 ArrayData *a = static_cast<ArrayData *>(base);
55 a->values.mark(stack);
56}
57
58
59void ArrayData::realloc(Object *o, Type newType, uint requested, bool enforceAttributes)
60{
61 Scope scope(o->engine());
62 Scoped<ArrayData> d(scope, o->arrayData());
63
64 uint alloc = 8;
65 uint toCopy = 0;
66 uint offset = 0;
67
68 if (d) {
69 bool hasAttrs = d->attrs();
70 enforceAttributes |= hasAttrs;
71
72 if (requested <= d->alloc() && newType == d->type() && hasAttrs == enforceAttributes)
73 return;
74 if (alloc < d->alloc())
75 alloc = d->alloc();
76
77 if (d->type() < Heap::ArrayData::Sparse) {
78 offset = d->d()->offset;
79 toCopy = d->d()->values.size;
80 } else {
81 toCopy = d->alloc();
82 }
83 if (d->type() > newType)
84 newType = d->type();
85 }
86
87 while (alloc < requested)
88 alloc *= 2;
89 size_t size = sizeof(Heap::ArrayData) + (alloc - 1)*sizeof(Value);
90 if (enforceAttributes)
91 size += alloc*sizeof(PropertyAttributes);
92
93 Scoped<ArrayData> newData(scope);
94 if (newType < Heap::ArrayData::Sparse) {
95 Heap::SimpleArrayData *n = scope.engine->memoryManager->allocManaged<SimpleArrayData>(size);
96 n->init();
97 n->offset = 0;
98 n->values.size = d ? d->d()->values.size : 0;
99 newData = n;
100 } else {
101 Heap::SparseArrayData *n = scope.engine->memoryManager->allocManaged<SparseArrayData>(size);
102 n->init();
103 newData = n;
104 }
105 newData->setAlloc(alloc);
106 newData->setType(newType);
107 newData->setAttrs(enforceAttributes ? reinterpret_cast<PropertyAttributes *>(newData->d()->values.values + alloc) : nullptr);
108 o->setArrayData(newData);
109
110 if (d) {
111 if (enforceAttributes) {
112 if (d->attrs())
113 memcpy(newData->attrs(), d->attrs(), sizeof(PropertyAttributes)*toCopy);
114 else
115 for (uint i = 0; i < toCopy; ++i)
116 newData->attrs()[i] = Attr_Data;
117 }
118
119 if (toCopy > d->d()->values.alloc - offset) {
120 uint copyFromStart = toCopy - (d->d()->values.alloc - offset);
121 // no write barrier required here
122 memcpy(newData->d()->values.values + toCopy - copyFromStart, d->d()->values.values, sizeof(Value)*copyFromStart);
123 toCopy -= copyFromStart;
124 }
125 // no write barrier required here
126 memcpy(newData->d()->values.values, d->d()->values.values + offset, sizeof(Value)*toCopy);
127 }
128
129 if (newType != Heap::ArrayData::Sparse)
130 return;
131
132 Heap::SparseArrayData *sparse = static_cast<Heap::SparseArrayData *>(newData->d());
133
134 Value *lastFree;
135 if (d && d->type() == Heap::ArrayData::Sparse) {
136 Heap::SparseArrayData *old = static_cast<Heap::SparseArrayData *>(d->d());
137 sparse->sparse = old->sparse;
138 old->sparse = nullptr;
139 lastFree = &sparse->sparse->freeList;
140 } else {
141 sparse->sparse = new SparseArray;
142 lastFree = &sparse->sparse->freeList;
143 *lastFree = Encode(0);
144 for (uint i = 0; i < toCopy; ++i) {
145 if (!sparse->values[i].isEmpty()) {
146 SparseArrayNode *n = sparse->sparse->insert(i);
147 n->value = i;
148 } else {
149 *lastFree = Encode(i);
150 sparse->values.values[i].setEmpty();
151 lastFree = &sparse->values.values[i];
152 }
153 }
154 }
155
156 if (toCopy < sparse->values.alloc) {
157 for (uint i = toCopy; i < sparse->values.alloc; ++i) {
158 *lastFree = Encode(i);
159 sparse->values.values[i].setEmpty();
160 lastFree = &sparse->values.values[i];
161 }
162 }
163 *lastFree = Encode(-1);
164
165 Q_ASSERT(sparse->sparse->freeList.isInteger());
166 // ### Could explicitly free the old data
167}
168
169Heap::ArrayData *SimpleArrayData::reallocate(Object *o, uint n, bool enforceAttributes)
170{
171 realloc(o, Heap::ArrayData::Simple, n, enforceAttributes);
172 return o->arrayData();
173}
174
175void ArrayData::ensureAttributes(Object *o)
176{
177 if (o->arrayData() && o->arrayData()->attrs)
178 return;
179
180 ArrayData::realloc(o, Heap::ArrayData::Simple, 0, true);
181}
182
183ReturnedValue SimpleArrayData::get(const Heap::ArrayData *d, uint index)
184{
185 const Heap::SimpleArrayData *dd = static_cast<const Heap::SimpleArrayData *>(d);
186 if (index >= dd->values.size)
187 return Value::emptyValue().asReturnedValue();
188 return dd->data(index).asReturnedValue();
189}
190
191bool SimpleArrayData::put(Object *o, uint index, const Value &value)
192{
193 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
194 Q_ASSERT(index >= dd->values.size || !dd->attrs || !dd->attrs[index].isAccessor());
195 // ### honour attributes
196 dd->setData(o->engine(), index, value);
197 if (index >= dd->values.size) {
198 if (dd->attrs)
199 dd->attrs[index] = Attr_Data;
200 dd->values.size = index + 1;
201 }
202 return true;
203}
204
205bool SimpleArrayData::del(Object *o, uint index)
206{
207 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
208 if (index >= dd->values.size)
209 return true;
210
211 if (!dd->attrs || dd->attrs[index].isConfigurable()) {
212 dd->setData(o->engine(), index, Value::emptyValue());
213 if (dd->attrs)
214 dd->attrs[index] = Attr_Data;
215 return true;
216 }
217 if (dd->data(index).isEmpty())
218 return true;
219 return false;
220}
221
222void SimpleArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs)
223{
224 o->arrayData()->attrs[index] = attrs;
225}
226
227void SimpleArrayData::push_front(Object *o, const Value *values, uint n)
228{
229 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
230 Q_ASSERT(!dd->attrs);
231 if (dd->values.size + n > dd->values.alloc) {
232 realloc(o, Heap::ArrayData::Simple, dd->values.size + n, false);
233 Q_ASSERT(o->d()->arrayData->type == Heap::ArrayData::Simple);
234 dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
235 }
236 if (n <= dd->offset) {
237 dd->offset -= n; // there is enough space left in front
238 } else {
239 // we need to wrap around, so:
240 dd->offset = dd->values.alloc - // start at the back, but subtract:
241 (n - dd->offset); // the number of items we can put in the free space at the start of the allocated array
242 }
243 dd->values.size += n;
244 for (uint i = 0; i < n; ++i)
245 dd->setData(o->engine(), i, values[i]);
246}
247
248ReturnedValue SimpleArrayData::pop_front(Object *o)
249{
250 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
251 Q_ASSERT(!dd->attrs);
252 if (!dd->values.size)
253 return Encode::undefined();
254
255 ReturnedValue v = dd->data(0).isEmpty() ? Encode::undefined() : dd->data(0).asReturnedValue();
256 dd->offset = (dd->offset + 1) % dd->values.alloc;
257 --dd->values.size;
258 return v;
259}
260
261uint SimpleArrayData::truncate(Object *o, uint newLen)
262{
263 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
264 if (dd->values.size < newLen)
265 return newLen;
266
267 if (!dd->attrs) {
268 for (uint i = newLen; i < dd->values.size; ++i)
269 dd->setData(dd->internalClass->engine, i, Value::emptyValue());
270 dd->values.size = newLen;
271 return newLen;
272 }
273
274 while (dd->values.size > newLen) {
275 const uint lastIndex = dd->values.size - 1;
276 if (!dd->data(lastIndex).isEmpty() && !dd->attrs[lastIndex].isConfigurable())
277 return dd->values.size;
278
279 dd->setData(dd->internalClass->engine, lastIndex, Value::emptyValue());
280 dd->values.size = lastIndex;
281 }
282 return dd->values.size;
283}
284
285uint SimpleArrayData::length(const Heap::ArrayData *d)
286{
287 return d->values.size;
288}
289
290bool SimpleArrayData::putArray(Object *o, uint index, const Value *values, uint n)
291{
292 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
293 if (index + n > dd->values.alloc) {
294 reallocate(o, index + n + 1, false);
295 dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
296 }
297 QV4::ExecutionEngine *e = o->engine();
298 for (uint i = dd->values.size; i < index; ++i)
299 dd->setData(e, i, Value::emptyValue());
300 for (uint i = 0; i < n; ++i)
301 dd->setData(e, index + i, values[i]);
302 dd->values.size = qMax(dd->values.size, index + n);
303 return true;
304}
305
306void SparseArrayData::free(Heap::ArrayData *d, uint idx)
307{
308 Q_ASSERT(d && d->type == Heap::ArrayData::Sparse);
309 Value *v = d->values.values + idx;
310 if (d->attrs && d->attrs[idx].isAccessor()) {
311 // double slot, free both. Order is important, so we have a double slot for allocation again afterwards.
312 v[1] = d->sparse->freeList;
313 v[0] = Encode(idx + 1);
314 } else {
315 *v = d->sparse->freeList;
316 }
317 d->sparse->freeList = Encode(idx);
318 if (d->attrs)
319 d->attrs[idx].clear();
320}
321
322Heap::ArrayData *SparseArrayData::reallocate(Object *o, uint n, bool enforceAttributes)
323{
324 realloc(o, Heap::ArrayData::Sparse, n, enforceAttributes);
325 return o->arrayData();
326}
327
328// double slots are required for accessor properties
329uint SparseArrayData::allocate(Object *o, bool doubleSlot)
330{
331 Q_ASSERT(o->d()->arrayData->type == Heap::ArrayData::Sparse);
332 Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
333 if (doubleSlot) {
334 Value *last = &dd->sparse->freeList;
335 while (1) {
336 if (last->int_32() == -1) {
337 reallocate(o, dd->values.alloc + 2, true);
338 dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
339 last = &dd->sparse->freeList;
340 Q_ASSERT(last->int_32() != -1);
341 }
342
343 Q_ASSERT(dd->values[static_cast<uint>(last->int_32())].int_32() != last->int_32());
344 if (dd->values[static_cast<uint>(last->int_32())].int_32() == last->int_32() + 1) {
345 // found two slots in a row
346 uint idx = static_cast<uint>(last->int_32());
347 *last = Encode(dd->values[static_cast<uint>(last->int_32()) + 1].int_32());
348 dd->attrs[idx] = Attr_Accessor;
349 return idx;
350 }
351 last = &dd->values.values[last->int_32()];
352 }
353 } else {
354 if (dd->sparse->freeList.int_32() == -1) {
355 reallocate(o, dd->values.alloc + 1, false);
356 dd = o->d()->arrayData.cast<Heap::SimpleArrayData>();
357 }
358 Q_ASSERT(dd->sparse->freeList.int_32() != -1);
359 uint idx = static_cast<uint>(dd->sparse->freeList.int_32());
360 dd->sparse->freeList = dd->values[idx];
361 Q_ASSERT(dd->sparse->freeList.isInteger());
362 if (dd->attrs)
363 dd->attrs[idx] = Attr_Data;
364 return idx;
365 }
366}
367
368ReturnedValue SparseArrayData::get(const Heap::ArrayData *d, uint index)
369{
370 const Heap::SparseArrayData *s = static_cast<const Heap::SparseArrayData *>(d);
371 index = s->mappedIndex(index);
372 if (index == UINT_MAX)
373 return Value::emptyValue().asReturnedValue();
374 return s->values[index].asReturnedValue();
375}
376
377bool SparseArrayData::put(Object *o, uint index, const Value &value)
378{
379 if (value.isEmpty())
380 return true;
381
382 Heap::SparseArrayData *s = o->d()->arrayData.cast<Heap::SparseArrayData>();
383 SparseArrayNode *n = s->sparse->insert(index);
384 Q_ASSERT(n->value == UINT_MAX || !s->attrs || !s->attrs[n->value].isAccessor());
385 if (n->value == UINT_MAX)
386 n->value = allocate(o);
387 s = o->d()->arrayData.cast<Heap::SparseArrayData>();
388 s->setArrayData(o->engine(), n->value, value);
389 if (s->attrs)
390 s->attrs[n->value] = Attr_Data;
391 return true;
392}
393
394bool SparseArrayData::del(Object *o, uint index)
395{
396 Heap::SparseArrayData *dd = o->d()->arrayData.cast<Heap::SparseArrayData>();
397
398 SparseArrayNode *n = dd->sparse->findNode(index);
399 if (!n)
400 return true;
401
402 uint pidx = n->value;
403 Q_ASSERT(!dd->values[pidx].isEmpty());
404
405 bool isAccessor = false;
406 if (dd->attrs) {
407 if (!dd->attrs[pidx].isConfigurable())
408 return false;
409
410 isAccessor = dd->attrs[pidx].isAccessor();
411 dd->attrs[pidx] = Attr_Data;
412 }
413
414 if (isAccessor) {
415 // free up both indices
416 dd->values.values[pidx + 1] = dd->sparse->freeList;
417 dd->values.values[pidx] = Encode(pidx + 1);
418 } else {
419 Q_ASSERT(dd->type == Heap::ArrayData::Sparse);
420 dd->values.values[pidx] = dd->sparse->freeList;
421 }
422
423 dd->sparse->freeList = Encode(pidx);
424 dd->sparse->erase(n);
425 return true;
426}
427
428void SparseArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs)
429{
430 Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>();
431 SparseArrayNode *n = d->sparse->insert(index);
432 if (n->value == UINT_MAX) {
433 n->value = allocate(o, attrs.isAccessor());
434 d = o->d()->arrayData.cast<Heap::SparseArrayData>();
435 }
436 else if (attrs.isAccessor() != d->attrs[n->value].isAccessor()) {
437 // need to convert the slot
438 free(o->arrayData(), n->value);
439 n->value = allocate(o, attrs.isAccessor());
440 d = o->d()->arrayData.cast<Heap::SparseArrayData>();
441 }
442 d->attrs[n->value] = attrs;
443}
444
445void SparseArrayData::push_front(Object *o, const Value *values, uint n)
446{
447 Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>();
448 Q_ASSERT(!d->attrs);
449 for (int i = static_cast<int>(n) - 1; i >= 0; --i) {
450 uint idx = allocate(o);
451 d = o->d()->arrayData.cast<Heap::SparseArrayData>();
452 d->setArrayData(o->engine(), idx, values[i]);
453 d->sparse->push_front(idx);
454 }
455}
456
457ReturnedValue SparseArrayData::pop_front(Object *o)
458{
459 Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>();
460 Q_ASSERT(!d->attrs);
461 uint idx = d->sparse->pop_front();
462 ReturnedValue v;
463 if (idx != UINT_MAX) {
464 v = d->values[idx].asReturnedValue();
465 free(o->arrayData(), idx);
466 } else {
467 v = Encode::undefined();
468 }
469 return v;
470}
471
472uint SparseArrayData::truncate(Object *o, uint newLen)
473{
474 Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>();
475 SparseArrayNode *begin = d->sparse->lowerBound(newLen);
476 if (begin != d->sparse->end()) {
477 SparseArrayNode *it = d->sparse->end()->previousNode();
478 while (1) {
479 if (d->attrs) {
480 if (!d->attrs[it->value].isConfigurable()) {
481 newLen = it->key() + 1;
482 break;
483 }
484 }
485 free(o->arrayData(), it->value);
486 bool brk = (it == begin);
487 SparseArrayNode *prev = it->previousNode();
488 d->sparse->erase(it);
489 if (brk)
490 break;
491 it = prev;
492 }
493 }
494 return newLen;
495}
496
497uint SparseArrayData::length(const Heap::ArrayData *d)
498{
499 const Heap::SparseArrayData *dd = static_cast<const Heap::SparseArrayData *>(d);
500 if (!dd->sparse)
501 return 0;
502 SparseArrayNode *n = dd->sparse->end();
503 n = n->previousNode();
504 return n ? n->key() + 1 : 0;
505}
506
507bool SparseArrayData::putArray(Object *o, uint index, const Value *values, uint n)
508{
509 for (uint i = 0; i < n; ++i)
510 put(o, index + i, values[i]);
511 return true;
512}
513
514
515uint ArrayData::append(Object *obj, ArrayObject *otherObj, uint n)
516{
517 Q_ASSERT(!obj->d()->arrayData || !obj->d()->arrayData->attrs);
518
519 if (!n)
520 return obj->getLength();
521
522 Scope scope(obj->engine());
523 Scoped<ArrayData> other(scope, otherObj->arrayData());
524
525 if (other && other->isSparse())
526 obj->initSparseArray();
527 else
528 obj->arrayCreate();
529
530 uint oldSize = obj->getLength();
531
532 if (!other || ArgumentsObject::isNonStrictArgumentsObject(otherObj)) {
533 ScopedValue v(scope);
534 for (uint i = 0; i < n; ++i)
535 obj->arraySet(oldSize + i, (v = otherObj->get(i)));
536 } else if (other->isSparse()) {
537 Heap::SparseArrayData *os = static_cast<Heap::SparseArrayData *>(other->d());
538 if (other->hasAttributes()) {
539 ScopedValue v(scope);
540 for (const SparseArrayNode *it = os->sparse->begin();
541 it != os->sparse->end(); it = it->nextNode()) {
542 v = otherObj->getValue(os->values[it->value], other->d()->attrs[it->value]);
543 obj->arraySet(oldSize + it->key(), v);
544 }
545 } else {
546 for (const SparseArrayNode *it = other->d()->sparse->begin();
547 it != os->sparse->end(); it = it->nextNode())
548 obj->arraySet(oldSize + it->key(), os->values[it->value]);
549 }
550 } else {
551 Heap::SimpleArrayData *os = static_cast<Heap::SimpleArrayData *>(other->d());
552 uint toCopy = n;
553 uint chunk = toCopy;
554 if (chunk > os->values.alloc - os->offset)
555 chunk = os->values.alloc - os->offset;
556 obj->arrayPut(oldSize, os->values.data() + os->offset, chunk);
557 toCopy -= chunk;
558 if (toCopy)
559 obj->arrayPut(oldSize + chunk, os->values.data(), toCopy);
560 }
561
562 return oldSize + n;
563}
564
565void ArrayData::insert(Object *o, uint index, const Value *v, bool isAccessor)
566{
567 if (!isAccessor && o->d()->arrayData->type != Heap::ArrayData::Sparse) {
568 Heap::SimpleArrayData *d = o->d()->arrayData.cast<Heap::SimpleArrayData>();
569 if (index < 0x1000 || index < d->values.size + (d->values.size >> 2)) {
570 if (index >= d->values.alloc) {
571 o->arrayReserve(index + 1);
572 d = o->d()->arrayData.cast<Heap::SimpleArrayData>();
573 }
574 if (index >= d->values.size) {
575 // mark possible hole in the array
576 for (uint i = d->values.size; i < index; ++i)
577 d->setData(o->engine(), i, Value::emptyValue());
578 d->values.size = index + 1;
579 }
580 d->setData(o->engine(), index, *v);
581 return;
582 }
583 }
584
585 o->initSparseArray();
586 Heap::SparseArrayData *s = o->d()->arrayData.cast<Heap::SparseArrayData>();
587 SparseArrayNode *n = s->sparse->insert(index);
588 if (n->value == UINT_MAX)
589 n->value = SparseArrayData::allocate(o, isAccessor);
590 s = o->d()->arrayData.cast<Heap::SparseArrayData>();
591 s->setArrayData(o->engine(), n->value, *v);
592 if (isAccessor)
593 s->setArrayData(o->engine(), n->value + Object::SetterOffset, v[Object::SetterOffset]);
594}
595
596bool ArrayElementLessThan::operator()(Value v1, Value v2) const
597{
598 Scope scope(m_engine);
599
600 if (v1.isUndefined() || v1.isEmpty())
601 return false;
602 if (v2.isUndefined() || v2.isEmpty())
603 return true;
604 ScopedFunctionObject o(scope, m_comparefn);
605 if (o) {
606 Scope scope(o->engine());
607 ScopedValue result(scope);
608 JSCallArguments jsCallData(scope, 2);
609 jsCallData.args[0] = v1;
610 jsCallData.args[1] = v2;
611 result = o->call(jsCallData);
612 if (scope.hasException())
613 return false;
614
615 return result->toNumber() < 0;
616 }
617 ScopedString p1s(scope, v1.toString(scope.engine));
618 ScopedString p2s(scope, v2.toString(scope.engine));
619
620 if (!p1s)
621 return false;
622 if (!p2s)
623 return true;
624
625 return p1s->toQString() < p2s->toQString();
626}
627
628void ArrayData::sort(ExecutionEngine *engine, Object *thisObject, const Value &comparefn, uint len)
629{
630 if (!len)
631 return;
632
633 Scope scope(engine);
634 Scoped<ArrayData> arrayData(scope, thisObject->arrayData());
635
636 if (!arrayData || !arrayData->length())
637 return;
638
639 // The spec says the sorting goes through a series of get,put and delete operations.
640 // this implies that the attributes don't get sorted around.
641
642 if (arrayData->type() == Heap::ArrayData::Sparse) {
643 // since we sort anyway, we can simply iterate over the entries in the sparse
644 // array and append them one by one to a regular one.
645 Scoped<SparseArrayData> sparse(scope, static_cast<Heap::SparseArrayData *>(arrayData->d()));
646
647 if (!sparse->sparse()->nEntries())
648 return;
649
650 thisObject->setArrayData(nullptr);
651 ArrayData::realloc(thisObject, Heap::ArrayData::Simple, sparse->sparse()->nEntries(), sparse->attrs() ? true : false);
652 Heap::SimpleArrayData *d = thisObject->d()->arrayData.cast<Heap::SimpleArrayData>();
653
654 SparseArrayNode *n = sparse->sparse()->begin();
655 uint i = 0;
656 if (sparse->attrs()) {
657 while (n != sparse->sparse()->end()) {
658 if (n->value >= len)
659 break;
660
661 PropertyAttributes a = sparse->attrs() ? sparse->attrs()[n->value] : Attr_Data;
662 d->setData(engine, i, Value::fromReturnedValue(thisObject->getValue(sparse->arrayData()[n->value], a)));
663 d->attrs[i] = a.isAccessor() ? Attr_Data : a;
664
665 n = n->nextNode();
666 ++i;
667 }
668 } else {
669 while (n != sparse->sparse()->end()) {
670 if (n->value >= len)
671 break;
672 d->setData(engine, i, sparse->arrayData()[n->value]);
673 n = n->nextNode();
674 ++i;
675 }
676 }
677 d->values.size = i;
678 if (len > i)
679 len = i;
680 if (n != sparse->sparse()->end()) {
681 // have some entries outside the sort range that we need to ignore when sorting
682 thisObject->initSparseArray();
683 while (n != sparse->sparse()->end()) {
684 PropertyAttributes a = sparse->attrs() ? sparse->attrs()[n->value] : Attr_Data;
685 thisObject->arraySet(n->value, reinterpret_cast<const Property *>(sparse->arrayData() + n->value), a);
686
687 n = n->nextNode();
688 }
689
690 }
691 } else {
692 Heap::SimpleArrayData *d = thisObject->d()->arrayData.cast<Heap::SimpleArrayData>();
693 if (len > d->values.size)
694 len = d->values.size;
695
696 // sort empty values to the end
697 for (uint i = 0; i < len; i++) {
698 if (d->data(i).isEmpty()) {
699 while (--len > i)
700 if (!d->data(len).isEmpty())
701 break;
702 Q_ASSERT(!d->attrs || !d->attrs[len].isAccessor());
703 d->setData(engine, i, d->data(len));
704 d->setData(engine, len, Value::emptyValue());
705 }
706 }
707
708 if (!len)
709 return;
710 }
711
712
713 ArrayElementLessThan lessThan(engine, comparefn);
714
715 const auto thisArrayData = thisObject->arrayData();
716 uint startIndex = thisArrayData->mappedIndex(0);
717 uint endIndex = thisArrayData->mappedIndex(len - 1) + 1;
718 if (startIndex < endIndex) {
719 // Values are contiguous. Sort right away.
720 sortHelper(
721 thisArrayData->values.values + startIndex,
722 thisArrayData->values.values + endIndex,
723 lessThan);
724 } else {
725 // Values wrap around the end of the allocation. Close the gap to form a contiguous array.
726 // We're going to sort anyway. So we don't need to care about order.
727
728 // ArrayElementLessThan sorts empty and undefined to the end of the array anyway, but we
729 // probably shouldn't rely on the unused slots to be actually undefined or empty.
730
731 const uint gap = startIndex - endIndex;
732 const uint allocEnd = thisArrayData->values.alloc - 1;
733 for (uint i = 0; i < gap; ++i) {
734 const uint from = allocEnd - i;
735 const uint to = endIndex + i;
736 if (from < startIndex)
737 break;
738
739 std::swap(thisArrayData->values.values[from], thisArrayData->values.values[to]);
740 }
741
742 thisArrayData->offset = 0;
743 sortHelper(thisArrayData->values.values, thisArrayData->values.values + len, lessThan);
744 }
745
746#ifdef CHECK_SPARSE_ARRAYS
747 thisObject->initSparseArray();
748#endif
749
750}
Q_STATIC_ASSERT
Q_STATIC_ASSERT(sizeof(SharedImageHeader) % 4==0)
DEFINE_MANAGED_VTABLE
DEFINE_MANAGED_VTABLE(ArrayData)