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 "IndexingType.h"
  30 #include "WeakGCMap.h"
  31 #include <wtf/HashFunctions.h>
  32 #include <wtf/OwnPtr.h>
  33 #include <wtf/RefPtr.h>
  34 #include <wtf/text/StringImpl.h>
  35
  36 namespace JSC {
  37
  38 class JSCell;
  39 class Structure;
  40
  41 static const unsigned FirstInternalAttribute = 1 << 6; // Use for transitions that don't have to do with property additions.
  42
  43 // Support for attributes used to indicate transitions not related to properties.
  44 // If any of these are used, the string portion of the key should be 0.
  45 enum NonPropertyTransition {
  46     AllocateUndecided,
  47     AllocateInt32,
  48     AllocateDouble,
  49     AllocateContiguous,
  50     AllocateArrayStorage,
  51     AllocateSlowPutArrayStorage,
  52     SwitchToSlowPutArrayStorage,
  53     AddIndexedAccessors
  54 };
  55
  56 inline unsigned toAttributes(NonPropertyTransition transition)
  57 {
  58     return transition + FirstInternalAttribute;
  59 }
  60
  61 inline IndexingType newIndexingType(IndexingType oldType, NonPropertyTransition transition)
  62 {
  63     switch (transition) {
  64     case AllocateUndecided:
  65         ASSERT(!hasIndexedProperties(oldType));
  66         return oldType | UndecidedShape;
  67     case AllocateInt32:
  68         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType));
  69         return (oldType & ~IndexingShapeMask) | Int32Shape;
  70     case AllocateDouble:
  71         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType));
  72         return (oldType & ~IndexingShapeMask) | DoubleShape;
  73     case AllocateContiguous:
  74         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType));
  75         return (oldType & ~IndexingShapeMask) | ContiguousShape;
  76     case AllocateArrayStorage:
  77         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType) || hasContiguous(oldType));
  78         return (oldType & ~IndexingShapeMask) | ArrayStorageShape;
  79     case AllocateSlowPutArrayStorage:
  80         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType) || hasContiguous(oldType) || hasContiguous(oldType));
  81         return (oldType & ~IndexingShapeMask) | SlowPutArrayStorageShape;
  82     case SwitchToSlowPutArrayStorage:
  83         ASSERT(hasFastArrayStorage(oldType));
  84         return (oldType & ~IndexingShapeMask) | SlowPutArrayStorageShape;
  85     case AddIndexedAccessors:
  86         return oldType | MayHaveIndexedAccessors;
  87     default:
  88         RELEASE_ASSERT_NOT_REACHED();
  89         return oldType;
  90     }
  91 }
  92
  93 class StructureTransitionTable {
  94     static const intptr_t UsingSingleSlotFlag = 1;
  95
  96     struct Hash {
  97         typedef std::pair<RefPtr<StringImpl>, unsigned> Key;
  98         static unsigned hash(const Key& p)
  99         {
 100             unsigned result = p.second;
 101             if (p.first)
 102                 result += p.first->existingHash();
 103             return result;
 104         }
 105
 106         static bool equal(const Key& a, const Key& b)
 107         {
 108             return a == b;
 109         }
 110
 111         static const bool safeToCompareToEmptyOrDeleted = true;
 112     };
 113
 114     typedef WeakGCMap<Hash::Key, Structure, Hash> TransitionMap;
 115
 116 public:
 117     StructureTransitionTable()
 118         : m_data(UsingSingleSlotFlag)
 119     {
 120     }
 121
 122     ~StructureTransitionTable()
 123     {
 124         if (!isUsingSingleSlot()) {
 125             delete map();
 126             return;
 127         }
 128
 129         WeakImpl* impl = this->weakImpl();
 130         if (!impl)
 131             return;
 132         WeakSet::deallocate(impl);
 133     }
 134
 135     inline void add(VM&, Structure*);
 136     inline bool contains(StringImpl* rep, unsigned attributes) const;
 137     inline Structure* get(StringImpl* rep, unsigned attributes) const;
 138
 139 private:
 140     bool isUsingSingleSlot() const
 141     {
 142         return m_data & UsingSingleSlotFlag;
 143     }
 144
 145     TransitionMap* map() const
 146     {
 147         ASSERT(!isUsingSingleSlot());
 148         return reinterpret_cast<TransitionMap*>(m_data);
 149     }
 150
 151     WeakImpl* weakImpl() const
 152     {
 153         ASSERT(isUsingSingleSlot());
 154         return reinterpret_cast<WeakImpl*>(m_data & ~UsingSingleSlotFlag);
 155     }
 156
 157     void setMap(TransitionMap* map)
 158     {
 159         ASSERT(isUsingSingleSlot());
 160
 161         if (WeakImpl* impl = this->weakImpl())
 162             WeakSet::deallocate(impl);
 163
 164         // This implicitly clears the flag that indicates we're using a single transition
 165         m_data = reinterpret_cast<intptr_t>(map);
 166
 167         ASSERT(!isUsingSingleSlot());
 168     }
 169
 170     Structure* singleTransition() const
 171     {
 172         ASSERT(isUsingSingleSlot());
 173         if (WeakImpl* impl = this->weakImpl()) {
 174             if (impl->state() == WeakImpl::Live)
 175                 return reinterpret_cast<Structure*>(impl->jsValue().asCell());
 176         }
 177         return 0;
 178     }
 179
 180     void setSingleTransition(VM&, Structure* structure)
 181     {
 182         ASSERT(isUsingSingleSlot());
 183         if (WeakImpl* impl = this->weakImpl())
 184             WeakSet::deallocate(impl);
 185         WeakImpl* impl = WeakSet::allocate(reinterpret_cast<JSCell*>(structure));
 186         m_data = reinterpret_cast<intptr_t>(impl) | UsingSingleSlotFlag;
 187     }
 188
 189     intptr_t m_data;
 190 };
 191
 192 } // namespace JSC
 193
 194 #endif // StructureTransitionTable_h