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#ifndef QV4ARRAYDATA_H
4#define QV4ARRAYDATA_H
5
6//
7// W A R N I N G
8// -------------
9//
10// This file is not part of the Qt API. It exists purely as an
11// implementation detail. This header file may change from version to
12// version without notice, or even be removed.
13//
14// We mean it.
15//
16
17#include "qv4global_p.h"
18#include "qv4managed_p.h"
19#include "qv4property_p.h"
20#include "qv4sparsearray_p.h"
21
22QT_BEGIN_NAMESPACE
23
24namespace QV4 {
25
26#define V4_ARRAYDATA(DataClass) \
27 public: \
28 Q_MANAGED_CHECK \
29 typedef QV4::Heap::DataClass Data; \
30 static const QV4::ArrayVTable static_vtbl; \
31 static inline const QV4::VTable *staticVTable() { return &static_vtbl.vTable; } \
32 V4_MANAGED_SIZE_TEST \
33 const Data *d() const { return static_cast<const Data *>(m()); } \
34 Data *d() { return static_cast<Data *>(m()); }
35
36
37struct ArrayData;
38
39struct ArrayVTable
40{
41 VTable vTable;
42 uint type;
43 Heap::ArrayData *(*reallocate)(Object *o, uint n, bool enforceAttributes);
44 ReturnedValue (*get)(const Heap::ArrayData *d, uint index);
45 bool (*put)(Object *o, uint index, const Value &value);
46 bool (*putArray)(Object *o, uint index, const Value *values, uint n);
47 bool (*del)(Object *o, uint index);
48 void (*setAttribute)(Object *o, uint index, PropertyAttributes attrs);
49 void (*push_front)(Object *o, const Value *values, uint n);
50 ReturnedValue (*pop_front)(Object *o);
51 uint (*truncate)(Object *o, uint newLen);
52 uint (*length)(const Heap::ArrayData *d);
53};
54
55namespace Heap {
56
57#define ArrayDataMembers(class, Member) \
58 Member(class, NoMark, ushort, type) \
59 Member(class, NoMark, ushort, unused) \
60 Member(class, NoMark, uint, offset) \
61 Member(class, NoMark, PropertyAttributes *, attrs) \
62 Member(class, NoMark, SparseArray *, sparse) \
63 Member(class, ValueArray, ValueArray, values)
64
65DECLARE_HEAP_OBJECT(ArrayData, Base) {
66 static void markObjects(Heap::Base *base, MarkStack *stack);
67
68 enum Type { Simple = 0, Sparse = 1, Custom = 2 };
69
70 bool isSparse() const { return type == Sparse; }
71
72 const ArrayVTable *vtable() const { return reinterpret_cast<const ArrayVTable *>(internalClass->vtable); }
73
74 inline ReturnedValue get(uint i) const {
75 return vtable()->get(this, i);
76 }
77 inline bool getProperty(uint index, Property *p, PropertyAttributes *attrs);
78 inline void setProperty(EngineBase *e, uint index, const Property *p);
79 inline PropertyIndex getValueOrSetter(uint index, PropertyAttributes *attrs);
80 inline PropertyAttributes attributes(uint i) const;
81
82 bool isEmpty(uint i) const {
83 return get(i) == Value::emptyValue().asReturnedValue();
84 }
85
86 inline uint length() const {
87 return vtable()->length(this);
88 }
89
90 void setArrayData(EngineBase *e, uint index, Value newVal) {
91 values.set(e, index, v: newVal);
92 }
93
94 uint mappedIndex(uint index) const;
95};
96Q_STATIC_ASSERT(std::is_trivial_v<ArrayData>);
97
98struct SimpleArrayData : public ArrayData {
99 uint mappedIndex(uint index) const { index += offset; if (index >= values.alloc) index -= values.alloc; return index; }
100 const Value &data(uint index) const { return values[mappedIndex(index)]; }
101 void setData(EngineBase *e, uint index, Value newVal) {
102 values.set(e, index: mappedIndex(index), v: newVal);
103 }
104
105 PropertyAttributes attributes(uint i) const {
106 return attrs ? attrs[i] : Attr_Data;
107 }
108};
109Q_STATIC_ASSERT(std::is_trivial_v<SimpleArrayData>);
110
111struct SparseArrayData : public ArrayData {
112 void destroy() {
113 delete sparse;
114 ArrayData::destroy();
115 }
116
117 uint mappedIndex(uint index) const {
118 SparseArrayNode *n = sparse->findNode(akey: index);
119 if (!n)
120 return UINT_MAX;
121 return n->value;
122 }
123
124 PropertyAttributes attributes(uint i) const {
125 if (!attrs)
126 return Attr_Data;
127 uint index = mappedIndex(index: i);
128 return index < UINT_MAX ? attrs[index] : Attr_Data;
129 }
130};
131
132}
133
134struct Q_QML_EXPORT ArrayData : public Managed
135{
136 typedef Heap::ArrayData::Type Type;
137 V4_MANAGED(ArrayData, Managed)
138 enum {
139 IsArrayData = true
140 };
141
142 uint alloc() const { return d()->values.alloc; }
143 uint &alloc() { return d()->values.alloc; }
144 void setAlloc(uint a) { d()->values.alloc = a; }
145 Type type() const { return static_cast<Type>(d()->type); }
146 void setType(Type t) { d()->type = t; }
147 PropertyAttributes *attrs() const { return d()->attrs; }
148 void setAttrs(PropertyAttributes *a) { d()->attrs = a; }
149 const Value *arrayData() const { return d()->values.data(); }
150 void setArrayData(EngineBase *e, uint index, Value newVal) {
151 d()->setArrayData(e, index, newVal);
152 }
153
154 const ArrayVTable *vtable() const { return d()->vtable(); }
155 bool isSparse() const { return type() == Heap::ArrayData::Sparse; }
156
157 uint length() const {
158 return d()->length();
159 }
160
161 bool hasAttributes() const {
162 return attrs();
163 }
164 PropertyAttributes attributes(uint i) const {
165 return d()->attributes(i);
166 }
167
168 bool isEmpty(uint i) const {
169 return d()->isEmpty(i);
170 }
171
172 ReturnedValue get(uint i) const {
173 return d()->get(i);
174 }
175
176 static void ensureAttributes(Object *o);
177 static void realloc(Object *o, Type newType, uint alloc, bool enforceAttributes);
178
179 static void sort(ExecutionEngine *engine, Object *thisObject, const Value &comparefn, uint dataLen);
180 static uint append(Object *obj, ArrayObject *otherObj, uint n);
181 static void insert(Object *o, uint index, const Value *v, bool isAccessor = false);
182};
183
184struct Q_QML_EXPORT SimpleArrayData : public ArrayData
185{
186 V4_ARRAYDATA(SimpleArrayData)
187 V4_INTERNALCLASS(SimpleArrayData)
188
189 uint mappedIndex(uint index) const { return d()->mappedIndex(index); }
190 Value data(uint index) const { return d()->data(index); }
191
192 uint &len() { return d()->values.size; }
193 uint len() const { return d()->values.size; }
194
195 static Heap::ArrayData *reallocate(Object *o, uint n, bool enforceAttributes);
196
197 static ReturnedValue get(const Heap::ArrayData *d, uint index);
198 static bool put(Object *o, uint index, const Value &value);
199 static bool putArray(Object *o, uint index, const Value *values, uint n);
200 static bool del(Object *o, uint index);
201 static void setAttribute(Object *o, uint index, PropertyAttributes attrs);
202 static void push_front(Object *o, const Value *values, uint n);
203 static ReturnedValue pop_front(Object *o);
204 static uint truncate(Object *o, uint newLen);
205 static uint length(const Heap::ArrayData *d);
206};
207
208struct Q_QML_EXPORT SparseArrayData : public ArrayData
209{
210 V4_ARRAYDATA(SparseArrayData)
211 V4_INTERNALCLASS(SparseArrayData)
212 V4_NEEDS_DESTROY
213
214 SparseArray *sparse() const { return d()->sparse; }
215 void setSparse(SparseArray *s) { d()->sparse = s; }
216
217 static uint allocate(Object *o, bool doubleSlot = false);
218 static void free(Heap::ArrayData *d, uint idx);
219
220 uint mappedIndex(uint index) const { return d()->mappedIndex(index); }
221
222 static Heap::ArrayData *reallocate(Object *o, uint n, bool enforceAttributes);
223 static ReturnedValue get(const Heap::ArrayData *d, uint index);
224 static bool put(Object *o, uint index, const Value &value);
225 static bool putArray(Object *o, uint index, const Value *values, uint n);
226 static bool del(Object *o, uint index);
227 static void setAttribute(Object *o, uint index, PropertyAttributes attrs);
228 static void push_front(Object *o, const Value *values, uint n);
229 static ReturnedValue pop_front(Object *o);
230 static uint truncate(Object *o, uint newLen);
231 static uint length(const Heap::ArrayData *d);
232};
233
234class ArrayElementLessThan
235{
236public:
237 inline ArrayElementLessThan(ExecutionEngine *engine, const Value &comparefn)
238 : m_engine(engine), m_comparefn(comparefn) {}
239
240 bool operator()(Value v1, Value v2) const;
241
242private:
243 ExecutionEngine *m_engine;
244 const Value &m_comparefn;
245};
246
247template <typename RandomAccessIterator, typename LessThan>
248void sortHelper(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
249{
250top:
251 using std::swap;
252
253 int span = int(end - start);
254 if (span < 2)
255 return;
256
257 --end;
258 RandomAccessIterator low = start, high = end - 1;
259 RandomAccessIterator pivot = start + span / 2;
260
261 if (lessThan(*end, *start))
262 swap(*end, *start);
263 if (span == 2)
264 return;
265
266 if (lessThan(*pivot, *start))
267 swap(*pivot, *start);
268 if (lessThan(*end, *pivot))
269 swap(*end, *pivot);
270 if (span == 3)
271 return;
272
273 swap(*pivot, *end);
274
275 while (low < high) {
276 while (low < high && lessThan(*low, *end))
277 ++low;
278
279 while (high > low && lessThan(*end, *high))
280 --high;
281
282 if (low < high) {
283 swap(*low, *high);
284 ++low;
285 --high;
286 } else {
287 break;
288 }
289 }
290
291 if (lessThan(*low, *end))
292 ++low;
293
294 swap(*end, *low);
295 sortHelper(start, low, lessThan);
296
297 start = low + 1;
298 ++end;
299 goto top;
300}
301
302namespace Heap {
303
304inline uint ArrayData::mappedIndex(uint index) const
305{
306 if (isSparse())
307 return static_cast<const SparseArrayData *>(this)->mappedIndex(index);
308 if (index >= values.size)
309 return UINT_MAX;
310 uint idx = static_cast<const SimpleArrayData *>(this)->mappedIndex(index);
311 return values[idx].isEmpty() ? UINT_MAX : idx;
312}
313
314bool ArrayData::getProperty(uint index, Property *p, PropertyAttributes *attrs)
315{
316 uint mapped = mappedIndex(index);
317 if (mapped == UINT_MAX) {
318 *attrs = Attr_Invalid;
319 return false;
320 }
321
322 *attrs = attributes(i: index);
323 if (p) {
324 p->value = *(PropertyIndex{ .base: this, .slot: values.values + mapped });
325 if (attrs->isAccessor())
326 p->set = *(PropertyIndex{ .base: this, .slot: values.values + mapped + 1 /*Object::SetterOffset*/ });
327 }
328 return true;
329}
330
331void ArrayData::setProperty(QV4::EngineBase *e, uint index, const Property *p)
332{
333 uint mapped = mappedIndex(index);
334 Q_ASSERT(mapped != UINT_MAX);
335 values.set(e, index: mapped, v: p->value);
336 if (attributes(i: index).isAccessor())
337 values.set(e, index: mapped + 1 /*QV4::Object::SetterOffset*/, v: p->set);
338}
339
340inline PropertyAttributes ArrayData::attributes(uint i) const
341{
342 if (isSparse())
343 return static_cast<const SparseArrayData *>(this)->attributes(i);
344 return static_cast<const SimpleArrayData *>(this)->attributes(i);
345}
346
347PropertyIndex ArrayData::getValueOrSetter(uint index, PropertyAttributes *attrs)
348{
349 uint idx = mappedIndex(index);
350 if (idx == UINT_MAX) {
351 *attrs = Attr_Invalid;
352 return { .base: nullptr, .slot: nullptr };
353 }
354
355 *attrs = attributes(i: index);
356 if (attrs->isAccessor())
357 ++idx;
358 return { .base: this, .slot: values.values + idx };
359}
360
361
362
363}
364
365}
366
367QT_END_NAMESPACE
368
369#endif
370

source code of qtdeclarative/src/qml/jsruntime/qv4arraydata_p.h