Resubmit r37716: Hash tables templates, wrapping Array.

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 11 matching lines @@
 #include "vm/dart_entry.h"
 #include "vm/datastream.h"
 #include "vm/debugger.h"
 #include "vm/deopt_instructions.h"
 #include "vm/disassembler.h"
 #include "vm/double_conversion.h"
 #include "vm/exceptions.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/growable_array.h"
+#include "vm/hash_table.h"
 #include "vm/heap.h"
 #include "vm/intermediate_language.h"
 #include "vm/intrinsifier.h"
 #include "vm/object_id_ring.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/report.h"
 #include "vm/reusable_handles.h"
 #include "vm/runtime_entry.h"
 #include "vm/scopes.h"
@@ skipping 8560 matching lines @@
     obj = LookupLocalObject(accessor_name);
     if (obj.IsNull()) {
       obj = LookupImportedObject(name);
     }
   }
   AddToResolvedNamesCache(name, obj);
   return obj.raw();
 }
 
 
-static intptr_t ResolvedNameCacheSize(const Array& cache) {
-  return (cache.Length() - 1) / 2;
-}
+class StringEqualsTraits {
+ public:
+  static bool IsMatch(const Object& a, const Object& b) {
+    return String::Cast(a).Equals(String::Cast(b));
+  }
+  static uword Hash(const Object& obj) {
+    return String::Cast(obj).Hash();
+  }
+};
+typedef UnorderedHashMap<StringEqualsTraits> ResolvedNamesMap;
 
 
 // Returns true if the name is found in the cache, false no cache hit.
 // obj is set to the cached entry. It may be null, indicating that the
 // name does not resolve to anything in this library.
 bool Library::LookupResolvedNamesCache(const String& name,
                                        Object* obj) const {
-  const Array& cache = Array::Handle(resolved_names());
-  const intptr_t cache_size = ResolvedNameCacheSize(cache);
-  intptr_t index = name.Hash() % cache_size;
-  String& entry_name = String::Handle();
-  entry_name ^= cache.At(index);
-  while (!entry_name.IsNull()) {
-    if (entry_name.Equals(name)) {
-      CompilerStats::num_lib_cache_hit++;
-      *obj = cache.At(index + cache_size);
-      return true;
-    }
-    index = (index + 1) % cache_size;
-    entry_name ^= cache.At(index);
-  }
-  *obj = Object::null();
-  return false;
-}
-
-
-void Library::GrowResolvedNamesCache() const {
-  const Array& old_cache = Array::Handle(resolved_names());
-  const intptr_t old_cache_size = ResolvedNameCacheSize(old_cache);
-
-  // Create empty new cache and add entries from the old cache.
-  const intptr_t new_cache_size = old_cache_size * 3 / 2;
-  InitResolvedNamesCache(new_cache_size);
-  String& name = String::Handle();
-  Object& entry = Object::Handle();
-  for (intptr_t i = 0; i < old_cache_size; i++) {
-    name ^= old_cache.At(i);
-    if (!name.IsNull()) {
-      entry = old_cache.At(i + old_cache_size);
-      AddToResolvedNamesCache(name, entry);
-    }
-  }
+  ResolvedNamesMap cache(Array::Handle(resolved_names()));
+  bool present = false;
+  *obj = cache.GetOrNull(name, &present);
+  RawArray* array = cache.Release();
+  ASSERT(array == resolved_names());
+  return present;
 }
 
 
 // Add a name to the resolved name cache. This name resolves to the
 // given object in this library scope. obj may be null, which means
 // the name does not resolve to anything in this library scope.
 void Library::AddToResolvedNamesCache(const String& name,
                                       const Object& obj) const {
   if (!FLAG_use_lib_cache) {
     return;
   }
-  ASSERT(!Field::IsGetterName(name) && !Field::IsSetterName(name));
-  const Array& cache = Array::Handle(resolved_names());
-  // let N = cache.Length();
-  // The entry cache[N-1] is used as a counter
-  // The array entries [0..N-2] are used as cache entries.
-  //   cache[i] contains the name of the entry
-  //   cache[i+(N-1)/2] contains the resolved entity, or NULL if that name
-  //   is not present in the library.
-  const intptr_t counter_index = cache.Length() - 1;
-  intptr_t cache_size = ResolvedNameCacheSize(cache);
-  intptr_t index = name.Hash() % cache_size;
-  String& entry_name = String::Handle();
-  entry_name ^= cache.At(index);
-  // An empty spot will be found because we keep the hash set at most 75% full.
-  while (!entry_name.IsNull()) {
-    index = (index + 1) % cache_size;
-    entry_name ^= cache.At(index);
-  }
-  // Insert the object at the empty slot.
-  cache.SetAt(index, name);
-  ASSERT(cache.At(index + cache_size) == Object::null());
-  cache.SetAt(index + cache_size, obj);
-
-  // One more element added.
-  intptr_t num_used = Smi::Value(Smi::RawCast(cache.At(counter_index))) + 1;
-  cache.SetAt(counter_index, Smi::Handle(Smi::New(num_used)));
-  CompilerStats::num_names_cached++;
-
-  // Rehash if symbol_table is 75% full.
-  if (num_used > ((cache_size / 4) * 3)) {
-    CompilerStats::num_names_cached -= num_used;
-    GrowResolvedNamesCache();
-  }
+  ResolvedNamesMap cache(Array::Handle(resolved_names()));
+  cache.UpdateOrInsert(name, obj);
+  StorePointer(&raw_ptr()->resolved_names_, cache.Release());
 }
 
 
 void Library::InvalidateResolvedName(const String& name) const {
   Object& entry = Object::Handle();
   if (LookupResolvedNamesCache(name, &entry)) {
+    // TODO(koda): Support deleted sentinel in snapshots and remove only 'name'.
     InvalidateResolvedNamesCache();
   }
 }
 
 
 void Library::InvalidateResolvedNamesCache() const {
   const intptr_t kInvalidatedCacheSize = 16;
   InitResolvedNamesCache(kInvalidatedCacheSize);
 }
 
@@ skipping 496 matching lines @@
 
 static RawArray* NewDictionary(intptr_t initial_size) {
   const Array& dict = Array::Handle(Array::New(initial_size + 1, Heap::kOld));
   // The last element of the dictionary specifies the number of in use slots.
   dict.SetAt(initial_size, Smi::Handle(Smi::New(0)));
   return dict.raw();
 }
 
 
 void Library::InitResolvedNamesCache(intptr_t size) const {
-  // Need space for 'size' names and 'size' resolved object entries.
-  StorePointer(&raw_ptr()->resolved_names_, NewDictionary(2 * size));
+  const Array& cache = Array::Handle(HashTables::New<ResolvedNamesMap>(size));
+  StorePointer(&raw_ptr()->resolved_names_, cache.raw());
 }
 
 
 void Library::InitClassDictionary() const {
   // TODO(iposva): Find reasonable initial size.
   const int kInitialElementCount = 16;
   StorePointer(&raw_ptr()->dictionary_, NewDictionary(kInitialElementCount));
 }
 
 
@@ skipping 9807 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart