我试图使用哈希函数获得基于字符串的开关表达式在C中工作。我已经能够使用'constexpr'和Clang / LLVM转向C ++,使用干净的语法,即使代码是C.
但是,编译为C ++当然有一些奇怪的副作用,比如缺乏void *隐式转换,这变得非常尴尬。
所以问题是如何解决这个难题(没有打破C11委员会的优势,为什么没有将这个问题添加到C规范中)
这是我目前的示例代码:
constexpr uint64 cHash(char const* text, uint64 last_value = basis)
{
return *str ? cHash(text+1, (*text ^ last_value) * prime) : last_value;
}
void SwitchFunction(char const* text)
{
switch(Hash(text))
{
case cHash("first"):
break;
case cHash("second"):
break;
case cHash("third"):
break;
default:
break;
}
}
我参加聚会有点晚了,但最近遇到了同样的问题。
对于这样一个简单的哈希函数,您可以使用C预处理器实现它。缺点是预处理器不能将字符串拆分成字符,所以你不得不写hash("first")
而不是HASH('f','i','r','s','t')
。 HASH
宏使用__VA_ARGS__
实现,适用于最多八个字符的字符串。
我还将散列函数从递归函数转换为迭代函数,这更容易阅读并且不需要可选参数。生成的程序集几乎相同(https://godbolt.org/z/1g8LPI)。
#include <stdio.h>
typedef unsigned long uint64;
#define HASH_BASIS 17UL
#define HASH_PRIME 11UL
#define HASH_1(ARG1) ((ARG1 ^ HASH_BASIS) * HASH_PRIME)
#define HASH_2(ARG1, ARG2) ((ARG2 ^ HASH_1(ARG1)) * HASH_PRIME)
#define HASH_3(ARG1, ARG2, ARG3) ((ARG3 ^ HASH_2(ARG1, ARG2)) * HASH_PRIME)
#define HASH_4(ARG1, ARG2, ARG3, ARG4) \
((ARG4 ^ HASH_3(ARG1, ARG2, ARG3)) * HASH_PRIME)
#define HASH_5(ARG1, ARG2, ARG3, ARG4, ARG5) \
((ARG5 ^ HASH_4(ARG1, ARG2, ARG3, ARG4)) * HASH_PRIME)
#define HASH_6(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6) \
((ARG6 ^ HASH_5(ARG1, ARG2, ARG3, ARG4, ARG5)) * HASH_PRIME)
#define HASH_7(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6, ARG7) \
((ARG7 ^ HASH_6(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6)) * HASH_PRIME)
#define HASH_8(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6, ARG7, ARG8) \
((ARG8 ^ HASH_7(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6, ARG7)) * HASH_PRIME)
#define HASH_COUNT(ARG1, ARG2, ARG3, ARG4, ARG5, ARG6, ARG7, ARG8, func, ...) \
func
#define HASH(...) \
HASH_COUNT(__VA_ARGS__, HASH_8(__VA_ARGS__), HASH_7(__VA_ARGS__), \
HASH_6(__VA_ARGS__), HASH_5(__VA_ARGS__), HASH_4(__VA_ARGS__), \
HASH_3(__VA_ARGS__), HASH_2(__VA_ARGS__), HASH_1(__VA_ARGS__))
uint64 hash(const char *text) {
uint64 h = HASH_BASIS;
char c;
while ((c = *text++) != '\0') {
h = (c ^ h) * HASH_PRIME;
}
return h;
}
int main(int argc, char *argv[]) {
const char *text = argc > 1 ? argv[1] : "";
switch (hash(text)) {
case HASH('f', 'i', 'r', 's', 't'):
puts(text);
break;
case HASH('s', 'e', 'c', 'o', 'n', 'd'):
puts(text);
break;
case HASH('t', 'h', 'i', 'r', 'd'):
puts(text);
break;
default:
puts("oops");
break;
}
}
如果你知道要提前散列的值,那么你可以使用gperf并生成一个完美的哈希? C不会与constexpr很好地配合。
有没有办法让C开启constexpr选项?
不,C中不存在这样的事情。
有没有办法用C ++启用隐式void *转换?
不,C ++具有强制类型指针安全性。
是否有另一种干净的方法来编写C11 / C99中不需要重新计算哈希值的代码?
唯一可行的方法是使用宏的传统方式。如果您使用这些参数创建类似函数的宏,并且仅在编译时常量上使用它,那么所有计算都将在编译时完成。不幸的是,代码将变得相当丑陋,但在C中没有办法避免这种情况。
最好的方法可能是使用外部脚本/程序准备所有这些编译时参数,然后将它们作为原始数据表存储在C程序中。
这不会在C中起作用。案例标签的值必须是常量。
您可以做的是预先计算cHash("first")
等的输出,然后使用case
中的值,例如:
#define CHASH_FIRST 0x831928 /* precalculated output for cHash ("first") */
switch (Hash(text))
{
case CHASH_FIRST:
break;
}
为了扩展它,您可以构建另一个二进制文件,它只计算哈希值,在构建过程中运行它,并使用在编译行上使用生成的预处理器定义的值。
如果您使用内联函数并使用优化编译代码,那么一个不错的编译器应该能够将constant propagation应用于您的代码。这是一个小例子:
const int basis = 17;
inline const int hash(const char* text, int last_value) {
return *text ? hash(text + 1, (*text ^ last_value) * 11) : last_value;
}
int main(int argc, const char** argv) {
if (hash(argv[0], basis) == hash("hello", basis)) {
return 0;
} else {
return 1;
}
}
如果使用-O3
标志调用,clang将优化掉对hash("hello", basis)
的调用并用静态替换它。如果生成LLVM字节代码(clang -S -emit-llvm example.c
),则可以看到优化:
; (...)
%18 = icmp ne i32 %14, 20068367
%19 = zext i1 %18 to i32
br label %20
; (...)
不幸的是,这并不意味着您可以使用hash
作为代码中的实际常量表达式,因为没有办法告诉编译器hash
必须是静态可优化的。因此,例如,您不能将它用作switch-case的值。对于这些特定的用例(没有双关语),你别无选择,只能使用预先计算的常量(即Lundin的建议)。
这可能不像你想象的那么难,取决于你的constexpr
s有多复杂。有无数的C语言分析器用各种脚本语言编写(例如Python的pycparser)。然后你需要做的就是走你的C AST并应用你认为合适的任何自定义预处理过程。