1 | // Copyright (C) 2018 Crimson AS <info@crimson.no> |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #include "qv4estable_p.h" |
5 | #include "qv4object_p.h" |
6 | |
7 | using namespace QV4; |
8 | |
9 | // The ES spec requires that Map/Set be implemented using a data structure that |
10 | // is a little different from most; it requires nonlinear access, and must also |
11 | // preserve the order of insertion of items in a deterministic way. |
12 | // |
13 | // This class implements those requirements, except for fast access: that |
14 | // will be addressed in a followup patch. |
15 | |
16 | ESTable::ESTable() |
17 | : m_capacity(8) |
18 | { |
19 | m_keys = (Value*)malloc(size: m_capacity * sizeof(Value)); |
20 | m_values = (Value*)malloc(size: m_capacity * sizeof(Value)); |
21 | memset(s: m_keys, c: 0, n: m_capacity); |
22 | memset(s: m_values, c: 0, n: m_capacity); |
23 | } |
24 | |
25 | ESTable::~ESTable() |
26 | { |
27 | free(ptr: m_keys); |
28 | free(ptr: m_values); |
29 | m_size = 0; |
30 | m_capacity = 0; |
31 | m_keys = nullptr; |
32 | m_values = nullptr; |
33 | } |
34 | |
35 | void ESTable::markObjects(MarkStack *s, bool isWeakMap) |
36 | { |
37 | for (uint i = 0; i < m_size; ++i) { |
38 | if (!isWeakMap) |
39 | m_keys[i].mark(markStack: s); |
40 | m_values[i].mark(markStack: s); |
41 | } |
42 | } |
43 | |
44 | // Pretends that there's nothing in the table. Doesn't actually free memory, as |
45 | // it will almost certainly be reused again anyway. |
46 | void ESTable::clear() |
47 | { |
48 | m_size = 0; |
49 | } |
50 | |
51 | // Update the table to contain \a value for a given \a key. The key is |
52 | // normalized, as required by the ES spec. |
53 | void ESTable::set(const Value &key, const Value &value) |
54 | { |
55 | for (uint i = 0; i < m_size; ++i) { |
56 | if (m_keys[i].sameValueZero(other: key)) { |
57 | m_values[i] = value; |
58 | return; |
59 | } |
60 | } |
61 | |
62 | if (m_capacity == m_size) { |
63 | uint oldCap = m_capacity; |
64 | m_capacity *= 2; |
65 | m_keys = (Value*)realloc(ptr: m_keys, size: m_capacity * sizeof(Value)); |
66 | m_values = (Value*)realloc(ptr: m_values, size: m_capacity * sizeof(Value)); |
67 | memset(s: m_keys + oldCap, c: 0, n: m_capacity - oldCap); |
68 | memset(s: m_values + oldCap, c: 0, n: m_capacity - oldCap); |
69 | } |
70 | |
71 | Value nk = key; |
72 | if (nk.isDouble()) { |
73 | if (nk.doubleValue() == 0 && std::signbit(x: nk.doubleValue())) |
74 | nk = Value::fromDouble(d: +0); |
75 | } |
76 | |
77 | m_keys[m_size] = nk; |
78 | m_values[m_size] = value; |
79 | |
80 | m_size++; |
81 | } |
82 | |
83 | // Returns true if the table contains \a key, false otherwise. |
84 | bool ESTable::has(const Value &key) const |
85 | { |
86 | for (uint i = 0; i < m_size; ++i) { |
87 | if (m_keys[i].sameValueZero(other: key)) |
88 | return true; |
89 | } |
90 | |
91 | return false; |
92 | } |
93 | |
94 | // Fetches the value for the given \a key, and if \a hasValue is passed in, |
95 | // it is set depending on whether or not the given key was found. |
96 | ReturnedValue ESTable::get(const Value &key, bool *hasValue) const |
97 | { |
98 | for (uint i = 0; i < m_size; ++i) { |
99 | if (m_keys[i].sameValueZero(other: key)) { |
100 | if (hasValue) |
101 | *hasValue = true; |
102 | return m_values[i].asReturnedValue(); |
103 | } |
104 | } |
105 | |
106 | if (hasValue) |
107 | *hasValue = false; |
108 | return Encode::undefined(); |
109 | } |
110 | |
111 | // Removes the given \a key from the table |
112 | bool ESTable::remove(const Value &key) |
113 | { |
114 | bool found = false; |
115 | uint idx = 0; |
116 | for (; idx < m_size; ++idx) { |
117 | if (m_keys[idx].sameValueZero(other: key)) { |
118 | found = true; |
119 | break; |
120 | } |
121 | } |
122 | |
123 | if (found == true) { |
124 | memmove(dest: m_keys + idx, src: m_keys + idx + 1, n: (m_size - idx)*sizeof(Value)); |
125 | memmove(dest: m_values + idx, src: m_values + idx + 1, n: (m_size - idx)*sizeof(Value)); |
126 | m_size--; |
127 | } |
128 | return found; |
129 | } |
130 | |
131 | // Returns the size of the table. Note that the size may not match the underlying allocation. |
132 | uint ESTable::size() const |
133 | { |
134 | return m_size; |
135 | } |
136 | |
137 | // Retrieves a key and value for a given \a idx, and places them in \a key and |
138 | // \a value. They must be valid pointers. |
139 | void ESTable::iterate(uint idx, Value *key, Value *value) |
140 | { |
141 | Q_ASSERT(idx < m_size); |
142 | Q_ASSERT(key); |
143 | Q_ASSERT(value); |
144 | *key = m_keys[idx]; |
145 | *value = m_values[idx]; |
146 | } |
147 | |
148 | void ESTable::removeUnmarkedKeys() |
149 | { |
150 | uint idx = 0; |
151 | uint toIdx = 0; |
152 | for (; idx < m_size; ++idx) { |
153 | Q_ASSERT(m_keys[idx].isObject()); |
154 | Object &o = static_cast<Object &>(m_keys[idx]); |
155 | if (o.d()->isMarked()) { |
156 | m_keys[toIdx] = m_keys[idx]; |
157 | m_values[toIdx] = m_values[idx]; |
158 | ++toIdx; |
159 | } |
160 | } |
161 | m_size = toIdx; |
162 | } |
163 | |
164 | |