summaryrefslogtreecommitdiffstats
path: root/base/containers
diff options
context:
space:
mode:
authordavidben <davidben@chromium.org>2014-10-24 13:19:55 -0700
committerCommit bot <commit-bot@chromium.org>2014-10-24 20:20:18 +0000
commit44d2e5c45975ab36f29035552521e41ae512c8bf (patch)
tree2bd17cfaaa7cb74c36759f81659404f7fc4d075d /base/containers
parent09ac0842aa0603f504d8877b015dc3d04a0b928f (diff)
downloadchromium_src-44d2e5c45975ab36f29035552521e41ae512c8bf.zip
chromium_src-44d2e5c45975ab36f29035552521e41ae512c8bf.tar.gz
chromium_src-44d2e5c45975ab36f29035552521e41ae512c8bf.tar.bz2
Align base::hash_map with C++11, part 2.
MSVC's stdext::hash_map, unlike C++11's std::unordered_map and GCC's __gnu_cxx::hash_map, requires a total order on the key. It also has a very different syntax for supplying a default hash function. Switch MSVC to std::unordered_map, but exposed as base::hash_map. This aligns both the container and the default hash function. The default hash function now differs from our GCC one in that const char * is no longer hashed as a C string. To align GCC with C++11 semantics and the MSVC ones this CL introduces, also provide a new hash function and swap the default hash with it. This new function is identical to __gnu_cxx::hash, but it does not specialize const char* and does specialize T* (which was already aligned by https://codereview.chromium.org/630503002/). Note: This CL changes a file in mojo/ and will need to be mirrored in the mojo repository before the next sync. BUG=420242 Review URL: https://codereview.chromium.org/623383002 Cr-Commit-Position: refs/heads/master@{#301185}
Diffstat (limited to 'base/containers')
-rw-r--r--base/containers/hash_tables.h123
-rw-r--r--base/containers/hash_tables_unittest.cc14
-rw-r--r--base/containers/small_map_unittest.cc5
3 files changed, 104 insertions, 38 deletions
diff --git a/base/containers/hash_tables.h b/base/containers/hash_tables.h
index c803ace..6bf029e 100644
--- a/base/containers/hash_tables.h
+++ b/base/containers/hash_tables.h
@@ -28,17 +28,14 @@
#include "build/build_config.h"
#if defined(COMPILER_MSVC)
-#include <hash_map>
-#include <hash_set>
+#include <unordered_map>
+#include <unordered_set>
-#define BASE_HASH_NAMESPACE stdext
+#define BASE_HASH_NAMESPACE std
#elif defined(COMPILER_GCC)
-#if defined(OS_ANDROID)
-#define BASE_HASH_NAMESPACE std
-#else
-#define BASE_HASH_NAMESPACE __gnu_cxx
-#endif
+
+#define BASE_HASH_NAMESPACE base_hash
// This is a hack to disable the gcc 4.4 warning about hash_map and hash_set
// being deprecated. We can get rid of this when we upgrade to VS2008 and we
@@ -51,9 +48,11 @@
#if defined(OS_ANDROID)
#include <hash_map>
#include <hash_set>
+#define BASE_HASH_IMPL_NAMESPACE std
#else
#include <ext/hash_map>
#include <ext/hash_set>
+#define BASE_HASH_IMPL_NAMESPACE __gnu_cxx
#endif
#include <string>
@@ -65,6 +64,26 @@
namespace BASE_HASH_NAMESPACE {
+// The pre-standard hash behaves like C++11's std::hash, except around pointers.
+// const char* is specialized to hash the C string and hash functions for
+// general T* are missing. Define a BASE_HASH_NAMESPACE::hash which aligns with
+// the C++11 behavior.
+
+template<typename T>
+struct hash {
+ std::size_t operator()(const T& value) const {
+ return BASE_HASH_IMPL_NAMESPACE::hash<T>()(value);
+ }
+};
+
+template<typename T>
+struct hash<T*> {
+ std::size_t operator()(T* value) const {
+ return BASE_HASH_IMPL_NAMESPACE::hash<uintptr_t>()(
+ reinterpret_cast<uintptr_t>(value));
+ }
+};
+
#if !defined(OS_ANDROID)
// The GNU C++ library provides identity hash functions for many integral types,
// but not for |long long|. This hash function will truncate if |size_t| is
@@ -85,17 +104,6 @@ DEFINE_TRIVIAL_HASH(unsigned long long);
#undef DEFINE_TRIVIAL_HASH
#endif // !defined(OS_ANDROID)
-// To align with C++11's std::hash and MSVC's pre-standard stdext::hash_value,
-// provide a default hash function for raw pointers. Note: const char * is still
-// specialized to hash as a C string. This is consistent with the currently used
-// stdext::hash_value, but not C++11.
-template<typename T>
-struct hash<T*> {
- std::size_t operator()(T* value) const {
- return hash<uintptr_t>()(reinterpret_cast<uintptr_t>(value));
- }
-};
-
// Implement string hash functions so that strings of various flavors can
// be used as keys in STL maps and sets. The hash algorithm comes from the
// GNU C++ library, in <tr1/functional>. It is duplicated here because GCC
@@ -125,10 +133,67 @@ DEFINE_STRING_HASH(base::string16);
#endif // COMPILER
namespace base {
-using BASE_HASH_NAMESPACE::hash_map;
-using BASE_HASH_NAMESPACE::hash_multimap;
-using BASE_HASH_NAMESPACE::hash_multiset;
-using BASE_HASH_NAMESPACE::hash_set;
+
+// On MSVC, use the C++11 containers.
+#if defined(COMPILER_MSVC)
+
+template<class Key, class T,
+ class Hash = std::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T>>>
+using hash_map = std::unordered_map<Key, T, Hash, Pred, Alloc>;
+
+template<class Key, class T,
+ class Hash = std::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T>>>
+using hash_multimap = std::unordered_multimap<Key, T, Hash, Pred, Alloc>;
+
+template<class Key,
+ class Hash = std::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<Key>>
+using hash_multiset = std::unordered_multiset<Key, Hash, Pred, Alloc>;
+
+template<class Key,
+ class Hash = std::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<Key>>
+using hash_set = std::unordered_set<Key, Hash, Pred, Alloc>;
+
+#else // !COMPILER_MSVC
+
+// Otherwise, use the pre-standard ones, but override the default hash to match
+// C++11.
+template<class Key, class T,
+ class Hash = BASE_HASH_NAMESPACE::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T>>>
+using hash_map = BASE_HASH_IMPL_NAMESPACE::hash_map<Key, T, Hash, Pred, Alloc>;
+
+template<class Key, class T,
+ class Hash = BASE_HASH_NAMESPACE::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<std::pair<const Key, T>>>
+using hash_multimap =
+ BASE_HASH_IMPL_NAMESPACE::hash_multimap<Key, T, Hash, Pred, Alloc>;
+
+template<class Key,
+ class Hash = BASE_HASH_NAMESPACE::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<Key>>
+using hash_multiset =
+ BASE_HASH_IMPL_NAMESPACE::hash_multiset<Key, Hash, Pred, Alloc>;
+
+template<class Key,
+ class Hash = BASE_HASH_NAMESPACE::hash<Key>,
+ class Pred = std::equal_to<Key>,
+ class Alloc = std::allocator<Key>>
+using hash_set = BASE_HASH_IMPL_NAMESPACE::hash_set<Key, Hash, Pred, Alloc>;
+
+#undef BASE_HASH_IMPL_NAMESPACE
+
+#endif // COMPILER_MSVC
// Implement hashing for pairs of at-most 32 bit integer values.
// When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using
@@ -248,14 +313,6 @@ namespace BASE_HASH_NAMESPACE {
// Implement methods for hashing a pair of integers, so they can be used as
// keys in STL containers.
-#if defined(COMPILER_MSVC)
-
-template<typename Type1, typename Type2>
-inline std::size_t hash_value(const std::pair<Type1, Type2>& value) {
- return base::HashPair(value.first, value.second);
-}
-
-#elif defined(COMPILER_GCC)
template<typename Type1, typename Type2>
struct hash<std::pair<Type1, Type2> > {
std::size_t operator()(std::pair<Type1, Type2> value) const {
@@ -263,10 +320,6 @@ struct hash<std::pair<Type1, Type2> > {
}
};
-#else
-#error define hash<std::pair<Type1, Type2> > for your compiler
-#endif // COMPILER
-
}
#undef DEFINE_PAIR_HASH_FUNCTION_START
diff --git a/base/containers/hash_tables_unittest.cc b/base/containers/hash_tables_unittest.cc
index 65724ec..60fbeaa 100644
--- a/base/containers/hash_tables_unittest.cc
+++ b/base/containers/hash_tables_unittest.cc
@@ -4,6 +4,8 @@
#include "base/containers/hash_tables.h"
+#include <string>
+
#include "base/basictypes.h"
#include "testing/gtest/include/gtest/gtest.h"
@@ -50,4 +52,16 @@ TEST_F(HashPairTest, IntegerPairs) {
(GG_INT64_C(1) << 60) + GG_INT64_C(78931732321));
}
+// Verify that base::hash_set<const char*> compares by pointer value, not as C
+// strings.
+TEST(HashTableTest, CharPointers) {
+ std::string str1("hello");
+ std::string str2("hello");
+ base::hash_set<const char*> set;
+
+ set.insert(str1.c_str());
+ EXPECT_EQ(1u, set.count(str1.c_str()));
+ EXPECT_EQ(0u, set.count(str2.c_str()));
+}
+
} // namespace
diff --git a/base/containers/small_map_unittest.cc b/base/containers/small_map_unittest.cc
index bc76e37..f87a8f0 100644
--- a/base/containers/small_map_unittest.cc
+++ b/base/containers/small_map_unittest.cc
@@ -414,9 +414,8 @@ namespace {
class hash_map_add_item : public hash_map<int, int> {
public:
- hash_map_add_item() : hash_map<int, int>() {}
- explicit hash_map_add_item(const std::pair<int, int>& item)
- : hash_map<int, int>() {
+ hash_map_add_item() {}
+ explicit hash_map_add_item(const std::pair<int, int>& item) {
insert(item);
}
};
generated by cgit v1.1 at 2025-03-11 01:11:11 +0000