Revert r37716 due to Windows compilation errors.

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 8608 matching lines @@
     obj = LookupLocalObject(accessor_name);
     if (obj.IsNull()) {
       obj = LookupImportedObject(name);
     }
   }
   AddToResolvedNamesCache(name, obj);
   return obj.raw();
 }
 
 
-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;
+static intptr_t ResolvedNameCacheSize(const Array& cache) {
+  return (cache.Length() - 1) / 2;
+}
 
 
 // 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 {
-  ResolvedNamesMap cache(Array::Handle(resolved_names()));
-  bool present = false;
-  *obj = cache.GetOrNull(name, &present);
-  RawArray* array = cache.Release();
-  ASSERT(array == resolved_names());
-  return present;
+  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);
+    }
+  }
 }
 
 
 // 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;
   }
-  ResolvedNamesMap cache(Array::Handle(resolved_names()));
-  cache.UpdateOrInsert(name, obj);
-  StorePointer(&raw_ptr()->resolved_names_, cache.Release());
+  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();
+  }
 }
 
 
 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 {
-  const Array& cache = Array::Handle(HashTables::New<ResolvedNamesMap>(size));
-  StorePointer(&raw_ptr()->resolved_names_, cache.raw());
+  // Need space for 'size' names and 'size' resolved object entries.
+  StorePointer(&raw_ptr()->resolved_names_, NewDictionary(2 * size));
 }
 
 
 void Library::InitClassDictionary() const {
   // TODO(iposva): Find reasonable initial size.
   const int kInitialElementCount = 16;
   StorePointer(&raw_ptr()->dictionary_, NewDictionary(kInitialElementCount));
 }
 
 
@@ skipping 9801 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart