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

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