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

base/trace_event/memory_usage_estimator.h

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
 #define BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
 
 #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>
 #include <unordered_set>
 #include <vector>
 
 #include "base/base_export.h"
 #include "base/strings/string16.h"
 #include "base/template_util.h"
 
@@ skipping 100 matching lines @@
 
 template <class T, class H, class KE, class A>
 size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set);
 
 template <class K, class V, class H, class KE, class A>
 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
 
 namespace internal {
 
 // HasEMU<T>::value is true iff EstimateMemoryUsage(T) is available.
 // (This is the default version, which is false.)
 template <class T, class X = void>
 struct HasEMU : std::false_type {};
 
@@ skipping 38 matching lines @@
 };
 
 template <class T>
 struct EMUCaller<
     T,
     typename std::enable_if<!HasEMU<T>::value &&
                             is_trivially_destructible<T>::value>::type> {
   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>.
 // To be used by EstimateMemoryUsage() implementations for containers.
 template <class T>
 size_t EstimateItemMemoryUsage(const T& value) {
   return internal::EMUCaller<T>::Call(value);
 }
 
 template <class I>
@@ skipping 222 matching lines @@
 
 template <class K, class V, class H, class KE, class A>
 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) {
   using value_type =
       typename std::unordered_multimap<K, V, H, KE, A>::value_type;
   return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
                                                 map.size()) +
          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
 
 #endif  // BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_