1 | /* |
2 | * Copyright (C) 2008, 2009 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 StructureTransitionTable_h |
27 | #define StructureTransitionTable_h |
28 | |
29 | #include "UString.h" |
30 | #include <wtf/HashFunctions.h> |
31 | #include <wtf/HashMap.h> |
32 | #include <wtf/HashTraits.h> |
33 | #include <wtf/PtrAndFlags.h> |
34 | #include <wtf/OwnPtr.h> |
35 | #include <wtf/RefPtr.h> |
36 | |
37 | namespace JSC { |
38 | |
39 | class Structure; |
40 | |
41 | struct StructureTransitionTableHash { |
42 | typedef std::pair<RefPtr<UString::Rep>, unsigned> Key; |
43 | static unsigned hash(const Key& p) |
44 | { |
45 | return p.first->existingHash(); |
46 | } |
47 | |
48 | static bool equal(const Key& a, const Key& b) |
49 | { |
50 | return a == b; |
51 | } |
52 | |
53 | static const bool safeToCompareToEmptyOrDeleted = true; |
54 | }; |
55 | |
56 | struct StructureTransitionTableHashTraits { |
57 | typedef WTF::HashTraits<RefPtr<UString::Rep> > FirstTraits; |
58 | typedef WTF::GenericHashTraits<unsigned> SecondTraits; |
59 | typedef std::pair<FirstTraits::TraitType, SecondTraits::TraitType > TraitType; |
60 | |
61 | static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; |
62 | static TraitType emptyValue() { return std::make_pair(x: FirstTraits::emptyValue(), y: SecondTraits::emptyValue()); } |
63 | |
64 | static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; |
65 | |
66 | static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot&: slot.first); } |
67 | static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value: value.first); } |
68 | }; |
69 | |
70 | class StructureTransitionTable { |
71 | typedef std::pair<Structure*, Structure*> Transition; |
72 | struct TransitionTable : public HashMap<StructureTransitionTableHash::Key, Transition, StructureTransitionTableHash, StructureTransitionTableHashTraits> { |
73 | typedef HashMap<unsigned, Structure*> AnonymousSlotMap; |
74 | |
75 | void addSlotTransition(unsigned count, Structure* structure) |
76 | { |
77 | ASSERT(!getSlotTransition(count)); |
78 | if (!m_anonymousSlotTable) |
79 | m_anonymousSlotTable.set(new AnonymousSlotMap); |
80 | m_anonymousSlotTable->add(key: count, mapped: structure); |
81 | } |
82 | |
83 | void removeSlotTransition(unsigned count) |
84 | { |
85 | ASSERT(getSlotTransition(count)); |
86 | m_anonymousSlotTable->remove(key: count); |
87 | } |
88 | |
89 | Structure* getSlotTransition(unsigned count) |
90 | { |
91 | if (!m_anonymousSlotTable) |
92 | return 0; |
93 | |
94 | AnonymousSlotMap::iterator find = m_anonymousSlotTable->find(key: count); |
95 | if (find == m_anonymousSlotTable->end()) |
96 | return 0; |
97 | return find->second; |
98 | } |
99 | private: |
100 | OwnPtr<AnonymousSlotMap> m_anonymousSlotTable; |
101 | }; |
102 | public: |
103 | StructureTransitionTable() { |
104 | m_transitions.m_singleTransition.set(0); |
105 | m_transitions.m_singleTransition.setFlag(usingSingleSlot); |
106 | } |
107 | |
108 | ~StructureTransitionTable() { |
109 | if (!usingSingleTransitionSlot()) |
110 | delete table(); |
111 | } |
112 | |
113 | // The contains and get methods accept imprecise matches, so if an unspecialised transition exists |
114 | // for the given key they will consider that transition to be a match. If a specialised transition |
115 | // exists and it matches the provided specificValue, get will return the specific transition. |
116 | inline bool contains(const StructureTransitionTableHash::Key&, JSCell* specificValue); |
117 | inline Structure* get(const StructureTransitionTableHash::Key&, JSCell* specificValue) const; |
118 | inline bool hasTransition(const StructureTransitionTableHash::Key& key) const; |
119 | void remove(const StructureTransitionTableHash::Key& key, JSCell* specificValue) |
120 | { |
121 | if (usingSingleTransitionSlot()) { |
122 | ASSERT(contains(key, specificValue)); |
123 | setSingleTransition(0); |
124 | return; |
125 | } |
126 | TransitionTable::iterator find = table()->find(key); |
127 | if (!specificValue) |
128 | find->second.first = 0; |
129 | else |
130 | find->second.second = 0; |
131 | if (!find->second.first && !find->second.second) |
132 | table()->remove(it: find); |
133 | } |
134 | void add(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue) |
135 | { |
136 | if (usingSingleTransitionSlot()) { |
137 | if (!singleTransition()) { |
138 | setSingleTransition(structure); |
139 | return; |
140 | } |
141 | reifySingleTransition(); |
142 | } |
143 | if (!specificValue) { |
144 | TransitionTable::iterator find = table()->find(key); |
145 | if (find == table()->end()) |
146 | table()->add(key, mapped: Transition(structure, (Structure*)0)); |
147 | else |
148 | find->second.first = structure; |
149 | } else { |
150 | // If we're adding a transition to a specific value, then there cannot be |
151 | // an existing transition |
152 | ASSERT(!table()->contains(key)); |
153 | table()->add(key, mapped: Transition((Structure*)0, structure)); |
154 | } |
155 | } |
156 | |
157 | Structure* getAnonymousSlotTransition(unsigned count) |
158 | { |
159 | if (usingSingleTransitionSlot()) |
160 | return 0; |
161 | return table()->getSlotTransition(count); |
162 | } |
163 | |
164 | void addAnonymousSlotTransition(unsigned count, Structure* structure) |
165 | { |
166 | if (usingSingleTransitionSlot()) |
167 | reifySingleTransition(); |
168 | ASSERT(!table()->getSlotTransition(count)); |
169 | table()->addSlotTransition(count, structure); |
170 | } |
171 | |
172 | void removeAnonymousSlotTransition(unsigned count) |
173 | { |
174 | ASSERT(!usingSingleTransitionSlot()); |
175 | table()->removeSlotTransition(count); |
176 | } |
177 | private: |
178 | TransitionTable* table() const { ASSERT(!usingSingleTransitionSlot()); return m_transitions.m_table; } |
179 | Structure* singleTransition() const { |
180 | ASSERT(usingSingleTransitionSlot()); |
181 | return m_transitions.m_singleTransition.get(); |
182 | } |
183 | bool usingSingleTransitionSlot() const { return m_transitions.m_singleTransition.isFlagSet(flagNumber: usingSingleSlot); } |
184 | void setSingleTransition(Structure* structure) |
185 | { |
186 | ASSERT(usingSingleTransitionSlot()); |
187 | m_transitions.m_singleTransition.set(structure); |
188 | } |
189 | |
190 | void setTransitionTable(TransitionTable* table) |
191 | { |
192 | ASSERT(usingSingleTransitionSlot()); |
193 | #ifndef NDEBUG |
194 | setSingleTransition(0); |
195 | #endif |
196 | m_transitions.m_table = table; |
197 | // This implicitly clears the flag that indicates we're using a single transition |
198 | ASSERT(!usingSingleTransitionSlot()); |
199 | } |
200 | inline void reifySingleTransition(); |
201 | |
202 | enum UsingSingleSlot { |
203 | usingSingleSlot |
204 | }; |
205 | // Last bit indicates whether we are using the single transition optimisation |
206 | union { |
207 | TransitionTable* m_table; |
208 | PtrAndFlagsBase<Structure, UsingSingleSlot> m_singleTransition; |
209 | } m_transitions; |
210 | }; |
211 | |
212 | } // namespace JSC |
213 | |
214 | #endif // StructureTransitionTable_h |
215 | |