Make order of addition the primary order of descriptor arrays.

src/objects-inl.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1869 matching lines @@
 }
 
 
 bool DescriptorArray::IsEmpty() {
   ASSERT(length() >= kFirstIndex ||
          this == HEAP->empty_descriptor_array());
   return length() < kFirstIndex;
 }
 
 
-void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array,
-                                                    int first,
-                                                    int second) {
-  Object* tmp = array->get(first);
-  NoIncrementalWriteBarrierSet(array, first, array->get(second));
-  NoIncrementalWriteBarrierSet(array, second, tmp);
-}
-
-
 // Perform a binary search in a fixed array. Low and high are entry indices. If
 // there are three entries in this array it should be called with low=0 and
 // high=2.
 template<typename T>
 int BinarySearch(T* array, String* name, int low, int high) {
   uint32_t hash = name->Hash();
   int limit = high;
 
   ASSERT(low <= high);
 
   while (low != high) {
     int mid = (low + high) / 2;
-    String* mid_name = array->GetKey(mid);
+    String* mid_name = array->GetSortedKey(mid);
     uint32_t mid_hash = mid_name->Hash();
 
     if (mid_hash >= hash) {
       high = mid;
     } else {
       low = mid + 1;
     }
   }
 
-  for (; low <= limit && array->GetKey(low)->Hash() == hash; ++low) {
-    if (array->GetKey(low)->Equals(name)) return low;
+  for (; low <= limit; ++low) {
+    int sort_index = array->GetSortedKeyIndex(low);
+    String* entry = array->GetKey(sort_index);
+    if (entry->Hash() != hash) break;
+    if (entry->Equals(name)) return sort_index;
   }
 
   return T::kNotFound;
 }
 
-
 // Perform a linear search in this fixed array. len is the number of entry
 // indices that are valid.
 template<typename T>
 int LinearSearch(T* array, String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
-    String* entry = array->GetKey(number);
+    int sorted_index = array->GetSortedKeyIndex(number);
+    String* entry = array->GetKey(sorted_index);
     uint32_t current_hash = entry->Hash();
     if (current_hash > hash) break;
-    if (current_hash == hash && name->Equals(entry)) return number;
+    if (current_hash == hash && entry->Equals(name)) return sorted_index;
   }
   return T::kNotFound;
 }
 
 
 template<typename T>
 int Search(T* array, String* name) {
   SLOW_ASSERT(array->IsSortedNoDuplicates());
 
-  // Check for empty descriptor array.
   int nof = array->number_of_entries();
   if (nof == 0) return T::kNotFound;
 
   // Fast case: do linear search for small arrays.
   const int kMaxElementsForLinearSearch = 8;
-  if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) {
+  if (nof < kMaxElementsForLinearSearch) {
     return LinearSearch(array, name, nof);
   }
 
   // Slow case: perform binary search.
   return BinarySearch(array, name, 0, nof - 1);
 }
 
 
 int DescriptorArray::Search(String* name) {
   return internal::Search(this, name);
 }
 
 
 int DescriptorArray::SearchWithCache(String* name) {
+  if (number_of_descriptors() == 0) return kNotFound;
+
   DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
   int number = cache->Lookup(this, name);
+
   if (number == DescriptorLookupCache::kAbsent) {
-    number = internal::Search(this, name);
+    number = Search(name);
     cache->Update(this, name, number);
   }
+
   return number;
 }
 
 
+void Map::LookupDescriptor(JSObject* holder,
+                           String* name,
+                           LookupResult* result) {
+  DescriptorArray* descriptors = this->instance_descriptors();
+  int number = descriptors->SearchWithCache(name);
+  if (number == DescriptorArray::kNotFound) return result->NotFound();
+  result->DescriptorResult(holder, descriptors->GetDetails(number), number);
+}
+
+
+void Map::LookupTransition(JSObject* holder,
+                           String* name,
+                           LookupResult* result) {
+  if (HasTransitionArray()) {
+    TransitionArray* transition_array = transitions();
+    int number = transition_array->Search(name);
+    if (number != TransitionArray::kNotFound) {
+      return result->TransitionResult(holder, number);
+    }
+  }
+  result->NotFound();
+}
+
+
 Object** DescriptorArray::GetKeySlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToKeyIndex(descriptor_number)));
 }
 
 
 String* DescriptorArray::GetKey(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return String::cast(get(ToKeyIndex(descriptor_number)));
 }
 
 
