1 // Copyright 2016 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
6 #define BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
7
8 #include <stdint.h>
9
10 #include <array>
11 #include <concepts>
12 #include <deque>
13 #include <list>
14 #include <map>
15 #include <memory>
16 #include <queue>
17 #include <set>
18 #include <stack>
19 #include <string>
20 #include <type_traits>
21 #include <unordered_map>
22 #include <unordered_set>
23 #include <vector>
24
25 #include "base/base_export.h"
26 #include "base/containers/circular_deque.h"
27 #include "base/containers/flat_map.h"
28 #include "base/containers/flat_set.h"
29 #include "base/containers/linked_list.h"
30 #include "base/containers/lru_cache.h"
31 #include "base/containers/queue.h"
32 #include "base/memory/raw_ptr.h"
33 #include "base/stl_util.h"
34 #include "base/template_util.h"
35 #include "base/types/always_false.h"
36
37 // Composable memory usage estimators.
38 //
39 // This file defines set of EstimateMemoryUsage(object) functions that return
40 // approximate dynamically allocated memory usage of their argument.
41 //
42 // The ultimate goal is to make memory usage estimation for a class simply a
43 // matter of aggregating EstimateMemoryUsage() results over all fields.
44 //
45 // That is achieved via composability: if EstimateMemoryUsage() is defined
46 // for T then EstimateMemoryUsage() is also defined for any combination of
47 // containers holding T (e.g. std::map<int, std::vector<T>>).
48 //
49 // There are two ways of defining EstimateMemoryUsage() for a type:
50 //
51 // 1. As a global function 'size_t EstimateMemoryUsage(T)' in
52 // in base::trace_event namespace.
53 //
54 // 2. As 'size_t T::EstimateMemoryUsage() const' method. In this case
55 // EstimateMemoryUsage(T) function in base::trace_event namespace is
56 // provided automatically.
57 //
58 // Here is an example implementation:
59 //
60 // class MyClass {
61 // ...
62 // ...
63 // size_t EstimateMemoryUsage() const {
64 // return base::trace_event::EstimateMemoryUsage(set_) +
65 // base::trace_event::EstimateMemoryUsage(name_) +
66 // base::trace_event::EstimateMemoryUsage(foo_);
67 // }
68 // ...
69 // private:
70 // ...
71 // std::set<int> set_;
72 // std::string name_;
73 // Foo foo_;
74 // int id_;
75 // bool success_;
76 // }
77 //
78 // The approach is simple: first call EstimateMemoryUsage() on all members,
79 // then recursively fix compilation errors that are caused by types not
80 // implementing EstimateMemoryUsage().
81 //
82 // Note that in the above example, the memory estimates for `id_` and `success_` are
83 // intentionally omitted. This is because these members do not allocate any _dynamic_ memory.
84 // If, for example, `MyClass` is declared as a heap-allocated `unique_ptr` member in some parent
85 // class, then `EstimateMemoryUsage` on the `unique_ptr` will automatically take into account
86 // `sizeof(MyClass)`.
87
88 namespace base {
89 namespace trace_event {
90
91 // Declarations
92
93 // If T declares 'EstimateMemoryUsage() const' member function, then
94 // global function EstimateMemoryUsage(T) is available, and just calls
95 // the member function.
96 template <class T>
97 auto EstimateMemoryUsage(const T& object)
98 -> decltype(object.EstimateMemoryUsage());
99
100 // String
101
102 template <class C, class T, class A>
103 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string);
104
105 // Arrays
106
107 template <class T, size_t N>
108 size_t EstimateMemoryUsage(const std::array<T, N>& array);
109
110 template <class T, size_t N>
111 size_t EstimateMemoryUsage(T (&array)[N]);
112
113 template <class T>
114 size_t EstimateMemoryUsage(const T* array, size_t array_length);
115
116 // std::unique_ptr
117
118 template <class T, class D>
119 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr);
120
121 template <class T, class D>
122 size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array,
123 size_t array_length);
124
125 // std::shared_ptr
126
127 template <class T>
128 size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr);
129
130 // Containers
131
132 template <class F, class S>
133 size_t EstimateMemoryUsage(const std::pair<F, S>& pair);
134
135 template <class T, class A>
136 size_t EstimateMemoryUsage(const std::vector<T, A>& vector);
137
138 template <class T, class A>
139 size_t EstimateMemoryUsage(const std::list<T, A>& list);
140
141 template <class T>
142 size_t EstimateMemoryUsage(const base::LinkedList<T>& list);
143
144 template <class T, class C, class A>
145 size_t EstimateMemoryUsage(const std::set<T, C, A>& set);
146
147 template <class T, class C, class A>
148 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set);
149
150 template <class K, class V, class C, class A>
151 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map);
152
153 template <class K, class V, class C, class A>
154 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map);
155
156 template <class T, class H, class KE, class A>
157 size_t EstimateMemoryUsage(const std::unordered_set<T, H, KE, A>& set);
158
159 template <class T, class H, class KE, class A>
160 size_t EstimateMemoryUsage(const std::unordered_multiset<T, H, KE, A>& set);
161
162 template <class K, class V, class H, class KE, class A>
163 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map);
164
165 template <class K, class V, class H, class KE, class A>
166 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map);
167
168 template <class T, class A>
169 size_t EstimateMemoryUsage(const std::deque<T, A>& deque);
170
171 template <class T, class C>
172 size_t EstimateMemoryUsage(const std::queue<T, C>& queue);
173
174 template <class T, class C>
175 size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue);
176
177 template <class T, class C>
178 size_t EstimateMemoryUsage(const std::stack<T, C>& stack);
179
180 template <class T>
181 size_t EstimateMemoryUsage(const base::circular_deque<T>& deque);
182
183 template <class T, class C>
184 size_t EstimateMemoryUsage(const base::flat_set<T, C>& set);
185
186 template <class K, class V, class C>
187 size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map);
188
189 template <class K, class V, class C>
190 size_t EstimateMemoryUsage(const base::LRUCache<K, V, C>& lru);
191
192 template <class K, class V, class C>
193 size_t EstimateMemoryUsage(const base::HashingLRUCache<K, V, C>& lru);
194
195 template <class V, class C>
196 size_t EstimateMemoryUsage(const base::LRUCacheSet<V, C>& lru);
197
198 template <class V, class C>
199 size_t EstimateMemoryUsage(const base::HashingLRUCacheSet<V, C>& lru);
200
201 // TODO(dskiba):
202 // std::forward_list
203
204 // Definitions
205
206 namespace internal {
207
208 // HasEMU<T> is true iff EstimateMemoryUsage(const T&) is available.
209 template <typename T>
requires(const T & t)210 concept HasEMU = requires(const T& t) {
211 { EstimateMemoryUsage(t) } -> std::same_as<size_t>;
212 };
213
214 template <typename I>
215 using IteratorValueType = typename std::iterator_traits<I>::value_type;
216
217 template <typename I, typename InstantiatedContainer>
218 concept IsIteratorOfInstantiatedContainer =
219 (std::same_as<typename InstantiatedContainer::iterator, I> ||
220 std::same_as<typename InstantiatedContainer::const_iterator, I> ||
221 std::same_as<typename InstantiatedContainer::reverse_iterator, I> ||
222 std::same_as<typename InstantiatedContainer::const_reverse_iterator, I>);
223
224 template <typename I, template <typename...> typename Container>
225 concept IsIteratorOfContainer =
226 !std::is_pointer_v<I> &&
227 IsIteratorOfInstantiatedContainer<I, Container<IteratorValueType<I>>>;
228
229 // std::array has an extra required template argument.
230 template <typename T>
231 using array_test_helper = std::array<T, 1>;
232
233 // TODO(dyaroshev): deal with maps iterators if there is a need.
234 // It requires to parse pairs into keys and values.
235 // TODO(dyaroshev): deal with unordered containers: they do not have reverse
236 // iterators.
237 template <typename T>
238 concept IsIteratorOfStandardContainer =
239 IsIteratorOfContainer<T, array_test_helper> ||
240 IsIteratorOfContainer<T, std::vector> ||
241 IsIteratorOfContainer<T, std::deque> ||
242 IsIteratorOfContainer<T, std::list> || IsIteratorOfContainer<T, std::set> ||
243 IsIteratorOfContainer<T, std::multiset>;
244
245 template <typename T>
246 concept IsKnownNonAllocatingType =
247 std::is_trivially_destructible_v<T> || base::IsRawPtrV<T> ||
248 IsIteratorOfStandardContainer<T>;
249
250 } // namespace internal
251
252 // Estimates T's memory usage as follows:
253 // 1. Calls `EstimateMemoryUsage(T)` if it is available.
254 // 2. If `EstimateMemoryUsage(T)` is not available, but T has trivial dtor
255 // (i.e. it's POD, integer, pointer, enum, etc.) then it returns 0. This is
256 // useful for containers, which allocate memory regardless of T (also for
257 // cases like std::map<int, MyClass>).
258 // 3. Otherwise, it triggers a `static_assert` with a helpful message.
259 //
260 // To be used by `EstimateMemoryUsage()` implementations for containers.
261 template <class T>
EstimateItemMemoryUsage(const T & value)262 size_t EstimateItemMemoryUsage(const T& value) {
263 if constexpr (internal::HasEMU<T>) {
264 return EstimateMemoryUsage(value);
265 } else if constexpr (!internal::IsKnownNonAllocatingType<T>) {
266 static_assert(base::AlwaysFalse<T>,
267 "Neither global function 'size_t EstimateMemoryUsage(T)' "
268 "nor member function 'size_t T::EstimateMemoryUsage() const' "
269 "is defined for the type.");
270 }
271 return 0;
272 }
273
274 template <class I>
EstimateIterableMemoryUsage(const I & iterable)275 size_t EstimateIterableMemoryUsage(const I& iterable) {
276 size_t memory_usage = 0;
277 for (const auto& item : iterable) {
278 memory_usage += EstimateItemMemoryUsage(item);
279 }
280 return memory_usage;
281 }
282
283 // Global EstimateMemoryUsage(T) that just calls T::EstimateMemoryUsage().
284 template <class T>
285 auto EstimateMemoryUsage(const T& object)
286 -> decltype(object.EstimateMemoryUsage()) {
287 static_assert(std::same_as<decltype(object.EstimateMemoryUsage()), size_t>,
288 "'T::EstimateMemoryUsage() const' must return size_t.");
289 return object.EstimateMemoryUsage();
290 }
291
292 // String
293
294 template <class C, class T, class A>
EstimateMemoryUsage(const std::basic_string<C,T,A> & string)295 size_t EstimateMemoryUsage(const std::basic_string<C, T, A>& string) {
296 using string_type = std::basic_string<C, T, A>;
297 using value_type = typename string_type::value_type;
298 // C++11 doesn't leave much room for implementors - std::string can
299 // use short string optimization, but that's about it. We detect SSO
300 // by checking that c_str() points inside |string|.
301 const uint8_t* cstr = reinterpret_cast<const uint8_t*>(string.c_str());
302 const uint8_t* inline_cstr = reinterpret_cast<const uint8_t*>(&string);
303 if (cstr >= inline_cstr && cstr < inline_cstr + sizeof(string)) {
304 // SSO string
305 return 0;
306 }
307 return (string.capacity() + 1) * sizeof(value_type);
308 }
309
310 // Use explicit instantiations from the .cc file (reduces bloat).
311 extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::string&);
312 extern template BASE_EXPORT size_t EstimateMemoryUsage(const std::u16string&);
313
314 // Arrays
315
316 template <class T, size_t N>
EstimateMemoryUsage(const std::array<T,N> & array)317 size_t EstimateMemoryUsage(const std::array<T, N>& array) {
318 return EstimateIterableMemoryUsage(array);
319 }
320
321 template <class T, size_t N>
EstimateMemoryUsage(T (& array)[N])322 size_t EstimateMemoryUsage(T (&array)[N]) {
323 return EstimateIterableMemoryUsage(array);
324 }
325
326 template <class T>
EstimateMemoryUsage(const T * array,size_t array_length)327 size_t EstimateMemoryUsage(const T* array, size_t array_length) {
328 size_t memory_usage = sizeof(T) * array_length;
329 for (size_t i = 0; i != array_length; ++i) {
330 memory_usage += EstimateItemMemoryUsage(array[i]);
331 }
332 return memory_usage;
333 }
334
335 // std::unique_ptr
336
337 template <class T, class D>
EstimateMemoryUsage(const std::unique_ptr<T,D> & ptr)338 size_t EstimateMemoryUsage(const std::unique_ptr<T, D>& ptr) {
339 return ptr ? (sizeof(T) + EstimateItemMemoryUsage(*ptr)) : 0;
340 }
341
342 template <class T, class D>
EstimateMemoryUsage(const std::unique_ptr<T[],D> & array,size_t array_length)343 size_t EstimateMemoryUsage(const std::unique_ptr<T[], D>& array,
344 size_t array_length) {
345 return EstimateMemoryUsage(array.get(), array_length);
346 }
347
348 // std::shared_ptr
349
350 template <class T>
EstimateMemoryUsage(const std::shared_ptr<T> & ptr)351 size_t EstimateMemoryUsage(const std::shared_ptr<T>& ptr) {
352 auto use_count = ptr.use_count();
353 if (use_count == 0) {
354 return 0;
355 }
356 // Model shared_ptr after libc++,
357 // see __shared_ptr_pointer from include/memory
358 struct SharedPointer {
359 raw_ptr<void> vtbl;
360 long shared_owners;
361 long shared_weak_owners;
362 raw_ptr<T> value;
363 };
364 // If object of size S shared N > S times we prefer to (potentially)
365 // overestimate than to return 0.
366 return sizeof(SharedPointer) +
367 (EstimateItemMemoryUsage(*ptr) + (use_count - 1)) / use_count;
368 }
369
370 // std::pair
371
372 template <class F, class S>
EstimateMemoryUsage(const std::pair<F,S> & pair)373 size_t EstimateMemoryUsage(const std::pair<F, S>& pair) {
374 return EstimateItemMemoryUsage(pair.first) +
375 EstimateItemMemoryUsage(pair.second);
376 }
377
378 // std::vector
379
380 template <class T, class A>
EstimateMemoryUsage(const std::vector<T,A> & vector)381 size_t EstimateMemoryUsage(const std::vector<T, A>& vector) {
382 return sizeof(T) * vector.capacity() + EstimateIterableMemoryUsage(vector);
383 }
384
385 // std::list
386
387 template <class T, class A>
EstimateMemoryUsage(const std::list<T,A> & list)388 size_t EstimateMemoryUsage(const std::list<T, A>& list) {
389 using value_type = typename std::list<T, A>::value_type;
390 struct Node {
391 raw_ptr<Node> prev;
392 raw_ptr<Node> next;
393 value_type value;
394 };
395 return sizeof(Node) * list.size() +
396 EstimateIterableMemoryUsage(list);
397 }
398
399 template <class T>
EstimateMemoryUsage(const base::LinkedList<T> & list)400 size_t EstimateMemoryUsage(const base::LinkedList<T>& list) {
401 size_t memory_usage = 0u;
402 for (base::LinkNode<T>* node = list.head(); node != list.end();
403 node = node->next()) {
404 // Since we increment by calling node = node->next() we know that node
405 // isn't nullptr.
406 memory_usage += EstimateMemoryUsage(*node->value()) + sizeof(T);
407 }
408 return memory_usage;
409 }
410
411 // Tree containers
412
413 template <class V>
EstimateTreeMemoryUsage(size_t size)414 size_t EstimateTreeMemoryUsage(size_t size) {
415 // Tree containers are modeled after libc++
416 // (__tree_node from include/__tree)
417 struct Node {
418 raw_ptr<Node> left;
419 raw_ptr<Node> right;
420 raw_ptr<Node> parent;
421 bool is_black;
422 V value;
423 };
424 return sizeof(Node) * size;
425 }
426
427 template <class T, class C, class A>
EstimateMemoryUsage(const std::set<T,C,A> & set)428 size_t EstimateMemoryUsage(const std::set<T, C, A>& set) {
429 using value_type = typename std::set<T, C, A>::value_type;
430 return EstimateTreeMemoryUsage<value_type>(set.size()) +
431 EstimateIterableMemoryUsage(set);
432 }
433
434 template <class T, class C, class A>
EstimateMemoryUsage(const std::multiset<T,C,A> & set)435 size_t EstimateMemoryUsage(const std::multiset<T, C, A>& set) {
436 using value_type = typename std::multiset<T, C, A>::value_type;
437 return EstimateTreeMemoryUsage<value_type>(set.size()) +
438 EstimateIterableMemoryUsage(set);
439 }
440
441 template <class K, class V, class C, class A>
EstimateMemoryUsage(const std::map<K,V,C,A> & map)442 size_t EstimateMemoryUsage(const std::map<K, V, C, A>& map) {
443 using value_type = typename std::map<K, V, C, A>::value_type;
444 return EstimateTreeMemoryUsage<value_type>(map.size()) +
445 EstimateIterableMemoryUsage(map);
446 }
447
448 template <class K, class V, class C, class A>
EstimateMemoryUsage(const std::multimap<K,V,C,A> & map)449 size_t EstimateMemoryUsage(const std::multimap<K, V, C, A>& map) {
450 using value_type = typename std::multimap<K, V, C, A>::value_type;
451 return EstimateTreeMemoryUsage<value_type>(map.size()) +
452 EstimateIterableMemoryUsage(map);
453 }
454
455 // HashMap containers
456
457 namespace internal {
458
459 // While hashtable containers model doesn't depend on STL implementation, one
460 // detail still crept in: bucket_count. It's used in size estimation, but its
461 // value after inserting N items is not predictable.
462 // This function is specialized by unittests to return constant value, thus
463 // excluding bucket_count from testing.
464 template <class V>
HashMapBucketCountForTesting(size_t bucket_count)465 size_t HashMapBucketCountForTesting(size_t bucket_count) {
466 return bucket_count;
467 }
468
469 template <class LruCacheType>
DoEstimateMemoryUsageForLruCache(const LruCacheType & lru_cache)470 size_t DoEstimateMemoryUsageForLruCache(const LruCacheType& lru_cache) {
471 return EstimateMemoryUsage(lru_cache.ordering_) +
472 EstimateMemoryUsage(lru_cache.index_);
473 }
474
475 } // namespace internal
476
477 template <class V>
EstimateHashMapMemoryUsage(size_t bucket_count,size_t size)478 size_t EstimateHashMapMemoryUsage(size_t bucket_count, size_t size) {
479 // Hashtable containers are modeled after libc++
480 // (__hash_node from include/__hash_table)
481 struct Node {
482 raw_ptr<void> next;
483 size_t hash;
484 V value;
485 };
486 using Bucket = void*;
487 bucket_count = internal::HashMapBucketCountForTesting<V>(bucket_count);
488 return sizeof(Bucket) * bucket_count + sizeof(Node) * size;
489 }
490
491 template <class K, class H, class KE, class A>
EstimateMemoryUsage(const std::unordered_set<K,H,KE,A> & set)492 size_t EstimateMemoryUsage(const std::unordered_set<K, H, KE, A>& set) {
493 using value_type = typename std::unordered_set<K, H, KE, A>::value_type;
494 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
495 set.size()) +
496 EstimateIterableMemoryUsage(set);
497 }
498
499 template <class K, class H, class KE, class A>
EstimateMemoryUsage(const std::unordered_multiset<K,H,KE,A> & set)500 size_t EstimateMemoryUsage(const std::unordered_multiset<K, H, KE, A>& set) {
501 using value_type = typename std::unordered_multiset<K, H, KE, A>::value_type;
502 return EstimateHashMapMemoryUsage<value_type>(set.bucket_count(),
503 set.size()) +
504 EstimateIterableMemoryUsage(set);
505 }
506
507 template <class K, class V, class H, class KE, class A>
EstimateMemoryUsage(const std::unordered_map<K,V,H,KE,A> & map)508 size_t EstimateMemoryUsage(const std::unordered_map<K, V, H, KE, A>& map) {
509 using value_type = typename std::unordered_map<K, V, H, KE, A>::value_type;
510 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
511 map.size()) +
512 EstimateIterableMemoryUsage(map);
513 }
514
515 template <class K, class V, class H, class KE, class A>
EstimateMemoryUsage(const std::unordered_multimap<K,V,H,KE,A> & map)516 size_t EstimateMemoryUsage(const std::unordered_multimap<K, V, H, KE, A>& map) {
517 using value_type =
518 typename std::unordered_multimap<K, V, H, KE, A>::value_type;
519 return EstimateHashMapMemoryUsage<value_type>(map.bucket_count(),
520 map.size()) +
521 EstimateIterableMemoryUsage(map);
522 }
523
524 // std::deque
525
526 template <class T, class A>
EstimateMemoryUsage(const std::deque<T,A> & deque)527 size_t EstimateMemoryUsage(const std::deque<T, A>& deque) {
528 // Since std::deque implementations are wildly different
529 // (see crbug.com/674287), we can't have one "good enough"
530 // way to estimate.
531
532 // kBlockSize - minimum size of a block, in bytes
533 // kMinBlockLength - number of elements in a block
534 // if sizeof(T) > kBlockSize
535 #if defined(_LIBCPP_VERSION)
536 size_t kBlockSize = 4096;
537 size_t kMinBlockLength = 16;
538 #elif defined(__GLIBCXX__)
539 size_t kBlockSize = 512;
540 size_t kMinBlockLength = 1;
541 #elif defined(_MSC_VER)
542 size_t kBlockSize = 16;
543 size_t kMinBlockLength = 1;
544 #else
545 size_t kBlockSize = 0;
546 size_t kMinBlockLength = 1;
547 #endif
548
549 size_t block_length =
550 (sizeof(T) > kBlockSize) ? kMinBlockLength : kBlockSize / sizeof(T);
551
552 size_t blocks = (deque.size() + block_length - 1) / block_length;
553
554 #if defined(__GLIBCXX__)
555 // libstdc++: deque always has at least one block
556 if (!blocks)
557 blocks = 1;
558 #endif
559
560 #if defined(_LIBCPP_VERSION)
561 // libc++: deque keeps at most two blocks when it shrinks,
562 // so even if the size is zero, deque might be holding up
563 // to 4096 * 2 bytes. One way to know whether deque has
564 // ever allocated (and hence has 1 or 2 blocks) is to check
565 // iterator's pointer. Non-zero value means that deque has
566 // at least one block.
567 if (!blocks && deque.begin().operator->())
568 blocks = 1;
569 #endif
570
571 return (blocks * block_length * sizeof(T)) +
572 EstimateIterableMemoryUsage(deque);
573 }
574
575 // Container adapters
576
577 template <class T, class C>
EstimateMemoryUsage(const std::queue<T,C> & queue)578 size_t EstimateMemoryUsage(const std::queue<T, C>& queue) {
579 return EstimateMemoryUsage(GetUnderlyingContainer(queue));
580 }
581
582 template <class T, class C>
EstimateMemoryUsage(const std::priority_queue<T,C> & queue)583 size_t EstimateMemoryUsage(const std::priority_queue<T, C>& queue) {
584 return EstimateMemoryUsage(GetUnderlyingContainer(queue));
585 }
586
587 template <class T, class C>
EstimateMemoryUsage(const std::stack<T,C> & stack)588 size_t EstimateMemoryUsage(const std::stack<T, C>& stack) {
589 return EstimateMemoryUsage(GetUnderlyingContainer(stack));
590 }
591
592 // base::circular_deque
593
594 template <class T>
EstimateMemoryUsage(const base::circular_deque<T> & deque)595 size_t EstimateMemoryUsage(const base::circular_deque<T>& deque) {
596 return sizeof(T) * deque.capacity() + EstimateIterableMemoryUsage(deque);
597 }
598
599 // Flat containers
600
601 template <class T, class C>
EstimateMemoryUsage(const base::flat_set<T,C> & set)602 size_t EstimateMemoryUsage(const base::flat_set<T, C>& set) {
603 using value_type = typename base::flat_set<T, C>::value_type;
604 return sizeof(value_type) * set.capacity() + EstimateIterableMemoryUsage(set);
605 }
606
607 template <class K, class V, class C>
EstimateMemoryUsage(const base::flat_map<K,V,C> & map)608 size_t EstimateMemoryUsage(const base::flat_map<K, V, C>& map) {
609 using value_type = typename base::flat_map<K, V, C>::value_type;
610 return sizeof(value_type) * map.capacity() + EstimateIterableMemoryUsage(map);
611 }
612
613 template <class K, class V, class C>
EstimateMemoryUsage(const LRUCache<K,V,C> & lru_cache)614 size_t EstimateMemoryUsage(const LRUCache<K, V, C>& lru_cache) {
615 return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
616 }
617
618 template <class K, class V, class C>
EstimateMemoryUsage(const HashingLRUCache<K,V,C> & lru_cache)619 size_t EstimateMemoryUsage(const HashingLRUCache<K, V, C>& lru_cache) {
620 return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
621 }
622
623 template <class V, class C>
EstimateMemoryUsage(const LRUCacheSet<V,C> & lru_cache)624 size_t EstimateMemoryUsage(const LRUCacheSet<V, C>& lru_cache) {
625 return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
626 }
627
628 template <class V, class C>
EstimateMemoryUsage(const HashingLRUCacheSet<V,C> & lru_cache)629 size_t EstimateMemoryUsage(const HashingLRUCacheSet<V, C>& lru_cache) {
630 return internal::DoEstimateMemoryUsageForLruCache(lru_cache);
631 }
632
633 } // namespace trace_event
634 } // namespace base
635
636 #endif // BASE_TRACE_EVENT_MEMORY_USAGE_ESTIMATOR_H_
637