• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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;
hashStructureTransitionTableHash43         static unsigned hash(const Key& p)
44         {
45             return p.first->existingHash();
46         }
47 
equalStructureTransitionTableHash48         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;
emptyValueStructureTransitionTableHashTraits62         static TraitType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
63 
64         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
65 
constructDeletedValueStructureTransitionTableHashTraits66         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
isDeletedValueStructureTransitionTableHashTraits67         static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
68     };
69 
70     class StructureTransitionTable {
71         typedef std::pair<Structure*, Structure*> Transition;
72         typedef HashMap<StructureTransitionTableHash::Key, Transition, StructureTransitionTableHash, StructureTransitionTableHashTraits> TransitionTable;
73     public:
StructureTransitionTable()74         StructureTransitionTable() {
75             m_transitions.m_singleTransition.set(0);
76             m_transitions.m_singleTransition.setFlag(usingSingleSlot);
77         }
78 
~StructureTransitionTable()79         ~StructureTransitionTable() {
80             if (!usingSingleTransitionSlot())
81                 delete table();
82         }
83 
84         // The contains and get methods accept imprecise matches, so if an unspecialised transition exists
85         // for the given key they will consider that transition to be a match.  If a specialised transition
86         // exists and it matches the provided specificValue, get will return the specific transition.
87         inline bool contains(const StructureTransitionTableHash::Key&, JSCell* specificValue);
88         inline Structure* get(const StructureTransitionTableHash::Key&, JSCell* specificValue) const;
89         inline bool hasTransition(const StructureTransitionTableHash::Key& key) const;
remove(const StructureTransitionTableHash::Key & key,JSCell * specificValue)90         void remove(const StructureTransitionTableHash::Key& key, JSCell* specificValue)
91         {
92             if (usingSingleTransitionSlot()) {
93                 ASSERT(contains(key, specificValue));
94                 setSingleTransition(0);
95                 return;
96             }
97             TransitionTable::iterator find = table()->find(key);
98             if (!specificValue)
99                 find->second.first = 0;
100             else
101                 find->second.second = 0;
102             if (!find->second.first && !find->second.second)
103                 table()->remove(find);
104         }
add(const StructureTransitionTableHash::Key & key,Structure * structure,JSCell * specificValue)105         void add(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue)
106         {
107             if (usingSingleTransitionSlot()) {
108                 if (!singleTransition()) {
109                     setSingleTransition(structure);
110                     return;
111                 }
112                 reifySingleTransition();
113             }
114             if (!specificValue) {
115                 TransitionTable::iterator find = table()->find(key);
116                 if (find == table()->end())
117                     table()->add(key, Transition(structure, 0));
118                 else
119                     find->second.first = structure;
120             } else {
121                 // If we're adding a transition to a specific value, then there cannot be
122                 // an existing transition
123                 ASSERT(!table()->contains(key));
124                 table()->add(key, Transition(0, structure));
125             }
126         }
127 
128     private:
table()129         TransitionTable* table() const { ASSERT(!usingSingleTransitionSlot()); return m_transitions.m_table; }
singleTransition()130         Structure* singleTransition() const {
131             ASSERT(usingSingleTransitionSlot());
132             return m_transitions.m_singleTransition.get();
133         }
usingSingleTransitionSlot()134         bool usingSingleTransitionSlot() const { return m_transitions.m_singleTransition.isFlagSet(usingSingleSlot); }
setSingleTransition(Structure * structure)135         void setSingleTransition(Structure* structure)
136         {
137             ASSERT(usingSingleTransitionSlot());
138             m_transitions.m_singleTransition.set(structure);
139         }
140 
setTransitionTable(TransitionTable * table)141         void setTransitionTable(TransitionTable* table)
142         {
143             ASSERT(usingSingleTransitionSlot());
144 #ifndef NDEBUG
145             setSingleTransition(0);
146 #endif
147             m_transitions.m_table = table;
148             // This implicitly clears the flag that indicates we're using a single transition
149             ASSERT(!usingSingleTransitionSlot());
150         }
151         inline void reifySingleTransition();
152 
153         enum UsingSingleSlot {
154             usingSingleSlot
155         };
156         // Last bit indicates whether we are using the single transition optimisation
157         union {
158             TransitionTable* m_table;
159             PtrAndFlagsBase<Structure, UsingSingleSlot> m_singleTransition;
160         } m_transitions;
161     };
162 
163 } // namespace JSC
164 
165 #endif // StructureTransitionTable_h
166