Repository: mesos Updated Branches: refs/heads/master eac75ee61 -> d5264b72d
Adds extra template parameters to hashset as well as implicit constructors from `std::set` and a initializer list constructor. These changes keep hashset up to date with the changes in hashmap. Review: https://reviews.apache.org/r/35874 Project: http://git-wip-us.apache.org/repos/asf/mesos/repo Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/d5264b72 Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/d5264b72 Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/d5264b72 Branch: refs/heads/master Commit: d5264b72de807b2c5b6ccbe5a970382718762191 Parents: eac75ee Author: Alexander Rojas <[email protected]> Authored: Wed Aug 5 20:33:16 2015 -0700 Committer: Michael Park <[email protected]> Committed: Wed Aug 5 21:57:17 2015 -0700 ---------------------------------------------------------------------- .../3rdparty/stout/include/stout/hashset.hpp | 65 +++++++++++-- .../3rdparty/stout/tests/hashset_tests.cpp | 96 ++++++++++++++++++++ 2 files changed, 152 insertions(+), 9 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/mesos/blob/d5264b72/3rdparty/libprocess/3rdparty/stout/include/stout/hashset.hpp ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/include/stout/hashset.hpp b/3rdparty/libprocess/3rdparty/stout/include/stout/hashset.hpp index 75ed9db..faae1aa 100644 --- a/3rdparty/libprocess/3rdparty/stout/include/stout/hashset.hpp +++ b/3rdparty/libprocess/3rdparty/stout/include/stout/hashset.hpp @@ -14,6 +14,9 @@ #ifndef __STOUT_HASHSET_HPP__ #define __STOUT_HASHSET_HPP__ +#include <set> +#include <utility> + #include <boost/get_pointer.hpp> #include <boost/unordered_set.hpp> @@ -25,20 +28,61 @@ // don't exist (until C++-11). Also, doing it this way allows us to // add functionality, or better naming of existing functionality, etc. -template <typename Elem> -class hashset : public boost::unordered_set<Elem> +template <typename Elem, + typename Hash = boost::hash<Elem>, + typename Equal = std::equal_to<Elem>> +class hashset : public boost::unordered_set<Elem, Hash, Equal> { public: - static const hashset<Elem>& EMPTY; + static const hashset<Elem, Hash, Equal>& EMPTY; // An explicit default constructor is needed so // 'const hashset<T> map;' is not an error. hashset() {} + // An implicit constructor for converting from a std::set. + // + // TODO(arojas): Allow any arbitrary type that supports 'begin()' + // and 'end()' passed into the specified 'emplace'? + hashset(const std::set<Elem> &set) + { + boost::unordered_set<Elem, Hash, Equal>::reserve(set.size()); + + for (auto iterator = set.begin(); iterator != set.end(); ++iterator) { + boost::unordered_set<Elem, Hash, Equal>::emplace(*iterator); + } + } + + // An implicit constructor for converting from an r-value std::set. + // + // TODO(arojas): Allow any arbitrary type that supports 'begin()' + // and 'end()' passed into the specified 'insert'? + hashset(std::set<Elem>&& set) + { + // An implementation based on the move constructor of 'hashmap' + // fails to compile on all major compilers except gcc 5.1 and up. + // See http://stackoverflow.com/q/31051466/118750?sem=2. + boost::unordered_set<Elem, Hash, Equal>::reserve(set.size()); + + for (auto iterator = set.begin(); iterator != set.end(); ++iterator) { + boost::unordered_set<Elem, Hash, Equal>::emplace(std::move(*iterator)); + } + } + + // Allow simple construction via initializer list. + hashset(std::initializer_list<Elem> list) + { + boost::unordered_set<Elem, Hash, Equal>::reserve(list.size()); + + for (auto iterator = list.begin(); iterator != list.end(); ++iterator) { + boost::unordered_set<Elem, Hash, Equal>::emplace(*iterator); + } + } + // Checks whether this map contains a binding for a key. bool contains(const Elem& elem) const { - return boost::unordered_set<Elem>::count(elem) > 0; + return boost::unordered_set<Elem, Hash, Equal>::count(elem) > 0; } // Checks whether there exists a value in this set that returns the @@ -70,17 +114,20 @@ public: // TODO(jmlvanre): Possibly remove this reference as per MESOS-2694. -template <typename Elem> -const hashset<Elem>& hashset<Elem>::EMPTY = *new hashset<Elem>(); +template <typename Elem, typename Hash, typename Equal> +const hashset<Elem, Hash, Equal>& hashset<Elem, Hash, Equal>::EMPTY = + *new hashset<Elem, Hash, Equal>(); // Union operator. -template <typename Elem> -hashset<Elem> operator | (const hashset<Elem>& left, const hashset<Elem>& right) +template <typename Elem, typename Hash, typename Equal> +hashset<Elem, Hash, Equal> operator | ( + const hashset<Elem, Hash, Equal>& left, + const hashset<Elem, Hash, Equal>& right) { // Note, we're not using 'set_union' since it affords us no benefit // in efficiency and is more complicated to use given we have sets. - hashset<Elem> result = left; + hashset<Elem, Hash, Equal> result = left; result.insert(right.begin(), right.end()); return result; } http://git-wip-us.apache.org/repos/asf/mesos/blob/d5264b72/3rdparty/libprocess/3rdparty/stout/tests/hashset_tests.cpp ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/tests/hashset_tests.cpp b/3rdparty/libprocess/3rdparty/stout/tests/hashset_tests.cpp index 2826742..341c5e0 100644 --- a/3rdparty/libprocess/3rdparty/stout/tests/hashset_tests.cpp +++ b/3rdparty/libprocess/3rdparty/stout/tests/hashset_tests.cpp @@ -13,6 +13,7 @@ */ #include <string> +#include <utility> #include <stout/hashset.hpp> @@ -23,6 +24,101 @@ using std::string; +TEST(HashsetTest, InitializerList) +{ + hashset<string> set{"hello"}; + EXPECT_EQ(1, set.size()); + + EXPECT_TRUE((hashset<int>{}.empty())); + + hashset<int> set1{1, 3, 5, 7, 11}; + EXPECT_EQ(5, set1.size()); + EXPECT_TRUE(set1.contains(1)); + EXPECT_TRUE(set1.contains(3)); + EXPECT_TRUE(set1.contains(5)); + EXPECT_TRUE(set1.contains(7)); + EXPECT_TRUE(set1.contains(11)); + + EXPECT_FALSE(set1.contains(2)); +} + + +TEST(HashsetTest, FromStdSet) +{ + std::set<int> set1{1, 3, 5, 7}; + + hashset<int> set2(set1); + + EXPECT_EQ(set1.size(), set2.size()); + EXPECT_EQ(4, set2.size()); + + foreach (const auto set1_entry, set1) { + EXPECT_TRUE(set2.contains(set1_entry)); + } +} + + +TEST(HashsetTest, FromRValueStdSet) +{ + std::set<int> set1{1, 3}; + + hashset<int> set2(std::move(set1)); + + EXPECT_EQ(2, set2.size()); + + EXPECT_TRUE(set2.contains(1)); + EXPECT_TRUE(set2.contains(3)); + + EXPECT_FALSE(set2.contains(2)); +} + + +TEST(HashsetTest, CustomHashAndEqual) +{ + struct CaseInsensitiveHash + { + size_t operator () (const string& key) const + { + size_t seed = 0; + foreach (const char c, key) { + boost::hash_combine(seed, ::tolower(c)); + } + return seed; + } + }; + + struct CaseInsensitiveEqual + { + bool operator () (const string& left, const string& right) const + { + if (left.size() != right.size()) { + return false; + } + for (size_t i = 0; i < left.size(); ++i) { + if (::tolower(left[i]) != ::tolower(right[i])) { + return false; + } + } + return true; + } + }; + + hashset<string, CaseInsensitiveHash, CaseInsensitiveEqual> set; + + set.insert("abc"); + set.insert("def"); + EXPECT_TRUE(set.contains("Abc")); + EXPECT_TRUE(set.contains("dEf")); + + EXPECT_EQ(2, set.size()); + set.insert("Abc"); + set.insert("DEF"); + EXPECT_EQ(2, set.size()); + EXPECT_TRUE(set.contains("abc")); + EXPECT_TRUE(set.contains("def")); +} + + TEST(HashsetTest, Insert) { hashset<string> hs1;
