legacy-libs/grpc-cloned/deps/grpc/third_party/abseil-cpp/absl/container/internal/hashtable_debug_hooks.h

   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>
  46 struct 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_