runtime/MapDataInlines.h

   1 /*
   2  * Copyright (C) 2013 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 = nullptr;
  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[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[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[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[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[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[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[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[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[ptr->value].key().get().asInt32();
 199     for (auto ptr = m_cellKeyedTable.begin(); ptr != m_cellKeyedTable.end(); ++ptr)
 200         ptr->value = m_entries[ptr->value].key().get().asInt32();
 201     for (auto ptr = m_stringKeyedTable.begin(); ptr != m_stringKeyedTable.end(); ++ptr)
 202         ptr->value = m_entries[ptr->value].key().get().asInt32();
 203     for (auto ptr = m_symbolKeyedTable.begin(); ptr != m_symbolKeyedTable.end(); ++ptr)
 204         ptr->value = m_entries[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 = 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, sizeof(Entry) * m_size);
 221     m_capacity = newCapacity;
 222     m_entries = 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;
 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, entries, 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)) {
 271         Entry* oldEntries = m_entries;
 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 }