runtime/MapData.cpp

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