aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2011-01-22 23:56:08 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2011-01-22 23:56:08 +0000
commit62a3e9ef98827094e0daa27418c4a08677ba1458 (patch)
tree2c40236b20fe26376523e0ce35658513f621ce66
parentc05f56916407d1730903472718fed9576bd214c9 (diff)
downloadpaludis-62a3e9ef98827094e0daa27418c4a08677ba1458.tar.gz
paludis-62a3e9ef98827094e0daa27418c4a08677ba1458.tar.xz
Support hashing tuples
-rw-r--r--.gitignore1
-rw-r--r--paludis/util/files.m42
-rw-r--r--paludis/util/hashes.hh40
-rw-r--r--paludis/util/hashes_TEST.cc51
4 files changed, 92 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore
index ace91fc..fd5a3ae 100644
--- a/.gitignore
+++ b/.gitignore
@@ -456,6 +456,7 @@ paludis-*.*.*.tar.bz2
/paludis/util/fs_path_TEST
/paludis/util/fs_stat_TEST
/paludis/util/graph_TEST
+/paludis/util/hashes_TEST
/paludis/util/indirect_iterator_TEST
/paludis/util/is_file_with_extension_TEST
/paludis/util/iterator_funcs_TEST
diff --git a/paludis/util/files.m4 b/paludis/util/files.m4
index e7aca68..c84ff36 100644
--- a/paludis/util/files.m4
+++ b/paludis/util/files.m4
@@ -43,7 +43,7 @@ add(`fs_error', `hh', `cc')
add(`fs_path', `hh', `cc', `fwd', `se', `test', `testscript')
add(`fs_stat', `hh', `cc', `fwd', `test', `testscript')
add(`graph', `hh', `cc', `fwd', `impl', `test')
-add(`hashes', `hh', `cc')
+add(`hashes', `hh', `cc', `test')
add(`iterator_funcs', `hh', `test')
add(`indirect_iterator', `hh', `fwd', `impl', `test')
add(`is_file_with_extension', `hh', `cc', `se', `test', `testscript')
diff --git a/paludis/util/hashes.hh b/paludis/util/hashes.hh
index c776819..5d74eed 100644
--- a/paludis/util/hashes.hh
+++ b/paludis/util/hashes.hh
@@ -1,7 +1,7 @@
/* vim: set sw=4 sts=4 et foldmethod=syntax : */
/*
- * Copyright (c) 2008, 2010 Ciaran McCreesh
+ * Copyright (c) 2008, 2010, 2011 Ciaran McCreesh
*
* This file is part of the Paludis package manager. Paludis is free software;
* you can redistribute it and/or modify it under the terms of the GNU General
@@ -24,6 +24,7 @@
#include <paludis/util/wrapped_value-fwd.hh>
#include <paludis/util/fs_path-fwd.hh>
#include <cstddef>
+#include <tuple>
#include <utility>
#include <string>
#include <type_traits>
@@ -83,6 +84,43 @@ namespace paludis
}
};
+ template <unsigned n_, typename... Keys_>
+ std::size_t single_tuple_hash(const std::tuple<Keys_...> & p)
+ {
+ return Hash<typename std::tuple_element<n_, std::tuple<Keys_...> >::type>()(std::get<n_>(p));
+ }
+
+ struct FinishedHashingTuple
+ {
+ };
+
+ struct NotFinishedHashingTuple
+ {
+ };
+
+ template <unsigned n_, typename... Keys_>
+ std::size_t accumulate_tuple_hash(const std::tuple<Keys_...> &, std::size_t v, const FinishedHashingTuple &)
+ {
+ return v;
+ }
+
+ template <unsigned n_, typename... Keys_>
+ std::size_t accumulate_tuple_hash(const std::tuple<Keys_...> & p, std::size_t v, const NotFinishedHashingTuple &)
+ {
+ return accumulate_tuple_hash<n_ + 1, Keys_...>(p, (v << 8) ^ single_tuple_hash<n_>(p),
+ typename std::conditional<std::tuple_size<std::tuple<Keys_...> >::value == n_ + 1,
+ FinishedHashingTuple, NotFinishedHashingTuple>::type());
+ }
+
+ template <typename... Keys_>
+ struct Hash<std::tuple<Keys_...> >
+ {
+ std::size_t operator() (const std::tuple<Keys_...> & p) const
+ {
+ return accumulate_tuple_hash<0, Keys_...>(p, 0, NotFinishedHashingTuple());
+ }
+ };
+
template <typename Tag_>
struct Hash<WrappedValue<Tag_> >
{
diff --git a/paludis/util/hashes_TEST.cc b/paludis/util/hashes_TEST.cc
new file mode 100644
index 0000000..46ada4e
--- /dev/null
+++ b/paludis/util/hashes_TEST.cc
@@ -0,0 +1,51 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2011 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/util/hashes.hh>
+#include <test/test_runner.hh>
+#include <test/test_framework.hh>
+#include <set>
+
+using namespace test;
+using namespace paludis;
+
+namespace test_cases
+{
+ struct HashTupleTest : TestCase
+ {
+ HashTupleTest() : TestCase("hash tuple") { }
+
+ void run()
+ {
+ std::set<std::size_t> hashes;
+
+ for (int x(1) ; x < 20 ; ++x)
+ TEST_CHECK(hashes.insert(Hash<std::tuple<int> >()(std::make_tuple(x))).second);
+
+ for (int x(1) ; x < 20 ; ++x)
+ for (int y(1) ; y < 20 ; ++y)
+ TEST_CHECK(hashes.insert(Hash<std::tuple<int, int> >()(std::make_tuple(x, y))).second);
+
+ for (int x(1) ; x < 20 ; ++x)
+ for (int y(1) ; y < 20 ; ++y)
+ TEST_CHECK(hashes.insert(Hash<std::tuple<int, int, int> >()(std::make_tuple(x, y, 42))).second);
+ }
+ } test_hash_tuple;
+}
+