Removed virtual behavior from Dictionaries.

src/objects.cc

 // Copyright 2006-2009 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 23 matching lines @@
 #include "objects-inl.h"
 #include "macro-assembler.h"
 #include "scanner.h"
 #include "scopeinfo.h"
 #include "string-stream.h"
 
 #ifdef ENABLE_DISASSEMBLER
 #include "disassembler.h"
 #endif
 
+
 namespace v8 {
 namespace internal {
 
 // Getters and setters are stored in a fixed array property.  These are
 // constants for their indices.
 const int kGetterIndex = 0;
 const int kSetterIndex = 1;
 
 bool Object::IsInstanceOf(FunctionTemplateInfo* expected) {
   // There is a constraint on the object; check
@@ skipping 367 matching lines @@
     property_dictionary()->ValueAtPut(result->GetDictionaryEntry(), value);
   }
   return value;
 }
 
 
 Object* JSObject::SetNormalizedProperty(String* name,
                                         Object* value,
                                         PropertyDetails details) {
   ASSERT(!HasFastProperties());
-  int entry = property_dictionary()->FindStringEntry(name);
-  if (entry == Dictionary::kNotFound) {
+  int entry = property_dictionary()->FindEntry(name);
+  if (entry == StringDictionary::kNotFound) {
     Object* store_value = value;
     if (IsGlobalObject()) {
       store_value = Heap::AllocateJSGlobalPropertyCell(value);
       if (store_value->IsFailure()) return store_value;
     }
     Object* dict =
-        property_dictionary()->AddStringEntry(name, store_value, details);
+        property_dictionary()->Add(name, store_value, details);
     if (dict->IsFailure()) return dict;
-    set_properties(Dictionary::cast(dict));
+    set_properties(StringDictionary::cast(dict));
     return value;
   }
   // Preserve enumeration index.
   details = PropertyDetails(details.attributes(),
                             details.type(),
                             property_dictionary()->DetailsAt(entry).index());
   if (IsGlobalObject()) {
     JSGlobalPropertyCell* cell =
         JSGlobalPropertyCell::cast(property_dictionary()->ValueAt(entry));
     cell->set_value(value);
     // Please note we have to update the property details.
     property_dictionary()->DetailsAtPut(entry, details);
   } else {
-    property_dictionary()->SetStringEntry(entry, name, value, details);
+    property_dictionary()->SetEntry(entry, name, value, details);
   }
   return value;
 }
 
 
 Object* JSObject::DeleteNormalizedProperty(String* name, DeleteMode mode) {
   ASSERT(!HasFastProperties());
-  Dictionary* dictionary = property_dictionary();
-  int entry = dictionary->FindStringEntry(name);
-  if (entry != Dictionary::kNotFound) {
+  StringDictionary* dictionary = property_dictionary();
+  int entry = dictionary->FindEntry(name);
+  if (entry != StringDictionary::kNotFound) {
     // If we have a global object set the cell to the hole.
     if (IsGlobalObject()) {
       PropertyDetails details = dictionary->DetailsAt(entry);
       if (details.IsDontDelete() && mode != FORCE_DELETION) {
         return Heap::false_value();
       }
       JSGlobalPropertyCell* cell =
           JSGlobalPropertyCell::cast(dictionary->ValueAt(entry));
       cell->set_value(Heap::the_hole_value());
       dictionary->DetailsAtPut(entry, details.AsDeleted());
@@ skipping 857 matching lines @@
 
   return function;
 }
 
 
 // Add property in slow mode
 Object* JSObject::AddSlowProperty(String* name,
                                   Object* value,
                                   PropertyAttributes attributes) {
   ASSERT(!HasFastProperties());
-  Dictionary* dict = property_dictionary();
+  StringDictionary* dict = property_dictionary();
   Object* store_value = value;
   if (IsGlobalObject()) {
     // In case name is an orphaned property reuse the cell.
-    int entry = dict->FindStringEntry(name);
-    if (entry != Dictionary::kNotFound) {
+    int entry = dict->FindEntry(name);
+    if (entry != StringDictionary::kNotFound) {
       store_value = dict->ValueAt(entry);
       JSGlobalPropertyCell::cast(store_value)->set_value(value);
       PropertyDetails details = PropertyDetails(attributes, NORMAL);
-      dict->SetStringEntry(entry, name, store_value, details);
+      dict->SetEntry(entry, name, store_value, details);
       return value;
     }
     store_value = Heap::AllocateJSGlobalPropertyCell(value);
     if (store_value->IsFailure()) return store_value;
     JSGlobalPropertyCell::cast(store_value)->set_value(value);
   }
   PropertyDetails details = PropertyDetails(attributes, NORMAL);
-  Object* result = dict->AddStringEntry(name, store_value, details);
+  Object* result = dict->Add(name, store_value, details);
   if (result->IsFailure()) return result;
-  if (dict != result) set_properties(Dictionary::cast(result));
+  if (dict != result) set_properties(StringDictionary::cast(result));
   return value;
 }
 
 
 Object* JSObject::AddProperty(String* name,
                               Object* value,
                               PropertyAttributes attributes) {
   ASSERT(!IsJSGlobalProxy());
   if (HasFastProperties()) {
     // Ensure the descriptor array does not get too big.
@@ skipping 25 matching lines @@
   LocalLookupRealNamedProperty(name, &result);
   if (result.IsValid()) return SetProperty(&result, name, value, attributes);
   // Add real property.
   return AddProperty(name, value, attributes);
 }
 
 
 Object* JSObject::ReplaceSlowProperty(String* name,
                                        Object* value,
                                        PropertyAttributes attributes) {
-  Dictionary* dictionary = property_dictionary();
-  int old_index = dictionary->FindStringEntry(name);
+  StringDictionary* dictionary = property_dictionary();
+  int old_index = dictionary->FindEntry(name);
   int new_enumeration_index = 0;  // 0 means "Use the next available index."
   if (old_index != -1) {
     // All calls to ReplaceSlowProperty have had all transitions removed.
     ASSERT(!dictionary->DetailsAt(old_index).IsTransition());
     new_enumeration_index = dictionary->DetailsAt(old_index).index();
   }
 
   PropertyDetails new_details(attributes, NORMAL, new_enumeration_index);
   return SetNormalizedProperty(name, value, new_details);
 }
@@ skipping 219 matching lines @@
   }
   result->NotFound();
 }
 
 
 Object* JSObject::LookupCallbackSetterInPrototypes(uint32_t index) {
   for (Object* pt = GetPrototype();
        pt != Heap::null_value();
        pt = pt->GetPrototype()) {
     if (JSObject::cast(pt)->HasFastElements()) continue;
-    Dictionary* dictionary = JSObject::cast(pt)->element_dictionary();
-    int entry = dictionary->FindNumberEntry(index);
-    if (entry != Dictionary::kNotFound) {
+    NumberDictionary* dictionary = JSObject::cast(pt)->element_dictionary();
+    int entry = dictionary->FindEntry(index);
+    if (entry != StringDictionary::kNotFound) {
       Object* element = dictionary->ValueAt(entry);
       PropertyDetails details = dictionary->DetailsAt(entry);
       if (details.type() == CALLBACKS) {
         // Only accessors allowed as elements.
         return FixedArray::cast(element)->get(kSetterIndex);
       }
     }
   }
   return Heap::undefined_value();
 }
@@ skipping 29 matching lines @@
       ASSERT(result->holder() == this && result->type() != NORMAL);
       // Disallow caching for uninitialized constants. These can only
       // occur as fields.
       if (result->IsReadOnly() && result->type() == FIELD &&
           FastPropertyAt(result->GetFieldIndex())->IsTheHole()) {
         result->DisallowCaching();
       }
       return;
     }
   } else {
-    int entry = property_dictionary()->FindStringEntry(name);
-    if (entry != Dictionary::kNotFound) {
+    int entry = property_dictionary()->FindEntry(name);
+    if (entry != StringDictionary::kNotFound) {
       // Make sure to disallow caching for uninitialized constants
       // found in the dictionary-mode objects.
       Object* value = property_dictionary()->ValueAt(entry);
       if (IsGlobalObject()) {
         PropertyDetails d = property_dictionary()->DetailsAt(entry);
         if (d.IsDeleted()) {
           result->NotFound();
           return;
         }
         value = JSGlobalPropertyCell::cast(value)->value();
@@ skipping 381 matching lines @@
   LocalLookup(name, &result);
   return GetPropertyAttribute(this, &result, name, false);
 }
 
 
 Object* JSObject::NormalizeProperties(PropertyNormalizationMode mode) {
   if (!HasFastProperties()) return this;
 
   // Allocate new content
   Object* obj =
-      Dictionary::Allocate(map()->NumberOfDescribedProperties() * 2 + 4);
+      StringDictionary::Allocate(map()->NumberOfDescribedProperties() * 2 + 4);
   if (obj->IsFailure()) return obj;
-  Dictionary* dictionary = Dictionary::cast(obj);
+  StringDictionary* dictionary = StringDictionary::cast(obj);
 
   for (DescriptorReader r(map()->instance_descriptors());
        !r.eos();
        r.advance()) {
     PropertyDetails details = r.GetDetails();
     switch (details.type()) {
       case CONSTANT_FUNCTION: {
         PropertyDetails d =
             PropertyDetails(details.attributes(), NORMAL, details.index());
         Object* value = r.GetConstantFunction();
         if (IsGlobalObject()) {
           value = Heap::AllocateJSGlobalPropertyCell(value);
           if (value->IsFailure()) return value;
         }
-        Object* result = dictionary->AddStringEntry(r.GetKey(), value, d);
+        Object* result = dictionary->Add(r.GetKey(), value, d);
         if (result->IsFailure()) return result;
-        dictionary = Dictionary::cast(result);
+        dictionary = StringDictionary::cast(result);
         break;
       }
       case FIELD: {
         PropertyDetails d =
             PropertyDetails(details.attributes(), NORMAL, details.index());
         Object* value = FastPropertyAt(r.GetFieldIndex());
         if (IsGlobalObject()) {
           value = Heap::AllocateJSGlobalPropertyCell(value);
           if (value->IsFailure()) return value;
         }
-        Object* result = dictionary->AddStringEntry(r.GetKey(), value, d);
+        Object* result = dictionary->Add(r.GetKey(), value, d);
         if (result->IsFailure()) return result;
-        dictionary = Dictionary::cast(result);
+        dictionary = StringDictionary::cast(result);
         break;
       }
       case CALLBACKS: {
         PropertyDetails d =
             PropertyDetails(details.attributes(), CALLBACKS, details.index());
         Object* value = r.GetCallbacksObject();
         if (IsGlobalObject()) {
           value = Heap::AllocateJSGlobalPropertyCell(value);
           if (value->IsFailure()) return value;
         }
-        Object* result = dictionary->AddStringEntry(r.GetKey(), value, d);
+        Object* result = dictionary->Add(r.GetKey(), value, d);
         if (result->IsFailure()) return result;
-        dictionary = Dictionary::cast(result);
+        dictionary = StringDictionary::cast(result);
         break;
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
       case NULL_DESCRIPTOR:
       case INTERCEPTOR:
         break;
       default:
       case NORMAL:
         UNREACHABLE();
@@ skipping 52 matching lines @@
 Object* JSObject::NormalizeElements() {
   if (!HasFastElements()) return this;
 
   // Get number of entries.
   FixedArray* array = FixedArray::cast(elements());
 
   // Compute the effective length.
   int length = IsJSArray() ?
                Smi::cast(JSArray::cast(this)->length())->value() :
                array->length();
-  Object* obj = Dictionary::Allocate(length);
+  Object* obj = NumberDictionary::Allocate(length);
   if (obj->IsFailure()) return obj;
-  Dictionary* dictionary = Dictionary::cast(obj);
+  NumberDictionary* dictionary = NumberDictionary::cast(obj);
   // Copy entries.
   for (int i = 0; i < length; i++) {
     Object* value = array->get(i);
     if (!value->IsTheHole()) {
       PropertyDetails details = PropertyDetails(NONE, NORMAL);
       Object* result = dictionary->AddNumberEntry(i, array->get(i), details);
       if (result->IsFailure()) return result;
-      dictionary = Dictionary::cast(result);
+      dictionary = NumberDictionary::cast(result);
     }
   }
   // Switch to using the dictionary as the backing storage for elements.
   set_elements(dictionary);
 
   Counters::elements_to_dictionary.Increment();
 
 #ifdef DEBUG
   if (FLAG_trace_normalization) {
     PrintF("Object elements have been normalized:\n");
@@ skipping 56 matching lines @@
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
       static_cast<uint32_t>(Smi::cast(JSArray::cast(this)->length())->value()) :
       static_cast<uint32_t>(FixedArray::cast(elements())->length());
     if (index < length) {
       FixedArray::cast(elements())->set_the_hole(index);
     }
     return Heap::true_value();
   }
   ASSERT(!HasFastElements());
-  Dictionary* dictionary = element_dictionary();
-  int entry = dictionary->FindNumberEntry(index);
-  if (entry != Dictionary::kNotFound) {
+  NumberDictionary* dictionary = element_dictionary();
+  int entry = dictionary->FindEntry(index);
+  if (entry != StringDictionary::kNotFound) {

[Mads Ager (chromium), 2009/07/01 15:32:49]

NumberDictionary::kNotFound

     return dictionary->DeleteProperty(entry, mode);
   }
   return Heap::true_value();
 }
 
 
 Object* JSObject::DeleteElementWithInterceptor(uint32_t index) {
   // Make sure that the top context does not change when doing
   // callbacks or interceptor calls.
   AssertNoContextChange ncc;
@@ skipping 51 matching lines @@
 
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
       static_cast<uint32_t>(Smi::cast(JSArray::cast(this)->length())->value()) :
       static_cast<uint32_t>(FixedArray::cast(elements())->length());
     if (index < length) {
       FixedArray::cast(elements())->set_the_hole(index);
     }
     return Heap::true_value();
   } else {
-    Dictionary* dictionary = element_dictionary();
-    int entry = dictionary->FindNumberEntry(index);
-    if (entry != Dictionary::kNotFound) {
+    NumberDictionary* dictionary = element_dictionary();
+    int entry = dictionary->FindEntry(index);
+    if (entry != NumberDictionary::kNotFound) {
       return dictionary->DeleteProperty(entry, mode);
     }
   }
   return Heap::true_value();
 }
 
 
 Object* JSObject::DeleteProperty(String* name, DeleteMode mode) {
   // ECMA-262, 3rd, 8.6.2.5
   ASSERT(name->IsString());
@@ skipping 284 matching lines @@
     }
   }
 
   uint32_t index;
   bool is_element = name->AsArrayIndex(&index);
   if (is_element && IsJSArray()) return Heap::undefined_value();
 
   if (is_element) {
     // Lookup the index.
     if (!HasFastElements()) {
-      Dictionary* dictionary = element_dictionary();
-      int entry = dictionary->FindNumberEntry(index);
-      if (entry != Dictionary::kNotFound) {
+      NumberDictionary* dictionary = element_dictionary();
+      int entry = dictionary->FindEntry(index);
+      if (entry != NumberDictionary::kNotFound) {
         Object* result = dictionary->ValueAt(entry);
         PropertyDetails details = dictionary->DetailsAt(entry);
         if (details.IsReadOnly()) return Heap::undefined_value();
         if (details.type() == CALLBACKS) {
           // Only accessors allowed as elements.
           ASSERT(result->IsFixedArray());
           return result;
         }
       }
     }
@@ skipping 15 matching lines @@
   if (structure->IsFailure()) return structure;
   PropertyDetails details = PropertyDetails(attributes, CALLBACKS);
 
   if (is_element) {
     // Normalize object to make this operation simple.
     Object* ok = NormalizeElements();
     if (ok->IsFailure()) return ok;
 
     // Update the dictionary with the new CALLBACKS property.
     Object* dict =
-        element_dictionary()->SetOrAddNumberEntry(index, structure, details);
+        element_dictionary()->Set(index, structure, details);
     if (dict->IsFailure()) return dict;
 
     // If name is an index we need to stay in slow case.
-    Dictionary* elements = Dictionary::cast(dict);
+    NumberDictionary* elements = NumberDictionary::cast(dict);
     elements->set_requires_slow_elements();
     // Set the potential new dictionary on the object.
-    set_elements(Dictionary::cast(dict));
+    set_elements(NumberDictionary::cast(dict));
   } else {
     // Normalize object to make this operation simple.
     Object* ok = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES);
     if (ok->IsFailure()) return ok;
 
     // For the global object allocate a new map to invalidate the global inline
     // caches which have a global property cell reference directly in the code.
     if (IsGlobalObject()) {
       Object* new_map = map()->CopyDropDescriptors();
       if (new_map->IsFailure()) return new_map;
@@ skipping 46 matching lines @@
 
   // Make the lookup and include prototypes.
   int accessor_index = is_getter ? kGetterIndex : kSetterIndex;
   uint32_t index;
   if (name->AsArrayIndex(&index)) {
     for (Object* obj = this;
          obj != Heap::null_value();
          obj = JSObject::cast(obj)->GetPrototype()) {
       JSObject* jsObject = JSObject::cast(obj);
       if (!jsObject->HasFastElements()) {
-        Dictionary* dictionary = jsObject->element_dictionary();
-        int entry = dictionary->FindNumberEntry(index);
-        if (entry != Dictionary::kNotFound) {
+        NumberDictionary* dictionary = jsObject->element_dictionary();
+        int entry = dictionary->FindEntry(index);
+        if (entry != NumberDictionary::kNotFound) {
           Object* element = dictionary->ValueAt(entry);
           PropertyDetails details = dictionary->DetailsAt(entry);
           if (details.type() == CALLBACKS) {
             // Only accessors allowed as elements.
             return FixedArray::cast(element)->get(accessor_index);
           }
         }
       }
     }
   } else {
@@ skipping 182 matching lines @@
   }
   return false;
 }
 
 
 Object* FixedArray::AddKeysFromJSArray(JSArray* array) {
   if (array->HasFastElements()) {
     return UnionOfKeys(array->elements());
   }
   ASSERT(!array->HasFastElements());
-  Dictionary* dict = array->element_dictionary();
+  NumberDictionary* dict = array->element_dictionary();
   int size = dict->NumberOfElements();
 
   // Allocate a temporary fixed array.
   Object* object = Heap::AllocateFixedArray(size);
   if (object->IsFailure()) return 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.
@@ skipping 2050 matching lines @@
 #endif
   WriteBarrierMode mode = elems->GetWriteBarrierMode();
   if (HasFastElements()) {
     FixedArray* old_elements = FixedArray::cast(elements());
     uint32_t old_length = static_cast<uint32_t>(old_elements->length());
     // Fill out the new array with this content and array holes.
     for (uint32_t i = 0; i < old_length; i++) {
       elems->set(i, old_elements->get(i), mode);
     }
   } else {
-    Dictionary* dictionary = Dictionary::cast(elements());
+    NumberDictionary* dictionary = NumberDictionary::cast(elements());
     for (int i = 0; i < dictionary->Capacity(); i++) {
       Object* key = dictionary->KeyAt(i);
       if (key->IsNumber()) {
         uint32_t entry = static_cast<uint32_t>(key->Number());
         elems->set(entry, dictionary->ValueAt(i), mode);
       }
     }
   }
   set_elements(elems);
 }
@@ skipping 144 matching lines @@
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
         static_cast<uint32_t>(
             Smi::cast(JSArray::cast(this)->length())->value()) :
         static_cast<uint32_t>(FixedArray::cast(elements())->length());
     if ((index < length) &&
         !FixedArray::cast(elements())->get(index)->IsTheHole()) {
       return true;
     }
   } else {
-    if (element_dictionary()->FindNumberEntry(index) != Dictionary::kNotFound) {
+    if (element_dictionary()->FindEntry(index)
+        != NumberDictionary::kNotFound) {
       return true;
     }
   }
 
   // Handle [] on String objects.
   if (this->IsStringObjectWithCharacterAt(index)) return true;
 
   Object* pt = GetPrototype();
   if (pt == Heap::null_value()) return false;
   return JSObject::cast(pt)->HasElementWithReceiver(receiver, index);
@@ skipping 56 matching lines @@
   if (this->IsStringObjectWithCharacterAt(index)) return true;
 
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
         static_cast<uint32_t>(
             Smi::cast(JSArray::cast(this)->length())->value()) :
         static_cast<uint32_t>(FixedArray::cast(elements())->length());
     return (index < length) &&
            !FixedArray::cast(elements())->get(index)->IsTheHole();
   } else {
-    return element_dictionary()->FindNumberEntry(index)
-        != Dictionary::kNotFound;
+    return element_dictionary()->FindEntry(index)
+        != NumberDictionary::kNotFound;
   }
 }
 
 
 bool JSObject::HasElementWithReceiver(JSObject* receiver, uint32_t index) {
   // Check access rights if needed.
   if (IsAccessCheckNeeded() &&
       !Top::MayIndexedAccess(this, index, v8::ACCESS_HAS)) {
     Top::ReportFailedAccessCheck(this, v8::ACCESS_HAS);
     return false;
   }
 
   // Check for lookup interceptor
   if (HasIndexedInterceptor()) {
     return HasElementWithInterceptor(receiver, index);
   }
 
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
         static_cast<uint32_t>(
             Smi::cast(JSArray::cast(this)->length())->value()) :
         static_cast<uint32_t>(FixedArray::cast(elements())->length());
     if ((index < length) &&
         !FixedArray::cast(elements())->get(index)->IsTheHole()) return true;
   } else {
-    if (element_dictionary()->FindNumberEntry(index) != Dictionary::kNotFound) {
+    if (element_dictionary()->FindEntry(index)
+        != NumberDictionary::kNotFound) {
       return true;
     }
   }
 
   // Handle [] on String objects.
   if (this->IsStringObjectWithCharacterAt(index)) return true;
 
   Object* pt = GetPrototype();
   if (pt == Heap::null_value()) return false;
   return JSObject::cast(pt)->HasElementWithReceiver(receiver, index);
@@ skipping 114 matching lines @@
 
 Object* JSObject::SetElementWithoutInterceptor(uint32_t index, Object* value) {
   // Fast case.
   if (HasFastElements()) return SetFastElement(index, value);
 
   // Dictionary case.
   ASSERT(!HasFastElements());
 
   // Insert element in the dictionary.
   FixedArray* elms = FixedArray::cast(elements());
-  Dictionary* dictionary = Dictionary::cast(elms);
+  NumberDictionary* dictionary = NumberDictionary::cast(elms);
 
-  int entry = dictionary->FindNumberEntry(index);
-  if (entry != Dictionary::kNotFound) {
+  int entry = dictionary->FindEntry(index);
+  if (entry != NumberDictionary::kNotFound) {
     Object* element = dictionary->ValueAt(entry);
     PropertyDetails details = dictionary->DetailsAt(entry);
     if (details.type() == CALLBACKS) {
       // Only accessors allowed as elements.
       FixedArray* structure = FixedArray::cast(element);
       if (structure->get(kSetterIndex)->IsJSFunction()) {
         JSFunction* setter = JSFunction::cast(structure->get(kSetterIndex));
         return SetPropertyWithDefinedSetter(setter, value);
       } else {
         Handle<Object> self(this);
@@ skipping 28 matching lines @@
     if (return_value->IsFailure()) return return_value;
   }
 
   // Attempt to put this object back in fast case.
   if (ShouldConvertToFastElements()) {
     uint32_t new_length = 0;
     if (IsJSArray()) {
       CHECK(Array::IndexFromObject(JSArray::cast(this)->length(), &new_length));
       JSArray::cast(this)->set_length(Smi::FromInt(new_length));
     } else {
-      new_length = Dictionary::cast(elements())->max_number_key() + 1;
+      new_length = NumberDictionary::cast(elements())->max_number_key() + 1;
     }
     Object* obj = Heap::AllocateFixedArrayWithHoles(new_length);
     if (obj->IsFailure()) return obj;
     SetFastElements(FixedArray::cast(obj));
 #ifdef DEBUG
     if (FLAG_trace_normalization) {
       PrintF("Object elements are fast case again:\n");
       Print();
     }
 #endif
@@ skipping 22 matching lines @@
                                             uint32_t index) {
   // Get element works for both JSObject and JSArray since
   // JSArray::length cannot change.
   if (HasFastElements()) {
     FixedArray* elms = FixedArray::cast(elements());
     if (index < static_cast<uint32_t>(elms->length())) {
       Object* value = elms->get(index);
       if (!value->IsTheHole()) return value;
     }
   } else {
-    Dictionary* dictionary = element_dictionary();
-    int entry = dictionary->FindNumberEntry(index);
-    if (entry != Dictionary::kNotFound) {
+    NumberDictionary* dictionary = element_dictionary();
+    int entry = dictionary->FindEntry(index);
+    if (entry != NumberDictionary::kNotFound) {
       Object* element = dictionary->ValueAt(entry);
       PropertyDetails details = dictionary->DetailsAt(entry);
       if (details.type() == CALLBACKS) {
         // Only accessors allowed as elements.
         FixedArray* structure = FixedArray::cast(element);
         Object* getter = structure->get(kGetterIndex);
         if (getter->IsJSFunction()) {
           return GetPropertyWithDefinedGetter(receiver,
                                               JSFunction::cast(getter));
         } else {
@@ skipping 61 matching lines @@
 
   // Get element works for both JSObject and JSArray since
   // JSArray::length cannot change.
   if (HasFastElements()) {
     FixedArray* elms = FixedArray::cast(elements());
     if (index < static_cast<uint32_t>(elms->length())) {
       Object* value = elms->get(index);
       if (!value->IsTheHole()) return value;
     }
   } else {
-    Dictionary* dictionary = element_dictionary();
-    int entry = dictionary->FindNumberEntry(index);
-    if (entry != Dictionary::kNotFound) {
+    NumberDictionary* dictionary = element_dictionary();
+    int entry = dictionary->FindEntry(index);
+    if (entry != NumberDictionary::kNotFound) {
       Object* element = dictionary->ValueAt(entry);
       PropertyDetails details = dictionary->DetailsAt(entry);
       if (details.type() == CALLBACKS) {
         // Only accessors allowed as elements.
         FixedArray* structure = FixedArray::cast(element);
         Object* getter = structure->get(kGetterIndex);
         if (getter->IsJSFunction()) {
           return GetPropertyWithDefinedGetter(receiver,
                                               JSFunction::cast(getter));
         } else {
@@ skipping 15 matching lines @@
   int capacity = 0;
   int number_of_elements = 0;
 
   if (HasFastElements()) {
     FixedArray* elms = FixedArray::cast(elements());
     capacity = elms->length();
     for (int i = 0; i < capacity; i++) {
       if (!elms->get(i)->IsTheHole()) number_of_elements++;
     }
   } else {
-    Dictionary* dictionary = Dictionary::cast(elements());
+    NumberDictionary* dictionary = NumberDictionary::cast(elements());
     capacity = dictionary->Capacity();
     number_of_elements = dictionary->NumberOfElements();
   }
 
   if (capacity == 0) return true;
   return (number_of_elements > (capacity / 2));
 }
 
 
 bool JSObject::ShouldConvertToSlowElements(int new_capacity) {
   ASSERT(HasFastElements());
   // Keep the array in fast case if the current backing storage is
   // almost filled and if the new capacity is no more than twice the
   // old capacity.
   int elements_length = FixedArray::cast(elements())->length();
   return !HasDenseElements() || ((new_capacity / 2) > elements_length);
 }
 
 
 bool JSObject::ShouldConvertToFastElements() {
   ASSERT(!HasFastElements());
-  Dictionary* dictionary = Dictionary::cast(elements());
+  NumberDictionary* dictionary = NumberDictionary::cast(elements());
   // If the elements are sparse, we should not go back to fast case.
   if (!HasDenseElements()) return false;
   // If an element has been added at a very high index in the elements
   // dictionary, we cannot go back to fast case.
   if (dictionary->requires_slow_elements()) return false;
   // An object requiring access checks is never allowed to have fast
   // elements.  If it had fast elements we would skip security checks.
   if (IsAccessCheckNeeded()) return false;
   // If the dictionary backing storage takes up roughly half as much
   // space as a fast-case backing storage would the array should have
   // fast elements.
   uint32_t length = 0;
   if (IsJSArray()) {
     CHECK(Array::IndexFromObject(JSArray::cast(this)->length(), &length));
   } else {
     length = dictionary->max_number_key();
   }
   return static_cast<uint32_t>(dictionary->Capacity()) >=
-      (length / (2 * Dictionary::kElementSize));
+      (length / (2 * NumberDictionary::kEntrySize));
 }
 
-
-void Dictionary::CopyValuesTo(FixedArray* elements) {
+template<typename Shape, typename Key>
+void Dictionary<Shape, Key>::CopyValuesTo(FixedArray* elements) {
   int pos = 0;
-  int capacity = Capacity();
+  int capacity = HashTable<Shape, Key>::Capacity();
   WriteBarrierMode mode = elements->GetWriteBarrierMode();
   for (int i = 0; i < capacity; i++) {
-    Object* k = KeyAt(i);
-    if (IsKey(k)) elements->set(pos++, ValueAt(i), mode);
+    Object* k =  Dictionary<Shape, Key>::KeyAt(i);
+    if (Dictionary<Shape, Key>::IsKey(k)) {
+      elements->set(pos++, ValueAt(i), mode);
+    }
   }
   ASSERT(pos == elements->length());
 }
 
 
 InterceptorInfo* JSObject::GetNamedInterceptor() {
   ASSERT(map()->has_named_interceptor());
   JSFunction* constructor = JSFunction::cast(map()->constructor());
   Object* template_info = constructor->shared()->function_data();
   Object* result =
@@ skipping 185 matching lines @@
   if (this->IsStringObjectWithCharacterAt(index)) return true;
 
   if (HasFastElements()) {
     uint32_t length = IsJSArray() ?
         static_cast<uint32_t>(
             Smi::cast(JSArray::cast(this)->length())->value()) :
         static_cast<uint32_t>(FixedArray::cast(elements())->length());
     return (index < length) &&
         !FixedArray::cast(elements())->get(index)->IsTheHole();
   }
-  return element_dictionary()->FindNumberEntry(index)
-      != Dictionary::kNotFound;
+  return element_dictionary()->FindEntry(index)
+      != NumberDictionary::kNotFound;
 }
 
 
 bool JSObject::HasRealNamedCallbackProperty(String* key) {
   // Check access rights if needed.
   if (IsAccessCheckNeeded() &&
       !Top::MayNamedAccess(this, key, v8::ACCESS_HAS)) {
     Top::ReportFailedAccessCheck(this, v8::ACCESS_HAS);
     return false;
   }
@@ skipping 212 matching lines @@
   return counter;
 }
 
 
 int JSObject::GetEnumElementKeys(FixedArray* storage) {
   return GetLocalElementKeys(storage,
                              static_cast<PropertyAttributes>(DONT_ENUM));
 }
 
 
-// The NumberKey uses carries the uint32_t as key.
-// This avoids allocation in HasProperty.
-class NumberKey : public HashTableKey {
- public:
-  explicit NumberKey(uint32_t number) : number_(number) { }
+bool NumberDictionaryShape::IsMatch(uint32_t key, Object* other) {
+  ASSERT(other->IsNumber());
+  return key == static_cast<uint32_t>(other->Number());
+}
 
-  bool IsMatch(Object* number) {
-    return number_ == ToUint32(number);
-  }
 
-  uint32_t Hash() { return ComputeIntegerHash(number_); }
+uint32_t NumberDictionaryShape::Hash(uint32_t key) {
+  return ComputeIntegerHash(key);
+}
 
-  HashFunction GetHashFunction() { return NumberHash; }
 
-  Object* GetObject() {
-    return Heap::NumberFromDouble(number_);
-  }
+uint32_t NumberDictionaryShape::HashForObject(uint32_t key, Object* other) {
+  ASSERT(other->IsNumber());
+  return ComputeIntegerHash(static_cast<uint32_t>(other->Number()));
+}
 
-  bool IsStringKey() { return false; }
 
- private:
-  static uint32_t NumberHash(Object* obj) {
-    return ComputeIntegerHash(ToUint32(obj));
-  }
+Object* NumberDictionaryShape::AsObject(uint32_t key) {
+  return Heap::NumberFromUint32(key);
+}
 
-  static uint32_t ToUint32(Object* obj) {
-    ASSERT(obj->IsNumber());
-    return static_cast<uint32_t>(obj->Number());
-  }
 
-  uint32_t number_;
-};
+bool StringDictionaryShape::IsMatch(String* key, Object* other) {
+  // We know that all entries in a hash table had their hash keys created.
+  // Use that knowledge to have fast failure.
+  if (key->Hash() != String::cast(other)->Hash()) return false;
+  return key->Equals(String::cast(other));
+}
+
+
+uint32_t StringDictionaryShape::Hash(String* key) {
+  return key->Hash();
+}
+
+
+uint32_t StringDictionaryShape::HashForObject(String* key, Object* other) {
+  return String::cast(other)->Hash();
+}
+
+
+Object* StringDictionaryShape::AsObject(String* key) {
+  return key;
+}
 
 
 // StringKey simply carries a string object as key.
 class StringKey : public HashTableKey {
  public:
   explicit StringKey(String* string) :
       string_(string),
-      hash_(StringHash(string)) { }
+      hash_(HashForObject(string)) { }
 
   bool IsMatch(Object* string) {
     // We know that all entries in a hash table had their hash keys created.
     // Use that knowledge to have fast failure.
-    if (hash_ != StringHash(string)) {
+    if (hash_ != HashForObject(string)) {
       return false;
     }
     return string_->Equals(String::cast(string));
   }
 
   uint32_t Hash() { return hash_; }
 
-  HashFunction GetHashFunction() { return StringHash; }
+  uint32_t HashForObject(Object* other) { return String::cast(other)->Hash(); }
 
-  Object* GetObject() { return string_; }
-
-  static uint32_t StringHash(Object* obj) {
-    return String::cast(obj)->Hash();
-  }
-
-  bool IsStringKey() { return true; }
+  Object* AsObject() { return string_; }
 
   String* string_;
   uint32_t hash_;
 };
 
 
 // StringSharedKeys are used as keys in the eval cache.
 class StringSharedKey : public HashTableKey {
  public:
   StringSharedKey(String* source, SharedFunctionInfo* shared)
       : source_(source), shared_(shared) { }
 
   bool IsMatch(Object* other) {
     if (!other->IsFixedArray()) return false;
     FixedArray* pair = FixedArray::cast(other);
     SharedFunctionInfo* shared = SharedFunctionInfo::cast(pair->get(0));
     if (shared != shared_) return false;
     String* source = String::cast(pair->get(1));
     return source->Equals(source_);
   }
 
-  typedef uint32_t (*HashFunction)(Object* obj);
-
-  virtual HashFunction GetHashFunction() { return StringSharedHash; }
-
   static uint32_t StringSharedHashHelper(String* source,
                                          SharedFunctionInfo* shared) {
     uint32_t hash = source->Hash();
     if (shared->HasSourceCode()) {
       // Instead of using the SharedFunctionInfo pointer in the hash
       // code computation, we use a combination of the hash of the
       // script source code and the start and end positions.  We do
       // this to ensure that the cache entries can survive garbage
       // collection.
       Script* script = Script::cast(shared->script());
       hash ^= String::cast(script->source())->Hash();
       hash += shared->start_position();
     }
     return hash;
   }
 
-  static uint32_t StringSharedHash(Object* obj) {
+  uint32_t Hash() {
+    return StringSharedHashHelper(source_, shared_);
+  }
+
+  uint32_t HashForObject(Object* obj) {
     FixedArray* pair = FixedArray::cast(obj);
     SharedFunctionInfo* shared = SharedFunctionInfo::cast(pair->get(0));
     String* source = String::cast(pair->get(1));
     return StringSharedHashHelper(source, shared);
   }
 
-  virtual uint32_t Hash() {
-    return StringSharedHashHelper(source_, shared_);
-  }
-
-  virtual Object* GetObject() {
+  Object* AsObject() {
     Object* obj = Heap::AllocateFixedArray(2);
     if (obj->IsFailure()) return obj;
     FixedArray* pair = FixedArray::cast(obj);
     pair->set(0, shared_);
     pair->set(1, source_);
     return pair;
   }
 
-  virtual bool IsStringKey() { return false; }
-
  private:
   String* source_;
   SharedFunctionInfo* shared_;
 };
 
 
 // RegExpKey carries the source and flags of a regular expression as key.
 class RegExpKey : public HashTableKey {
  public:
   RegExpKey(String* string, JSRegExp::Flags flags)
       : string_(string),
         flags_(Smi::FromInt(flags.value())) { }
 
   bool IsMatch(Object* obj) {
     FixedArray* val = FixedArray::cast(obj);
     return string_->Equals(String::cast(val->get(JSRegExp::kSourceIndex)))
         && (flags_ == val->get(JSRegExp::kFlagsIndex));
   }
 
   uint32_t Hash() { return RegExpHash(string_, flags_); }
 
-  HashFunction GetHashFunction() { return RegExpObjectHash; }
-
-  Object* GetObject() {
+  Object* AsObject() {
     // Plain hash maps, which is where regexp keys are used, don't
     // use this function.
     UNREACHABLE();
     return NULL;
   }
 
-  static uint32_t RegExpObjectHash(Object* obj) {
+  uint32_t HashForObject(Object* obj) {
     FixedArray* val = FixedArray::cast(obj);
     return RegExpHash(String::cast(val->get(JSRegExp::kSourceIndex)),
                       Smi::cast(val->get(JSRegExp::kFlagsIndex)));
   }
 
   static uint32_t RegExpHash(String* string, Smi* flags) {
     return string->Hash() + flags->value();
   }
 
-  bool IsStringKey() { return false; }
-
   String* string_;
   Smi* flags_;
 };
 
 // Utf8SymbolKey carries a vector of chars as key.
 class Utf8SymbolKey : public HashTableKey {
  public:
   explicit Utf8SymbolKey(Vector<const char> string)
       : string_(string), length_field_(0) { }
 
   bool IsMatch(Object* string) {
     return String::cast(string)->IsEqualTo(string_);
   }
 
-  HashFunction GetHashFunction() {
-    return StringHash;
-  }
-
   uint32_t Hash() {
     if (length_field_ != 0) return length_field_ >> String::kHashShift;
     unibrow::Utf8InputBuffer<> buffer(string_.start(),
                                       static_cast<unsigned>(string_.length()));
     chars_ = buffer.Length();
     length_field_ = String::ComputeLengthAndHashField(&buffer, chars_);
     uint32_t result = length_field_ >> String::kHashShift;
     ASSERT(result != 0);  // Ensure that the hash value of 0 is never computed.
     return result;
   }
 
-  Object* GetObject() {
+  uint32_t HashForObject(Object* other) {
+    return String::cast(other)->Hash();
+  }
+
+  Object* AsObject() {
     if (length_field_ == 0) Hash();
     return Heap::AllocateSymbol(string_, chars_, length_field_);
   }
 
-  static uint32_t StringHash(Object* obj) {
-    return String::cast(obj)->Hash();
-  }
-
-  bool IsStringKey() { return true; }
-
   Vector<const char> string_;
   uint32_t length_field_;
   int chars_;  // Caches the number of characters when computing the hash code.
 };
 
 
 // SymbolKey carries a string/symbol object as key.
 class SymbolKey : public HashTableKey {
  public:
   explicit SymbolKey(String* string) : string_(string) { }
 
-  HashFunction GetHashFunction() {
-    return StringHash;
-  }
-
   bool IsMatch(Object* string) {
     return String::cast(string)->Equals(string_);
   }
 
   uint32_t Hash() { return string_->Hash(); }
 
-  Object* GetObject() {
+  uint32_t HashForObject(Object* other) {
+    return String::cast(other)->Hash();
+  }
+
+  Object* AsObject() {
     // If the string is a cons string, attempt to flatten it so that
     // symbols will most often be flat strings.
     if (StringShape(string_).IsCons()) {
       ConsString* cons_string = ConsString::cast(string_);
       cons_string->TryFlatten();
       if (cons_string->second()->length() == 0) {
         string_ = cons_string->first();
       }
     }
     // Transform string to symbol if possible.
     Map* map = Heap::SymbolMapForString(string_);
     if (map != NULL) {
       string_->set_map(map);
       ASSERT(string_->IsSymbol());
       return string_;
     }
     // Otherwise allocate a new symbol.
     StringInputBuffer buffer(string_);
     return Heap::AllocateInternalSymbol(&buffer,
                                         string_->length(),
                                         string_->length_field());
   }
 
   static uint32_t StringHash(Object* obj) {
     return String::cast(obj)->Hash();
   }
 
-  bool IsStringKey() { return true; }
-
   String* string_;
 };
 
 
-template<int prefix_size, int element_size>
-void HashTable<prefix_size, element_size>::IteratePrefix(ObjectVisitor* v) {
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::IteratePrefix(ObjectVisitor* v) {
   IteratePointers(v, 0, kElementsStartOffset);
 }
 
 
-template<int prefix_size, int element_size>
-void HashTable<prefix_size, element_size>::IterateElements(ObjectVisitor* v) {
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::IterateElements(ObjectVisitor* v) {
   IteratePointers(v,
                   kElementsStartOffset,
                   kHeaderSize + length() * kPointerSize);
 }
 
 
-template<int prefix_size, int element_size>
-Object* HashTable<prefix_size, element_size>::Allocate(int at_least_space_for) {
+template<typename Shape, typename Key>
+Object* HashTable<Shape, Key>::Allocate(
+    int at_least_space_for) {
   int capacity = RoundUpToPowerOf2(at_least_space_for);
   if (capacity < 4) capacity = 4;  // Guarantee min capacity.
   Object* obj = Heap::AllocateHashTable(EntryToIndex(capacity));
   if (!obj->IsFailure()) {
     HashTable::cast(obj)->SetNumberOfElements(0);
     HashTable::cast(obj)->SetCapacity(capacity);
   }
   return obj;
 }
 
 
+
 // Find entry for key otherwise return -1.
-template <int prefix_size, int element_size>
-int HashTable<prefix_size, element_size>::FindEntry(HashTableKey* key) {
+template<typename Shape, typename Key>
+int HashTable<Shape, Key>::FindEntry(Key key) {
   uint32_t nof = NumberOfElements();
   if (nof == 0) return kNotFound;  // Bail out if empty.
 
   uint32_t capacity = Capacity();
-  uint32_t hash = key->Hash();
+  uint32_t hash = Shape::Hash(key);
   uint32_t entry = GetProbe(hash, 0, capacity);
 
   Object* element = KeyAt(entry);
   uint32_t passed_elements = 0;
   if (!element->IsNull()) {
-    if (!element->IsUndefined() && key->IsMatch(element)) return entry;
+    if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
     if (++passed_elements == nof) return kNotFound;
   }
   for (uint32_t i = 1; !element->IsUndefined(); i++) {
     entry = GetProbe(hash, i, capacity);
     element = KeyAt(entry);
     if (!element->IsNull()) {
-      if (!element->IsUndefined() && key->IsMatch(element)) return entry;
+      if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
       if (++passed_elements == nof) return kNotFound;
     }
   }
   return kNotFound;
 }
 
 
-template<int prefix_size, int element_size>
-Object* HashTable<prefix_size, element_size>::EnsureCapacity(
-    int n, HashTableKey* key) {
+template<typename Shape, typename Key>
+Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
   // Make sure 50% is free
   if (nof + (nof >> 1) <= capacity) return this;
 
   Object* obj = Allocate(nof * 2);
   if (obj->IsFailure()) return obj;
   HashTable* table = HashTable::cast(obj);
   WriteBarrierMode mode = table->GetWriteBarrierMode();
 
   // Copy prefix to new array.
-  for (int i = kPrefixStartIndex; i < kPrefixStartIndex + prefix_size; i++) {
+  for (int i = kPrefixStartIndex;
+       i < kPrefixStartIndex + Shape::kPrefixSize;
+       i++) {
     table->set(i, get(i), mode);
   }
   // Rehash the elements.
-  uint32_t (*Hash)(Object* key) = key->GetHashFunction();
   for (int i = 0; i < capacity; i++) {
     uint32_t from_index = EntryToIndex(i);
-    Object* key = get(from_index);
-    if (IsKey(key)) {
+    Object* k = get(from_index);
+    if (IsKey(k)) {
+      uint32_t hash = Shape::HashForObject(key, k);
       uint32_t insertion_index =
-          EntryToIndex(table->FindInsertionEntry(key, Hash(key)));
-      for (int j = 0; j < element_size; j++) {
+          EntryToIndex(table->FindInsertionEntry(hash));
+      for (int j = 0; j < Shape::kEntrySize; j++) {
         table->set(insertion_index + j, get(from_index + j), mode);
       }
     }
   }
   table->SetNumberOfElements(NumberOfElements());
   return table;
 }
 
 
-template<int prefix_size, int element_size>
-uint32_t HashTable<prefix_size, element_size>::FindInsertionEntry(
-      Object* key,
-      uint32_t hash) {
+template<typename Shape, typename Key>
+uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
   uint32_t capacity = Capacity();
   uint32_t entry = GetProbe(hash, 0, capacity);
   Object* element = KeyAt(entry);
 
   for (uint32_t i = 1; !(element->IsUndefined() || element->IsNull()); i++) {
     entry = GetProbe(hash, i, capacity);
     element = KeyAt(entry);
   }
 
   return entry;
 }
 
+// Force instantiation of template instances class
+template class HashTable<SymbolTableShape, HashTableKey*>;
 
-// Force instantiation of SymbolTable's base class
-template class HashTable<0, 1>;
+template class HashTable<CompilationCacheShape, HashTableKey*>;
+
+template class HashTable<MapCacheShape, HashTableKey*>;
+
+template class Dictionary<StringDictionaryShape, String*>;
+
+template class Dictionary<NumberDictionaryShape, uint32_t>;
 
 
-// Force instantiation of Dictionary's base class
-template class HashTable<2, 3>;
+template Object* Dictionary<NumberDictionaryShape, uint32_t>::Allocate(
+    int at_least_space_for);
 
-
-// Force instantiation of EvalCache's base class
-template class HashTable<0, 2>;
-
+template Object* Dictionary<StringDictionaryShape, String*>::Allocate(
+    int at_least_space_for);
 
 // Collates undefined and unexisting elements below limit from position
 // zero of the elements. The object stays in Dictionary mode.
 Object* JSObject::PrepareSlowElementsForSort(uint32_t limit) {
   ASSERT(!HasFastElements());
   // Must stay in dictionary mode, either because of requires_slow_elements,
   // or because we are not going to sort (and therefore compact) all of the
   // elements.
-  Dictionary* dict = element_dictionary();
+  NumberDictionary* dict = element_dictionary();
   HeapNumber* result_double = NULL;
   if (limit > static_cast<uint32_t>(Smi::kMaxValue)) {
     // Allocate space for result before we start mutating the object.
     Object* new_double = Heap::AllocateHeapNumber(0.0);
     if (new_double->IsFailure()) return new_double;
     result_double = HeapNumber::cast(new_double);
   }
 
   int capacity = dict->Capacity();
-  Object* obj = Dictionary::Allocate(dict->Capacity());
+  Object* obj = NumberDictionary::Allocate(dict->Capacity());
   if (obj->IsFailure()) return obj;
-  Dictionary* new_dict = Dictionary::cast(obj);
+  NumberDictionary* new_dict = NumberDictionary::cast(obj);
 
   AssertNoAllocation no_alloc;
 
   uint32_t pos = 0;
   uint32_t undefs = 0;
   for (int i = 0; i < capacity; i++) {
     Object* k = dict->KeyAt(i);
     if (dict->IsKey(k)) {
       ASSERT(k->IsNumber());
       ASSERT(!k->IsSmi() || Smi::cast(k)->value() >= 0);
@@ skipping 40 matching lines @@
 
 
 // Collects all defined (non-hole) and non-undefined (array) elements at
 // the start of the elements array.
 // If the object is in dictionary mode, it is converted to fast elements
 // mode.
 Object* JSObject::PrepareElementsForSort(uint32_t limit) {
   if (!HasFastElements()) {
     // Convert to fast elements containing only the existing properties.
     // Ordering is irrelevant, since we are going to sort anyway.
-    Dictionary* dict = element_dictionary();
+    NumberDictionary* dict = element_dictionary();
     if (IsJSArray() || dict->requires_slow_elements() ||
         dict->max_number_key() >= limit) {
       return PrepareSlowElementsForSort(limit);
     }
     // Convert to fast elements.
 
     PretenureFlag tenure = Heap::InNewSpace(this) ? NOT_TENURED: TENURED;
     Object* new_array =
         Heap::AllocateFixedArray(dict->NumberOfElements(), tenure);
     if (new_array->IsFailure()) {
@@ skipping 119 matching lines @@
   if (entry != kNotFound) {
     *s = KeyAt(entry);
     return this;
   }
 
   // Adding new symbol. Grow table if needed.
   Object* obj = EnsureCapacity(1, key);
   if (obj->IsFailure()) return obj;
 
   // Create symbol object.
-  Object* symbol = key->GetObject();
+  Object* symbol = key->AsObject();
   if (symbol->IsFailure()) return symbol;
 
   // If the symbol table grew as part of EnsureCapacity, obj is not
   // the current symbol table and therefore we cannot use
   // SymbolTable::cast here.
   SymbolTable* table = reinterpret_cast<SymbolTable*>(obj);
 
   // Add the new symbol and return it along with the symbol table.
-  entry = table->FindInsertionEntry(symbol, key->Hash());
+  entry = table->FindInsertionEntry(key->Hash());
   table->set(EntryToIndex(entry), symbol);
   table->ElementAdded();
   *s = symbol;
   return table;
 }
 
 
 Object* CompilationCacheTable::Lookup(String* src) {
   StringKey key(src);
   int entry = FindEntry(&key);
@@ skipping 19 matching lines @@
 }
 
 
 Object* CompilationCacheTable::Put(String* src, Object* value) {
   StringKey key(src);
   Object* obj = EnsureCapacity(1, &key);
   if (obj->IsFailure()) return obj;
 
   CompilationCacheTable* cache =
       reinterpret_cast<CompilationCacheTable*>(obj);
-  int entry = cache->FindInsertionEntry(src, key.Hash());
+  int entry = cache->FindInsertionEntry(key.Hash());
   cache->set(EntryToIndex(entry), src);
   cache->set(EntryToIndex(entry) + 1, value);
   cache->ElementAdded();
   return cache;
 }
 
 
 Object* CompilationCacheTable::PutEval(String* src,
                                        Context* context,
                                        Object* value) {
   StringSharedKey key(src, context->closure()->shared());
   Object* obj = EnsureCapacity(1, &key);
   if (obj->IsFailure()) return obj;
 
   CompilationCacheTable* cache =
       reinterpret_cast<CompilationCacheTable*>(obj);
-  int entry = cache->FindInsertionEntry(src, key.Hash());
+  int entry = cache->FindInsertionEntry(key.Hash());
 
-  Object* k = key.GetObject();
+  Object* k = key.AsObject();
   if (k->IsFailure()) return k;
 
   cache->set(EntryToIndex(entry), k);
   cache->set(EntryToIndex(entry) + 1, value);
   cache->ElementAdded();
   return cache;
 }
 
 
 Object* CompilationCacheTable::PutRegExp(String* src,
                                          JSRegExp::Flags flags,
                                          FixedArray* value) {
   RegExpKey key(src, flags);
   Object* obj = EnsureCapacity(1, &key);
   if (obj->IsFailure()) return obj;
 
   CompilationCacheTable* cache =
       reinterpret_cast<CompilationCacheTable*>(obj);
-  int entry = cache->FindInsertionEntry(value, key.Hash());
+  int entry = cache->FindInsertionEntry(key.Hash());
   cache->set(EntryToIndex(entry), value);
   cache->set(EntryToIndex(entry) + 1, value);
   cache->ElementAdded();
   return cache;
 }
 
 
 // SymbolsKey used for HashTable where key is array of symbols.
 class SymbolsKey : public HashTableKey {
  public:
   explicit SymbolsKey(FixedArray* symbols) : symbols_(symbols) { }
 
   bool IsMatch(Object* symbols) {
     FixedArray* o = FixedArray::cast(symbols);
     int len = symbols_->length();
     if (o->length() != len) return false;
     for (int i = 0; i < len; i++) {
       if (o->get(i) != symbols_->get(i)) return false;
     }
     return true;
   }
 
-  uint32_t Hash() { return SymbolsHash(symbols_); }
+  uint32_t Hash() { return HashForObject(symbols_); }
 
-  HashFunction GetHashFunction() { return SymbolsHash; }
-
-  Object* GetObject() { return symbols_; }
-
-  static uint32_t SymbolsHash(Object* obj) {
+  uint32_t HashForObject(Object* obj) {
     FixedArray* symbols = FixedArray::cast(obj);
     int len = symbols->length();
     uint32_t hash = 0;
     for (int i = 0; i < len; i++) {
       hash ^= String::cast(symbols->get(i))->Hash();
     }
     return hash;
   }
 
-  bool IsStringKey() { return false; }
+  Object* AsObject() { return symbols_; }
 
  private:
   FixedArray* symbols_;
 };
 
 
 Object* MapCache::Lookup(FixedArray* array) {
   SymbolsKey key(array);
   int entry = FindEntry(&key);
   if (entry == kNotFound) return Heap::undefined_value();
   return get(EntryToIndex(entry) + 1);
 }
 
 
 Object* MapCache::Put(FixedArray* array, Map* value) {
   SymbolsKey key(array);
   Object* obj = EnsureCapacity(1, &key);
   if (obj->IsFailure()) return obj;
 
   MapCache* cache = reinterpret_cast<MapCache*>(obj);
-  int entry = cache->FindInsertionEntry(array, key.Hash());
+  int entry = cache->FindInsertionEntry(key.Hash());
   cache->set(EntryToIndex(entry), array);
   cache->set(EntryToIndex(entry) + 1, value);
   cache->ElementAdded();
   return cache;
 }
 
 
-Object* Dictionary::Allocate(int at_least_space_for) {
-  Object* obj = DictionaryBase::Allocate(at_least_space_for);
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::Allocate(int at_least_space_for) {
+  Object* obj = HashTable<Shape, Key>::Allocate(at_least_space_for);
   // Initialize the next enumeration index.
   if (!obj->IsFailure()) {
-    Dictionary::cast(obj)->
+    Dictionary<Shape, Key>::cast(obj)->
         SetNextEnumerationIndex(PropertyDetails::kInitialIndex);
   }
   return obj;
 }
 
 
-Object* Dictionary::GenerateNewEnumerationIndices() {
-  int length = NumberOfElements();
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::GenerateNewEnumerationIndices() {
+  int length = HashTable<Shape, Key>::NumberOfElements();
 
   // Allocate and initialize iteration order array.
   Object* obj = Heap::AllocateFixedArray(length);
   if (obj->IsFailure()) return obj;
   FixedArray* iteration_order = FixedArray::cast(obj);
   for (int i = 0; i < length; i++) {
     iteration_order->set(i, Smi::FromInt(i), SKIP_WRITE_BARRIER);
   }
 
   // Allocate array with enumeration order.
   obj = Heap::AllocateFixedArray(length);
   if (obj->IsFailure()) return obj;
   FixedArray* enumeration_order = FixedArray::cast(obj);
 
   // Fill the enumeration order array with property details.
-  int capacity = Capacity();
+  int capacity = HashTable<Shape, Key>::Capacity();
   int pos = 0;
   for (int i = 0; i < capacity; i++) {
-    if (IsKey(KeyAt(i))) {
+    if (Dictionary<Shape, Key>::IsKey(Dictionary<Shape, Key>::KeyAt(i))) {
       enumeration_order->set(pos++,
                              Smi::FromInt(DetailsAt(i).index()),
                              SKIP_WRITE_BARRIER);
     }
   }
 
   // Sort the arrays wrt. enumeration order.
   iteration_order->SortPairs(enumeration_order, enumeration_order->length());
 
   // Overwrite the enumeration_order with the enumeration indices.
   for (int i = 0; i < length; i++) {
     int index = Smi::cast(iteration_order->get(i))->value();
     int enum_index = PropertyDetails::kInitialIndex + i;
     enumeration_order->set(index,
                            Smi::FromInt(enum_index),
                            SKIP_WRITE_BARRIER);
   }
 
   // Update the dictionary with new indices.
-  capacity = Capacity();
+  capacity = HashTable<Shape, Key>::Capacity();
   pos = 0;
   for (int i = 0; i < capacity; i++) {
-    if (IsKey(KeyAt(i))) {
+    if (Dictionary<Shape, Key>::IsKey(Dictionary<Shape, Key>::KeyAt(i))) {
       int enum_index = Smi::cast(enumeration_order->get(pos++))->value();
       PropertyDetails details = DetailsAt(i);
       PropertyDetails new_details =
           PropertyDetails(details.attributes(), details.type(), enum_index);
       DetailsAtPut(i, new_details);
     }
   }
 
   // Set the next enumeration index.
   SetNextEnumerationIndex(PropertyDetails::kInitialIndex+length);
   return this;
 }
 
-
-Object* Dictionary::EnsureCapacity(int n, HashTableKey* key) {
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::EnsureCapacity(int n, Key key) {
   // Check whether there are enough enumeration indices to add n elements.
-  if (key->IsStringKey() &&
+  if (Shape::kIsEnumerable &&
       !PropertyDetails::IsValidIndex(NextEnumerationIndex() + n)) {
     // If not, we generate new indices for the properties.
     Object* result = GenerateNewEnumerationIndices();
     if (result->IsFailure()) return result;
   }
-  return DictionaryBase::EnsureCapacity(n, key);
+  return HashTable<Shape, Key>::EnsureCapacity(n, key);
 }
 
 
-void Dictionary::RemoveNumberEntries(uint32_t from, uint32_t to) {
+void NumberDictionary::RemoveNumberEntries(uint32_t from, uint32_t to) {
   // Do nothing if the interval [from, to) is empty.
   if (from >= to) return;
 
   int removed_entries = 0;
   Object* sentinel = Heap::null_value();
   int capacity = Capacity();
   for (int i = 0; i < capacity; i++) {
     Object* key = KeyAt(i);
     if (key->IsNumber()) {
       uint32_t number = static_cast<uint32_t>(key->Number());
       if (from <= number && number < to) {
         SetEntry(i, sentinel, sentinel, Smi::FromInt(0));
         removed_entries++;
       }
     }
   }
 
   // Update the number of elements.
   SetNumberOfElements(NumberOfElements() - removed_entries);
 }
 
-
-Object* Dictionary::DeleteProperty(int entry, JSObject::DeleteMode mode) {
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::DeleteProperty(int entry,
+                                               JSObject::DeleteMode mode) {
   PropertyDetails details = DetailsAt(entry);
   // Ignore attributes if forcing a deletion.
   if (details.IsDontDelete() && mode == JSObject::NORMAL_DELETION) {
     return Heap::false_value();
   }
   SetEntry(entry, Heap::null_value(), Heap::null_value(), Smi::FromInt(0));
-  ElementRemoved();
+  HashTable<Shape, Key>::ElementRemoved();
   return Heap::true_value();
 }
 
 
-int Dictionary::FindStringEntry(String* key) {
-  StringKey k(key);
-  return FindEntry(&k);
-}
-
-
-int Dictionary::FindNumberEntry(uint32_t index) {
-  NumberKey k(index);
-  return FindEntry(&k);
-}
-
-
-Object* Dictionary::AtPut(HashTableKey* key, Object* value) {
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::AtPut(Key key, Object* value) {
   int entry = FindEntry(key);
 
   // If the entry is present set the value;
-  if (entry != kNotFound) {
+  if (entry != Dictionary<Shape, Key>::kNotFound) {
     ValueAtPut(entry, value);
     return this;
   }
 
   // Check whether the dictionary should be extended.
   Object* obj = EnsureCapacity(1, key);
   if (obj->IsFailure()) return obj;
-  Object* k = key->GetObject();
+
+  Object* k = Shape::AsObject(key);
   if (k->IsFailure()) return k;
   PropertyDetails details = PropertyDetails(NONE, NORMAL);
-  Dictionary::cast(obj)->AddEntry(k, value, details, key->Hash());
-  return obj;
+  return Dictionary<Shape, Key>::cast(obj)->
+      AddEntry(key, value, details, Shape::Hash(key));
 }
 
 
-Object* Dictionary::Add(HashTableKey* key, Object* value,
-                        PropertyDetails details) {
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::Add(Key key,
+                                    Object* value,
+                                    PropertyDetails details) {
+  // Valdate key is absent.
+  SLOW_ASSERT((FindEntry(key) == Dictionary<Shape, Key>::kNotFound));
   // Check whether the dictionary should be extended.
   Object* obj = EnsureCapacity(1, key);
   if (obj->IsFailure()) return obj;
-  // Compute the key object.
-  Object* k = key->GetObject();
-  if (k->IsFailure()) return k;
-  Dictionary::cast(obj)->AddEntry(k, value, details, key->Hash());
-  return obj;
+  return Dictionary<Shape, Key>::cast(obj)->
+      AddEntry(key, value, details, Shape::Hash(key));
 }
 
 
 // Add a key, value pair to the dictionary.
-void Dictionary::AddEntry(Object* key,
-                          Object* value,
-                          PropertyDetails details,
-                          uint32_t hash) {
-  uint32_t entry = FindInsertionEntry(key, hash);
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::AddEntry(Key key,
+                                         Object* value,
+                                         PropertyDetails details,
+                                         uint32_t hash) {
+  // Compute the key object.
+  Object* k = Shape::AsObject(key);
+  if (k->IsFailure()) return k;
+
+  uint32_t entry = Dictionary<Shape, Key>::FindInsertionEntry(hash);
   // Insert element at empty or deleted entry
-  if (details.index() == 0 && key->IsString()) {
+  if (details.index() == 0 && Shape::kIsEnumerable) {
     // Assign an enumeration index to the property and update
     // SetNextEnumerationIndex.
     int index = NextEnumerationIndex();
     details = PropertyDetails(details.attributes(), details.type(), index);
     SetNextEnumerationIndex(index + 1);
   }
-  SetEntry(entry, key, value, details);
-  ASSERT(KeyAt(entry)->IsNumber() || KeyAt(entry)->IsString());
-  ElementAdded();
+  SetEntry(entry, k, value, details);
+  ASSERT((Dictionary<Shape, Key>::KeyAt(entry)->IsNumber()
+          || Dictionary<Shape, Key>::KeyAt(entry)->IsString()));
+  HashTable<Shape, Key>::ElementAdded();
+  return this;
 }
 
 
-void Dictionary::UpdateMaxNumberKey(uint32_t key) {
+void NumberDictionary::UpdateMaxNumberKey(uint32_t key) {
   // If the dictionary requires slow elements an element has already
   // been added at a high index.
   if (requires_slow_elements()) return;
   // Check if this index is high enough that we should require slow
   // elements.
   if (key > kRequiresSlowElementsLimit) {
     set_requires_slow_elements();
     return;
   }
   // Update max key value.
   Object* max_index_object = get(kMaxNumberKeyIndex);
   if (!max_index_object->IsSmi() || max_number_key() < key) {
-    set(kMaxNumberKeyIndex,
-        Smi::FromInt(key << kRequiresSlowElementsTagSize),
-        SKIP_WRITE_BARRIER);
+    FixedArray::set(kMaxNumberKeyIndex,
+                    Smi::FromInt(key << kRequiresSlowElementsTagSize),
+                    SKIP_WRITE_BARRIER);
   }
 }
 
 
-Object* Dictionary::AddStringEntry(String* key,
-                                   Object* value,
-                                   PropertyDetails details) {
-  StringKey k(key);
-  SLOW_ASSERT(FindEntry(&k) == kNotFound);
-  return Add(&k, value, details);
+Object* NumberDictionary::AddNumberEntry(uint32_t key,
+                                         Object* value,
+                                         PropertyDetails details) {
+  UpdateMaxNumberKey(key);
+  SLOW_ASSERT(FindEntry(key) == kNotFound);
+  return Add(key, value, details);
 }
 
 
-Object* Dictionary::AddNumberEntry(uint32_t key,
-                                   Object* value,
-                                   PropertyDetails details) {
-  NumberKey k(key);
+Object* NumberDictionary::AtNumberPut(uint32_t key, Object* value) {
   UpdateMaxNumberKey(key);
-  SLOW_ASSERT(FindEntry(&k) == kNotFound);
-  return Add(&k, value, details);
+  return AtPut(key, value);
 }
 
 
-Object* Dictionary::AtNumberPut(uint32_t key, Object* value) {
-  NumberKey k(key);
-  UpdateMaxNumberKey(key);
-  return AtPut(&k, value);
-}
-
-
-Object* Dictionary::SetStringEntry(int entry,
-                                   String* key,
-                                   Object* value,
-                                   PropertyDetails details) {
+Object* NumberDictionary::Set(uint32_t key,
+                              Object* value,
+                              PropertyDetails details) {
+  int entry = FindEntry(key);
+  if (entry == kNotFound) return AddNumberEntry(key, value, details);
   // Preserve enumeration index.
   details = PropertyDetails(details.attributes(),
                             details.type(),
                             DetailsAt(entry).index());
-  SetEntry(entry, key, value, details);
+  SetEntry(entry, NumberDictionaryShape::AsObject(key), value, details);
   return this;
 }
 
 
-Object* Dictionary::SetOrAddNumberEntry(uint32_t key,
-                                        Object* value,
-                                        PropertyDetails details) {
-  NumberKey k(key);
-  int entry = FindEntry(&k);
-  if (entry == -1) return AddNumberEntry(key, value, details);
-  // Preserve enumeration index.
-  details = PropertyDetails(details.attributes(),
-                            details.type(),
-                            DetailsAt(entry).index());
-  SetEntry(entry, k.GetObject(), value, details);
-  return this;
-}
 
-
-int Dictionary::NumberOfElementsFilterAttributes(PropertyAttributes filter) {
-  int capacity = Capacity();
+template<typename Shape, typename Key>
+int Dictionary<Shape, Key>::NumberOfElementsFilterAttributes(
+    PropertyAttributes filter) {
+  int capacity = HashTable<Shape, Key>::Capacity();
   int result = 0;
   for (int i = 0; i < capacity; i++) {
-    Object* k = KeyAt(i);
-    if (IsKey(k)) {
+    Object* k = HashTable<Shape, Key>::KeyAt(i);
+    if (HashTable<Shape, Key>::IsKey(k)) {
       PropertyAttributes attr = DetailsAt(i).attributes();
       if ((attr & filter) == 0) result++;
     }
   }
   return result;
 }
 
 
-int Dictionary::NumberOfEnumElements() {
+template<typename Shape, typename Key>
+int Dictionary<Shape, Key>::NumberOfEnumElements() {
   return NumberOfElementsFilterAttributes(
       static_cast<PropertyAttributes>(DONT_ENUM));
 }
 
 
-void Dictionary::CopyKeysTo(FixedArray* storage, PropertyAttributes filter) {
+template<typename Shape, typename Key>
+void Dictionary<Shape, Key>::CopyKeysTo(FixedArray* storage,
+                                        PropertyAttributes filter) {
   ASSERT(storage->length() >= NumberOfEnumElements());
-  int capacity = Capacity();
+  int capacity = HashTable<Shape, Key>::Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
-     Object* k = KeyAt(i);
-     if (IsKey(k)) {
+     Object* k = HashTable<Shape, Key>::KeyAt(i);
+     if (HashTable<Shape, Key>::IsKey(k)) {
        PropertyAttributes attr = DetailsAt(i).attributes();
        if ((attr & filter) == 0) storage->set(index++, k);
      }
   }
   storage->SortPairs(storage, index);
   ASSERT(storage->length() >= index);
 }
 
 
-void Dictionary::CopyEnumKeysTo(FixedArray* storage, FixedArray* sort_array) {
+void StringDictionary::CopyEnumKeysTo(FixedArray* storage,
+                                      FixedArray* sort_array) {
   ASSERT(storage->length() >= NumberOfEnumElements());
   int capacity = Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
      Object* k = KeyAt(i);
      if (IsKey(k)) {
        PropertyDetails details = DetailsAt(i);
        if (!details.IsDontEnum()) {
          storage->set(index, k);
          sort_array->set(index,
                          Smi::FromInt(details.index()),
                          SKIP_WRITE_BARRIER);
          index++;
        }
      }
   }
   storage->SortPairs(sort_array, sort_array->length());
   ASSERT(storage->length() >= index);
 }
 
 
-void Dictionary::CopyKeysTo(FixedArray* storage) {
+template<typename Shape, typename Key>
+void Dictionary<Shape, Key>::CopyKeysTo(FixedArray* storage) {
   ASSERT(storage->length() >= NumberOfElementsFilterAttributes(
       static_cast<PropertyAttributes>(NONE)));
-  int capacity = Capacity();
+  int capacity = HashTable<Shape, Key>::Capacity();
   int index = 0;
   for (int i = 0; i < capacity; i++) {
-    Object* k = KeyAt(i);
-    if (IsKey(k)) {
+    Object* k = HashTable<Shape, Key>::KeyAt(i);
+    if (HashTable<Shape, Key>::IsKey(k)) {
       storage->set(index++, k);
     }
   }
   ASSERT(storage->length() >= index);
 }
 
 
 // Backwards lookup (slow).
-Object* Dictionary::SlowReverseLookup(Object* value) {
-  int capacity = Capacity();
+template<typename Shape, typename Key>
+Object* Dictionary<Shape, Key>::SlowReverseLookup(Object* value) {
+  int capacity = HashTable<Shape, Key>::Capacity();
   for (int i = 0; i < capacity; i++) {
-    Object* k = KeyAt(i);
-    if (IsKey(k)) {
+    Object* k =  HashTable<Shape, Key>::KeyAt(i);
+    if (Dictionary<Shape, Key>::IsKey(k)) {
       Object* e = ValueAt(i);
       if (e->IsJSGlobalPropertyCell()) {
         e = JSGlobalPropertyCell::cast(e)->value();
       }
       if (e == value) return k;
     }
   }
   return Heap::undefined_value();
 }
 
 
-Object* Dictionary::TransformPropertiesToFastFor(JSObject* obj,
-                                                 int unused_property_fields) {
+Object* StringDictionary::TransformPropertiesToFastFor(
+    JSObject* obj, int unused_property_fields) {
   // Make sure we preserve dictionary representation if there are too many
   // descriptors.
   if (NumberOfElements() > DescriptorArray::kMaxNumberOfDescriptors) return obj;
 
   // Figure out if it is necessary to generate new enumeration indices.
   int max_enumeration_index =
       NextEnumerationIndex() +
-          (DescriptorArray::kMaxNumberOfDescriptors - NumberOfElements());
+          (DescriptorArray::kMaxNumberOfDescriptors -
+           NumberOfElements());
   if (!PropertyDetails::IsValidIndex(max_enumeration_index)) {
     Object* result = GenerateNewEnumerationIndices();
     if (result->IsFailure()) return result;
   }
 
   int instance_descriptor_length = 0;
   int number_of_fields = 0;
 
   // Compute the length of the instance descriptor.
   int capacity = Capacity();
@@ skipping 328 matching lines @@
 int BreakPointInfo::GetBreakPointCount() {
   // No break point.
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
+
 } }  // namespace v8::internal