Revision control
++ // Copyright (C) 2016 The Qt Company Ltd.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:significant
++ #ifndef QV4ARRAYDATA_H
++ #define QV4ARRAYDATA_H
++
++ //
++ // W A R N I N G
++ // -------------
++ //
++ // This file is not part of the Qt API. It exists purely as an
++ // implementation detail. This header file may change from version to
++ // version without notice, or even be removed.
++ //
++ // We mean it.
++ //
++
++ #include "qv4global_p.h"
++ #include "qv4managed_p.h"
++ #include "qv4property_p.h"
++ #include "qv4sparsearray_p.h"
++
++ QT_BEGIN_NAMESPACE
++
++ namespace QV4 {
++
++ #define V4_ARRAYDATA(DataClass) \
++ public: \
++ Q_MANAGED_CHECK \
++ typedef QV4::Heap::DataClass Data; \
++ static const QV4::ArrayVTable static_vtbl; \
++ static inline const QV4::VTable *staticVTable() { return &static_vtbl.vTable; } \
++ V4_MANAGED_SIZE_TEST \
++ const Data *d() const { return static_cast<const Data *>(m()); } \
++ Data *d() { return static_cast<Data *>(m()); }
++
++
++ struct ArrayData;
++
++ struct ArrayVTable
++ {
++ VTable vTable;
++ uint type;
++ Heap::ArrayData *(*reallocate)(Object *o, uint n, bool enforceAttributes);
++ ReturnedValue (*get)(const Heap::ArrayData *d, uint index);
++ bool (*put)(Object *o, uint index, const Value &value);
++ bool (*putArray)(Object *o, uint index, const Value *values, uint n);
++ bool (*del)(Object *o, uint index);
++ void (*setAttribute)(Object *o, uint index, PropertyAttributes attrs);
++ void (*push_front)(Object *o, const Value *values, uint n);
++ ReturnedValue (*pop_front)(Object *o);
++ uint (*truncate)(Object *o, uint newLen);
++ uint (*length)(const Heap::ArrayData *d);
++ };
++
++ namespace Heap {
++
++ #define ArrayDataMembers(class, Member) \
++ Member(class, NoMark, ushort, type) \
++ Member(class, NoMark, ushort, unused) \
++ Member(class, NoMark, uint, offset) \
++ Member(class, NoMark, PropertyAttributes *, attrs) \
++ Member(class, NoMark, SparseArray *, sparse) \
++ Member(class, ValueArray, ValueArray, values)
++
++ DECLARE_HEAP_OBJECT(ArrayData, Base) {
++ static void markObjects(Heap::Base *base, MarkStack *stack);
++
++ enum Type { Simple = 0, Sparse = 1, Custom = 2 };
++
++ bool isSparse() const { return type == Sparse; }
++
++ const ArrayVTable *vtable() const { return reinterpret_cast<const ArrayVTable *>(internalClass->vtable); }
++
++ inline ReturnedValue get(uint i) const {
++ return vtable()->get(this, i);
++ }
++ inline bool getProperty(uint index, Property *p, PropertyAttributes *attrs);
++ inline void setProperty(EngineBase *e, uint index, const Property *p);
++ inline PropertyIndex getValueOrSetter(uint index, PropertyAttributes *attrs);
++ inline PropertyAttributes attributes(uint i) const;
++
++ bool isEmpty(uint i) const {
++ return get(i) == Value::emptyValue().asReturnedValue();
++ }
++
++ inline uint length() const {
++ return vtable()->length(this);
++ }
++
++ void setArrayData(EngineBase *e, uint index, Value newVal) {
++ values.set(e, index, newVal);
++ }
++
++ uint mappedIndex(uint index) const;
++ };
++ static_assert(std::is_trivially_copyable_v<ArrayData>);
++ static_assert(std::is_trivially_default_constructible_v<ArrayData>);
++
++ struct SimpleArrayData : public ArrayData {
++ uint mappedIndex(uint index) const { index += offset; if (index >= values.alloc) index -= values.alloc; return index; }
++ const Value &data(uint index) const { return values[mappedIndex(index)]; }
++ void setData(EngineBase *e, uint index, Value newVal) {
++ values.set(e, mappedIndex(index), newVal);
++ }
++
++ PropertyAttributes attributes(uint i) const {
++ return attrs ? attrs[i] : Attr_Data;
++ }
++ };
++ static_assert(std::is_trivially_copyable_v<SimpleArrayData>);
++ static_assert(std::is_trivially_default_constructible_v<SimpleArrayData>);
++
++ struct SparseArrayData : public ArrayData {
++ void destroy() {
++ delete sparse;
++ ArrayData::destroy();
++ }
++
++ uint mappedIndex(uint index) const {
++ SparseArrayNode *n = sparse->findNode(index);
++ if (!n)
++ return UINT_MAX;
++ return n->value;
++ }
++
++ PropertyAttributes attributes(uint i) const {
++ if (!attrs)
++ return Attr_Data;
++ uint index = mappedIndex(i);
++ return index < UINT_MAX ? attrs[index] : Attr_Data;
++ }
++ };
++
++ }
++
++ struct Q_QML_EXPORT ArrayData : public Managed
++ {
++ typedef Heap::ArrayData::Type Type;
++ V4_MANAGED(ArrayData, Managed)
++ Q_MANAGED_TYPE(ArrayData);
++ enum {
++ IsArrayData = true
++ };
++
++ uint alloc() const { return d()->values.alloc; }
++ uint &alloc() { return d()->values.alloc; }
++ void setAlloc(uint a) { d()->values.alloc = a; }
++ Type type() const { return static_cast<Type>(d()->type); }
++ void setType(Type t) { d()->type = t; }
++ PropertyAttributes *attrs() const { return d()->attrs; }
++ void setAttrs(PropertyAttributes *a) { d()->attrs = a; }
++ const Value *arrayData() const { return d()->values.data(); }
++ void setArrayData(EngineBase *e, uint index, Value newVal) {
++ d()->setArrayData(e, index, newVal);
++ }
++
++ const ArrayVTable *vtable() const { return d()->vtable(); }
++ bool isSparse() const { return type() == Heap::ArrayData::Sparse; }
++
++ uint length() const {
++ return d()->length();
++ }
++
++ bool hasAttributes() const {
++ return attrs();
++ }
++ PropertyAttributes attributes(uint i) const {
++ return d()->attributes(i);
++ }
++
++ bool isEmpty(uint i) const {
++ return d()->isEmpty(i);
++ }
++
++ ReturnedValue get(uint i) const {
++ return d()->get(i);
++ }
++
++ static void ensureAttributes(Object *o);
++ static void realloc(Object *o, Type newType, uint alloc, bool enforceAttributes);
++
++ static void sort(ExecutionEngine *engine, Object *thisObject, const Value &comparefn, uint dataLen);
++ static uint append(Object *obj, ArrayObject *otherObj, uint n);
++ static void insert(Object *o, uint index, const Value *v, bool isAccessor = false);
++ };
++
++ struct Q_QML_EXPORT SimpleArrayData : public ArrayData
++ {
++ V4_ARRAYDATA(SimpleArrayData)
++ V4_INTERNALCLASS(SimpleArrayData)
++
++ uint mappedIndex(uint index) const { return d()->mappedIndex(index); }
++ Value data(uint index) const { return d()->data(index); }
++
++ uint &len() { return d()->values.size; }
++ uint len() const { return d()->values.size; }
++
++ static Heap::ArrayData *reallocate(Object *o, uint n, bool enforceAttributes);
++
++ static ReturnedValue get(const Heap::ArrayData *d, uint index);
++ static bool put(Object *o, uint index, const Value &value);
++ static bool putArray(Object *o, uint index, const Value *values, uint n);
++ static bool del(Object *o, uint index);
++ static void setAttribute(Object *o, uint index, PropertyAttributes attrs);
++ static void push_front(Object *o, const Value *values, uint n);
++ static ReturnedValue pop_front(Object *o);
++ static uint truncate(Object *o, uint newLen);
++ static uint length(const Heap::ArrayData *d);
++ };
++
++ struct Q_QML_EXPORT SparseArrayData : public ArrayData
++ {
++ V4_ARRAYDATA(SparseArrayData)
++ V4_INTERNALCLASS(SparseArrayData)
++ V4_NEEDS_DESTROY
++
++ SparseArray *sparse() const { return d()->sparse; }
++ void setSparse(SparseArray *s) { d()->sparse = s; }
++
++ static uint allocate(Object *o, bool doubleSlot = false);
++ static void free(Heap::ArrayData *d, uint idx);
++
++ uint mappedIndex(uint index) const { return d()->mappedIndex(index); }
++
++ static Heap::ArrayData *reallocate(Object *o, uint n, bool enforceAttributes);
++ static ReturnedValue get(const Heap::ArrayData *d, uint index);
++ static bool put(Object *o, uint index, const Value &value);
++ static bool putArray(Object *o, uint index, const Value *values, uint n);
++ static bool del(Object *o, uint index);
++ static void setAttribute(Object *o, uint index, PropertyAttributes attrs);
++ static void push_front(Object *o, const Value *values, uint n);
++ static ReturnedValue pop_front(Object *o);
++ static uint truncate(Object *o, uint newLen);
++ static uint length(const Heap::ArrayData *d);
++ };
++
++ class ArrayElementLessThan
++ {
++ public:
++ inline ArrayElementLessThan(ExecutionEngine *engine, const Value &comparefn)
++ : m_engine(engine), m_comparefn(comparefn) {}
++
++ bool operator()(Value v1, Value v2) const;
++
++ private:
++ ExecutionEngine *m_engine;
++ const Value &m_comparefn;
++ };
++
++ template <typename RandomAccessIterator, typename LessThan>
++ void sortHelper(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
++ {
++ top:
++ using std::swap;
++
++ int span = int(end - start);
++ if (span < 2)
++ return;
++
++ --end;
++ RandomAccessIterator low = start, high = end - 1;
++ RandomAccessIterator pivot = start + span / 2;
++
++ if (lessThan(*end, *start))
++ swap(*end, *start);
++ if (span == 2)
++ return;
++
++ if (lessThan(*pivot, *start))
++ swap(*pivot, *start);
++ if (lessThan(*end, *pivot))
++ swap(*end, *pivot);
++ if (span == 3)
++ return;
++
++ swap(*pivot, *end);
++
++ while (low < high) {
++ while (low < high && lessThan(*low, *end))
++ ++low;
++
++ while (high > low && lessThan(*end, *high))
++ --high;
++
++ if (low < high) {
++ swap(*low, *high);
++ ++low;
++ --high;
++ } else {
++ break;
++ }
++ }
++
++ if (lessThan(*low, *end))
++ ++low;
++
++ swap(*end, *low);
++ sortHelper(start, low, lessThan);
++
++ start = low + 1;
++ ++end;
++ goto top;
++ }
++
++ namespace Heap {
++
++ inline uint ArrayData::mappedIndex(uint index) const
++ {
++ if (isSparse())
++ return static_cast<const SparseArrayData *>(this)->mappedIndex(index);
++ if (index >= values.size)
++ return UINT_MAX;
++ uint idx = static_cast<const SimpleArrayData *>(this)->mappedIndex(index);
++ return values[idx].isEmpty() ? UINT_MAX : idx;
++ }
++
++ bool ArrayData::getProperty(uint index, Property *p, PropertyAttributes *attrs)
++ {
++ uint mapped = mappedIndex(index);
++ if (mapped == UINT_MAX) {
++ *attrs = Attr_Invalid;
++ return false;
++ }
++
++ *attrs = attributes(index);
++ if (p) {
++ p->value = *(PropertyIndex{ this, values.values + mapped });
++ if (attrs->isAccessor())
++ p->set = *(PropertyIndex{ this, values.values + mapped + 1 /*Object::SetterOffset*/ });
++ }
++ return true;
++ }
++
++ void ArrayData::setProperty(QV4::EngineBase *e, uint index, const Property *p)
++ {
++ uint mapped = mappedIndex(index);
++ Q_ASSERT(mapped != UINT_MAX);
++ values.set(e, mapped, p->value);
++ if (attributes(index).isAccessor())
++ values.set(e, mapped + 1 /*QV4::Object::SetterOffset*/, p->set);
++ }
++
++ inline PropertyAttributes ArrayData::attributes(uint i) const
++ {
++ if (isSparse())
++ return static_cast<const SparseArrayData *>(this)->attributes(i);
++ return static_cast<const SimpleArrayData *>(this)->attributes(i);
++ }
++
++ PropertyIndex ArrayData::getValueOrSetter(uint index, PropertyAttributes *attrs)
++ {
++ uint idx = mappedIndex(index);
++ if (idx == UINT_MAX) {
++ *attrs = Attr_Invalid;
++ return { nullptr, nullptr };
++ }
++
++ *attrs = attributes(index);
++ if (attrs->isAccessor())
++ ++idx;
++ return { this, values.values + idx };
++ }
++
++
++
++ }
++
++ }
++
++ QT_END_NAMESPACE
++
++ #endif