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
Allocate(Isolate * isolate,int number_of_transitions)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
AllocateSimple(Isolate * isolate,Handle<Map> target)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
NoIncrementalWriteBarrierCopyFrom(TransitionArray * origin,int origin_transition,int target_transition)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
InsertionPointFound(Name * key1,Name * key2)42 static bool InsertionPointFound(Name* key1, Name* key2) {
43 return key1->Hash() > key2->Hash();
44 }
45
46
NewWith(Handle<Map> map,Handle<Name> name,Handle<Map> target,SimpleTransitionFlag flag)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
ExtendToFullTransitionArray(Handle<Map> containing_map)65 Handle<TransitionArray> TransitionArray::ExtendToFullTransitionArray(
66 Handle<Map> containing_map) {
67 DCHECK(!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 DCHECK(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
CopyInsert(Handle<Map> map,Handle<Name> name,Handle<Map> target,SimpleTransitionFlag flag)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 DCHECK(map->HasTransitionArray());
108 DisallowHeapAllocation no_gc;
109 TransitionArray* array = map->transitions();
110 if (array->number_of_transitions() != number_of_transitions) {
111 DCHECK(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