hashtable_debug_hooks.h (2976B)
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 #include "absl/base/config.h" 27 28 namespace absl { 29 ABSL_NAMESPACE_BEGIN 30 namespace container_internal { 31 namespace hashtable_debug_internal { 32 33 // If it is a map, call get<0>(). 34 using std::get; 35 template <typename T, typename = typename T::mapped_type> 36 auto GetKey(const typename T::value_type& pair, int) -> decltype(get<0>(pair)) { 37 return get<0>(pair); 38 } 39 40 // If it is not a map, return the value directly. 41 template <typename T> 42 const typename T::key_type& GetKey(const typename T::key_type& key, char) { 43 return key; 44 } 45 46 // Containers should specialize this to provide debug information for that 47 // container. 48 template <class Container, typename Enabler = void> 49 struct HashtableDebugAccess { 50 // Returns the number of probes required to find `key` in `c`. The "number of 51 // probes" is a concept that can vary by container. Implementations should 52 // return 0 when `key` was found in the minimum number of operations and 53 // should increment the result for each non-trivial operation required to find 54 // `key`. 55 // 56 // The default implementation uses the bucket api from the standard and thus 57 // works for `std::unordered_*` containers. 58 static size_t GetNumProbes(const Container& c, 59 const typename Container::key_type& key) { 60 if (!c.bucket_count()) return {}; 61 size_t num_probes = 0; 62 size_t bucket = c.bucket(key); 63 for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) { 64 if (it == e) return num_probes; 65 if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes; 66 } 67 } 68 69 // Returns the number of bytes requested from the allocator by the container 70 // and not freed. 71 // 72 // static size_t AllocatedByteSize(const Container& c); 73 74 // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type 75 // `Container` and `c.size()` is equal to `num_elements`. 76 // 77 // static size_t LowerBoundAllocatedByteSize(size_t num_elements); 78 }; 79 80 } // namespace hashtable_debug_internal 81 } // namespace container_internal 82 ABSL_NAMESPACE_END 83 } // namespace absl 84 85 #endif // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_