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
11namespace v8 {
12namespace internal {
13
14
15Handle<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
24Handle<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
33void 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
42static bool InsertionPointFound(Name* key1, Name* key2) {
43  return key1->Hash() > key2->Hash();
44}
45
46
47Handle<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
65Handle<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
88Handle<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
157