compile-time string hashing

Question

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.

can you use struct with static string instead of string directly? perhaps a macro to generate them too? — Anycorn, Feb 12 '11 at 04:19
@aaa: macros don't split tokens, they can stringize or concatenate them, but not split them. — Matthieu M., Feb 12 '11 at 10:26
@Matt macros to generate struct with name and static string. eg `#define str(n) struct n { ... }` — Anycorn, Feb 12 '11 at 18:31
Any thoughts of using gperf and wrapping the results with a type? — CoreyStup, Feb 16 '11 at 17:41

niXman · Accepted Answer · 2013-02-22T06:37:20.877

9

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!

edited Feb 22 '13 at 06:37

answered Feb 16 '11 at 17:07

niXman

1,698
3
16
40

Are you actually getting this to compile with gcc 4.6 without a recursion error? – Damon Oct 14 '11 at 13:09
Funny, my gcc-4.6.1 (MingW-TDM) rejects that code with said error (is the reason why I asked). – Damon Oct 15 '11 at 20:22
In instantiation of 'static constexpr size_t hash_calc::apply(const char (&)[N]) [with unsigned int N = 10u, size_t = unsigned int]': recursively instantiated from 'static constexpr size_t hash_calc::apply(const char (&)[N]) [with unsigned int N = 10u, unsigned int I = 1u, size_t = unsigned int]' instantiated from 'static constexpr size_t hash_calc::apply(const char (&)[N]) [with unsigned int N = 10u, unsigned int I = 0u, size_t = unsigned int]' instantiated from 'constexpr size_t hash(const char (&)[N]) [with unsigned int N = 10u, size_t = unsigned int]' – Damon Oct 17 '11 at 18:51
I'm not sure about the TDM builds. I use these builds: http://code.google.com/p/mingw-builds/ – niXman Oct 18 '11 at 16:02

score 5 · Answer 2 · answered Feb 12 '11 at 06:05

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.

score 1 · Answer 3 · answered Oct 29 '14 at 14:58

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.

hkaiser · Answer 4 · 2011-02-15T17:44:37.933

1

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).

edited Feb 15 '11 at 17:44

answered Feb 12 '11 at 17:03

hkaiser

11,403
1
30
35

compile-time string hashing

4 Answers4

Linked