about summary refs log tree commit diff
path: root/absl/container/internal/hashtable_debug_hooks.h
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal/hashtable_debug_hooks.h')
-rw-r--r--absl/container/internal/hashtable_debug_hooks.h81
1 files changed, 81 insertions, 0 deletions
diff --git a/absl/container/internal/hashtable_debug_hooks.h b/absl/container/internal/hashtable_debug_hooks.h
new file mode 100644
index 000000000000..8f219726bee0
--- /dev/null
+++ b/absl/container/internal/hashtable_debug_hooks.h
@@ -0,0 +1,81 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Provides the internal API for hashtable_debug.h.
+
+#ifndef ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
+#define ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_
+
+#include <cstddef>
+
+#include <algorithm>
+#include <type_traits>
+#include <vector>
+
+namespace absl {
+namespace container_internal {
+namespace hashtable_debug_internal {
+
+// If it is a map, call get<0>().
+using std::get;
+template <typename T, typename = typename T::mapped_type>
+auto GetKey(const typename T::value_type& pair, int) -> decltype(get<0>(pair)) {
+  return get<0>(pair);
+}
+
+// If it is not a map, return the value directly.
+template <typename T>
+const typename T::key_type& GetKey(const typename T::key_type& key, char) {
+  return key;
+}
+
+// Containers should specialize this to provide debug information for that
+// container.
+template <class Container, typename Enabler = void>
+struct HashtableDebugAccess {
+  // Returns the number of probes required to find `key` in `c`.  The "number of
+  // probes" is a concept that can vary by container.  Implementations should
+  // return 0 when `key` was found in the minimum number of operations and
+  // should increment the result for each non-trivial operation required to find
+  // `key`.
+  //
+  // The default implementation uses the bucket api from the standard and thus
+  // works for `std::unordered_*` containers.
+  static size_t GetNumProbes(const Container& c,
+                             const typename Container::key_type& key) {
+    if (!c.bucket_count()) return {};
+    size_t num_probes = 0;
+    size_t bucket = c.bucket(key);
+    for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) {
+      if (it == e) return num_probes;
+      if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes;
+    }
+  }
+
+  // Returns the number of bytes requested from the allocator by the container
+  // and not freed.
+  //
+  // static size_t AllocatedByteSize(const Container& c);
+
+  // Returns a tight lower bound for AllocatedByteSize(c) where `c` is of type
+  // `Container` and `c.size()` is equal to `num_elements`.
+  //
+  // static size_t LowerBoundAllocatedByteSize(size_t num_elements);
+};
+
+}  // namespace hashtable_debug_internal
+}  // namespace container_internal
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_HASHTABLE_DEBUG_HOOKS_H_