aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-01-31 21:05:26 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-01-31 21:05:26 +0000
commit9f314d06ae24387194d098235472c2f35a60298d (patch)
tree52d762112af7411e8b6e6eeed297353979ebc871
parent439193d50d82cbb41ebb1fdb7c34a1b8055fc79e (diff)
downloadpaludis-9f314d06ae24387194d098235472c2f35a60298d.tar.gz
paludis-9f314d06ae24387194d098235472c2f35a60298d.tar.xz
Standardise hash table usage through an icky template trick
-rw-r--r--configure.ac5
-rw-r--r--paludis/Makefile.am.m47
-rw-r--r--paludis/files.m41
-rw-r--r--paludis/hashed_containers.cc82
-rw-r--r--paludis/hashed_containers.hh.in135
-rw-r--r--paludis/hashed_containers_TEST.cc45
-rw-r--r--paludis/portage_repository.cc191
7 files changed, 282 insertions, 184 deletions
diff --git a/configure.ac b/configure.ac
index 87e52b1..cb59789 100644
--- a/configure.ac
+++ b/configure.ac
@@ -137,8 +137,12 @@ int main(int, char **)
]
]))
+HAVE_TR1_HASHES=$have_tr1_hashes
AC_DEFINE_UNQUOTED([HAVE_TR1_HASHES], $have_tr1_hashes, [Do we have std::tr1:: hashes?])
+AC_SUBST([HAVE_TR1_HASHES])
+HAVE_EXT_HASHES=$have_ext_hashes
AC_DEFINE_UNQUOTED([HAVE_EXT_HASHES], $have_ext_hashes, [Do we have __gnu_cxx hashes?])
+AC_SUBST([HAVE_EXT_HASHES])
dnl }}}
dnl {{{ we need libebt.
@@ -278,6 +282,7 @@ AC_OUTPUT(
misc/svn-version-filter-data.bash
paludis/Makefile
paludis/about.hh
+ paludis/hashed_containers.hh
paludis/args/Makefile
src/Makefile
test/Makefile
diff --git a/paludis/Makefile.am.m4 b/paludis/Makefile.am.m4
index 96a0bf0..5a1fd75 100644
--- a/paludis/Makefile.am.m4
+++ b/paludis/Makefile.am.m4
@@ -28,11 +28,12 @@ addthis(`$1',`$5')addthis(`$1',`$6')')dnl
include(`paludis/files.m4')
CLEANFILES = *~
-MAINTAINERCLEANFILES = Makefile.in Makefile.am about.hh paludis.hh smart_record.hh comparison_policy.hh
+MAINTAINERCLEANFILES = Makefile.in Makefile.am about.hh paludis.hh smart_record.hh \
+ hashed_containers.hh comparison_policy.hh
AM_CXXFLAGS = -I$(top_srcdir)
DEFS=-DSYSCONFDIR=\"$(sysconfdir)\" -DLIBEXECDIR=\"$(libexecdir)\"
-EXTRA_DIST = about.hh.in Makefile.am.m4 paludis.hh.m4 files.m4 smart_record.hh.m4 comparison_policy.hh.m4 \
- testscriptlist
+EXTRA_DIST = about.hh.in Makefile.am.m4 paludis.hh.m4 files.m4 smart_record.hh.m4 \
+ comparison_policy.hh.m4 hashed_containers.hh.in testscriptlist
SUBDIRS = . args
libpaludis_a_SOURCES = filelist
diff --git a/paludis/files.m4 b/paludis/files.m4
index f7e2982..fdf1303 100644
--- a/paludis/files.m4
+++ b/paludis/files.m4
@@ -40,6 +40,7 @@ add(`fake_repository', `hh', `cc')
add(`filter_insert_iterator', `hh', `cc', `test')
add(`fs_entry', `hh', `cc', `test', `testscript')
add(`getenv', `hh', `cc', `test')
+add(`hashed_containers', `hh', `cc', `test')
add(`indirect_iterator', `hh', `cc', `test')
add(`instantiation_policy', `hh', `cc', `test')
add(`is_const', `hh', `cc', `test')
diff --git a/paludis/hashed_containers.cc b/paludis/hashed_containers.cc
new file mode 100644
index 0000000..050ce8e
--- /dev/null
+++ b/paludis/hashed_containers.cc
@@ -0,0 +1,82 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2006 Ciaran McCreesh <ciaranm@gentoo.org>
+ *
+ * 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 "hashed_containers.hh"
+
+using namespace paludis;
+
+#if PALUDIS_HAVE_TR1_HASHES || PALUDIS_HAVE_EXT_HASHES
+
+std::size_t
+CRCHash<QualifiedPackageName>::operator() (const QualifiedPackageName & val) const
+{
+ const std::string & s1(val.get<qpn_category>().data()), s2(val.get<qpn_package>().data());
+ std::size_t h(0);
+
+ for (std::string::size_type t(0) ; t < s1.length() ; ++t)
+ {
+ std::size_t hh(h & h_mask);
+ h <<= 5;
+ h ^= (hh >> h_shift);
+ h ^= s1[t];
+ }
+
+ for (std::string::size_type t(0) ; t < s2.length() ; ++t)
+ {
+ std::size_t hh(h & h_mask);
+ h <<= 5;
+ h ^= (hh >> h_shift);
+ h ^= s2[t];
+ }
+
+ return h;
+}
+
+std::size_t
+CRCHash<std::pair<QualifiedPackageName, VersionSpec> >::operator() (
+ const std::pair<QualifiedPackageName, VersionSpec> & val) const
+{
+ const std::string & s1(val.first.get<qpn_category>().data()),
+ s2(val.first.get<qpn_package>().data());
+
+ std::size_t h(0);
+
+ for (std::string::size_type t(0) ; t < s1.length() ; ++t)
+ {
+ std::size_t hh(h & h_mask);
+ h <<= 5;
+ h ^= (hh >> h_shift);
+ h ^= s1[t];
+ }
+
+ for (std::string::size_type t(0) ; t < s2.length() ; ++t)
+ {
+ std::size_t hh(h & h_mask);
+ h <<= 5;
+ h ^= (hh >> h_shift);
+ h ^= s2[t];
+ }
+
+ h ^= val.second.hash_value();
+
+ return h;
+}
+
+#endif
+
diff --git a/paludis/hashed_containers.hh.in b/paludis/hashed_containers.hh.in
new file mode 100644
index 0000000..ef67f57
--- /dev/null
+++ b/paludis/hashed_containers.hh.in
@@ -0,0 +1,135 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+@GENERATED_FILE@
+
+/*
+ * Copyright (c) 2006 Ciaran McCreesh <ciaranm@gentoo.org>
+ *
+ * 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
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_HASHED_CONTAINERS_HH
+#define PALUDIS_GUARD_PALUDIS_HASHED_CONTAINERS_HH 1
+
+#define PALUDIS_HAVE_TR1_HASHES @HAVE_TR1_HASHES@
+#define PALUDIS_HAVE_EXT_HASHES @HAVE_EXT_HASHES@
+
+#include <paludis/qualified_package_name.hh>
+#include <paludis/version_spec.hh>
+#include <paludis/validated.hh>
+
+#if PALUDIS_HAVE_TR1_HASHES
+# include <tr1/unordered_set>
+# include <tr1/unordered_map>
+#elif PALUDIS_HAVE_EXT_HASHES
+# include <ext/hash_set>
+# include <ext/hash_map>
+#else
+# include <set>
+# include <map>
+#endif
+
+#include <limits>
+#include <string>
+#include <functional>
+
+namespace paludis
+{
+ template <typename T_>
+ struct CRCHash;
+
+ template <typename Key_, typename Value_>
+ struct MakeHashedMap
+ {
+#if PALUDIS_HAVE_TR1_HASHES
+ typedef std::tr1::unordered_map<Key_, Value_, CRCHash<Key_> > Type;
+#elif PALUDIS_HAVE_EXT_HASHES
+ typedef __gnu_cxx::hash_map<Key_, Value_, CRCHash<Key_> > Type;
+#else
+ typedef std::map<Key_, Value_> Type;
+#endif
+ };
+
+ template <typename Key_>
+ struct MakeHashedSet
+ {
+#if PALUDIS_HAVE_TR1_HASHES
+ typedef std::tr1::unordered_set<Key_, CRCHash<Key_> > Type;
+#elif PALUDIS_HAVE_EXT_HASHES
+ typedef __gnu_cxx::hash_set<Key_, CRCHash<Key_> > Type;
+#else
+ typedef std::set<Key_> Type;
+#endif
+ };
+
+#if PALUDIS_HAVE_TR1_HASHES || PALUDIS_HAVE_EXT_HASHES
+ namespace
+ {
+ struct CRCHashBase
+ {
+ static const std::size_t h_shift = std::numeric_limits<std::size_t>::digits - 5;
+ static const std::size_t h_mask = 0x1f << h_shift;
+ };
+ }
+
+ template <>
+ class CRCHash<QualifiedPackageName> :
+ public std::unary_function<QualifiedPackageName, std::size_t>,
+ protected CRCHashBase
+ {
+ public:
+ std::size_t operator() (const QualifiedPackageName & val) const;
+ };
+
+ template <typename Validated_>
+ class CRCHash<Validated<std::string, Validated_> > :
+ public std::unary_function<Validated<std::string, Validated_>, std::size_t>,
+ protected CRCHashBase
+ {
+ public:
+ std::size_t operator() (const Validated<std::string, Validated_> & val) const;
+ };
+
+ template <>
+ class CRCHash<std::pair<QualifiedPackageName, VersionSpec> > :
+ public std::unary_function<std::pair<QualifiedPackageName, VersionSpec>, std::size_t>,
+ protected CRCHashBase
+ {
+ public:
+ std::size_t operator() (const std::pair<QualifiedPackageName, VersionSpec> & val) const;
+ };
+
+ template <typename Validated_>
+ std::size_t
+ CRCHash<Validated<std::string, Validated_> >::operator() (const Validated<std::string, Validated_> & val) const
+ {
+ const std::string & s1(val.data());
+ std::size_t h(0);
+
+ for (std::string::size_type t(0) ; t < s1.length() ; ++t)
+ {
+ std::size_t hh(h & h_mask);
+ h <<= 5;
+ h ^= (hh >> h_shift);
+ h ^= s1[t];
+ }
+
+ return h;
+ }
+
+#endif
+
+}
+
+#endif
diff --git a/paludis/hashed_containers_TEST.cc b/paludis/hashed_containers_TEST.cc
new file mode 100644
index 0000000..ce04c9a
--- /dev/null
+++ b/paludis/hashed_containers_TEST.cc
@@ -0,0 +1,45 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2006 Ciaran McCreesh <ciaranm@gentoo.org>
+ *
+ * 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 "hashed_containers.hh"
+#include <test/test_framework.hh>
+#include <test/test_runner.hh>
+
+using namespace paludis;
+using namespace test;
+
+namespace test_cases
+{
+ struct HashSetTestQPN : TestCase
+ {
+ HashSetTestQPN() : TestCase("hash set qpn") { }
+
+ void run()
+ {
+ MakeHashedSet<QualifiedPackageName>::Type s;
+ TEST_CHECK(s.empty());
+ TEST_CHECK(s.end() == s.find(QualifiedPackageName("foo/bar")));
+ TEST_CHECK(s.insert(QualifiedPackageName("foo/bar")).second);
+ TEST_CHECK(s.end() != s.find(QualifiedPackageName("foo/bar")));
+ TEST_CHECK(! s.empty());
+ TEST_CHECK(! s.insert(QualifiedPackageName("foo/bar")).second);
+ }
+ } test_hash_set_qpn;
+}
+
diff --git a/paludis/portage_repository.cc b/paludis/portage_repository.cc
index c9c7781..bddddc7 100644
--- a/paludis/portage_repository.cc
+++ b/paludis/portage_repository.cc
@@ -22,6 +22,7 @@
#include "dir_iterator.hh"
#include "filter_insert_iterator.hh"
#include "fs_entry.hh"
+#include "hashed_containers.hh"
#include "indirect_iterator.hh"
#include "is_file_with_extension.hh"
#include "key_value_config_file.hh"
@@ -35,204 +36,32 @@
#include "strip.hh"
#include "tokeniser.hh"
#include "transform_insert_iterator.hh"
+
#include <map>
#include <fstream>
#include <functional>
#include <algorithm>
#include <vector>
#include <deque>
-
#include <limits>
-#if HAVE_TR1_HASHES
-# include <tr1/unordered_set>
-# include <tr1/unordered_map>
-#elif HAVE_EXT_HASHES
-# include <ext/hash_set>
-# include <ext/hash_map>
-#else
-# include <set>
-# include <map>
-#endif
-
using namespace paludis;
-#if HAVE_TR1_HASHES || HAVE_EXT_HASHES
-
-template <typename T_>
-struct CRCHash;
-
-template <>
-class CRCHash<QualifiedPackageName> :
- std::unary_function<QualifiedPackageName, std::size_t>
-{
- private:
- static const std::size_t h_shift = std::numeric_limits<std::size_t>::digits - 5;
- static const std::size_t h_mask = 0x1f << h_shift;
-
- public:
- std::size_t operator() (const QualifiedPackageName & val) const
- {
- const std::string & s1(val.get<qpn_category>().data()), s2(val.get<qpn_package>().data());
- std::size_t h(0);
-
- for (std::string::size_type t(0) ; t < s1.length() ; ++t)
- {
- std::size_t hh(h & h_mask);
- h <<= 5;
- h ^= (hh >> h_shift);
- h ^= s1[t];
- }
-
- for (std::string::size_type t(0) ; t < s2.length() ; ++t)
- {
- std::size_t hh(h & h_mask);
- h <<= 5;
- h ^= (hh >> h_shift);
- h ^= s2[t];
- }
-
- return h;
- }
-};
-
-template <typename Validated_>
-class CRCHash<Validated<std::string, Validated_> > :
- std::unary_function<Validated<std::string, Validated_>, std::size_t>
-{
- private:
- static const std::size_t h_shift = std::numeric_limits<std::size_t>::digits - 5;
- static const std::size_t h_mask = 0x1f << h_shift;
-
- public:
- std::size_t operator() (const Validated<std::string, Validated_> & val) const
- {
- const std::string & s1(val.data());
- std::size_t h(0);
-
- for (std::string::size_type t(0) ; t < s1.length() ; ++t)
- {
- std::size_t hh(h & h_mask);
- h <<= 5;
- h ^= (hh >> h_shift);
- h ^= s1[t];
- }
-
- return h;
- }
-};
-
-template <>
-class CRCHash<std::pair<QualifiedPackageName, VersionSpec> > :
- std::unary_function<std::pair<QualifiedPackageName, VersionSpec>, std::size_t>
-{
- private:
- static const std::size_t h_shift = std::numeric_limits<std::size_t>::digits - 5;
- static const std::size_t h_mask = 0x1f << h_shift;
-
- public:
- std::size_t operator() (const std::pair<QualifiedPackageName, VersionSpec> & val) const
- {
- const std::string & s1(val.first.get<qpn_category>().data()),
- s2(val.first.get<qpn_package>().data());
-
- std::size_t h(0);
-
- for (std::string::size_type t(0) ; t < s1.length() ; ++t)
- {
- std::size_t hh(h & h_mask);
- h <<= 5;
- h ^= (hh >> h_shift);
- h ^= s1[t];
- }
-
- for (std::string::size_type t(0) ; t < s2.length() ; ++t)
- {
- std::size_t hh(h & h_mask);
- h <<= 5;
- h ^= (hh >> h_shift);
- h ^= s2[t];
- }
-
- h ^= val.second.hash_value();
-
- return h;
- }
-};
-
-#endif
-
-#if HAVE_TR1_HASHES
-
-typedef std::tr1::unordered_map<QualifiedPackageName, VersionSpecCollection::Pointer,
- CRCHash<QualifiedPackageName> > VersionsMap;
-
-typedef std::tr1::unordered_map<QualifiedPackageName, PackageDepAtom::ConstPointer,
- CRCHash<QualifiedPackageName> > VirtualsMap;
-
-typedef std::tr1::unordered_map<QualifiedPackageName, std::deque<PackageDepAtom::ConstPointer>,
- CRCHash<QualifiedPackageName> > RepositoryMaskMap;
-
-typedef std::tr1::unordered_map<CategoryNamePart, bool,
- CRCHash<CategoryNamePart> > CategoryMap;
-
-typedef std::tr1::unordered_map<QualifiedPackageName, bool,
- CRCHash<QualifiedPackageName> > PackagesMap;
-
-typedef std::tr1::unordered_map<UseFlagName, UseFlagState,
- CRCHash<UseFlagName> > UseMap;
-
-typedef std::tr1::unordered_set<UseFlagName,
- CRCHash<UseFlagName> > UseMaskSet;
-
-typedef std::tr1::unordered_map<std::pair<QualifiedPackageName, VersionSpec>,
- VersionMetadata::Pointer, CRCHash<std::pair<QualifiedPackageName, VersionSpec> > > MetadataMap;
-
-#elif HAVE_EXT_HASHES
-
-typedef __gnu_cxx::hash_map<QualifiedPackageName, VersionSpecCollection::Pointer,
- CRCHash<QualifiedPackageName> > VersionsMap;
-
-typedef __gnu_cxx::hash_map<QualifiedPackageName, PackageDepAtom::ConstPointer,
- CRCHash<QualifiedPackageName> > VirtualsMap;
-
-typedef __gnu_cxx::hash_map<QualifiedPackageName, std::deque<PackageDepAtom::ConstPointer>,
- CRCHash<QualifiedPackageName> > RepositoryMaskMap;
-
-typedef __gnu_cxx::hash_map<CategoryNamePart, bool,
- CRCHash<CategoryNamePart> > CategoryMap;
-
-typedef __gnu_cxx::hash_map<QualifiedPackageName, bool,
- CRCHash<QualifiedPackageName> > PackagesMap;
-
-typedef __gnu_cxx::hash_map<UseFlagName, UseFlagState,
- CRCHash<UseFlagName> > UseMap;
-
-typedef __gnu_cxx::hash_set<UseFlagName,
- CRCHash<UseFlagName> > UseMaskSet;
-
-typedef __gnu_cxx::hash_map<std::pair<QualifiedPackageName, VersionSpec>,
- VersionMetadata::Pointer, CRCHash<std::pair<QualifiedPackageName, VersionSpec> > > MetadataMap;
-
-#else
-
-typedef std::map<QualifiedPackageName, VersionSpecCollection::Pointer> VersionsMap;
-
-typedef std::map<QualifiedPackageName, PackageDepAtom::ConstPointer> VirtualsMap;
+typedef MakeHashedMap<QualifiedPackageName, VersionSpecCollection::Pointer>::Type VersionsMap;
-typedef std::map<QualifiedPackageName, std::deque<PackageDepAtom::ConstPointer> > RepositoryMaskMap;
+typedef MakeHashedMap<QualifiedPackageName, PackageDepAtom::ConstPointer>::Type VirtualsMap;
-typedef std::map<CategoryNamePart, bool> CategoryMap;
+typedef MakeHashedMap<QualifiedPackageName, std::deque<PackageDepAtom::ConstPointer> >::Type RepositoryMaskMap;
-typedef std::map<QualifiedPackageName, bool> PackagesMap;
+typedef MakeHashedMap<CategoryNamePart, bool>::Type CategoryMap;
-typedef std::map<UseFlagName, UseFlagState> UseMap;
+typedef MakeHashedMap<QualifiedPackageName, bool>::Type PackagesMap;
-typedef std::set<UseFlagName> UseMaskSet;
+typedef MakeHashedMap<UseFlagName, UseFlagState>::Type UseMap;
-typedef std::map<std::pair<QualifiedPackageName, VersionSpec>, VersionMetadata::Pointer> MetadataMap;
+typedef MakeHashedSet<UseFlagName>::Type UseMaskSet;
-#endif
+typedef MakeHashedMap<std::pair<QualifiedPackageName, VersionSpec>, VersionMetadata::Pointer>::Type MetadataMap;
namespace paludis
{