From ff13ab457504e7edc63186bd3de120674595bb81 Mon Sep 17 00:00:00 2001 From: "danno@chromium.org" Date: Wed, 10 Aug 2011 10:51:01 +0000 Subject: [PATCH] Refactor UnionOfKeys into ElementsAccessor BUG=none TEST=none Review URL: http://codereview.chromium.org/7529046 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@8870 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/elements.cc | 111 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/elements.h | 3 ++ src/objects.cc | 109 +------------------------------------------------------ src/objects.h | 4 -- 4 files changed, 115 insertions(+), 112 deletions(-) diff --git a/src/elements.cc b/src/elements.cc index 45ab2d9..9cfccee 100644 --- a/src/elements.cc +++ b/src/elements.cc @@ -37,6 +37,20 @@ namespace internal { ElementsAccessor** ElementsAccessor::elements_accessors_; +bool HasKey(FixedArray* array, Object* key) { + int len0 = array->length(); + for (int i = 0; i < len0; i++) { + Object* element = array->get(i); + if (element->IsSmi() && element == key) return true; + if (element->IsString() && + key->IsString() && String::cast(element)->Equals(String::cast(key))) { + return true; + } + } + return false; +} + + // Base class for element handler implementations. Contains the // the common logic for objects with different ElementsKinds. // Subclasses must specialize method for which the element @@ -73,6 +87,78 @@ class ElementsAccessorBase : public ElementsAccessor { uint32_t index, JSReceiver::DeleteMode mode) = 0; + virtual MaybeObject* AddJSArrayKeysToFixedArray(JSArray* other, + FixedArray* keys) { + int len0 = keys->length(); +#ifdef DEBUG + if (FLAG_enable_slow_asserts) { + for (int i = 0; i < len0; i++) { + ASSERT(keys->get(i)->IsString() || keys->get(i)->IsNumber()); + } + } +#endif + int len1 = ElementsAccessorSubclass::GetCapacity(other); + + // Optimize if 'other' is empty. + // We cannot optimize if 'this' is empty, as other may have holes + // or non keys. + if (len1 == 0) return keys; + + // Compute how many elements are not in other. + int extra = 0; + for (int y = 0; y < len1; y++) { + Object* value; + MaybeObject* maybe_value = + ElementsAccessorSubclass::GetElementAtCapacityIndex(other, y); + if (!maybe_value->ToObject(&value)) return maybe_value; + if (!value->IsTheHole() && !HasKey(keys, value)) extra++; + } + + if (extra == 0) return keys; + + // Allocate the result + FixedArray* result; + MaybeObject* maybe_obj = + other->GetHeap()->AllocateFixedArray(len0 + extra); + if (!maybe_obj->To(&result)) return maybe_obj; + + // Fill in the content + { + AssertNoAllocation no_gc; + WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc); + for (int i = 0; i < len0; i++) { + Object* e = keys->get(i); + ASSERT(e->IsString() || e->IsNumber()); + result->set(i, e, mode); + } + } + // Fill in the extra keys. + int index = 0; + for (int y = 0; y < len1; y++) { + MaybeObject* maybe_value = + ElementsAccessorSubclass::GetElementAtCapacityIndex(other, y); + Object* value; + if (!maybe_value->ToObject(&value)) return maybe_value; + if (!value->IsTheHole() && !HasKey(keys, value)) { + ASSERT(value->IsString() || value->IsNumber()); + result->set(len0 + index, value); + index++; + } + } + ASSERT(extra == index); + return result; + } + + static uint32_t GetCapacity(JSObject* obj) { + return ElementsAccessorSubclass::GetBackingStore(obj)->length(); + } + + static MaybeObject* GetElementAtCapacityIndex(JSObject* obj, int index) { + BackingStoreClass* backing_store = + ElementsAccessorSubclass::GetBackingStore(obj); + return backing_store->get(index); + } + protected: static BackingStoreClass* GetBackingStore(JSObject* obj) { return BackingStoreClass::cast(obj->elements()); @@ -325,6 +411,19 @@ class DictionaryElementsAccessor obj->element_dictionary(), index); } + + static uint32_t GetCapacity(JSObject* obj) { + return obj->element_dictionary()->Capacity(); + } + + static MaybeObject* GetElementAtCapacityIndex(JSObject* obj, int index) { + NumberDictionary* dict = obj->element_dictionary(); + if (dict->IsKey(dict->KeyAt(index))) { + return dict->ValueAt(index); + } else { + return obj->GetHeap()->the_hole_value(); + } + } }; @@ -382,6 +481,18 @@ class NonStrictArgumentsElementsAccessor } return obj->GetHeap()->true_value(); } + + static uint32_t GetCapacity(JSObject* obj) { + // TODO(danno): Return max of parameter map length or backing store + // capacity. + return 0; + } + + static MaybeObject* GetElementAtCapacityIndex(JSObject* obj, int index) { + // TODO(danno): Return either value from parameter map of backing + // store value at index. + return obj->GetHeap()->the_hole_value(); + } }; diff --git a/src/elements.h b/src/elements.h index b552286..f64244e 100644 --- a/src/elements.h +++ b/src/elements.h @@ -47,6 +47,9 @@ class ElementsAccessor { uint32_t index, JSReceiver::DeleteMode mode) = 0; + virtual MaybeObject* AddJSArrayKeysToFixedArray(JSArray* other, + FixedArray* keys) = 0; + // Returns a shared ElementsAccessor for the specified ElementsKind. static ElementsAccessor* ForKind(JSObject::ElementsKind elements_kind) { ASSERT(elements_kind < JSObject::kElementsKindCount); diff --git a/src/objects.cc b/src/objects.cc index 1345f27..e35274d 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -4637,51 +4637,7 @@ MaybeObject* PolymorphicCodeCacheHashTable::Put(MapList* maps, MaybeObject* FixedArray::AddKeysFromJSArray(JSArray* array) { - ASSERT(!array->HasExternalArrayElements()); - switch (array->GetElementsKind()) { - case JSObject::FAST_ELEMENTS: - return UnionOfKeys(FixedArray::cast(array->elements())); - case JSObject::FAST_DOUBLE_ELEMENTS: - return UnionOfDoubleKeys(FixedDoubleArray::cast(array->elements())); - break; - case JSObject::DICTIONARY_ELEMENTS: { - NumberDictionary* dict = array->element_dictionary(); - int size = dict->NumberOfElements(); - - // Allocate a temporary fixed array. - Object* object; - { MaybeObject* maybe_object = GetHeap()->AllocateFixedArray(size); - if (!maybe_object->ToObject(&object)) return maybe_object; - } - FixedArray* key_array = FixedArray::cast(object); - - int capacity = dict->Capacity(); - int pos = 0; - // Copy the elements from the JSArray to the temporary fixed array. - for (int i = 0; i < capacity; i++) { - if (dict->IsKey(dict->KeyAt(i))) { - key_array->set(pos++, dict->ValueAt(i)); - } - } - // Compute the union of this and the temporary fixed array. - return UnionOfKeys(key_array); - } - case JSObject::NON_STRICT_ARGUMENTS_ELEMENTS: - UNIMPLEMENTED(); - break; - case JSObject::EXTERNAL_BYTE_ELEMENTS: - case JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS: - case JSObject::EXTERNAL_SHORT_ELEMENTS: - case JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS: - case JSObject::EXTERNAL_INT_ELEMENTS: - case JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS: - case JSObject::EXTERNAL_FLOAT_ELEMENTS: - case JSObject::EXTERNAL_DOUBLE_ELEMENTS: - case JSObject::EXTERNAL_PIXEL_ELEMENTS: - break; - } - UNREACHABLE(); - return GetHeap()->null_value(); // Failure case needs to "return" a value. + return array->GetElementsAccessor()->AddJSArrayKeysToFixedArray(array, this); } @@ -4739,69 +4695,6 @@ MaybeObject* FixedArray::UnionOfKeys(FixedArray* other) { } -MaybeObject* FixedArray::UnionOfDoubleKeys(FixedDoubleArray* other) { - int len0 = length(); -#ifdef DEBUG - if (FLAG_enable_slow_asserts) { - for (int i = 0; i < len0; i++) { - ASSERT(get(i)->IsString() || get(i)->IsNumber()); - } - } -#endif - int len1 = other->length(); - // Optimize if 'other' is empty. - // We cannot optimize if 'this' is empty, as other may have holes - // or non keys. - if (len1 == 0) return this; - - // Compute how many elements are not in this. - int extra = 0; - Heap* heap = GetHeap(); - Object* obj; - for (int y = 0; y < len1; y++) { - if (!other->is_the_hole(y)) { - MaybeObject* maybe_obj = heap->NumberFromDouble(other->get_scalar(y)); - if (!maybe_obj->ToObject(&obj)) return maybe_obj; - if (!HasKey(this, obj)) extra++; - } - } - - if (extra == 0) return this; - - // Allocate the result - { MaybeObject* maybe_obj = GetHeap()->AllocateFixedArray(len0 + extra); - if (!maybe_obj->ToObject(&obj)) return maybe_obj; - } - // Fill in the content - FixedArray* result = FixedArray::cast(obj); - { - // Limit the scope of the AssertNoAllocation - AssertNoAllocation no_gc; - WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc); - for (int i = 0; i < len0; i++) { - Object* e = get(i); - ASSERT(e->IsString() || e->IsNumber()); - result->set(i, e, mode); - } - } - - // Fill in the extra keys. - int index = 0; - for (int y = 0; y < len1; y++) { - if (!other->is_the_hole(y)) { - MaybeObject* maybe_obj = heap->NumberFromDouble(other->get_scalar(y)); - if (!maybe_obj->ToObject(&obj)) return maybe_obj; - if (!HasKey(this, obj)) { - result->set(len0 + index, obj); - index++; - } - } - } - ASSERT(extra == index); - return result; -} - - MaybeObject* FixedArray::CopySize(int new_length) { Heap* heap = GetHeap(); if (new_length == 0) return heap->empty_fixed_array(); diff --git a/src/objects.h b/src/objects.h index 8f9f18c..ff13aed 100644 --- a/src/objects.h +++ b/src/objects.h @@ -2128,10 +2128,6 @@ class FixedArray: public FixedArrayBase { // Compute the union of this and other. MUST_USE_RESULT MaybeObject* UnionOfKeys(FixedArray* other); - // Compute the union of this and other. - MUST_USE_RESULT MaybeObject* UnionOfDoubleKeys( - FixedDoubleArray* other); - // Copy a sub array from the receiver to dest. void CopyTo(int pos, FixedArray* dest, int dest_pos, int len); -- 2.7.4