container/internal/hashtable_debug_hooks.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // Provides the internal API for hashtable_debug.h.
0016
0017 #ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
0018 #define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
0019
0020 #include <cstddef>
0021
0022 #include <algorithm>
0023 #include <type_traits>
0024 #include <vector>
0025
0026 #include "absl/base/config.h"
0027
0028 namespace absl {
0029 ABSL_NAMESPACE_BEGIN
0030 namespace container_internal {
0031 namespace hashtable_debug_internal {
0032
0033 // If it is a map, call get<0>().
0034 using std::get;
0035 template <typename T, typename = typename T::mapped_type>
0036 auto GetKey(const typename T::value_type& pair, int) -> decltype(get<0>(pair)) {
0037   return get<0>(pair);
0038 }
0039
0040 // If it is not a map, return the value directly.
0041 template <typename T>
0042 const typename T::key_type& GetKey(const typename T::key_type& key, char) {
0043   return key;
0044 }
0045
0046 // Containers should specialize this to provide debug information for that
0047 // container.
0048 template <class Container, typename Enabler = void>
0049 struct HashtableDebugAccess {
0050   // Returns the number of probes required to find `key` in `c`.  The "number of
0051   // probes" is a concept that can vary by container.  Implementations should
0052   // return 0 when `key` was found in the minimum number of operations and
0053   // should increment the result for each non-trivial operation required to find
0054   // `key`.
0055   //
0056   // The default implementation uses the bucket api from the standard and thus
0057   // works for `std::unordered_*` containers.
0058   static size_t GetNumProbes(const Container& c,
0059                              const typename Container::key_type& key) {
0060     if (!c.bucket_count()) return {};
0061     size_t num_probes = 0;
0062     size_t bucket = c.bucket(key);
0063     for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) {
0064       if (it == e) return num_probes;
0065       if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes;
0066     }
0067   }
0068
0069   // Returns the number of bytes requested from the allocator by the container
0070   // and not freed.
0071   //
0072   // static size_t AllocatedByteSize(const Container& c);
0073
0074   // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type
0075   // `Container` and `c.size()` is equal to `num_elements`.
0076   //
0077   // static size_t LowerBoundAllocatedByteSize(size_t num_elements);
0078 };
0079
0080 }  // namespace hashtable_debug_internal
0081 }  // namespace container_internal
0082 ABSL_NAMESPACE_END
0083 }  // namespace absl
0084
0085 #endif  // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_