2008-11-15 Darin Adler <darin@apple.com>
[WebKit-https.git] / JavaScriptCore / runtime / StructureID.h
1 /*
2  * Copyright (C) 2008 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 COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef StructureID_h
27 #define StructureID_h
28
29 #include "Identifier.h"
30 #include "JSType.h"
31 #include "JSValue.h"
32 #include "PropertyMapHashTable.h"
33 #include "StructureIDChain.h"
34 #include "StructureIDTransitionTable.h"
35 #include "TypeInfo.h"
36 #include "UString.h"
37 #include <wtf/HashFunctions.h>
38 #include <wtf/HashTraits.h>
39 #include <wtf/OwnArrayPtr.h>
40 #include <wtf/PassRefPtr.h>
41 #include <wtf/RefCounted.h>
42
43 #ifndef NDEBUG
44 #define DUMP_PROPERTYMAP_STATS 0
45 #else
46 #define DUMP_PROPERTYMAP_STATS 0
47 #endif
48
49 namespace JSC {
50
51     class PropertyNameArray;
52     class PropertyNameArrayData;
53
54     class StructureID : public RefCounted<StructureID> {
55     public:
56         friend class CTI;
57         static PassRefPtr<StructureID> create(JSValue* prototype, const TypeInfo& typeInfo)
58         {
59             return adoptRef(new StructureID(prototype, typeInfo));
60         }
61
62         static void startIgnoringLeaks();
63         static void stopIgnoringLeaks();
64
65         static void dumpStatistics();
66
67         static PassRefPtr<StructureID> addPropertyTransition(StructureID*, const Identifier& propertyName, unsigned attributes, size_t& offset);
68         static PassRefPtr<StructureID> addPropertyTransitionToExistingStructure(StructureID*, const Identifier& propertyName, unsigned attributes, size_t& offset);
69         static PassRefPtr<StructureID> removePropertyTransition(StructureID*, const Identifier& propertyName, size_t& offset);
70         static PassRefPtr<StructureID> changePrototypeTransition(StructureID*, JSValue* prototype);
71         static PassRefPtr<StructureID> getterSetterTransition(StructureID*);
72         static PassRefPtr<StructureID> toDictionaryTransition(StructureID*);
73         static PassRefPtr<StructureID> fromDictionaryTransition(StructureID*);
74
75         ~StructureID();
76
77         void mark()
78         {
79             if (!m_prototype->marked())
80                 m_prototype->mark();
81         }
82
83         // These should be used with caution.  
84         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes);
85         size_t removePropertyWithoutTransition(const Identifier& propertyName);
86         void setPrototypeWithoutTransition(JSValue* prototype) { m_prototype = prototype; }
87
88         bool isDictionary() const { return m_isDictionary; }
89
90         const TypeInfo& typeInfo() const { return m_typeInfo; }
91
92         // For use when first creating a new structure.
93         TypeInfo& mutableTypeInfo() { return m_typeInfo; }
94
95         JSValue* storedPrototype() const { return m_prototype; }
96         JSValue* prototypeForLookup(ExecState*); 
97
98         StructureID* previousID() const { return m_previous.get(); }
99
100         StructureIDChain* createCachedPrototypeChain();
101         void setCachedPrototypeChain(PassRefPtr<StructureIDChain> cachedPrototypeChain) { m_cachedPrototypeChain = cachedPrototypeChain; }
102         StructureIDChain* cachedPrototypeChain() const { return m_cachedPrototypeChain.get(); }
103
104         void growPropertyStorageCapacity();
105         size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; }
106         size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + m_deletedOffsets.size() : m_offset + 1; }
107
108         size_t get(const Identifier& propertyName);
109         size_t get(const Identifier& propertyName, unsigned& attributes);
110         void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*);
111
112         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
113         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
114
115         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == WTF::notFound; }
116
117     private:
118         StructureID(JSValue* prototype, const TypeInfo&);
119
120         size_t put(const Identifier& propertyName, unsigned attributes);
121         size_t remove(const Identifier& propertyName);
122         void getEnumerablePropertyNamesInternal(PropertyNameArray&);
123
124         void expandPropertyMapHashTable();
125         void rehashPropertyMapHashTable();
126         void rehashPropertyMapHashTable(unsigned newTableSize);
127         void createPropertyMapHashTable();
128         void createPropertyMapHashTable(unsigned newTableSize);
129         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
130         void checkConsistency();
131
132         PropertyMapHashTable* copyPropertyTable();
133         void materializePropertyMap();
134         void materializePropertyMapIfNecessary()
135         {
136             if (m_propertyTable || !m_previous)             
137                 return;
138             materializePropertyMap();
139         }
140
141         void clearEnumerationCache();
142
143         static const unsigned emptyEntryIndex = 0;
144     
145         static const size_t s_maxTransitionLength = 64;
146
147         TypeInfo m_typeInfo;
148
149         JSValue* m_prototype;
150         RefPtr<StructureIDChain> m_cachedPrototypeChain;
151
152         RefPtr<StructureID> m_previous;
153         UString::Rep* m_nameInPrevious;
154
155         size_t m_transitionCount;
156         union {
157             StructureID* singleTransition;
158             StructureIDTransitionTable* table;
159         } m_transitions;
160
161         RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData;
162
163         PropertyMapHashTable* m_propertyTable;
164         Vector<unsigned> m_deletedOffsets;
165
166         size_t m_propertyStorageCapacity;
167         size_t m_offset;
168
169         bool m_isDictionary : 1;
170         bool m_isPinnedPropertyTable : 1;
171         bool m_hasGetterSetterProperties : 1;
172         bool m_usingSingleTransitionSlot : 1;
173         unsigned m_attributesInPrevious : 5;
174     };
175
176     inline size_t StructureID::get(const Identifier& propertyName)
177     {
178         ASSERT(!propertyName.isNull());
179
180         materializePropertyMapIfNecessary();
181         if (!m_propertyTable)
182             return WTF::notFound;
183
184         UString::Rep* rep = propertyName._ustring.rep();
185
186         unsigned i = rep->computedHash();
187
188 #if DUMP_PROPERTYMAP_STATS
189         ++numProbes;
190 #endif
191
192         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
193         if (entryIndex == emptyEntryIndex)
194             return WTF::notFound;
195
196         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
197             return m_propertyTable->entries()[entryIndex - 1].offset;
198
199 #if DUMP_PROPERTYMAP_STATS
200         ++numCollisions;
201 #endif
202
203         unsigned k = 1 | WTF::doubleHash(rep->computedHash());
204
205         while (1) {
206             i += k;
207
208 #if DUMP_PROPERTYMAP_STATS
209             ++numRehashes;
210 #endif
211
212             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
213             if (entryIndex == emptyEntryIndex)
214                 return WTF::notFound;
215
216             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
217                 return m_propertyTable->entries()[entryIndex - 1].offset;
218         }
219     }
220
221 } // namespace JSC
222
223 #endif // StructureID_h