According to the standard, all specializations of std::hash must export
argument_type and result_type [20.8.12/1]. The version of libc++ (LLVM's
alternative C++ standard library) tripped over this requirement on my
machine, so this patch adds the typedefs.

(cherry picked from commit a64ca159)
Signed-off-by: Steffen Müthing <muething@dune-project.org>

There is more macro magic to be removed.

Make type of std::site_t an additional template parameter to avoid the
warning. While this is conceptually redunant its OK since we only use
it in a helper struct.

As Carsten pointed out, the hash combining algorithms doesn't work
correctly for 32-bit platforms because it uses a multiplication with
a 64-bit constant.

This patch adds a switch for picking different algorithms based on the
size of std::size_t using a new struct hash_combiner that is templated
on the size of std::size_t.

Right now, there are implementations for 64-bit and 32-bit platforms,
both based on CityHash.

Steffen Müthing authored 11 years ago and Christoph Grüninger committed 11 years ago

The current algorithm for hash combining behaves very poorly when hashing
multiple short streams of small integers like (0,1,1,0,x) that only differ
by a single large number x. These objects appear frequently in PDELab's ordering
framework, and the resulting bad hash distribution really hurts the performance
of the unordered containers in PDELab.

This patch switches to an algorithm that is inspired by CityHash (see the source
code comment) and has proven to be much more robust in testing.

[[Imported from SVN: r7425]]

Add support for boost::hash

This patch adds boost::hash as a fallback option for Dune::hash
if neither std::hash nor std::tr1::hash can be found. We only
have to include the appropriate header and import the name into
the Dune namespace, as the built-in extension mechanism of boost::hash
will automatically pick up the global hash_value() functions.

To test whether the mechanism actually works, the patch also adds
boost::hash to the list of hash implementations tested in
bigunsignedinttest.

Kudos to Steffen Müthing, see FS#1192

[[Imported from SVN: r7067]]

Add basic support for hashing using Dune::hash

This patch introduces the functor Dune::hash in a similar manner to
other C++11 functionality by importing the definition from namespace std.

Apart from that, the patch also provides some basic functionality to simplify
making user-defined types hashable, in particular functions for combining hashes
and hashing iterator ranges as well as a mechanism for defining the struct
specializations required by std::hash and std::tr1::hash in the correct namespace.

The current implementation will first try to use std::hash and, if that fails,
attempt to fall back on std::tr1::hash. If that is not available either, hash
support is disabled as there is no homegrown fallback for now.
The extension mechanism will register the type with both std::hash and std::tr1::hash,
if available. This should make it possible to use unordered_{set,map} from both C++11
and TR1 without having to specify a custom hasher.

Kudos to Steffen Müthing, see FS#1192

[[Imported from SVN: r7065]]