+int DescriptorArray::GetSortedKeyIndex(int descriptor_number) {
+  return GetDetails(descriptor_number).pointer();
+}
+
+
+String* DescriptorArray::GetSortedKey(int descriptor_number) {
+  return GetKey(GetSortedKeyIndex(descriptor_number));
+}
+
+
+void DescriptorArray::SetSortedKey(int pointer, int descriptor_number) {
+  int details_index = ToDetailsIndex(pointer);
+  PropertyDetails details = PropertyDetails(Smi::cast(get(details_index)));
+  set_unchecked(details_index, details.set_pointer(descriptor_number).AsSmi());
+}
+
+
 Object** DescriptorArray::GetValueSlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToValueIndex(descriptor_number)));
 }
 
 
 Object* DescriptorArray::GetValue(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
@@ skipping 41 matching lines @@
              GetValue(descriptor_number),
              GetDetails(descriptor_number));
 }
 
 
 void DescriptorArray::Set(int descriptor_number,
                           Descriptor* desc,
                           const WhitenessWitness&) {
   // Range check.
   ASSERT(descriptor_number < number_of_descriptors());
-  ASSERT(desc->GetDetails().index() <= number_of_descriptors());
-  ASSERT(desc->GetDetails().index() > 0);
+  ASSERT(desc->GetDetails().descriptor_index() <=
+         number_of_descriptors());
+  ASSERT(desc->GetDetails().descriptor_index() > 0);
 
   NoIncrementalWriteBarrierSet(this,
                                ToKeyIndex(descriptor_number),
                                desc->GetKey());
   NoIncrementalWriteBarrierSet(this,
                                ToValueIndex(descriptor_number),
                                desc->GetValue());
   NoIncrementalWriteBarrierSet(this,
                                ToDetailsIndex(descriptor_number),
                                desc->GetDetails().AsSmi());
 }
 
 
-int DescriptorArray::Append(Descriptor* desc,
-                            const WhitenessWitness& witness,
-                            int number_of_set_descriptors) {
-  int descriptor_number = number_of_set_descriptors;
-  int enumeration_index = descriptor_number + 1;
+void DescriptorArray::Append(Descriptor* desc,
+                             const WhitenessWitness& witness,
+                             int number_of_set_descriptors) {
+  int enumeration_index = number_of_set_descriptors + 1;
   desc->SetEnumerationIndex(enumeration_index);
+  Set(number_of_set_descriptors, desc, witness);
 
   uint32_t hash = desc->GetKey()->Hash();
 
-  for (; descriptor_number > 0; --descriptor_number) {
-    String* key = GetKey(descriptor_number - 1);
+  int insertion;
+
+  for (insertion = number_of_set_descriptors; insertion > 0; --insertion) {
+    String* key = GetSortedKey(insertion - 1);
     if (key->Hash() <= hash) break;
-    Object* value = GetValue(descriptor_number - 1);
-    PropertyDetails details = GetDetails(descriptor_number - 1);
-    Descriptor moved_descriptor(key, value, details);
-    Set(descriptor_number, &moved_descriptor, witness);
+    SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1));
   }
 
-  Set(descriptor_number, desc, witness);
-  return descriptor_number;
+  SetSortedKey(insertion, number_of_set_descriptors);
 }
 
 
