1// Copyright 2018 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Provides the internal API for hashtable_debug.h.
16
17#ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
18#define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
19
20#include <cstddef>
21
22#include <algorithm>
23#include <type_traits>
24#include <vector>
25
26namespace absl {
27namespace container_internal {
28namespace hashtable_debug_internal {
29
30// If it is a map, call get<0>().
31using std::get;
32template <typename T, typename = typename T::mapped_type>
33auto GetKey(const typename T::value_type& pair, int) -> decltype(get<0>(pair)) {
34 return get<0>(pair);
35}
36
37// If it is not a map, return the value directly.
38template <typename T>
39const typename T::key_type& GetKey(const typename T::key_type& key, char) {
40 return key;
41}
42
43// Containers should specialize this to provide debug information for that
44// container.
45template <class Container, typename Enabler = void>
46struct HashtableDebugAccess {
47 // Returns the number of probes required to find `key` in `c`. The "number of
48 // probes" is a concept that can vary by container. Implementations should
49 // return 0 when `key` was found in the minimum number of operations and
50 // should increment the result for each non-trivial operation required to find
51 // `key`.
52 //
53 // The default implementation uses the bucket api from the standard and thus
54 // works for `std::unordered_*` containers.
55 static size_t GetNumProbes(const Container& c,
56 const typename Container::key_type& key) {
57 if (!c.bucket_count()) return {};
58 size_t num_probes = 0;
59 size_t bucket = c.bucket(key);
60 for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) {
61 if (it == e) return num_probes;
62 if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes;
63 }
64 }
65
66 // Returns the number of bytes requested from the allocator by the container
67 // and not freed.
68 //
69 // static size_t AllocatedByteSize(const Container& c);
70
71 // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type
72 // `Container` and `c.size()` is equal to `num_elements`.
73 //
74 // static size_t LowerBoundAllocatedByteSize(size_t num_elements);
75};
76
77} // namespace hashtable_debug_internal
78} // namespace container_internal
79} // namespace absl
80
81#endif // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
82