c0504a67599d262241d789636d017f56d854ee34
[WebKit-https.git] / Source / JavaScriptCore / 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 { RELEASE_ASSERT(!atEnd()); return m_mapData->m_entries[m_index].key.get(); }
46         JSValue value() const { RELEASE_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(CellType, 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 = StructureIsImmortal | Base::StructureFlags;
101
102 private:
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
144 ALWAYS_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
155 ALWAYS_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
174 ALWAYS_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     
184 ALWAYS_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
197 ALWAYS_INLINE MapData::const_iterator::const_iterator(const MapData* mapData)
198     : m_mapData(mapData)
199     , m_index(-1)
200 {
201     internalIncrement();
202 }
203
204 ALWAYS_INLINE MapData::const_iterator::~const_iterator()
205 {
206     m_mapData->m_iteratorCount--;
207 }
208
209 ALWAYS_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
215 ALWAYS_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
222 ALWAYS_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
230 ALWAYS_INLINE bool MapData::const_iterator::operator==(const const_iterator& other)
231 {
232     return !(*this != other);
233 }
234
235 }
236
237 #endif /* !defined(MapData_h) */