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 | |
22 | QT_BEGIN_NAMESPACE |
23 | |
24 | namespace 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 | |
37 | struct ArrayData; |
38 | |
39 | struct 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 | |
55 | namespace 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 | |
65 | DECLARE_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 | }; |
96 | Q_STATIC_ASSERT(std::is_trivial_v<ArrayData>); |
97 | |
98 | struct 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 | }; |
109 | Q_STATIC_ASSERT(std::is_trivial_v<SimpleArrayData>); |
110 | |
111 | struct 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 | |
134 | struct 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 | |
184 | struct 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 | |
208 | struct 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 | |
234 | class ArrayElementLessThan |
235 | { |
236 | public: |
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 | |
242 | private: |
243 | ExecutionEngine *m_engine; |
244 | const Value &m_comparefn; |
245 | }; |
246 | |
247 | template <typename RandomAccessIterator, typename LessThan> |
248 | void sortHelper(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan) |
249 | { |
250 | top: |
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 | |
302 | namespace Heap { |
303 | |
304 | inline 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 | |
314 | bool 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 | |
331 | void 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 | |
340 | inline 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 | |
347 | PropertyIndex 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 | |
367 | QT_END_NAMESPACE |
368 | |
369 | #endif |
370 | |