src/v8/src/transitions.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/objects.h"
   8 #include "src/transitions-inl.h"
   9 #include "src/utils.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13
  14
  15 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
  16                                                   int number_of_transitions,
  17                                                   int slack) {
  18   Handle<FixedArray> array = isolate->factory()->NewFixedArray(
  19       LengthFor(number_of_transitions + slack));
  20   array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
  21   array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
  22   return Handle<TransitionArray>::cast(array);
  23 }
  24
  25
  26 Handle<TransitionArray> TransitionArray::AllocateSimple(Isolate* isolate,
  27                                                         Handle<Map> target) {
  28   Handle<FixedArray> array =
  29       isolate->factory()->NewFixedArray(kSimpleTransitionSize);
  30   array->set(kSimpleTransitionTarget, *target);
  31   return Handle<TransitionArray>::cast(array);
  32 }
  33
  34
  35 void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
  36                                                         int origin_transition,
  37                                                         int target_transition) {
  38   NoIncrementalWriteBarrierSet(target_transition,
  39                                origin->GetKey(origin_transition),
  40                                origin->GetTarget(origin_transition));
  41 }
  42
  43
  44 Handle<TransitionArray> TransitionArray::NewWith(Handle<Map> map,
  45                                                  Handle<Name> name,
  46                                                  Handle<Map> target,
  47                                                  SimpleTransitionFlag flag) {
  48   Handle<TransitionArray> result;
  49   Isolate* isolate = name->GetIsolate();
  50
  51   if (flag == SIMPLE_TRANSITION) {
  52     result = AllocateSimple(isolate, target);
  53   } else {
  54     result = Allocate(isolate, 1);
  55     result->NoIncrementalWriteBarrierSet(0, *name, *target);
  56   }
  57   result->set_back_pointer_storage(map->GetBackPointer());
  58   return result;
  59 }
  60
  61
  62 Handle<TransitionArray> TransitionArray::ExtendToFullTransitionArray(
  63     Handle<Map> containing_map) {
  64   DCHECK(!containing_map->transitions()->IsFullTransitionArray());
  65   int nof = containing_map->transitions()->number_of_transitions();
  66
  67   // A transition array may shrink during GC.
  68   Handle<TransitionArray> result = Allocate(containing_map->GetIsolate(), nof);
  69   DisallowHeapAllocation no_gc;
  70   int new_nof = containing_map->transitions()->number_of_transitions();
  71   if (new_nof != nof) {
  72     DCHECK(new_nof == 0);
  73     result->Shrink(ToKeyIndex(0));
  74     result->SetNumberOfTransitions(0);
  75   } else if (nof == 1) {
  76     result->NoIncrementalWriteBarrierCopyFrom(
  77         containing_map->transitions(), kSimpleTransitionIndex, 0);
  78   }
  79
  80   result->set_back_pointer_storage(
  81       containing_map->transitions()->back_pointer_storage());
  82   return result;
  83 }
  84
  85
  86 Handle<TransitionArray> TransitionArray::Insert(Handle<Map> map,
  87                                                 Handle<Name> name,
  88                                                 Handle<Map> target,
  89                                                 SimpleTransitionFlag flag) {
  90   if (!map->HasTransitionArray()) {
  91     return TransitionArray::NewWith(map, name, target, flag);
  92   }
  93
  94   int number_of_transitions = map->transitions()->number_of_transitions();
  95   int new_nof = number_of_transitions;
  96
  97   int insertion_index = kNotFound;
  98   int index = map->transitions()->Search(*name, &insertion_index);
  99
 100   if (index == kNotFound) {
 101     ++new_nof;
 102   } else {
 103     insertion_index = index;
 104   }
 105   DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
 106
 107   CHECK(new_nof <= kMaxNumberOfTransitions);
 108
 109   if (new_nof <= map->transitions()->number_of_transitions_storage()) {
 110     DisallowHeapAllocation no_gc;
 111     TransitionArray* array = map->transitions();
 112
 113     if (index != kNotFound) {
 114       array->SetTarget(index, *target);
 115       return handle(array);
 116     }
 117
 118     array->SetNumberOfTransitions(new_nof);
 119     for (index = number_of_transitions; index > insertion_index; --index) {
 120       Name* key = array->GetKey(index - 1);
 121       DCHECK(key->Hash() > name->Hash());
 122       array->SetKey(index, key);
 123       array->SetTarget(index, array->GetTarget(index - 1));
 124     }
 125     array->SetKey(index, *name);
 126     array->SetTarget(index, *target);
 127     return handle(array);
 128   }
 129
 130   Handle<TransitionArray> result = Allocate(
 131       map->GetIsolate(), new_nof,
 132       Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
 133
 134   // The map's transition array may grown smaller during the allocation above as
 135   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
 136   // result copy if needed, and recompute variables.
 137   DCHECK(map->HasTransitionArray());
 138   DisallowHeapAllocation no_gc;
 139   TransitionArray* array = map->transitions();
 140   if (array->number_of_transitions() != number_of_transitions) {
 141     DCHECK(array->number_of_transitions() < number_of_transitions);
 142
 143     number_of_transitions = array->number_of_transitions();
 144     new_nof = number_of_transitions;
 145
 146     insertion_index = kNotFound;
 147     index = array->Search(*name, &insertion_index);
 148     if (index == kNotFound) {
 149       ++new_nof;
 150     } else {
 151       insertion_index = index;
 152     }
 153     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
 154
 155     result->Shrink(ToKeyIndex(new_nof));
 156     result->SetNumberOfTransitions(new_nof);
 157   }
 158
 159   if (array->HasPrototypeTransitions()) {
 160     result->SetPrototypeTransitions(array->GetPrototypeTransitions());
 161   }
 162
 163   DCHECK_NE(kNotFound, insertion_index);
 164   for (int i = 0; i < insertion_index; ++i) {
 165     result->NoIncrementalWriteBarrierCopyFrom(array, i, i);
 166   }
 167   result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
 168   for (int i = insertion_index; i < number_of_transitions; ++i) {
 169     result->NoIncrementalWriteBarrierCopyFrom(array, i, i + 1);
 170   }
 171
 172   result->set_back_pointer_storage(array->back_pointer_storage());
 173   return result;
 174 }
 175
 176
 177 } }  // namespace v8::internal