VM-internalize the default Map implementation.

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 936 matching lines @@
   Class& cls = Class::Handle(isolate);
   Type& type = Type::Handle(isolate);
   Array& array = Array::Handle(isolate);
   Library& lib = Library::Handle(isolate);
 
   // All RawArray fields will be initialized to an empty array, therefore
   // initialize array class first.
   cls = Class::New<Array>();
   object_store->set_array_class(cls);
 
-  // Array and ImmutableArray are the only VM classes that are parameterized.
-  // Since they are pre-finalized, CalculateFieldOffsets() is not called, so we
-  // need to set the offset of their type_arguments_ field, which is explicitly
-  // declared in RawArray.
+  // VM classes that are parameterized (Array, ImmutableArray,
+  // GrowableObjectArray, and LinkedHashMap) are also pre-finalized,
+  // so CalculateFieldOffsets() is not called, so we need to set the
+  // offset of their type_arguments_ field, which is explicitly
+  // declared in their respective Raw* classes.
   cls.set_type_arguments_field_offset(Array::type_arguments_offset());
   cls.set_num_type_arguments(1);
 
   // Set up the growable object array class (Has to be done after the array
   // class is setup as one of its field is an array object).
   cls = Class::New<GrowableObjectArray>();
   object_store->set_growable_object_array_class(cls);
   cls.set_type_arguments_field_offset(
       GrowableObjectArray::type_arguments_offset());
   cls.set_num_type_arguments(1);
@@ skipping 236 matching lines @@
   // LinkedHashMap there rather than the core library.
   lib = Library::LookupLibrary(Symbols::DartCollection());
   if (lib.IsNull()) {
     lib = Library::NewLibraryHelper(Symbols::DartCollection(), true);
     lib.SetLoadRequested();
     lib.Register();
     object_store->set_bootstrap_library(ObjectStore::kCollection, lib);
   }
   ASSERT(!lib.IsNull());
   ASSERT(lib.raw() == Library::CollectionLibrary());
-
   cls = Class::New<LinkedHashMap>();
   object_store->set_linked_hash_map_class(cls);
   cls.set_type_arguments_field_offset(LinkedHashMap::type_arguments_offset());
   cls.set_num_type_arguments(2);
   cls.set_num_own_type_arguments(2);
   RegisterPrivateClass(cls, Symbols::_LinkedHashMap(), lib);
   pending_classes.Add(cls);
 
   // Pre-register the developer library so we can place the vm class
   // UserTag there rather than the core library.
@@ skipping 9234 matching lines @@
   } else {                                                                     \
     CHECK_FINGERPRINT3(func, class_name, function_name, dest, fp);             \
   }                                                                            \
 
   all_libs.Add(&Library::ZoneHandle(Library::CoreLibrary()));
   CORE_LIB_INTRINSIC_LIST(CHECK_FINGERPRINTS);
   CORE_INTEGER_LIB_INTRINSIC_LIST(CHECK_FINGERPRINTS);
 
   all_libs.Add(&Library::ZoneHandle(Library::MathLibrary()));
   all_libs.Add(&Library::ZoneHandle(Library::TypedDataLibrary()));
+  all_libs.Add(&Library::ZoneHandle(Library::CollectionLibrary()));
   OTHER_RECOGNIZED_LIST(CHECK_FINGERPRINTS);
   INLINE_WHITE_LIST(CHECK_FINGERPRINTS);
   INLINE_BLACK_LIST(CHECK_FINGERPRINTS);
   POLYMORPHIC_TARGET_LIST(CHECK_FINGERPRINTS);
 
   all_libs.Clear();
   all_libs.Add(&Library::ZoneHandle(Library::DeveloperLibrary()));
   DEVELOPER_LIB_INTRINSIC_LIST(CHECK_FINGERPRINTS);
 
   all_libs.Clear();
@@ skipping 9036 matching lines @@
       return static_cast<uword>(
           Integer::Cast(hash_code).AsTruncatedUint32Value());
     } else {
       return 0;
     }
   }
 };
 typedef EnumIndexHashMap<DefaultHashTraits> EnumIndexDefaultMap;
 
 