-void DescriptorArray::NoIncrementalWriteBarrierSwapDescriptors(
-    int first, int second) {
-  NoIncrementalWriteBarrierSwap(this, ToKeyIndex(first), ToKeyIndex(second));
-  NoIncrementalWriteBarrierSwap(this,
-                                ToValueIndex(first),
-                                ToValueIndex(second));
-  NoIncrementalWriteBarrierSwap(this,
-                                ToDetailsIndex(first),
-                                ToDetailsIndex(second));
+void DescriptorArray::SwapSortedKeys(int first, int second) {
+  int first_key = GetSortedKeyIndex(first);
+  SetSortedKey(first, GetSortedKeyIndex(second));
+  SetSortedKey(second, first_key);
 }
 
 
 FixedArray::WhitenessWitness::WhitenessWitness(FixedArray* array)
     : marking_(array->GetHeap()->incremental_marking()) {
   marking_->EnterNoMarkingScope();
   ASSERT(Marking::Color(array) == Marking::WHITE_OBJECT);
 }
 
 
@@ skipping 1337 matching lines @@
   ASSERT(!is_shared());
   MaybeObject* maybe_failure = EnsureHasTransitionArray(this);
   if (maybe_failure->IsFailure()) return maybe_failure;
 
   transitions()->set_descriptors(value, mode);
   return this;
 }
 
 
 MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) {
+#ifdef DEBUG
   int len = descriptors->number_of_descriptors();
   ASSERT(len <= DescriptorArray::kMaxNumberOfDescriptors);
   SLOW_ASSERT(descriptors->IsSortedNoDuplicates());
 
-#ifdef DEBUG
   bool used_indices[DescriptorArray::kMaxNumberOfDescriptors];
   for (int i = 0; i < len; ++i) used_indices[i] = false;
 
   // Ensure that all enumeration indexes between 1 and length occur uniquely in
   // the descriptor array.
   for (int i = 0; i < len; ++i) {
-    int enum_index = descriptors->GetDetails(i).index() -
+    int enum_index = descriptors->GetDetails(i).descriptor_index() -
                      PropertyDetails::kInitialIndex;
     ASSERT(0 <= enum_index && enum_index < len);
     ASSERT(!used_indices[enum_index]);
     used_indices[enum_index] = true;
   }
 #endif
 
   MaybeObject* maybe_failure = SetDescriptors(descriptors);
   if (maybe_failure->IsFailure()) return maybe_failure;
 
-  for (int i = 0; i < len; ++i) {
-    if (descriptors->GetDetails(i).index() == len) {
-      SetLastAdded(i);
-      return this;
-    }
-  }
+  SetNumberOfOwnDescriptors(descriptors->number_of_descriptors());
 
-  ASSERT(len == 0 && LastAdded() == kNoneAdded);
   return this;
 }
 
 
 SMI_ACCESSORS(Map, bit_field3, kBitField3Offset)
 
 
 void Map::ClearTransitions(Heap* heap, WriteBarrierMode mode) {
   Object* back_pointer = GetBackPointer();
 #ifdef DEBUG
   Object* object = READ_FIELD(this, kTransitionsOrBackPointerOffset);
   if (object->IsTransitionArray()) {
     ZapTransitions();
   } else {
     ASSERT(object->IsMap() || object->IsUndefined());
   }
 #endif
   WRITE_FIELD(this, kTransitionsOrBackPointerOffset, back_pointer);
   CONDITIONAL_WRITE_BARRIER(
       heap, this, kTransitionsOrBackPointerOffset, back_pointer, mode);
 }
 
 
 void Map::AppendDescriptor(Descriptor* desc,
                            const DescriptorArray::WhitenessWitness& witness) {
   DescriptorArray* descriptors = instance_descriptors();
-  int set_descriptors = NumberOfSetDescriptors();
-  int new_last_added = descriptors->Append(desc, witness, set_descriptors);
-  SetLastAdded(new_last_added);
+  int number_of_own_descriptors = NumberOfOwnDescriptors();
+  ASSERT(number_of_own_descriptors < descriptors->number_of_descriptors());
+  descriptors->Append(desc, witness, number_of_own_descriptors);
+  SetNumberOfOwnDescriptors(number_of_own_descriptors + 1);
 }
 
 
 Object* Map::GetBackPointer() {
   Object* object = READ_FIELD(this, kTransitionsOrBackPointerOffset);
   if (object->IsDescriptorArray()) {
     return TransitionArray::cast(object)->back_pointer_storage();
   } else {
     ASSERT(object->IsMap() || object->IsUndefined());
     return object;
@@ skipping 1467 matching lines @@
                                       Object* value) {
   SetEntry(entry, key, value, PropertyDetails(Smi::FromInt(0)));
 }
 
 
 template<typename Shape, typename Key>
 void Dictionary<Shape, Key>::SetEntry(int entry,
                                       Object* key,
                                       Object* value,
                                       PropertyDetails details) {
-  ASSERT(!key->IsString() || details.IsDeleted() || details.index() > 0);
+  ASSERT(!key->IsString() ||
+         details.IsDeleted() ||
+         details.dictionary_index() > 0);
   int index = HashTable<Shape, Key>::EntryToIndex(entry);
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = FixedArray::GetWriteBarrierMode(no_gc);
   FixedArray::set(index, key, mode);
   FixedArray::set(index+1, value, mode);
   FixedArray::set(index+2, details.AsSmi());
 }
 
 
 bool NumberDictionaryShape::IsMatch(uint32_t key, Object* other) {
@@ skipping 297 matching lines @@
 #undef WRITE_UINT32_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_