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 | |
48 | using namespace QV4; |
49 | |
50 | DEFINE_MANAGED_VTABLE(ArrayData); |
51 | |
52 | const 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 | |
68 | const 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 | |
84 | Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SimpleArrayData)); |
85 | Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SparseArrayData)); |
86 | |
87 | void 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 | |
94 | void 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 | |
204 | Heap::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 | |
210 | void 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 | |
218 | ReturnedValue 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 | |
226 | bool 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 | |
240 | bool 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 | |
257 | void SimpleArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs) |
258 | { |
259 | o->arrayData()->attrs[index] = attrs; |
260 | } |
261 | |
262 | void 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 | |
283 | ReturnedValue 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 | |
296 | uint 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 | |
315 | uint SimpleArrayData::length(const Heap::ArrayData *d) |
316 | { |
317 | return d->values.size; |
318 | } |
319 | |
320 | bool 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 | |
336 | void 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 | |
352 | Heap::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 |
359 | uint 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 | |
398 | ReturnedValue 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 | |
407 | bool 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 | |
424 | bool 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 | |
458 | void 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 | |
475 | void 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 | |
487 | ReturnedValue 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 | |
502 | uint 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 | |
527 | uint 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 | |
537 | bool 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 | |
545 | uint 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 | |
595 | void 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 | |
627 | class ArrayElementLessThan |
628 | { |
629 | public: |
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 | |
635 | private: |
636 | ExecutionEngine *m_engine; |
637 | const Value &m_comparefn; |
638 | }; |
639 | |
640 | |
641 | bool 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 | |
673 | template <typename RandomAccessIterator, typename T, typename LessThan> |
674 | void sortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan) |
675 | { |
676 | top: |
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 | |
727 | void 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 | |