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#ifndef MapData_h 27#define MapData_h 28 29#include "JSCell.h" 30#include "Structure.h" 31#include <wtf/HashFunctions.h> 32#include <wtf/HashMap.h> 33#include <wtf/MathExtras.h> 34 35namespace JSC { 36 37class MapData : public JSCell { 38public: 39 typedef JSCell Base; 40 41 struct const_iterator { 42 const_iterator(const MapData*); 43 ~const_iterator(); 44 const WTF::KeyValuePair<JSValue, JSValue> operator*() const; 45 JSValue key() const { ASSERT(!atEnd()); return m_mapData->m_entries[m_index].key.get(); } 46 JSValue value() const { ASSERT(!atEnd()); return m_mapData->m_entries[m_index].value.get(); } 47 void operator++() { ASSERT(!atEnd()); internalIncrement(); } 48 static const_iterator end(const MapData*); 49 bool operator!=(const const_iterator& other); 50 bool operator==(const const_iterator& other); 51 void finish() { m_index = std::numeric_limits<int32_t>::max(); } 52 53 bool ensureSlot(); 54 55 private: 56 // This is a bit gnarly. We use an index of -1 to indicate the 57 // "end()" iterator. By casting to unsigned we can immediately 58 // test if both iterators are at the end of their iteration. 59 // We need this in order to keep the common case (eg. iter != end()) 60 // fast. 61 bool atEnd() const { return static_cast<size_t>(m_index) >= static_cast<size_t>(m_mapData->m_size); } 62 void internalIncrement(); 63 const MapData* m_mapData; 64 int32_t m_index; 65 }; 66 67 struct KeyType { 68 ALWAYS_INLINE KeyType() { } 69 KeyType(JSValue); 70 JSValue value; 71 }; 72 73 static MapData* create(VM& vm) 74 { 75 MapData* mapData = new (NotNull, allocateCell<MapData>(vm.heap)) MapData(vm); 76 mapData->finishCreation(vm); 77 return mapData; 78 } 79 80 static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype) 81 { 82 return Structure::create(vm, globalObject, prototype, TypeInfo(CompoundType, StructureFlags), info()); 83 } 84 85 static const bool needsDestruction = true; 86 static const bool hasImmortalStructure = true; 87 88 JS_EXPORT_PRIVATE void set(CallFrame*, KeyType, JSValue); 89 JSValue get(CallFrame*, KeyType); 90 bool remove(CallFrame*, KeyType); 91 bool contains(CallFrame*, KeyType); 92 size_t size(CallFrame*) const { return m_size - m_deletedCount; } 93 94 const_iterator begin() const { return const_iterator(this); } 95 const_iterator end() const { return const_iterator::end(this); } 96 97 void clear(); 98 99 DECLARE_INFO; 100 static const unsigned StructureFlags = OverridesVisitChildren | StructureIsImmortal | Base::StructureFlags; 101 102private: 103 typedef WTF::UnsignedWithZeroKeyHashTraits<int32_t> IndexTraits; 104 105 // Our marking functions expect Entry to maintain this layout, and have all 106 // fields be WriteBarrier<Unknown> 107 struct Entry { 108 WriteBarrier<Unknown> key; 109 WriteBarrier<Unknown> value; 110 }; 111 112 typedef HashMap<JSCell*, int32_t, typename WTF::DefaultHash<JSCell*>::Hash, WTF::HashTraits<JSCell*>, IndexTraits> CellKeyedMap; 113 typedef HashMap<EncodedJSValue, int32_t, EncodedJSValueHash, EncodedJSValueHashTraits, IndexTraits> ValueKeyedMap; 114 typedef HashMap<StringImpl*, int32_t, typename WTF::DefaultHash<StringImpl*>::Hash, WTF::HashTraits<StringImpl*>, IndexTraits> StringKeyedMap; 115 116 size_t capacityInBytes() { return m_capacity * sizeof(Entry); } 117 118 MapData(VM&); 119 static void destroy(JSCell*); 120 static void visitChildren(JSCell*, SlotVisitor&); 121 static void copyBackingStore(JSCell*, CopyVisitor&, CopyToken); 122 123 124 ALWAYS_INLINE Entry* find(CallFrame*, KeyType); 125 ALWAYS_INLINE Entry* add(CallFrame*, KeyType); 126 template <typename Map, typename Key> ALWAYS_INLINE Entry* add(CallFrame*, Map&, Key, KeyType); 127 128 ALWAYS_INLINE bool shouldPack() const { return m_deletedCount && !m_iteratorCount; } 129 CheckedBoolean ensureSpaceForAppend(CallFrame*); 130 131 ALWAYS_INLINE void replaceAndPackBackingStore(Entry* destination, int32_t newSize); 132 ALWAYS_INLINE void replaceBackingStore(Entry* destination, int32_t newSize); 133 134 CellKeyedMap m_cellKeyedTable; 135 ValueKeyedMap m_valueKeyedTable; 136 StringKeyedMap m_stringKeyedTable; 137 int32_t m_capacity; 138 int32_t m_size; 139 int32_t m_deletedCount; 140 mutable int32_t m_iteratorCount; 141 Entry* m_entries; 142}; 143 144ALWAYS_INLINE void MapData::clear() 145{ 146 m_cellKeyedTable.clear(); 147 m_valueKeyedTable.clear(); 148 m_stringKeyedTable.clear(); 149 m_capacity = 0; 150 m_size = 0; 151 m_deletedCount = 0; 152 m_entries = nullptr; 153} 154 155ALWAYS_INLINE MapData::KeyType::KeyType(JSValue v) 156{ 157 if (!v.isDouble()) { 158 value = v; 159 return; 160 } 161 double d = v.asDouble(); 162 if (std::isnan(d) || (std::signbit(d) && d == 0.0)) { 163 value = v; 164 return; 165 } 166 167 int i = static_cast<int>(v.asDouble()); 168 if (i != d) 169 value = v; 170 else 171 value = jsNumber(i); 172} 173 174ALWAYS_INLINE void MapData::const_iterator::internalIncrement() 175{ 176 Entry* entries = m_mapData->m_entries; 177 size_t index = m_index + 1; 178 size_t end = m_mapData->m_size; 179 while (index < end && !entries[index].key) 180 index++; 181 m_index = index; 182} 183 184ALWAYS_INLINE bool MapData::const_iterator::ensureSlot() 185{ 186 // When an iterator exists outside of host cost it is possible for 187 // the containing map to be modified 188 Entry* entries = m_mapData->m_entries; 189 size_t index = m_index; 190 size_t end = m_mapData->m_size; 191 if (index < end && entries[index].key) 192 return true; 193 internalIncrement(); 194 return static_cast<size_t>(m_index) < end; 195} 196 197ALWAYS_INLINE MapData::const_iterator::const_iterator(const MapData* mapData) 198 : m_mapData(mapData) 199 , m_index(-1) 200{ 201 internalIncrement(); 202} 203 204ALWAYS_INLINE MapData::const_iterator::~const_iterator() 205{ 206 m_mapData->m_iteratorCount--; 207} 208 209ALWAYS_INLINE const WTF::KeyValuePair<JSValue, JSValue> MapData::const_iterator::operator*() const 210{ 211 Entry* entry = &m_mapData->m_entries[m_index]; 212 return WTF::KeyValuePair<JSValue, JSValue>(entry->key.get(), entry->value.get()); 213} 214 215ALWAYS_INLINE MapData::const_iterator MapData::const_iterator::end(const MapData* mapData) 216{ 217 const_iterator result(mapData); 218 result.m_index = -1; 219 return result; 220} 221 222ALWAYS_INLINE bool MapData::const_iterator::operator!=(const const_iterator& other) 223{ 224 ASSERT(other.m_mapData == m_mapData); 225 if (atEnd() && other.atEnd()) 226 return false; 227 return m_index != other.m_index; 228} 229 230ALWAYS_INLINE bool MapData::const_iterator::operator==(const const_iterator& other) 231{ 232 return !(*this != other); 233} 234 235} 236 237#endif /* !defined(MapData_h) */ 238