2008-10-07 Cameron Zwarich <zwarich@apple.com>
[WebKit.git] / JavaScriptCore / kjs / PropertyMap.h
1 /*
2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3  *
4  *  This library is free software; you can redistribute it and/or
5  *  modify it under the terms of the GNU Library General Public
6  *  License as published by the Free Software Foundation; either
7  *  version 2 of the License, or (at your option) any later version.
8  *
9  *  This library is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  *  Library General Public License for more details.
13  *
14  *  You should have received a copy of the GNU Library General Public License
15  *  along with this library; see the file COPYING.LIB.  If not, write to
16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  *  Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #ifndef PropertyMap_h
22 #define PropertyMap_h
23
24 #include "PropertySlot.h"
25 #include "identifier.h"
26 #include <wtf/OwnArrayPtr.h>
27 #include <wtf/NotFound.h>
28
29 #ifndef NDEBUG
30 #define DUMP_PROPERTYMAP_STATS 0
31 #else
32 #define DUMP_PROPERTYMAP_STATS 0
33 #endif
34
35 namespace JSC {
36
37     class JSObject;
38     class JSValue;
39     class PropertyNameArray;
40
41     typedef JSValue** PropertyStorage;
42
43     struct PropertyMapEntry {
44         UString::Rep* key;
45         unsigned attributes;
46         unsigned index;
47
48         PropertyMapEntry(UString::Rep* k, int a)
49             : key(k)
50             , attributes(a)
51             , index(0)
52         {
53         }
54     };
55
56     // lastIndexUsed is an ever-increasing index used to identify the order items
57     // were inserted into the property map. It's required that getEnumerablePropertyNames
58     // return the properties in the order they were added for compatibility with other
59     // browsers' JavaScript implementations.
60     struct PropertyMapHashTable {
61         unsigned sizeMask;
62         unsigned size;
63         unsigned keyCount;
64         unsigned deletedSentinelCount;
65         unsigned lastIndexUsed;
66         unsigned entryIndices[1];
67
68         PropertyMapEntry* entries()
69         {
70             // The entries vector comes after the indices vector.
71             // The 0th item in the entries vector is not really used; it has to
72             // have a 0 in its key to allow the hash table lookup to handle deleted
73             // sentinels without any special-case code, but the other fields are unused.
74             return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]);
75         }
76
77         static size_t allocationSize(unsigned size)
78         {
79             // We never let a hash table get more than half full,
80             // So the number of indices we need is the size of the hash table.
81             // But the number of entries is half that (plus one for the deleted sentinel).
82             return sizeof(PropertyMapHashTable)
83                 + (size - 1) * sizeof(unsigned)
84                 + (1 + size / 2) * sizeof(PropertyMapEntry);
85         }
86     };
87
88     class PropertyMap {
89     public:
90         PropertyMap();
91         ~PropertyMap();
92
93         PropertyMap& operator=(const PropertyMap&);
94
95         bool isEmpty() { return !m_table; }
96
97         size_t put(const Identifier& propertyName, JSValue*, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot&, PropertyStorage&);
98         void remove(const Identifier& propertyName, PropertyStorage&);
99
100         size_t getOffset(const Identifier& propertyName);
101         size_t getOffset(const Identifier& propertyName, unsigned& attributes);
102
103         void getEnumerablePropertyNames(PropertyNameArray&) const;
104
105         bool hasGetterSetterProperties() const { return m_getterSetterFlag; }
106         void setHasGetterSetterProperties(bool f) { m_getterSetterFlag = f; }
107
108         unsigned size() const { return m_table ? m_table->size : 0; }
109         unsigned storageSize() const { return m_table ? m_table->keyCount + m_table->deletedSentinelCount : 0; }
110
111         static const unsigned emptyEntryIndex = 0;
112
113     private:
114         typedef PropertyMapEntry Entry;
115         typedef PropertyMapHashTable Table;
116
117         void expand(PropertyStorage&);
118         void rehash(PropertyStorage&);
119         void rehash(unsigned newTableSize, PropertyStorage&);
120         void createTable(PropertyStorage&);
121
122         void insert(const Entry&, JSValue*, PropertyStorage&);
123
124         void checkConsistency(PropertyStorage&);
125
126         Table* m_table;
127         bool m_getterSetterFlag : 1;
128     };
129
130     inline PropertyMap::PropertyMap() 
131         : m_table(0)
132         , m_getterSetterFlag(false)
133     {
134     }
135
136     inline size_t PropertyMap::getOffset(const Identifier& propertyName)
137     {
138         ASSERT(!propertyName.isNull());
139
140         if (!m_table)
141             return WTF::notFound;
142
143         UString::Rep* rep = propertyName._ustring.rep();
144
145         unsigned i = rep->computedHash();
146
147 #if DUMP_PROPERTYMAP_STATS
148         ++numProbes;
149 #endif
150
151         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
152         if (entryIndex == emptyEntryIndex)
153             return WTF::notFound;
154
155         if (rep == m_table->entries()[entryIndex - 1].key)
156             return entryIndex - 2;
157
158 #if DUMP_PROPERTYMAP_STATS
159         ++numCollisions;
160 #endif
161
162         unsigned k = 1 | WTF::doubleHash(rep->computedHash());
163
164         while (1) {
165             i += k;
166
167 #if DUMP_PROPERTYMAP_STATS
168             ++numRehashes;
169 #endif
170
171             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
172             if (entryIndex == emptyEntryIndex)
173                 return WTF::notFound;
174
175             if (rep == m_table->entries()[entryIndex - 1].key)
176                 return entryIndex - 2;
177         }
178     }
179
180 } // namespace JSC
181
182 #endif // PropertyMap_h