2008-10-06 Sam Weinig <sam@webkit.org>
[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 offset;
46         unsigned attributes;
47         unsigned index;
48
49         PropertyMapEntry(UString::Rep* k, int a)
50             : key(k)
51             , offset(0)
52             , attributes(a)
53             , index(0)
54         {
55         }
56     };
57
58     // lastIndexUsed is an ever-increasing index used to identify the order items
59     // were inserted into the property map. It's required that getEnumerablePropertyNames
60     // return the properties in the order they were added for compatibility with other
61     // browsers' JavaScript implementations.
62     struct PropertyMapHashTable {
63         unsigned sizeMask;
64         unsigned size;
65         unsigned keyCount;
66         unsigned deletedSentinelCount;
67         unsigned lastIndexUsed;
68         unsigned entryIndices[1];
69
70         PropertyMapEntry* entries()
71         {
72             // The entries vector comes after the indices vector.
73             // The 0th item in the entries vector is not really used; it has to
74             // have a 0 in its key to allow the hash table lookup to handle deleted
75             // sentinels without any special-case code, but the other fields are unused.
76             return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]);
77         }
78
79         static size_t allocationSize(unsigned size)
80         {
81             // We never let a hash table get more than half full,
82             // So the number of indices we need is the size of the hash table.
83             // But the number of entries is half that (plus one for the deleted sentinel).
84             return sizeof(PropertyMapHashTable)
85                 + (size - 1) * sizeof(unsigned)
86                 + (1 + size / 2) * sizeof(PropertyMapEntry);
87         }
88     };
89
90     class PropertyMap {
91     public:
92         PropertyMap();
93         ~PropertyMap();
94
95         PropertyMap& operator=(const PropertyMap&);
96
97         bool isEmpty() { return !m_table; }
98
99         size_t get(const Identifier& propertyName);
100         size_t get(const Identifier& propertyName, unsigned& attributes);
101         size_t put(const Identifier& propertyName, unsigned attributes);
102         size_t remove(const Identifier& propertyName);
103
104         void getEnumerablePropertyNames(PropertyNameArray&) const;
105
106         bool hasGetterSetterProperties() const { return m_getterSetterFlag; }
107         void setHasGetterSetterProperties(bool f) { m_getterSetterFlag = f; }
108
109         unsigned size() const { return m_table ? m_table->size : 0; }
110         unsigned storageSize() const { return m_table ? m_table->keyCount + m_table->deletedSentinelCount : 0; }
111
112         static const unsigned emptyEntryIndex = 0;
113
114     private:
115         typedef PropertyMapEntry Entry;
116         typedef PropertyMapHashTable Table;
117
118         void expand();
119         void rehash();
120         void rehash(unsigned newTableSize);
121         void createTable();
122
123         void insert(const Entry&);
124
125         void checkConsistency();
126
127         Table* m_table;
128         Vector<unsigned> m_deletedOffsets;
129         bool m_getterSetterFlag : 1;
130     };
131
132     inline PropertyMap::PropertyMap() 
133         : m_table(0)
134         , m_getterSetterFlag(false)
135     {
136     }
137
138     inline size_t PropertyMap::get(const Identifier& propertyName)
139     {
140         ASSERT(!propertyName.isNull());
141
142         if (!m_table)
143             return WTF::notFound;
144
145         UString::Rep* rep = propertyName._ustring.rep();
146
147         unsigned i = rep->computedHash();
148
149 #if DUMP_PROPERTYMAP_STATS
150         ++numProbes;
151 #endif
152
153         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
154         if (entryIndex == emptyEntryIndex)
155             return WTF::notFound;
156
157         if (rep == m_table->entries()[entryIndex - 1].key)
158             return m_table->entries()[entryIndex - 1].offset;
159
160 #if DUMP_PROPERTYMAP_STATS
161         ++numCollisions;
162 #endif
163
164         unsigned k = 1 | WTF::doubleHash(rep->computedHash());
165
166         while (1) {
167             i += k;
168
169 #if DUMP_PROPERTYMAP_STATS
170             ++numRehashes;
171 #endif
172
173             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
174             if (entryIndex == emptyEntryIndex)
175                 return WTF::notFound;
176
177             if (rep == m_table->entries()[entryIndex - 1].key)
178                 return m_table->entries()[entryIndex - 1].offset;
179         }
180     }
181
182 } // namespace JSC
183
184 #endif // PropertyMap_h