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
37namespace 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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/runtime/StructureTransitionTable.h