转载请注明出处为KlayGE游戏引擎,本文的永久链接为http://www.klayge.org/?p=2201

时间过得真快,离上一次讨论编译期字符串Hash已经差不多2年了。上次的尝试失败了,只能产生优化期常量,没有做到编译期常量的效果。现在有了C++11,情况会不会有所改变呢?

constexpr

上次的帖子中,在回复mtlung的时候,我提到了C++0x的constexpr可能会成为救星。现在C++11的标准出来了,GCC 4.6+和Clang 3.1+也开始支持constexpr了。首先尝试宏的做法,代码和上次几乎相同:

constexpr inline size_t HASH_FUNCTION(size_t seed, char ch)
{
    return seed ^ (ch + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

#define HASH_RECURSE_00(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_01(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_01(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_02(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_02(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_03(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_03(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_04(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_04(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_05(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_05(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_06(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_06(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_07(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_07(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_08(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_08(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_09(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_09(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_10(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_10(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_11(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_11(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_12(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_12(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_13(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_13(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_14(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_14(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_15(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_15(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_16(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_16(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_17(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_17(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_18(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_18(seed, str) (*(str + 1) == 0 ? HASH_FUNCTION((seed), *(str)) : HASH_RECURSE_19(HASH_FUNCTION((seed), *(str)), (str + 1)))
#define HASH_RECURSE_19(seed, str) HASH_FUNCTION((seed), *(str))

#define CT_HASH(str) HASH_RECURSE_00(0, (str))

唯一的区别也就是HASH_FUNCTION之前加了个constexpr。结果一下成功!switch case这种必须要编译期常量的测试顺利通过。也就是说constexpr确实像预期一般起到了作用,解决了这个问题。还剩下字符串长度的问题,目前只到了20,需要增长还得写更多的宏,还是有点不方便。

彻底解决?

宏没法自动嵌套展开,模板可以。那么如果用constexpr配合模板展开又会如何呢?试试这个:

constexpr size_t _Hash(const char (&str)[1])
{
   return *str + 0x9e3779b9;
}

template <size_t N>
constexpr size_t _Hash(const char (&str)[N])
{
   typedef const char (&truncated_str)[N - 1];
   #define seed _Hash((truncated_str)str)
   return seed ^ (*(str + N - 1) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
   #undef seed
}

template <size_t N>
constexpr size_t CTHash(const char (&str)[N])
{
   typedef const char (&truncated_str)[N - 1];
   return _Hash<N - 1>((truncated_str)str);
}

因为带constexpr的函数必须是只包含return语句的,所以_Hash里面没法定义seed变量,而是用一个临时的宏来代替。结果也成功!switch case能通过,同时字符串长度不受限制。

至此,在C++11的帮助下,编译期字符串Hash的问题在技术上得到了圆满解决。接着就是等待更多的编译器——尤其是VC——支持constexpr。