Implement ES6 Symbol
[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     typedef HashMap<AtomicStringImpl*, int32_t, typename WTF::DefaultHash<AtomicStringImpl*>::Hash, WTF::HashTraits<AtomicStringImpl*>, IndexTraits> SymbolKeyedMap;
116
117     size_t capacityInBytes() { return m_capacity * sizeof(Entry); }
118
119     MapData(VM&);
120     static void destroy(JSCell*);
121     static void visitChildren(JSCell*, SlotVisitor&);
122     static void copyBackingStore(JSCell*, CopyVisitor&, CopyToken);
123
124
125     ALWAYS_INLINE Entry* find(CallFrame*, KeyType);
126     ALWAYS_INLINE Entry* add(CallFrame*, KeyType);
127     template <typename Map, typename Key> ALWAYS_INLINE Entry* add(CallFrame*, Map&, Key, KeyType);
128
129     ALWAYS_INLINE bool shouldPack() const { return m_deletedCount && !m_iteratorCount; }
130     CheckedBoolean ensureSpaceForAppend(CallFrame*);
131
132     ALWAYS_INLINE void replaceAndPackBackingStore(Entry* destination, int32_t newSize);
133     ALWAYS_INLINE void replaceBackingStore(Entry* destination, int32_t newSize);
134
135     CellKeyedMap m_cellKeyedTable;
136     ValueKeyedMap m_valueKeyedTable;
137     StringKeyedMap m_stringKeyedTable;
138     SymbolKeyedMap m_symbolKeyedTable;
139     int32_t m_capacity;
140     int32_t m_size;
141     int32_t m_deletedCount;
142     mutable int32_t m_iteratorCount;
143     Entry* m_entries;
144 };
145
146 ALWAYS_INLINE void MapData::clear()
147 {
148     m_cellKeyedTable.clear();
149     m_valueKeyedTable.clear();
150     m_stringKeyedTable.clear();
151     m_symbolKeyedTable.clear();
152     m_capacity = 0;
153     m_size = 0;
154     m_deletedCount = 0;
155     m_entries = nullptr;
156 }
157
158 ALWAYS_INLINE MapData::KeyType::KeyType(JSValue v)
159 {
160     if (!v.isDouble()) {
161         value = v;
162         return;
163     }
164     double d = v.asDouble();
165     if (std::isnan(d) || (std::signbit(d) && d == 0.0)) {
166         value = v;
167         return;
168     }
169
170     int i = static_cast<int>(v.asDouble());
171     if (i != d)
172         value = v;
173     else
174         value = jsNumber(i);
175 }
176
177 ALWAYS_INLINE void MapData::const_iterator::internalIncrement()
178 {
179     Entry* entries = m_mapData->m_entries;
180     size_t index = m_index + 1;
181     size_t end = m_mapData->m_size;
182     while (index < end && !entries[index].key)
183         index++;
184     m_index = index;
185 }
186     
187 ALWAYS_INLINE bool MapData::const_iterator::ensureSlot()
188 {
189     // When an iterator exists outside of host cost it is possible for
190     // the containing map to be modified
191     Entry* entries = m_mapData->m_entries;
192     size_t index = m_index;
193     size_t end = m_mapData->m_size;
194     if (index < end && entries[index].key)
195         return true;
196     internalIncrement();
197     return static_cast<size_t>(m_index) < end;
198 }
199
200 ALWAYS_INLINE MapData::const_iterator::const_iterator(const MapData* mapData)
201     : m_mapData(mapData)
202     , m_index(-1)
203 {
204     internalIncrement();
205 }
206
207 ALWAYS_INLINE MapData::const_iterator::~const_iterator()
208 {
209     m_mapData->m_iteratorCount--;
210 }
211
212 ALWAYS_INLINE const WTF::KeyValuePair<JSValue, JSValue> MapData::const_iterator::operator*() const
213 {
214     Entry* entry = &m_mapData->m_entries[m_index];
215     return WTF::KeyValuePair<JSValue, JSValue>(entry->key.get(), entry->value.get());
216 }
217
218 ALWAYS_INLINE MapData::const_iterator MapData::const_iterator::end(const MapData* mapData)
219 {
220     const_iterator result(mapData);
221     result.m_index = -1;
222     return result;
223 }
224
225 ALWAYS_INLINE bool MapData::const_iterator::operator!=(const const_iterator& other)
226 {
227     ASSERT(other.m_mapData == m_mapData);
228     if (atEnd() && other.atEnd())
229         return false;
230     return m_index != other.m_index;
231 }
232
233 ALWAYS_INLINE bool MapData::const_iterator::operator==(const const_iterator& other)
234 {
235     return !(*this != other);
236 }
237
238 }
239
240 #endif /* !defined(MapData_h) */