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