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 Structure_h 27 #define Structure_h 28 29 #include "Identifier.h" 30 #include "JSType.h" 31 #include "JSValue.h" 32 #include "PropertyMapHashTable.h" 33 #include "StructureChain.h" 34 #include "StructureTransitionTable.h" 35 #include "TypeInfo.h" 36 #include "UString.h" 37 #include <wtf/PassRefPtr.h> 38 #include <wtf/RefCounted.h> 39 40 #ifndef NDEBUG 41 #define DUMP_PROPERTYMAP_STATS 0 42 #else 43 #define DUMP_PROPERTYMAP_STATS 0 44 #endif 45 46 namespace JSC { 47 48 class PropertyNameArray; 49 class PropertyNameArrayData; 50 51 class Structure : public RefCounted<Structure> { 52 public: 53 friend class JIT; create(JSValuePtr prototype,const TypeInfo & typeInfo)54 static PassRefPtr<Structure> create(JSValuePtr prototype, const TypeInfo& typeInfo) 55 { 56 return adoptRef(new Structure(prototype, typeInfo)); 57 } 58 59 static void startIgnoringLeaks(); 60 static void stopIgnoringLeaks(); 61 62 static void dumpStatistics(); 63 64 static PassRefPtr<Structure> addPropertyTransition(Structure*, const Identifier& propertyName, unsigned attributes, size_t& offset); 65 static PassRefPtr<Structure> addPropertyTransitionToExistingStructure(Structure*, const Identifier& propertyName, unsigned attributes, size_t& offset); 66 static PassRefPtr<Structure> removePropertyTransition(Structure*, const Identifier& propertyName, size_t& offset); 67 static PassRefPtr<Structure> changePrototypeTransition(Structure*, JSValuePtr prototype); 68 static PassRefPtr<Structure> getterSetterTransition(Structure*); 69 static PassRefPtr<Structure> toDictionaryTransition(Structure*); 70 static PassRefPtr<Structure> fromDictionaryTransition(Structure*); 71 72 ~Structure(); 73 mark()74 void mark() 75 { 76 if (!m_prototype.marked()) 77 m_prototype.mark(); 78 } 79 80 // These should be used with caution. 81 size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes); 82 size_t removePropertyWithoutTransition(const Identifier& propertyName); setPrototypeWithoutTransition(JSValuePtr prototype)83 void setPrototypeWithoutTransition(JSValuePtr prototype) { m_prototype = prototype; } 84 isDictionary()85 bool isDictionary() const { return m_isDictionary; } 86 typeInfo()87 const TypeInfo& typeInfo() const { return m_typeInfo; } 88 storedPrototype()89 JSValuePtr storedPrototype() const { return m_prototype; } 90 JSValuePtr prototypeForLookup(ExecState*); 91 previousID()92 Structure* previousID() const { return m_previous.get(); } 93 94 StructureChain* createCachedPrototypeChain(); setCachedPrototypeChain(PassRefPtr<StructureChain> cachedPrototypeChain)95 void setCachedPrototypeChain(PassRefPtr<StructureChain> cachedPrototypeChain) { m_cachedPrototypeChain = cachedPrototypeChain; } cachedPrototypeChain()96 StructureChain* cachedPrototypeChain() const { return m_cachedPrototypeChain.get(); } 97 98 void growPropertyStorageCapacity(); propertyStorageCapacity()99 size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; } propertyStorageSize()100 size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : m_offset + 1; } 101 102 size_t get(const Identifier& propertyName); 103 size_t get(const Identifier& propertyName, unsigned& attributes); 104 void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*); 105 hasGetterSetterProperties()106 bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; } setHasGetterSetterProperties(bool hasGetterSetterProperties)107 void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; } 108 isEmpty()109 bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; } 110 111 private: 112 Structure(JSValuePtr prototype, const TypeInfo&); 113 114 size_t put(const Identifier& propertyName, unsigned attributes); 115 size_t remove(const Identifier& propertyName); 116 void getEnumerablePropertyNamesInternal(PropertyNameArray&); 117 118 void expandPropertyMapHashTable(); 119 void rehashPropertyMapHashTable(); 120 void rehashPropertyMapHashTable(unsigned newTableSize); 121 void createPropertyMapHashTable(); 122 void createPropertyMapHashTable(unsigned newTableSize); 123 void insertIntoPropertyMapHashTable(const PropertyMapEntry&); 124 void checkConsistency(); 125 126 PropertyMapHashTable* copyPropertyTable(); 127 void materializePropertyMap(); materializePropertyMapIfNecessary()128 void materializePropertyMapIfNecessary() 129 { 130 if (m_propertyTable || !m_previous) 131 return; 132 materializePropertyMap(); 133 } 134 135 void clearEnumerationCache(); 136 addressOfCount()137 void* addressOfCount() 138 { 139 return &m_refCount; 140 } 141 transitionCount()142 signed char transitionCount() const 143 { 144 // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both. 145 return m_offset == noOffset ? 0 : m_offset + 1; 146 } 147 148 static const unsigned emptyEntryIndex = 0; 149 150 static const signed char s_maxTransitionLength = 64; 151 152 static const signed char noOffset = -1; 153 154 TypeInfo m_typeInfo; 155 156 JSValuePtr m_prototype; 157 RefPtr<StructureChain> m_cachedPrototypeChain; 158 159 RefPtr<Structure> m_previous; 160 RefPtr<UString::Rep> m_nameInPrevious; 161 162 union { 163 Structure* singleTransition; 164 StructureTransitionTable* table; 165 } m_transitions; 166 167 RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData; 168 169 PropertyMapHashTable* m_propertyTable; 170 171 size_t m_propertyStorageCapacity; 172 signed char m_offset; 173 174 bool m_isDictionary : 1; 175 bool m_isPinnedPropertyTable : 1; 176 bool m_hasGetterSetterProperties : 1; 177 bool m_usingSingleTransitionSlot : 1; 178 unsigned m_attributesInPrevious : 5; 179 }; 180 get(const Identifier & propertyName)181 inline size_t Structure::get(const Identifier& propertyName) 182 { 183 ASSERT(!propertyName.isNull()); 184 185 materializePropertyMapIfNecessary(); 186 if (!m_propertyTable) 187 return WTF::notFound; 188 189 UString::Rep* rep = propertyName._ustring.rep(); 190 191 unsigned i = rep->computedHash(); 192 193 #if DUMP_PROPERTYMAP_STATS 194 ++numProbes; 195 #endif 196 197 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 198 if (entryIndex == emptyEntryIndex) 199 return WTF::notFound; 200 201 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 202 return m_propertyTable->entries()[entryIndex - 1].offset; 203 204 #if DUMP_PROPERTYMAP_STATS 205 ++numCollisions; 206 #endif 207 208 unsigned k = 1 | WTF::doubleHash(rep->computedHash()); 209 210 while (1) { 211 i += k; 212 213 #if DUMP_PROPERTYMAP_STATS 214 ++numRehashes; 215 #endif 216 217 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 218 if (entryIndex == emptyEntryIndex) 219 return WTF::notFound; 220 221 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 222 return m_propertyTable->entries()[entryIndex - 1].offset; 223 } 224 } 225 226 } // namespace JSC 227 228 #endif // Structure_h 229