Home | History | Annotate | Download | only in runtime 
      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
    166