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 "v8.h"
   6
   7 #include "objects.h"
   8 #include "transitions-inl.h"
   9 #include "utils.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13
  14
  15 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
  16                                                   int number_of_transitions) {
  17   Handle<FixedArray> array =
  18       isolate->factory()->NewFixedArray(ToKeyIndex(number_of_transitions));
  19   array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
  20   return Handle<TransitionArray>::cast(array);
  21 }
  22
  23
  24 Handle<TransitionArray> TransitionArray::AllocateSimple(Isolate* isolate,
  25                                                         Handle<Map> target) {
  26   Handle<FixedArray> array =
  27       isolate->factory()->NewFixedArray(kSimpleTransitionSize);
  28   array->set(kSimpleTransitionTarget, *target);
  29   return Handle<TransitionArray>::cast(array);
  30 }
  31
  32
  33 void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
  34                                                         int origin_transition,
  35                                                         int target_transition) {
  36   NoIncrementalWriteBarrierSet(target_transition,
  37                                origin->GetKey(origin_transition),
  38                                origin->GetTarget(origin_transition));
  39 }
  40
  41
  42 static bool InsertionPointFound(Name* key1, Name* key2) {
  43   return key1->Hash() > key2->Hash();
  44 }
  45
  46
  47 Handle<TransitionArray> TransitionArray::NewWith(Handle<Map> map,
  48                                                  Handle<Name> name,
  49                                                  Handle<Map> target,
  50                                                  SimpleTransitionFlag flag) {
  51   Handle<TransitionArray> result;
  52   Isolate* isolate = name->GetIsolate();
  53
  54   if (flag == SIMPLE_TRANSITION) {
  55     result = AllocateSimple(isolate, target);
  56   } else {
  57     result = Allocate(isolate, 1);
  58     result->NoIncrementalWriteBarrierSet(0, *name, *target);
  59   }
  60   result->set_back_pointer_storage(map->GetBackPointer());
  61   return result;
  62 }
  63
  64
  65 Handle<TransitionArray> TransitionArray::ExtendToFullTransitionArray(
  66     Handle<Map> containing_map) {
  67   ASSERT(!containing_map->transitions()->IsFullTransitionArray());
  68   int nof = containing_map->transitions()->number_of_transitions();
  69
  70   // A transition array may shrink during GC.
  71   Handle<TransitionArray> result = Allocate(containing_map->GetIsolate(), nof);
  72   DisallowHeapAllocation no_gc;
  73   int new_nof = containing_map->transitions()->number_of_transitions();
  74   if (new_nof != nof) {
  75     ASSERT(new_nof == 0);
  76     result->Shrink(ToKeyIndex(0));
  77   } else if (nof == 1) {
  78     result->NoIncrementalWriteBarrierCopyFrom(
  79         containing_map->transitions(), kSimpleTransitionIndex, 0);
  80   }
  81
  82   result->set_back_pointer_storage(
  83       containing_map->transitions()->back_pointer_storage());
  84   return result;
  85 }
  86
  87
  88 Handle<TransitionArray> TransitionArray::CopyInsert(Handle<Map> map,
  89                                                     Handle<Name> name,
  90                                                     Handle<Map> target,
  91                                                     SimpleTransitionFlag flag) {
  92   if (!map->HasTransitionArray()) {
  93     return TransitionArray::NewWith(map, name, target, flag);
  94   }
  95
  96   int number_of_transitions = map->transitions()->number_of_transitions();
  97   int new_size = number_of_transitions;
  98
  99   int insertion_index = map->transitions()->Search(*name);
 100   if (insertion_index == kNotFound) ++new_size;
 101
 102   Handle<TransitionArray> result = Allocate(map->GetIsolate(), new_size);
 103
 104   // The map's transition array may grown smaller during the allocation above as
 105   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
 106   // result copy if needed, and recompute variables.
 107   ASSERT(map->HasTransitionArray());
 108   DisallowHeapAllocation no_gc;
 109   TransitionArray* array = map->transitions();
 110   if (array->number_of_transitions() != number_of_transitions) {
 111     ASSERT(array->number_of_transitions() < number_of_transitions);
 112
 113     number_of_transitions = array->number_of_transitions();
 114     new_size = number_of_transitions;
 115
 116     insertion_index = array->Search(*name);
 117     if (insertion_index == kNotFound) ++new_size;
 118
 119     result->Shrink(ToKeyIndex(new_size));
 120   }
 121
 122   if (array->HasPrototypeTransitions()) {
 123     result->SetPrototypeTransitions(array->GetPrototypeTransitions());
 124   }
 125
 126   if (insertion_index != kNotFound) {
 127     for (int i = 0; i < number_of_transitions; ++i) {
 128       if (i != insertion_index) {
 129         result->NoIncrementalWriteBarrierCopyFrom(array, i, i);
 130       }
 131     }
 132     result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
 133     result->set_back_pointer_storage(array->back_pointer_storage());
 134     return result;
 135   }
 136
 137   insertion_index = 0;
 138   for (; insertion_index < number_of_transitions; ++insertion_index) {
 139     if (InsertionPointFound(array->GetKey(insertion_index), *name)) break;
 140     result->NoIncrementalWriteBarrierCopyFrom(
 141         array, insertion_index, insertion_index);
 142   }
 143
 144   result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
 145
 146   for (; insertion_index < number_of_transitions; ++insertion_index) {
 147     result->NoIncrementalWriteBarrierCopyFrom(
 148         array, insertion_index, insertion_index + 1);
 149   }
 150
 151   result->set_back_pointer_storage(array->back_pointer_storage());
 152   return result;
 153 }
 154
 155
 156 } }  // namespace v8::internal