compile-time string hashing

问题:

I need to use a string as the ID to obtain some object. At implement this in a run-time, and works well. But this makes the static type checking impossible, for obvious reasons.

I've Googled for the algorithm for calculating the hash-sum of string in the compile-time: C++ compile-time string hashing with Boost.MPL.

It seems to be the perfect solution to my problem, except that the sring which is necessary to the algorithm should be split into pieces by 4 characters, or character-by-character, as well, for obvious reasons.

i.e., instead of the usual current record of the ID's, I'll have to write this way:

hash_cstring<boost::mpl::string<'obje', 'ct.m', 'etho', 'd'>>::value

This is absolutely unusable.

The question is, how to pass correctly the string such as "object.method" to this algorithm?

Thank you all.

回答1:

Solution with gcc-4.6:

#include <iostream>
template<size_t N, size_t I=0>
struct hash_calc {
    static constexpr size_t apply (const char (&s)[N]) {
       return  (hash_calc<N, I+1>::apply(s) ^ s[I]) * 16777619u;
    };
};

template<size_t N>
struct hash_calc<N,N> {
    static constexpr size_t apply (const char (&s)[N]) {
       return  2166136261u;
    };
};

template<size_t N>
constexpr size_t hash ( const char (&s)[N] ) {
    return hash_calc<N>::apply(s);
}

int main() {
   char a[] = "12345678";
   std::cout << std::hex << hash(a) << std::endl;
   std::cout << std::hex << hash("12345678") << std::endl;
}

http://liveworkspace.org/code/DPObf

I`m happy!

回答2:

I don't know of a way to do this with the preprocessor or with templates. I suspect your best bet is to create a separate pre-compile step (say with perl or such) to generate the hash_cstring statements from a set of source statements. Then at least you don't have to split the strings manually when you add new ones, and the generation is fully automated and repeatable.

回答3:

Templates can be instantiated with any external symbol, therefore this should work as expected:

external char const* object_method = "object.method";
... = hash_cstring<object_method>::value;

(given the template hash_cstring<> is able to deal with pointer values).

回答4:

In case anyone is interested, I walk through how to create a compile time hash of Murmur3_32 using C++11 constexpr functions and variadic templates here:

http://roartindon.blogspot.sg/2014/10/compile-time-murmur-hash-in-c.html

Most of the examples I've seen deal with hashes that are based on consuming one character of the string at a time. The Murmur3_32 hash is a bit more interesting in that it consumes 4 characters at a time and needs some special case code to handle the remaining 0, 1, 2 or 3 bytes.