Merge "ART: Use arena allocator with HashSet/HashMap."

5 files changed, 172 insertions, 63 deletions

diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index ab42bc5b27..fc27a2b446 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -63,6 +63,7 @@ class StackMapStream : public ValueObject {
       : allocator_(allocator),
         stack_maps_(allocator->Adapter(kArenaAllocStackMapStream)),
         location_catalog_entries_(allocator->Adapter(kArenaAllocStackMapStream)),
+        location_catalog_entries_indices_(allocator->Adapter(kArenaAllocStackMapStream)),
         dex_register_locations_(allocator->Adapter(kArenaAllocStackMapStream)),
         inline_infos_(allocator->Adapter(kArenaAllocStackMapStream)),
         stack_mask_max_(-1),
@@ -173,8 +174,10 @@ class StackMapStream : public ValueObject {
   ArenaVector<DexRegisterLocation> location_catalog_entries_;
   // Map from Dex register location catalog entries to their indices in the
   // location catalog.
-  typedef HashMap<DexRegisterLocation, size_t, LocationCatalogEntriesIndicesEmptyFn,
-                  DexRegisterLocationHashFn> LocationCatalogEntriesIndices;
+  using LocationCatalogEntriesIndices = ArenaHashMap<DexRegisterLocation,
+                                                     size_t,
+                                                     LocationCatalogEntriesIndicesEmptyFn,
+                                                     DexRegisterLocationHashFn>;
   LocationCatalogEntriesIndices location_catalog_entries_indices_;
 
   // A set of concatenated maps of Dex register locations indices to `location_catalog_entries_`.
diff --git a/runtime/base/arena_containers.h b/runtime/base/arena_containers.h
index 66b52896a4..9174d2d6d9 100644
--- a/runtime/base/arena_containers.h
+++ b/runtime/base/arena_containers.h
@@ -20,9 +20,12 @@
 #include <deque>
 #include <queue>
 #include <set>
+#include <utility>
 
 #include "arena_allocator.h"
 #include "base/dchecked_vector.h"
+#include "hash_map.h"
+#include "hash_set.h"
 #include "safe_map.h"
 
 namespace art {
@@ -57,6 +60,24 @@ template <typename K, typename V, typename Comparator = std::less<K>>
 using ArenaSafeMap =
     SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
 
+template <typename T,
+          typename EmptyFn = DefaultEmptyFn<T>,
+          typename HashFn = std::hash<T>,
+          typename Pred = std::equal_to<T>>
+using ArenaHashSet = HashSet<T, EmptyFn, HashFn, Pred, ArenaAllocatorAdapter<T>>;
+
+template <typename Key,
+          typename Value,
+          typename EmptyFn = DefaultEmptyFn<std::pair<Key, Value>>,
+          typename HashFn = std::hash<Key>,
+          typename Pred = std::equal_to<Key>>
+using ArenaHashMap = HashMap<Key,
+                             Value,
+                             EmptyFn,
+                             HashFn,
+                             Pred,
+                             ArenaAllocatorAdapter<std::pair<Key, Value>>>;
+
 // Implementation details below.
 
 template <bool kCount>
@@ -164,11 +185,13 @@ class ArenaAllocatorAdapter : private ArenaAllocatorAdapterKind {
     arena_allocator_->MakeInaccessible(p, sizeof(T) * n);
   }
 
-  void construct(pointer p, const_reference val) {
-    new (static_cast<void*>(p)) value_type(val);
+  template <typename U, typename... Args>
+  void construct(U* p, Args&&... args) {
+    ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
   }
-  void destroy(pointer p) {
-    p->~value_type();
+  template <typename U>
+  void destroy(U* p) {
+    p->~U();
   }
 
  private:
diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h
index eab80ff19f..b18d586f3a 100644
--- a/runtime/base/hash_map.h
+++ b/runtime/base/hash_map.h
@@ -51,8 +51,22 @@ class HashMapWrapper {
 template <class Key, class Value, class EmptyFn,
     class HashFn = std::hash<Key>, class Pred = std::equal_to<Key>,
     class Alloc = std::allocator<std::pair<Key, Value>>>
-class HashMap : public HashSet<std::pair<Key, Value>, EmptyFn, HashMapWrapper<HashFn>,
-                               HashMapWrapper<Pred>, Alloc> {
+class HashMap : public HashSet<std::pair<Key, Value>,
+                               EmptyFn,
+                               HashMapWrapper<HashFn>,
+                               HashMapWrapper<Pred>,
+                               Alloc> {
+ private:
+  using Base = HashSet<std::pair<Key, Value>,
+                       EmptyFn,
+                       HashMapWrapper<HashFn>,
+                       HashMapWrapper<Pred>,
+                       Alloc>;
+
+ public:
+  HashMap() : Base() { }
+  explicit HashMap(const Alloc& alloc)
+      : Base(alloc) { }
 };
 
 }  // namespace art
diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h
index d110fe30b7..f2b1cc06d7 100644
--- a/runtime/base/hash_set.h
+++ b/runtime/base/hash_set.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_BASE_HASH_SET_H_
 
 #include <functional>
+#include <iterator>
 #include <memory>
 #include <stdint.h>
 #include <utility>
@@ -45,7 +46,7 @@ class DefaultEmptyFn<T*> {
   void MakeEmpty(T*& item) const {
     item = nullptr;
   }
-  bool IsEmpty(const T*& item) const {
+  bool IsEmpty(T* const& item) const {
     return item == nullptr;
   }
 };
@@ -59,7 +60,7 @@ template <class T, class EmptyFn = DefaultEmptyFn<T>, class HashFn = std::hash<T
     class Pred = std::equal_to<T>, class Alloc = std::allocator<T>>
 class HashSet {
   template <class Elem, class HashSetType>
-  class BaseIterator {
+  class BaseIterator : std::iterator<std::forward_iterator_tag, Elem> {
    public:
     BaseIterator(const BaseIterator&) = default;
     BaseIterator(BaseIterator&&) = default;
@@ -82,7 +83,7 @@ class HashSet {
     }
 
     BaseIterator operator++(int) {
-      Iterator temp = *this;
+      BaseIterator temp = *this;
       this->index_ = this->NextNonEmptySlot(this->index_, hash_set_);
       return temp;
     }
@@ -96,7 +97,7 @@ class HashSet {
       return &**this;
     }
 
-    // TODO: Operator -- --(int)
+    // TODO: Operator -- --(int)  (and use std::bidirectional_iterator_tag)
 
    private:
     size_t index_;
@@ -115,34 +116,87 @@ class HashSet {
   };
 
  public:
+  using value_type = T;
+  using allocator_type = Alloc;
+  using reference = T&;
+  using const_reference = const T&;
+  using pointer = T*;
+  using const_pointer = const T*;
+  using iterator = BaseIterator<T, HashSet>;
+  using const_iterator = BaseIterator<const T, const HashSet>;
+  using size_type = size_t;
+  using difference_type = ptrdiff_t;
+
   static constexpr double kDefaultMinLoadFactor = 0.5;
   static constexpr double kDefaultMaxLoadFactor = 0.9;
   static constexpr size_t kMinBuckets = 1000;
 
-  typedef BaseIterator<T, HashSet> Iterator;
-  typedef BaseIterator<const T, const HashSet> ConstIterator;
-
   // If we don't own the data, this will create a new array which owns the data.
   void Clear() {
     DeallocateStorage();
-    AllocateStorage(1);
     num_elements_ = 0;
     elements_until_expand_ = 0;
   }
 
-  HashSet() : num_elements_(0), num_buckets_(0), owns_data_(false), data_(nullptr),
-      min_load_factor_(kDefaultMinLoadFactor), max_load_factor_(kDefaultMaxLoadFactor) {
-    Clear();
-  }
-
-  HashSet(const HashSet& other) : num_elements_(0), num_buckets_(0), owns_data_(false),
-      data_(nullptr) {
-    *this = other;
+  HashSet()
+      : num_elements_(0u),
+        num_buckets_(0u),
+        elements_until_expand_(0u),
+        owns_data_(false),
+        data_(nullptr),
+        min_load_factor_(kDefaultMinLoadFactor),
+        max_load_factor_(kDefaultMaxLoadFactor) {
+  }
+
+  explicit HashSet(const allocator_type& alloc)
+      : allocfn_(alloc),
+        hashfn_(),
+        emptyfn_(),
+        pred_(),
+        num_elements_(0u),
+        num_buckets_(0u),
+        elements_until_expand_(0u),
+        owns_data_(false),
+        data_(nullptr),
+        min_load_factor_(kDefaultMinLoadFactor),
+        max_load_factor_(kDefaultMaxLoadFactor) {
+  }
+
+  HashSet(const HashSet& other)
+      : allocfn_(other.allocfn_),
+        hashfn_(other.hashfn_),
+        emptyfn_(other.emptyfn_),
+        pred_(other.pred_),
+        num_elements_(other.num_elements_),
+        num_buckets_(0),
+        elements_until_expand_(other.elements_until_expand_),
+        owns_data_(false),
+        data_(nullptr),
+        min_load_factor_(other.min_load_factor_),
+        max_load_factor_(other.max_load_factor_) {
+    AllocateStorage(other.NumBuckets());
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      ElementForIndex(i) = other.data_[i];
+    }
   }
 
-  HashSet(HashSet&& other) : num_elements_(0), num_buckets_(0), owns_data_(false),
-      data_(nullptr) {
-    *this = std::move(other);
+  HashSet(HashSet&& other)
+      : allocfn_(std::move(other.allocfn_)),
+        hashfn_(std::move(other.hashfn_)),
+        emptyfn_(std::move(other.emptyfn_)),
+        pred_(std::move(other.pred_)),
+        num_elements_(other.num_elements_),
+        num_buckets_(other.num_buckets_),
+        elements_until_expand_(other.elements_until_expand_),
+        owns_data_(other.owns_data_),
+        data_(other.data_),
+        min_load_factor_(other.min_load_factor_),
+        max_load_factor_(other.max_load_factor_) {
+    other.num_elements_ = 0u;
+    other.num_buckets_ = 0u;
+    other.elements_until_expand_ = 0u;
+    other.owns_data_ = false;
+    other.data_ = nullptr;
   }
 
   // Construct from existing data.
@@ -199,32 +253,18 @@ class HashSet {
   }
 
   HashSet& operator=(HashSet&& other) {
-    std::swap(data_, other.data_);
-    std::swap(num_buckets_, other.num_buckets_);
-    std::swap(num_elements_, other.num_elements_);
-    std::swap(elements_until_expand_, other.elements_until_expand_);
-    std::swap(min_load_factor_, other.min_load_factor_);
-    std::swap(max_load_factor_, other.max_load_factor_);
-    std::swap(owns_data_, other.owns_data_);
+    HashSet(std::move(other)).swap(*this);
     return *this;
   }
 
   HashSet& operator=(const HashSet& other) {
-    DeallocateStorage();
-    AllocateStorage(other.NumBuckets());
-    for (size_t i = 0; i < num_buckets_; ++i) {
-      ElementForIndex(i) = other.data_[i];
-    }
-    num_elements_ = other.num_elements_;
-    elements_until_expand_ = other.elements_until_expand_;
-    min_load_factor_ = other.min_load_factor_;
-    max_load_factor_ = other.max_load_factor_;
+    HashSet(other).swap(*this);  // NOLINT(runtime/explicit) - a case of lint gone mad.
     return *this;
   }
 
   // Lower case for c++11 for each.
-  Iterator begin() {
-    Iterator ret(this, 0);
+  iterator begin() {
+    iterator ret(this, 0);
     if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) {
       ++ret;  // Skip all the empty slots.
     }
@@ -232,8 +272,8 @@ class HashSet {
   }
 
   // Lower case for c++11 for each. const version.
-  ConstIterator begin() const {
-    ConstIterator ret(this, 0);
+  const_iterator begin() const {
+    const_iterator ret(this, 0);
     if (num_buckets_ != 0 && IsFreeSlot(ret.index_)) {
       ++ret;  // Skip all the empty slots.
     }
@@ -241,13 +281,13 @@ class HashSet {
   }
 
   // Lower case for c++11 for each.
-  Iterator end() {
-    return Iterator(this, NumBuckets());
+  iterator end() {
+    return iterator(this, NumBuckets());
   }
 
   // Lower case for c++11 for each. const version.
-  ConstIterator end() const {
-    return ConstIterator(this, NumBuckets());
+  const_iterator end() const {
+    return const_iterator(this, NumBuckets());
   }
 
   bool Empty() {
@@ -262,7 +302,7 @@ class HashSet {
   // and set the empty slot to be the location we just moved from.
   // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an
   // element to its actual location/index.
-  Iterator Erase(Iterator it) {
+  iterator Erase(iterator it) {
     // empty_index is the index that will become empty.
     size_t empty_index = it.index_;
     DCHECK(!IsFreeSlot(empty_index));
@@ -313,23 +353,23 @@ class HashSet {
   // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy
   // object in the heap for performance solution.
   template <typename K>
-  Iterator Find(const K& key) {
+  iterator Find(const K& key) {
     return FindWithHash(key, hashfn_(key));
   }
 
   template <typename K>
-  ConstIterator Find(const K& key) const {
+  const_iterator Find(const K& key) const {
     return FindWithHash(key, hashfn_(key));
   }
 
   template <typename K>
-  Iterator FindWithHash(const K& key, size_t hash) {
-    return Iterator(this, FindIndex(key, hash));
+  iterator FindWithHash(const K& key, size_t hash) {
+    return iterator(this, FindIndex(key, hash));
   }
 
   template <typename K>
-  ConstIterator FindWithHash(const K& key, size_t hash) const {
-    return ConstIterator(this, FindIndex(key, hash));
+  const_iterator FindWithHash(const K& key, size_t hash) const {
+    return const_iterator(this, FindIndex(key, hash));
   }
 
   // Insert an element, allows duplicates.
@@ -352,6 +392,26 @@ class HashSet {
     return num_elements_;
   }
 
+  void swap(HashSet& other) {
+    // Use argument-dependent lookup with fall-back to std::swap() for function objects.
+    using std::swap;
+    swap(allocfn_, other.allocfn_);
+    swap(hashfn_, other.hashfn_);
+    swap(emptyfn_, other.emptyfn_);
+    swap(pred_, other.pred_);
+    std::swap(data_, other.data_);
+    std::swap(num_buckets_, other.num_buckets_);
+    std::swap(num_elements_, other.num_elements_);
+    std::swap(elements_until_expand_, other.elements_until_expand_);
+    std::swap(min_load_factor_, other.min_load_factor_);
+    std::swap(max_load_factor_, other.max_load_factor_);
+    std::swap(owns_data_, other.owns_data_);
+  }
+
+  allocator_type get_allocator() const {
+    return allocfn_;
+  }
+
   void ShrinkToMaximumLoad() {
     Resize(Size() / max_load_factor_);
   }
@@ -429,7 +489,7 @@ class HashSet {
   }
 
   // Find the hash table slot for an element, or return NumBuckets() if not found.
-  // This value for not found is important so that Iterator(this, FindIndex(...)) == end().
+  // This value for not found is important so that iterator(this, FindIndex(...)) == end().
   template <typename K>
   size_t FindIndex(const K& element, size_t hash) const {
     // Guard against failing to get an element for a non-existing index.
@@ -560,6 +620,12 @@ class HashSet {
   double max_load_factor_;
 };
 
+template <class T, class EmptyFn, class HashFn, class Pred, class Alloc>
+void swap(HashSet<T, EmptyFn, HashFn, Pred, Alloc>& lhs,
+          HashSet<T, EmptyFn, HashFn, Pred, Alloc>& rhs) {
+  lhs.swap(rhs);
+}
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_BASE_HASH_SET_H_
diff --git a/runtime/base/scoped_arena_containers.h b/runtime/base/scoped_arena_containers.h
index 380ed118d2..7c64449dd9 100644
--- a/runtime/base/scoped_arena_containers.h
+++ b/runtime/base/scoped_arena_containers.h
@@ -21,6 +21,7 @@
 #include <queue>
 #include <set>
 #include <unordered_map>
+#include <utility>
 
 #include "arena_containers.h"  // For ArenaAllocatorAdapterKind.
 #include "base/dchecked_vector.h"
@@ -157,13 +158,15 @@ class ScopedArenaAllocatorAdapter
     arena_stack_->MakeInaccessible(p, sizeof(T) * n);
   }
 
-  void construct(pointer p, const_reference val) {
+  template <typename U, typename... Args>
+  void construct(U* p, Args&&... args) {
     // Don't CheckTop(), allow reusing existing capacity of a vector/deque below the top.
-    new (static_cast<void*>(p)) value_type(val);
+    ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
   }
-  void destroy(pointer p) {
+  template <typename U>
+  void destroy(U* p) {
     // Don't CheckTop(), allow reusing existing capacity of a vector/deque below the top.
-    p->~value_type();
+    p->~U();
   }
 
  private: