runtime/MapData.h

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