hashtable_debug_hooks.h
Go to the documentation of this file.
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 
26 namespace absl {
27 namespace container_internal {
28 namespace hashtable_debug_internal {
29 
30 // If it is a map, call get<0>().
31 using std::get;
32 template <typename T, typename = typename T::mapped_type>
33 auto 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.
38 template <typename T>
39 const 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.
45 template <class Container, typename Enabler = void>
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_
auto GetKey(const typename T::value_type &pair, int) -> decltype(get< 0 >(pair))
Definition: algorithm.h:29
std::pair< std::string, std::string > pair
static size_t GetNumProbes(const Container &c, const typename Container::key_type &key)
absl::string_view get(const Cont &c)


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:18