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 "WeakGCMapInlines.h"
  31 #include <wtf/HashFunctions.h>
  32 #include <wtf/HashMap.h>
  33 #include <wtf/MathExtras.h>
  34 #include <wtf/RefCounted.h>
  35 #include <wtf/RefPtr.h>
  36 #include <wtf/Vector.h>
  37
  38 namespace JSC {
  39
  40 class ExecState;
  41 class VM;
  42
  43 template<typename Entry, typename JSIterator>
  44 class MapDataImpl {
  45 public:
  46     enum : int32_t {
  47         minimumMapSize = 8
  48     };
  49
  50     class IteratorData {
  51     public:
  52         friend class MapDataImpl;
  53
  54         IteratorData(const MapDataImpl*);
  55         bool next(WTF::KeyValuePair<JSValue, JSValue>&);
  56
  57         // This function is called while packing a map's backing store. The
  58         // passed-in index is the new index the entry would have after packing.
  59         void didRemoveEntry(int32_t packedIndex)
  60         {
  61             if (isFinished())
  62                 return;
  63
  64             if (m_index <= packedIndex)
  65                 return;
  66
  67             --m_index;
  68         }
  69
  70         void didRemoveAllEntries()
  71         {
  72             if (isFinished())
  73                 return;
  74             m_index = 0;
  75         }
  76
  77         void finish()
  78         {
  79             m_index = -1;
  80         }
  81
  82     private:
  83         bool ensureSlot() const;
  84         bool isFinished() const { return m_index == -1; }
  85         int32_t refreshCursor() const;
  86
  87         const MapDataImpl* m_mapData;
  88         mutable int32_t m_index;
  89     };
  90
  91     struct KeyType {
  92         ALWAYS_INLINE KeyType() { }
  93         KeyType(JSValue);
  94         JSValue value;
  95     };
  96
  97     MapDataImpl(VM&);
  98
  99     void set(ExecState*, JSCell* owner, KeyType, JSValue);
 100     JSValue get(ExecState*, KeyType);
 101     bool remove(ExecState*, KeyType);
 102     bool contains(ExecState*, KeyType);
 103     size_t size(ExecState*) const { return m_size - m_deletedCount; }
 104
 105     IteratorData createIteratorData(JSIterator*);
 106
 107     void clear();
 108
 109     void visitChildren(JSCell* owner, SlotVisitor&);
 110     void copyBackingStore(CopyVisitor&, CopyToken);
 111
 112 private:
 113     typedef WTF::UnsignedWithZeroKeyHashTraits<int32_t> IndexTraits;
 114
 115     typedef HashMap<JSCell*, int32_t, typename WTF::DefaultHash<JSCell*>::Hash, WTF::HashTraits<JSCell*>, IndexTraits> CellKeyedMap;
 116     typedef HashMap<EncodedJSValue, int32_t, EncodedJSValueHash, EncodedJSValueHashTraits, IndexTraits> ValueKeyedMap;
 117     typedef HashMap<StringImpl*, int32_t, typename WTF::DefaultHash<StringImpl*>::Hash, WTF::HashTraits<StringImpl*>, IndexTraits> StringKeyedMap;
 118     typedef HashMap<SymbolImpl*, int32_t, typename WTF::PtrHash<SymbolImpl*>, WTF::HashTraits<SymbolImpl*>, IndexTraits> SymbolKeyedMap;
 119
 120     size_t capacityInBytes() { return m_capacity * sizeof(Entry); }
 121
 122     ALWAYS_INLINE Entry* find(ExecState*, KeyType);
 123     ALWAYS_INLINE Entry* add(ExecState*, JSCell* owner, KeyType);
 124     template <typename Map, typename Key> ALWAYS_INLINE Entry* add(ExecState*, JSCell* owner, Map&, Key, KeyType);
 125
 126     ALWAYS_INLINE bool shouldPack() const { return m_deletedCount; }
 127     CheckedBoolean ensureSpaceForAppend(ExecState*, JSCell* owner);
 128
 129     ALWAYS_INLINE void replaceAndPackBackingStore(Entry* destination, int32_t newSize);
 130     ALWAYS_INLINE void replaceBackingStore(Entry* destination, int32_t newSize);
 131
 132     CellKeyedMap m_cellKeyedTable;
 133     ValueKeyedMap m_valueKeyedTable;
 134     StringKeyedMap m_stringKeyedTable;
 135     SymbolKeyedMap m_symbolKeyedTable;
 136     int32_t m_capacity;
 137     int32_t m_size;
 138     int32_t m_deletedCount;
 139     Entry* m_entries;
 140     WeakGCMap<JSIterator*, JSIterator> m_iterators;
 141 };
 142
 143 template<typename Entry, typename JSIterator>
 144 ALWAYS_INLINE MapDataImpl<Entry, JSIterator>::MapDataImpl(VM& vm)
 145     : m_capacity(0)
 146     , m_size(0)
 147     , m_deletedCount(0)
 148     , m_entries(nullptr)
 149     , m_iterators(vm)
 150 {
 151 }
 152
 153 template<typename Entry, typename JSIterator>
 154 ALWAYS_INLINE MapDataImpl<Entry, JSIterator>::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)) {
 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 template<typename Entry, typename JSIterator>
 174 ALWAYS_INLINE MapDataImpl<Entry, JSIterator>::IteratorData::IteratorData(const MapDataImpl<Entry, JSIterator>* mapData)
 175     : m_mapData(mapData)
 176     , m_index(0)
 177 {
 178 }
 179
 180 template<typename Entry, typename JSIterator>
 181 ALWAYS_INLINE bool MapDataImpl<Entry, JSIterator>::IteratorData::next(WTF::KeyValuePair<JSValue, JSValue>& pair)
 182 {
 183     if (!ensureSlot())
 184         return false;
 185     Entry* entry = &m_mapData->m_entries[m_index];
 186     pair = WTF::KeyValuePair<JSValue, JSValue>(entry->key().get(), entry->value().get());
 187     m_index += 1;
 188     return true;
 189 }
 190
 191 // This is a bit gnarly. We use an index of -1 to indicate the
 192 // finished state. By casting to unsigned we can immediately
 193 // test if both iterators are at the end of their iteration.
 194 template<typename Entry, typename JSIterator>
 195 ALWAYS_INLINE bool MapDataImpl<Entry, JSIterator>::IteratorData::ensureSlot() const
 196 {
 197     int32_t index = refreshCursor();
 198     return static_cast<size_t>(index) < static_cast<size_t>(m_mapData->m_size);
 199 }
 200
 201 template<typename Entry, typename JSIterator>
 202 ALWAYS_INLINE int32_t MapDataImpl<Entry, JSIterator>::IteratorData::refreshCursor() const
 203 {
 204     if (isFinished())
 205         return m_index;
 206
 207     Entry* entries = m_mapData->m_entries;
 208     size_t end = m_mapData->m_size;
 209     while (static_cast<size_t>(m_index) < end && !entries[m_index].key())
 210         m_index++;
 211     return m_index;
 212 }
 213
 214 }
 215
 216 #endif /* !defined(MapData_h) */