C中的Const表达式 - 如何散列字符串？

Question

我正在创建一个内核模块.在这个模块中,我需要检查一些预定义字符串的输入.在C++中,可以创建一个constexpr函数,用于在编译时计算哈希值.我正在寻找一种方法来做到这一点.

一些使用Jenkins哈希函数的伪代码:

u32 hash(const char *key)
{
    u32 hash, i;
    size_t len;

    len = strlen(key);
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}


const u32 myStringList [] = {
    hash("hello"),
    hash("this is a text"),
    hash("good morning")
};

int findString(const char * searchStr) {
    u32 h;
    int i;

    h = hash(searchStr);
    for (i = 0; i < sizeof(myStringList)/sizeof(const u32); i++) {
        if (h == myStringList[i]) return i;
    }
    return -1;
}

如何修改才能搞定？

Answer 1

我不认为你可以,C没有constexpr或编译时评估.这就是为什么许多人转向预处理器(在C++中不经常使用)的原因,但使用它的字符串处理(与字符串"构造"相对)并不容易.

有时这可以通过添加另一个预处理步骤来解决,也许使用一些更高级的语言(我更喜欢Python)来构建所需的C代码.

如果这不是一个选项,那么我只是在启动期间初始化哈希表一次.如果您没有显式的init函数(我相信Linux内核模块可以),您当然可以使用静态标志:

static const char *strings[] = { "hello", "this is a text", "good morning", NULL };
static uint32_t myStringList[(sizeof strings / sizeof *strings) - 1];

void something(const char *string)
{
  static bool hash_initialized = false;
  if(!hash_initialized)
  {
    for(size_t i = 0; strings[i] != NULL; ++i)
      myStringList[i] = hash(strings[i]);
    hash_initialized = true;
  }
  if(hash_lookup(string))
  {
   ...
  }
}