-intptr_t LinkedHashMap::Length() const {
-  EnumIndexDefaultMap map(data());
-  intptr_t result = map.NumOccupied();
-  ASSERT(map.Release().raw() == data());
-  return result;
+RawLinkedHashMap* LinkedHashMap::NewDefault(Heap::Space space) {
+  // Keep this in sync with Dart implementation (lib/compact_hash.dart).

[siva, 2015/05/22 16:27:11]

I think you need to add a verification step for this see 
ClassFinalizer::VerifyImplicitFieldOffsets

I think we should also add this class into
ClassFinalizer::VerifyBootstrapClasses() to ensure InstanceSize matches the size
reported by the class.

[koda, 2015/05/26 12:22:04]

Done, as a unit test (which can be extended as more methods get C++
counterparts)
Done.

+  static const intptr_t kInitialIndexBits = 3;
+  static const intptr_t kInitialIndexSize = 1 << (kInitialIndexBits + 1);
+  const Array& data = Array::Handle(Array::New(kInitialIndexSize, space));
+  const TypedData& index = TypedData::Handle(TypedData::New(
+      kTypedDataUint32ArrayCid, kInitialIndexSize, space));
+  static const intptr_t kInitialHashMask =
+#if defined(ARCH_IS_64_BIT)
+      (1 << (32 - kInitialIndexBits)) - 1;
+#else
+      (1 << (30 - kInitialIndexBits)) - 1;
+#endif
+  return LinkedHashMap::New(data, index, kInitialHashMask, 0, 0, space);
 }
 
 
-void LinkedHashMap::InsertOrUpdate(const Object& key,
-                                     const Object& value) const {
-  ASSERT(!IsNull());
-  EnumIndexDefaultMap map(data());
-  if (!map.UpdateOrInsert(key, value)) {
-    SetModified();
-  }
-  StorePointer(&raw_ptr()->data_, map.Release().raw());
-}
-
-
-RawObject* LinkedHashMap::LookUp(const Object& key) const {
-  ASSERT(!IsNull());
-  EnumIndexDefaultMap map(data());
-  {
-    NoSafepointScope no_safepoint;
-    RawObject* result = map.GetOrNull(key);
-    ASSERT(map.Release().raw() == data());
-    return result;
-  }
-}
-
-
-bool LinkedHashMap::Contains(const Object& key) const {
-  ASSERT(!IsNull());
-  EnumIndexDefaultMap map(data());
-  bool result = map.ContainsKey(key);
-  ASSERT(map.Release().raw() == data());
-  return result;
-}
-
-
-RawObject* LinkedHashMap::Remove(const Object& key) const {
-  ASSERT(!IsNull());
-  EnumIndexDefaultMap map(data());
-  // TODO(koda): Make 'Remove' also return the old value.
-  const PassiveObject& result = PassiveObject::Handle(map.GetOrNull(key));
-  if (map.Remove(key)) {
-    SetModified();
-  }
-  StorePointer(&raw_ptr()->data_, map.Release().raw());
+RawLinkedHashMap* LinkedHashMap::New(const Array& data,
+                                     const TypedData& index,
+                                     intptr_t hash_mask,
+                                     intptr_t used_data,
+                                     intptr_t deleted_keys,
+                                     Heap::Space space) {
+  ASSERT(Isolate::Current()->object_store()->linked_hash_map_class()
+         != Class::null());
+  LinkedHashMap& result = LinkedHashMap::Handle(
+      LinkedHashMap::NewUninitialized(space));
+  result.SetData(data);
+  result.SetIndex(index);
+  result.SetHashMask(hash_mask);
+  result.SetUsedData(used_data);
+  result.SetDeletedKeys(deleted_keys);
   return result.raw();
 }
 
 
-void LinkedHashMap::Clear() const {
-  ASSERT(!IsNull());
-  if (Length() != 0) {
-    EnumIndexDefaultMap map(data());
-    map.Initialize();
-    SetModified();
-    StorePointer(&raw_ptr()->data_, map.Release().raw());
-  }
-}
-
-
-RawArray* LinkedHashMap::ToArray() const {
-  EnumIndexDefaultMap map(data());
-  const Array& result = Array::Handle(HashTables::ToArray(map, true));
-  ASSERT(map.Release().raw() == data());
-  return result.raw();
-}
-
-
-void LinkedHashMap::SetModified() const {
-  StorePointer(&raw_ptr()->cme_mark_, Instance::null());
-}
-
-
-RawInstance* LinkedHashMap::GetModificationMark(bool create) const {
-  if (create && raw_ptr()->cme_mark_ == Instance::null()) {
-    Isolate* isolate = Isolate::Current();
-    const Class& object_class =
-        Class::Handle(isolate, isolate->object_store()->object_class());
-    const Instance& current =
-        Instance::Handle(isolate, Instance::New(object_class));
-    StorePointer(&raw_ptr()->cme_mark_, current.raw());
-  }
-  return raw_ptr()->cme_mark_;
-}
-
-
-RawLinkedHashMap* LinkedHashMap::New(Heap::Space space) {
+RawLinkedHashMap* LinkedHashMap::NewUninitialized(Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->linked_hash_map_class()
          != Class::null());
-  static const intptr_t kInitialCapacity = 4;
-  const Array& data =
-      Array::Handle(HashTables::New<EnumIndexDefaultMap>(kInitialCapacity,
-                                                         space));
   LinkedHashMap& result = LinkedHashMap::Handle();
   {
     RawObject* raw = Object::Allocate(LinkedHashMap::kClassId,
                                       LinkedHashMap::InstanceSize(),
                                       space);
     NoSafepointScope no_safepoint;
     result ^= raw;
-    result.SetData(data);
-    result.SetModified();
   }
   return result.raw();
 }
 
 
 const char* LinkedHashMap::ToCString() const {
   // TODO(koda): Print key/value pairs.
   return "_LinkedHashMap";
 }
 
@@ skipping 1086 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart