runtime/StructureTransitionTable.h

   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(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
  63
  64         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
  65
  66         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
  67         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:
  74         StructureTransitionTable() {
  75             m_transitions.m_singleTransition.set(0);
  76             m_transitions.m_singleTransition.setFlag(usingSingleSlot);
  77         }
  78
  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;
  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         }
 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:
 129         TransitionTable* table() const { ASSERT(!usingSingleTransitionSlot()); return m_transitions.m_table; }
 130         Structure* singleTransition() const {
 131             ASSERT(usingSingleTransitionSlot());
 132             return m_transitions.m_singleTransition.get();
 133         }
 134         bool usingSingleTransitionSlot() const { return m_transitions.m_singleTransition.isFlagSet(usingSingleSlot); }
 135         void setSingleTransition(Structure* structure)
 136         {
 137             ASSERT(usingSingleTransitionSlot());
 138             m_transitions.m_singleTransition.set(structure);
 139         }
 140
 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