1// Copyright 2012 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "v8.h"
29
30#include "objects.h"
31#include "transitions-inl.h"
32#include "utils.h"
33
34namespace v8 {
35namespace internal {
36
37
38static MaybeObject* AllocateRaw(Isolate* isolate, int length) {
39  // Use FixedArray to not use TransitionArray::cast on incomplete object.
40  FixedArray* array;
41  MaybeObject* maybe_array = isolate->heap()->AllocateFixedArray(length);
42  if (!maybe_array->To(&array)) return maybe_array;
43  return array;
44}
45
46
47MaybeObject* TransitionArray::Allocate(Isolate* isolate,
48                                       int number_of_transitions) {
49  FixedArray* array;
50  MaybeObject* maybe_array =
51      AllocateRaw(isolate, ToKeyIndex(number_of_transitions));
52  if (!maybe_array->To(&array)) return maybe_array;
53  array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
54  return array;
55}
56
57
58void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
59                                                        int origin_transition,
60                                                        int target_transition) {
61  NoIncrementalWriteBarrierSet(target_transition,
62                               origin->GetKey(origin_transition),
63                               origin->GetTarget(origin_transition));
64}
65
66
67static bool InsertionPointFound(Name* key1, Name* key2) {
68  return key1->Hash() > key2->Hash();
69}
70
71
72MaybeObject* TransitionArray::NewWith(SimpleTransitionFlag flag,
73                                      Name* key,
74                                      Map* target,
75                                      Object* back_pointer) {
76  TransitionArray* result;
77  MaybeObject* maybe_result;
78
79  if (flag == SIMPLE_TRANSITION) {
80    maybe_result = AllocateRaw(target->GetIsolate(), kSimpleTransitionSize);
81    if (!maybe_result->To(&result)) return maybe_result;
82    result->set(kSimpleTransitionTarget, target);
83  } else {
84    maybe_result = Allocate(target->GetIsolate(), 1);
85    if (!maybe_result->To(&result)) return maybe_result;
86    result->NoIncrementalWriteBarrierSet(0, key, target);
87  }
88  result->set_back_pointer_storage(back_pointer);
89  return result;
90}
91
92
93MaybeObject* TransitionArray::ExtendToFullTransitionArray() {
94  ASSERT(!IsFullTransitionArray());
95  int nof = number_of_transitions();
96  TransitionArray* result;
97  MaybeObject* maybe_result = Allocate(GetIsolate(), nof);
98  if (!maybe_result->To(&result)) return maybe_result;
99
100  if (nof == 1) {
101    result->NoIncrementalWriteBarrierCopyFrom(this, kSimpleTransitionIndex, 0);
102  }
103
104  result->set_back_pointer_storage(back_pointer_storage());
105  return result;
106}
107
108
109MaybeObject* TransitionArray::CopyInsert(Name* name, Map* target) {
110  TransitionArray* result;
111
112  int number_of_transitions = this->number_of_transitions();
113  int new_size = number_of_transitions;
114
115  int insertion_index = this->Search(name);
116  if (insertion_index == kNotFound) ++new_size;
117
118  MaybeObject* maybe_array;
119  maybe_array = TransitionArray::Allocate(GetIsolate(), new_size);
120  if (!maybe_array->To(&result)) return maybe_array;
121
122  if (HasPrototypeTransitions()) {
123    result->SetPrototypeTransitions(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(this, i, i);
130      }
131    }
132    result->NoIncrementalWriteBarrierSet(insertion_index, name, target);
133    result->set_back_pointer_storage(back_pointer_storage());
134    return result;
135  }
136
137  insertion_index = 0;
138  for (; insertion_index < number_of_transitions; ++insertion_index) {
139    if (InsertionPointFound(GetKey(insertion_index), name)) break;
140    result->NoIncrementalWriteBarrierCopyFrom(
141        this, 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        this, insertion_index, insertion_index + 1);
149  }
150
151  result->set_back_pointer_storage(back_pointer_storage());
152  return result;
153}
154
155
156} }  // namespace v8::internal
157