Merge changes I2dfa0347,I951ff7a7

* changes:
  Do not blindly emplace in interner.
  Use unordered_set for interner.

src/profiling/memory/bookkeeping.h

diff --git a/src/profiling/memory/bookkeeping.h b/src/profiling/memory/bookkeeping.h
index 32166c2..1559459 100644
--- a/src/profiling/memory/bookkeeping.h
+++ b/src/profiling/memory/bookkeeping.h
@@ -17,6 +17,7 @@
 #ifndef SRC_PROFILING_MEMORY_BOOKKEEPING_H_
 #define SRC_PROFILING_MEMORY_BOOKKEEPING_H_
 
+#include <functional>
 #include <map>
 #include <string>
 #include <vector>
@@ -110,6 +111,11 @@
            std::tie(other.build_id, other.offset, other.start, other.end,
                     other.load_bias, other.path_components);
   }
+  bool operator==(const Mapping& other) const {
+    return std::tie(build_id, offset, start, end, load_bias, path_components) ==
+           std::tie(other.build_id, other.offset, other.start, other.end,
+                    other.load_bias, other.path_components);
+  }
 };
 
 struct Frame {
@@ -123,6 +129,11 @@
     return std::tie(mapping, function_name, rel_pc) <
            std::tie(other.mapping, other.function_name, other.rel_pc);
   }
+
+  bool operator==(const Frame& other) const {
+    return std::tie(mapping, function_name, rel_pc) ==
+           std::tie(other.mapping, other.function_name, other.rel_pc);
+  }
 };
 
 // Graph of function callsites. This is shared between heap dumps for
@@ -366,4 +377,35 @@
 }  // namespace profiling
 }  // namespace perfetto
 
+namespace std {
+template <>
+struct hash<::perfetto::profiling::Mapping> {
+  using argument_type = ::perfetto::profiling::Mapping;
+  using result_type = size_t;
+  result_type operator()(const argument_type& mapping) {
+    size_t h =
+        std::hash<::perfetto::profiling::InternID>{}(mapping.build_id.id());
+    h ^= std::hash<uint64_t>{}(mapping.offset);
+    h ^= std::hash<uint64_t>{}(mapping.start);
+    h ^= std::hash<uint64_t>{}(mapping.end);
+    h ^= std::hash<uint64_t>{}(mapping.load_bias);
+    for (const auto& path : mapping.path_components)
+      h ^= std::hash<uint64_t>{}(path.id());
+    return h;
+  }
+};
+
+template <>
+struct hash<::perfetto::profiling::Frame> {
+  using argument_type = ::perfetto::profiling::Frame;
+  using result_type = size_t;
+  result_type operator()(const argument_type& frame) {
+    size_t h = std::hash<::perfetto::profiling::InternID>{}(frame.mapping.id());
+    h ^= std::hash<::perfetto::profiling::InternID>{}(frame.function_name.id());
+    h ^= std::hash<uint64_t>{}(frame.rel_pc);
+    return h;
+  }
+};
+}  // namespace std
+
 #endif  // SRC_PROFILING_MEMORY_BOOKKEEPING_H_

src/profiling/memory/interner.h

diff --git a/src/profiling/memory/interner.h b/src/profiling/memory/interner.h
index e5b6ed1..e67fcb5 100644
--- a/src/profiling/memory/interner.h
+++ b/src/profiling/memory/interner.h
@@ -19,7 +19,8 @@
 
 #include <stddef.h>
 #include <stdint.h>
-#include <set>
+#include <functional>
+#include <unordered_set>
 
 #include "perfetto/base/logging.h"
 
@@ -37,6 +38,13 @@
         : data(std::forward<U...>(args...)), id(i), interner(in) {}
 
     bool operator<(const Entry& other) const { return data < other.data; }
+    bool operator==(const Entry& other) const { return data == other.data; }
+
+    struct Hash {
+      size_t operator()(const Entry& e) const noexcept {
+        return std::hash<T>{}(e.data);
+      }
+    };
 
     const T data;
     size_t ref_count = 0;
@@ -77,6 +85,10 @@
       return entry_ < other.entry_;
     }
 
+    bool operator==(const Interned& other) const {
+      return entry_ == other.entry_;
+    }
+
     const T* operator->() const { return &entry_->data; }
 
    private:
@@ -85,11 +97,17 @@
 
   template <typename... U>
   Interned Intern(U... args) {
-    auto itr_and_inserted =
-        entries_.emplace(this, next_id, std::forward<U...>(args...));
-    if (itr_and_inserted.second)
+    Entry item(this, next_id, std::forward<U...>(args...));
+    auto it = entries_.find(item);
+    if (it == entries_.cend()) {
+      // This does not invalidate pointers to entries we hold in Interned. See
+      // https://timsong-cpp.github.io/cppwp/n3337/unord.req#8
+      auto it_and_inserted = entries_.emplace(std::move(item));
       next_id++;
-    Entry& entry = const_cast<Entry&>(*itr_and_inserted.first);
+      it = it_and_inserted.first;
+      PERFETTO_DCHECK(it_and_inserted.second);
+    }
+    Entry& entry = const_cast<Entry&>(*it);
     entry.ref_count++;
     return Interned(&entry);
   }
@@ -104,7 +122,7 @@
       entries_.erase(*entry);
   }
   uint64_t next_id = 1;
-  std::set<Entry> entries_;
+  std::unordered_set<Entry, typename Entry::Hash> entries_;
   static_assert(sizeof(Interned) == sizeof(void*),
                 "interned things should be small");
 };

src/profiling/memory/interner_unittest.cc

diff --git a/src/profiling/memory/interner_unittest.cc b/src/profiling/memory/interner_unittest.cc
index dd166cb..6b239fd 100644
--- a/src/profiling/memory/interner_unittest.cc
+++ b/src/profiling/memory/interner_unittest.cc
@@ -129,25 +129,6 @@
   ASSERT_EQ(interner.entry_count_for_testing(), 0);
 }
 
-class NoCopyOrMove {
- public:
-  NoCopyOrMove(const NoCopyOrMove&) = delete;
-  NoCopyOrMove& operator=(const NoCopyOrMove&) = delete;
-  NoCopyOrMove(const NoCopyOrMove&&) = delete;
-  NoCopyOrMove& operator=(const NoCopyOrMove&&) = delete;
-  NoCopyOrMove(int d) : data(d) {}
-  ~NoCopyOrMove() {}
-  bool operator<(const NoCopyOrMove& other) const { return data < other.data; }
-
- private:
-  int data;
-};
-
-TEST(InternerStringTest, NoCopyOrMove) {
-  Interner<NoCopyOrMove> interner;
-  Interned<NoCopyOrMove> interned_str = interner.Intern(1);
-}
-
 }  // namespace
 }  // namespace profiling
 }  // namespace perfetto