[memory-infra] Add EstimateMemoryUsage() for deque and friends.

base/trace_event/memory_usage_estimator.h

Index: base/trace_event/memory_usage_estimator.h
diff --git a/base/trace_event/memory_usage_estimator.h b/base/trace_event/memory_usage_estimator.h
index 4f230c7b3890911c73c50d786a78514ac6ada83d..1f4132bdcb2dcf29cd0396fe7c2ac691b0e6769b 100644
--- a/base/trace_event/memory_usage_estimator.h
+++ b/base/trace_event/memory_usage_estimator.h
@@ -8,10 +8,13 @@
 #include <stdint.h>
 
 #include <array>
+#include <deque>
 #include <list>
 #include <map>
 #include <memory>
+#include <queue>
 #include <set>
+#include <stack>
 #include <string>
 #include <type_traits>
 #include <unordered_map>
@@ -132,13 +135,20 @@ size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map);
 template <class K, class V, class H, class KE, class A>
 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map);
 
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::deque<T, A>& deque);
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::queue<T, C>& queue);
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue);
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::stack<T, C>& stack);
+
 // TODO(dskiba):
 //   std::forward_list
-//   std::deque
-//   std::queue
-//   std::stack
-//   std::queue
-//   std::priority_queue
 
 // Definitions
 
@@ -197,6 +207,16 @@ struct EMUCaller<
   static size_t Call(const T& value) { return 0; }
 };
 
+// Returns reference to the underlying container of a container adapter.
+// Works for std::stack, std::queue and std::priority_queue.
+template <class A>
+const typename A::container_type& GetUnderlyingContainer(const A& adapter) {
+  struct ExposedAdapter : A {
+    using A::c;
+  };
+  return adapter.*&ExposedAdapter::c;
+}
+
 }  // namespace internal
 
 // Proxy that deducts T and calls EMUCaller<T>.
@@ -439,6 +459,74 @@ size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) {
          EstimateIterableMemoryUsage(map);
 }
 
+// std::deque
+
+template <class T, class A>
+size_t EstimateMemoryUsage(const std::deque<T, A>& deque) {
+// Since std::deque implementations are wildly different
+// (see crbug.com/674287), we can't have one "good enough"
+// way to estimate.
+
+// kBlockSize      - minimum size of a block, in bytes
+// kMinBlockLength - number of elements in a block
+//                   if sizeof(T) > kBlockSize
+#if defined(_LIBCPP_VERSION)
+  size_t kBlockSize = 4096;
+  size_t kMinBlockLength = 16;
+#elif defined(__GLIBCXX__)
+  size_t kBlockSize = 512;
+  size_t kMinBlockLength = 1;
+#elif defined(_MSC_VER)
+  size_t kBlockSize = 16;
+  size_t kMinBlockLength = 1;
+#else
+  size_t kBlockSize = 0;
+  size_t kMinBlockLength = 1;
+#endif
+
+  size_t block_length =
+      (sizeof(T) > kBlockSize) ? kMinBlockLength : kBlockSize / sizeof(T);
+
+  size_t blocks = (deque.size() + block_length - 1) / block_length;
+
+#if defined(__GLIBCXX__)
+  // libstdc++: deque always has at least one block
+  if (!blocks)
+    blocks = 1;
+#endif
+
+#if defined(_LIBCPP_VERSION)
+  // libc++: deque keeps at most two blocks when it shrinks,
+  // so even if the size is zero, deque might be holding up
+  // to 4096 * 2 bytes. One way to know whether deque has
+  // ever allocated (and hence has 1 or 2 blocks) is to check
+  // iterator's pointer. Non-zero value means that deque has
+  // at least one block.
+  if (!blocks && deque.begin().operator->())
+    blocks = 1;
+#endif
+
+  return (blocks * block_length * sizeof(T)) +
+         EstimateIterableMemoryUsage(deque);
+}
+
+// Container adapters
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::queue<T, C>& queue) {
+  return EstimateMemoryUsage(internal::GetUnderlyingContainer(queue));
+}
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue) {
+  return EstimateMemoryUsage(internal::GetUnderlyingContainer(queue));
+}
+
+template <class T, class C>
+size_t EstimateMemoryUsage(const std::stack<T, C>& stack) {
+  return EstimateMemoryUsage(internal::GetUnderlyingContainer(stack));
+}
+
 }  // namespace trace_event
 }  // namespace base