Add hash set

More memory efficient than libcxx since we do not box the values.

Change intern table to use new hash set. Clean up intern table by
removing const casts and deleting unnecessary code.

Changed the class linker to use a hash set, also added a pre-zygote
class table.

5 samples of:
adb shell stop && adb shell start && sleep 60 && adb shell dumpsys meminfo
Before:
165929 kB: Native
175859 kB: Native
168434 kB: Native
166559 kB: Native
169958 kB: Native

After:
160972 kB: Native
159439 kB: Native
157204 kB: Native
165093 kB: Native
163039 kB: Native

TODO: Add HashTable which is implemented by using a HashSet.
TODO: Use for DexFile::find_class_def_misses_.
TODO: Investigate using mem maps instead of native heap.

Bug: 17808975

Change-Id: I93e376cf6eb9628cf52f4aefdadb6157acfb799a

(cherry picked from commit e05d1d5fd86867afc7513b1c546375dba11eee50)

1 files changed, 16 insertions, 7 deletions

diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index 0bff7b9ad2..371d3f7d2c 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -20,6 +20,7 @@
 #include <unordered_set>
 
 #include "base/allocator.h"
+#include "base/hash_set.h"
 #include "base/mutex.h"
 #include "gc_root.h"
 #include "object_callbacks.h"
@@ -98,10 +99,19 @@ class InternTable {
  private:
   class StringHashEquals {
    public:
-    std::size_t operator()(const GcRoot<mirror::String>& root) NO_THREAD_SAFETY_ANALYSIS;
-    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b)
+    std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
         NO_THREAD_SAFETY_ANALYSIS;
   };
+  class GcRootEmptyFn {
+   public:
+    void MakeEmpty(GcRoot<mirror::String>& item) const {
+      item = GcRoot<mirror::String>();
+    }
+    bool IsEmpty(const GcRoot<mirror::String>& item) const {
+      return item.IsNull();
+    }
+  };
 
   // Table which holds pre zygote and post zygote interned strings. There is one instance for
   // weak interns and strong interns.
@@ -114,19 +124,17 @@ class InternTable {
     void Remove(mirror::String* s)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    void VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags)
+    void VisitRoots(RootCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SweepWeaks(IsMarkedCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SwapPostZygoteWithPreZygote() EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_) {
-      return pre_zygote_table_.size() + post_zygote_table_.size();
-    }
+    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
 
    private:
-    typedef std::unordered_set<GcRoot<mirror::String>, StringHashEquals, StringHashEquals,
+    typedef HashSet<GcRoot<mirror::String>, GcRootEmptyFn, StringHashEquals, StringHashEquals,
         TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>> UnorderedSet;
 
     void SweepWeaks(UnorderedSet* set, IsMarkedCallback* callback, void* arg)
@@ -141,6 +149,7 @@ class InternTable {
     UnorderedSet post_zygote_table_;
   };
 
+  // Insert if non null, otherwise return nullptr.
   mirror::String* Insert(mirror::String* s, bool is_strong)
       LOCKS_EXCLUDED(Locks::intern_table_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);