38f5ffe60afc3fb2abfea0f5405808e09c1a3ff3
[WebKit-https.git] / Source / JavaScriptCore / runtime / MapDataInlines.h
1 /*
2  * Copyright (C) 2013, 2016 Apple Inc. All rights reserved.
3  * Copyright (C) 2015 Yusuke Suzuki <utatane.tea@gmail.com>.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24  * THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "CopiedAllocator.h"
28 #include "CopyVisitorInlines.h"
29 #include "ExceptionHelpers.h"
30 #include "JSCJSValueInlines.h"
31 #include "MapData.h"
32 #include "SlotVisitorInlines.h"
33
34 #include <wtf/CryptographicallyRandomNumber.h>
35 #include <wtf/MathExtras.h>
36
37
38 namespace JSC {
39
40 template<typename Entry, typename JSIterator>
41 inline void MapDataImpl<Entry, JSIterator>::clear()
42 {
43     m_cellKeyedTable.clear();
44     m_valueKeyedTable.clear();
45     m_stringKeyedTable.clear();
46     m_symbolKeyedTable.clear();
47     m_capacity = 0;
48     m_size = 0;
49     m_deletedCount = 0;
50     m_entries.clear();
51     m_iterators.forEach([](JSIterator* iterator, JSIterator*) {
52         iterator->iteratorData()->didRemoveAllEntries();
53     });
54 }
55
56 template<typename Entry, typename JSIterator>
57 inline Entry* MapDataImpl<Entry, JSIterator>::find(ExecState* exec, KeyType key)
58 {
59     if (key.value.isString()) {
60         auto iter = m_stringKeyedTable.find(asString(key.value)->value(exec).impl());
61         if (iter == m_stringKeyedTable.end())
62             return 0;
63         return &m_entries.get()[iter->value];
64     }
65     if (key.value.isSymbol()) {
66         auto iter = m_symbolKeyedTable.find(asSymbol(key.value)->privateName().uid());
67         if (iter == m_symbolKeyedTable.end())
68             return 0;
69         return &m_entries.get()[iter->value];
70     }
71     if (key.value.isCell()) {
72         auto iter = m_cellKeyedTable.find(key.value.asCell());
73         if (iter == m_cellKeyedTable.end())
74             return 0;
75         return &m_entries.get()[iter->value];
76     }
77
78     auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
79     if (iter == m_valueKeyedTable.end())
80         return 0;
81     return &m_entries.get()[iter->value];
82 }
83
84 template<typename Entry, typename JSIterator>
85 inline bool MapDataImpl<Entry, JSIterator>::contains(ExecState* exec, KeyType key)
86 {
87     return find(exec, key);
88 }
89
90 template<typename Entry, typename JSIterator>
91 template <typename Map, typename Key>
92 inline Entry* MapDataImpl<Entry, JSIterator>::add(ExecState* exec, JSCell* owner, Map& map, Key key, KeyType keyValue)
93 {
94     typename Map::iterator location = map.find(key);
95     if (location != map.end())
96         return &m_entries.get()[location->value];
97
98     if (!ensureSpaceForAppend(exec, owner))
99         return 0;
100
101     auto result = map.add(key, m_size);
102     RELEASE_ASSERT(result.isNewEntry);
103     Entry* entry = &m_entries.get()[m_size++];
104     new (entry) Entry();
105     entry->setKey(exec->vm(), owner, keyValue.value);
106     return entry;
107 }
108
109 template<typename Entry, typename JSIterator>
110 inline void MapDataImpl<Entry, JSIterator>::set(ExecState* exec, JSCell* owner, KeyType key, JSValue value)
111 {
112     Entry* location = add(exec, owner, key);
113     if (!location)
114         return;
115     location->setValue(exec->vm(), owner, value);
116 }
117
118 template<typename Entry, typename JSIterator>
119 inline Entry* MapDataImpl<Entry, JSIterator>::add(ExecState* exec, JSCell* owner, KeyType key)
120 {
121     if (key.value.isString())
122         return add(exec, owner, m_stringKeyedTable, asString(key.value)->value(exec).impl(), key);
123     if (key.value.isSymbol())
124         return add(exec, owner, m_symbolKeyedTable, asSymbol(key.value)->privateName().uid(), key);
125     if (key.value.isCell())
126         return add(exec, owner, m_cellKeyedTable, key.value.asCell(), key);
127     return add(exec, owner, m_valueKeyedTable, JSValue::encode(key.value), key);
128 }
129
130 template<typename Entry, typename JSIterator>
131 inline JSValue MapDataImpl<Entry, JSIterator>::get(ExecState* exec, KeyType key)
132 {
133     if (Entry* entry = find(exec, key))
134         return entry->value().get();
135     return JSValue();
136 }
137
138 template<typename Entry, typename JSIterator>
139 inline bool MapDataImpl<Entry, JSIterator>::remove(ExecState* exec, KeyType key)
140 {
141     int32_t location;
142     if (key.value.isString()) {
143         auto iter = m_stringKeyedTable.find(asString(key.value)->value(exec).impl());
144         if (iter == m_stringKeyedTable.end())
145             return false;
146         location = iter->value;
147         m_stringKeyedTable.remove(iter);
148     }  else if (key.value.isSymbol()) {
149         auto iter = m_symbolKeyedTable.find(asSymbol(key.value)->privateName().uid());
150         if (iter == m_symbolKeyedTable.end())
151             return false;
152         location = iter->value;
153         m_symbolKeyedTable.remove(iter);
154     } else if (key.value.isCell()) {
155         auto iter = m_cellKeyedTable.find(key.value.asCell());
156         if (iter == m_cellKeyedTable.end())
157             return false;
158         location = iter->value;
159         m_cellKeyedTable.remove(iter);
160     } else {
161         auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
162         if (iter == m_valueKeyedTable.end())
163             return false;
164         location = iter->value;
165         m_valueKeyedTable.remove(iter);
166     }
167     m_entries.get()[location].clear();
168     m_deletedCount++;
169     return true;
170 }
171
172 template<typename Entry, typename JSIterator>
173 inline void MapDataImpl<Entry, JSIterator>::replaceAndPackBackingStore(Entry* destination, int32_t newCapacity)
174 {
175     ASSERT(shouldPack());
176     int32_t newEnd = 0;
177     RELEASE_ASSERT(newCapacity > 0);
178     for (int32_t i = 0; i < m_size; i++) {
179         Entry& entry = m_entries.get()[i];
180         if (!entry.key()) {
181             m_iterators.forEach([newEnd](JSIterator* iterator, JSIterator*) {
182                 iterator->iteratorData()->didRemoveEntry(newEnd);
183             });
184             continue;
185         }
186         ASSERT(newEnd < newCapacity);
187         destination[newEnd] = entry;
188
189         // We overwrite the old entry with a forwarding index for the new entry,
190         // so that we can fix up our hash tables below without doing additional
191         // hash lookups
192         entry.setKeyWithoutWriteBarrier(jsNumber(newEnd));
193         newEnd++;
194     }
195
196     // Fixup for the hashmaps
197     for (auto ptr = m_valueKeyedTable.begin(); ptr != m_valueKeyedTable.end(); ++ptr)
198         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
199     for (auto ptr = m_cellKeyedTable.begin(); ptr != m_cellKeyedTable.end(); ++ptr)
200         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
201     for (auto ptr = m_stringKeyedTable.begin(); ptr != m_stringKeyedTable.end(); ++ptr)
202         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
203     for (auto ptr = m_symbolKeyedTable.begin(); ptr != m_symbolKeyedTable.end(); ++ptr)
204         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
205
206     ASSERT((m_size - newEnd) == m_deletedCount);
207     m_deletedCount = 0;
208
209     m_capacity = newCapacity;
210     m_size = newEnd;
211     m_entries.setWithoutBarrier(destination);
212 }
213
214 template<typename Entry, typename JSIterator>
215 inline void MapDataImpl<Entry, JSIterator>::replaceBackingStore(Entry* destination, int32_t newCapacity)
216 {
217     ASSERT(!shouldPack());
218     RELEASE_ASSERT(newCapacity > 0);
219     ASSERT(newCapacity >= m_capacity);
220     memcpy(destination, m_entries.get(), sizeof(Entry) * m_size);
221     m_capacity = newCapacity;
222     m_entries.setWithoutBarrier(destination);
223 }
224
225 template<typename Entry, typename JSIterator>
226 inline CheckedBoolean MapDataImpl<Entry, JSIterator>::ensureSpaceForAppend(ExecState* exec, JSCell* owner)
227 {
228     if (m_capacity > m_size)
229         return true;
230
231     size_t requiredSize = std::max(m_capacity + (m_capacity / 2) + 1, static_cast<int32_t>(minimumMapSize));
232     void* newStorage = nullptr;
233     DeferGC defer(*exec->heap());
234     if (!exec->heap()->tryAllocateStorage(owner, requiredSize * sizeof(Entry), &newStorage)) {
235         throwOutOfMemoryError(exec);
236         return false;
237     }
238     Entry* newEntries = static_cast<Entry*>(newStorage);
239     if (shouldPack())
240         replaceAndPackBackingStore(newEntries, requiredSize);
241     else
242         replaceBackingStore(newEntries, requiredSize);
243     exec->heap()->writeBarrier(owner);
244     return true;
245 }
246
247 template<typename Entry, typename JSIterator>
248 inline void MapDataImpl<Entry, JSIterator>::visitChildren(JSCell* owner, SlotVisitor& visitor)
249 {
250     Entry* entries = m_entries.get();
251     if (!entries)
252         return;
253     if (m_deletedCount) {
254         for (int32_t i = 0; i < m_size; i++) {
255             if (!entries[i].key())
256                 continue;
257             entries[i].visitChildren(visitor);
258         }
259     } else {
260         // Guaranteed that all fields of Entry type is WriteBarrier<Unknown>.
261         visitor.appendValues(reinterpret_cast<WriteBarrier<Unknown>*>(&entries[0]), m_size * (sizeof(Entry) / sizeof(WriteBarrier<Unknown>)));
262     }
263
264     visitor.copyLater(owner, MapBackingStoreCopyToken, m_entries.get(), capacityInBytes());
265 }
266
267 template<typename Entry, typename JSIterator>
268 inline void MapDataImpl<Entry, JSIterator>::copyBackingStore(CopyVisitor& visitor, CopyToken token)
269 {
270     if (token == MapBackingStoreCopyToken && visitor.checkIfShouldCopy(m_entries.get())) {
271         Entry* oldEntries = m_entries.get();
272         Entry* newEntries = static_cast<Entry*>(visitor.allocateNewSpace(capacityInBytes()));
273         if (shouldPack())
274             replaceAndPackBackingStore(newEntries, m_capacity);
275         else
276             replaceBackingStore(newEntries, m_capacity);
277         visitor.didCopy(oldEntries, capacityInBytes());
278     }
279 }
280
281 template<typename Entry, typename JSIterator>
282 inline auto MapDataImpl<Entry, JSIterator>::createIteratorData(JSIterator* iterator) -> IteratorData
283 {
284     m_iterators.set(iterator, iterator);
285     return IteratorData(this);
286 }
287
288 }