+++ /dev/null
-/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
- * THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include "config.h"
-#include "MapData.h"
-
-#include "CopiedAllocator.h"
-#include "CopyVisitorInlines.h"
-#include "ExceptionHelpers.h"
-#include "JSCJSValueInlines.h"
-#include "SlotVisitorInlines.h"
-
-#include <wtf/CryptographicallyRandomNumber.h>
-#include <wtf/MathExtras.h>
-
-
-namespace JSC {
-
-const ClassInfo MapData::s_info = { "MapData", 0, 0, 0, CREATE_METHOD_TABLE(MapData) };
-
-static const int32_t minimumMapSize = 8;
-
-MapData::MapData(VM& vm)
- : Base(vm, vm.mapDataStructure.get())
- , m_capacity(0)
- , m_size(0)
- , m_deletedCount(0)
- , m_iteratorCount(0)
- , m_entries(0)
-{
-}
-
-MapData::Entry* MapData::find(CallFrame* callFrame, KeyType key)
-{
- if (key.value.isString()) {
- auto iter = m_stringKeyedTable.find(asString(key.value)->value(callFrame).impl());
- if (iter == m_stringKeyedTable.end())
- return 0;
- return &m_entries[iter->value];
- }
- if (key.value.isCell()) {
- auto iter = m_cellKeyedTable.find(key.value.asCell());
- if (iter == m_cellKeyedTable.end())
- return 0;
- return &m_entries[iter->value];
- }
-
- auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
- if (iter == m_valueKeyedTable.end())
- return 0;
- return &m_entries[iter->value];
-}
-
-bool MapData::contains(CallFrame* callFrame, KeyType key)
-{
- return find(callFrame, key);
-}
-
-template <typename Map, typename Key> MapData::Entry* MapData::add(CallFrame* callFrame, Map& map, Key key, KeyType keyValue)
-{
- typename Map::iterator location = map.find(key);
- if (location != map.end())
- return &m_entries[location->value];
-
- if (!ensureSpaceForAppend(callFrame))
- return 0;
-
- auto result = map.add(key, m_size);
- RELEASE_ASSERT(result.isNewEntry);
- Entry* entry = &m_entries[m_size++];
- new (entry) Entry();
- entry->key.set(callFrame->vm(), this, keyValue.value);
- return entry;
-}
-
-void MapData::set(CallFrame* callFrame, KeyType key, JSValue value)
-{
- Entry* location = add(callFrame, key);
- if (!location)
- return;
- location->value.set(callFrame->vm(), this, value);
-}
-
-MapData::Entry* MapData::add(CallFrame* callFrame, KeyType key)
-{
- if (key.value.isString())
- return add(callFrame, m_stringKeyedTable, asString(key.value)->value(callFrame).impl(), key);
- if (key.value.isCell())
- return add(callFrame, m_cellKeyedTable, key.value.asCell(), key);
- return add(callFrame, m_valueKeyedTable, JSValue::encode(key.value), key);
-}
-
-JSValue MapData::get(CallFrame* callFrame, KeyType key)
-{
- if (Entry* entry = find(callFrame, key))
- return entry->value.get();
- return JSValue();
-}
-
-bool MapData::remove(CallFrame* callFrame, KeyType key)
-{
- int32_t location;
- if (key.value.isString()) {
- auto iter = m_stringKeyedTable.find(asString(key.value)->value(callFrame).impl());
- if (iter == m_stringKeyedTable.end())
- return false;
- location = iter->value;
- m_stringKeyedTable.remove(iter);
- } else if (key.value.isCell()) {
- auto iter = m_cellKeyedTable.find(key.value.asCell());
- if (iter == m_cellKeyedTable.end())
- return false;
- location = iter->value;
- m_cellKeyedTable.remove(iter);
- } else {
- auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
- if (iter == m_valueKeyedTable.end())
- return false;
- location = iter->value;
- m_valueKeyedTable.remove(iter);
- }
- m_entries[location].key.clear();
- m_entries[location].value.clear();
- m_deletedCount++;
- return true;
-}
-
-void MapData::replaceAndPackBackingStore(Entry* destination, int32_t newCapacity)
-{
- ASSERT(shouldPack());
- int32_t newEnd = 0;
- RELEASE_ASSERT(newCapacity > 0);
- for (int32_t i = 0; i < m_size; i++) {
- Entry& entry = m_entries[i];
- if (!entry.key)
- continue;
- ASSERT(newEnd < newCapacity);
- destination[newEnd] = entry;
-
- // We overwrite the old entry with a forwarding index for the new entry,
- // so that we can fix up our hash tables below without doing additional
- // hash lookups
- entry.value.setWithoutWriteBarrier(jsNumber(newEnd));
- newEnd++;
- }
-
- // Fixup for the hashmaps
- for (auto ptr = m_valueKeyedTable.begin(); ptr != m_valueKeyedTable.end(); ++ptr)
- ptr->value = m_entries[ptr->value].value.get().asInt32();
- for (auto ptr = m_cellKeyedTable.begin(); ptr != m_cellKeyedTable.end(); ++ptr)
- ptr->value = m_entries[ptr->value].value.get().asInt32();
- for (auto ptr = m_stringKeyedTable.begin(); ptr != m_stringKeyedTable.end(); ++ptr)
- ptr->value = m_entries[ptr->value].value.get().asInt32();
-
- ASSERT((m_size - newEnd) == m_deletedCount);
- m_deletedCount = 0;
-
- m_capacity = newCapacity;
- m_size = newEnd;
- m_entries = destination;
-
-}
-
-void MapData::replaceBackingStore(Entry* destination, int32_t newCapacity)
-{
- ASSERT(!shouldPack());
- RELEASE_ASSERT(newCapacity > 0);
- ASSERT(newCapacity >= m_capacity);
- memcpy(destination, m_entries, sizeof(Entry) * m_size);
- m_capacity = newCapacity;
- m_entries = destination;
-}
-
-CheckedBoolean MapData::ensureSpaceForAppend(CallFrame* callFrame)
-{
- if (m_capacity > m_size)
- return true;
-
- size_t requiredSize = std::max(m_capacity + (m_capacity / 2) + 1, minimumMapSize);
- void* newStorage = 0;
- DeferGC defer(*callFrame->heap());
- if (!callFrame->heap()->tryAllocateStorage(this, requiredSize * sizeof(Entry), &newStorage)) {
- throwOutOfMemoryError(callFrame);
- return false;
- }
- Entry* newEntries = static_cast<Entry*>(newStorage);
- if (shouldPack())
- replaceAndPackBackingStore(newEntries, requiredSize);
- else
- replaceBackingStore(newEntries, requiredSize);
- callFrame->heap()->writeBarrier(this);
- return true;
-}
-
-void MapData::visitChildren(JSCell* cell, SlotVisitor& visitor)
-{
- Base::visitChildren(cell, visitor);
- MapData* thisObject = jsCast<MapData*>(cell);
- Entry* entries = thisObject->m_entries;
- if (!entries)
- return;
- size_t size = thisObject->m_size;
- if (thisObject->m_deletedCount) {
- for (size_t i = 0; i < size; i++) {
- if (!entries[i].key)
- continue;
- visitor.append(&entries[i].key);
- visitor.append(&entries[i].value);
- }
- } else
- visitor.appendValues(&entries[0].key, size * (sizeof(Entry) / sizeof(WriteBarrier<Unknown>)));
-
- visitor.copyLater(thisObject, MapBackingStoreCopyToken, entries, thisObject->capacityInBytes());
-}
-
-void MapData::copyBackingStore(JSCell* cell, CopyVisitor& visitor, CopyToken token)
-{
- MapData* thisObject = jsCast<MapData*>(cell);
- if (token == MapBackingStoreCopyToken && visitor.checkIfShouldCopy(thisObject->m_entries)) {
- Entry* oldEntries = thisObject->m_entries;
- Entry* newEntries = static_cast<Entry*>(visitor.allocateNewSpace(thisObject->capacityInBytes()));
- if (thisObject->shouldPack())
- thisObject->replaceAndPackBackingStore(newEntries, thisObject->m_capacity);
- else
- thisObject->replaceBackingStore(newEntries, thisObject->m_capacity);
- visitor.didCopy(oldEntries, thisObject->capacityInBytes());
- }
- Base::copyBackingStore(cell, visitor, token);
-}
-
-void MapData::destroy(JSCell* cell)
-{
- static_cast<MapData*>(cell)->~MapData();
-}
-
-}
projects / apple / javascriptcore.git / blobdiff