c - (int, const char *) 作为 uthash 库的复合键

Question

我想使用 uthash以一对 int 和 const char * 作为复合键的哈希表库:

typedef struct entry_s {
    // This field is needed by the uthash library
    UT_hash_handle hh;

    // Values
    /* ... */

    // Compound key
    int num;
    const char *str;
} entry;

具体来说，我希望 const char * 指向的字符串成为键的一部分。澄清一下:指针的不同值可能对应于相同的字符串(在 strcmp() 的意义上)。

userguide展示了如何使用 int 和 char[] 作为复合键来实现与我想要的类似的键:

typedef struct another_entry_s {
    // This field is needed by the uthash library
    UT_hash_handle hh;

    // Values
    /* ... */

    int str_len;

    // Compound key
    int num;
    char str[];
} another_entry;

但是，第二种方法(即 (int, char[]))假设字符串被复制到 char[]，但我想避免复制。

此外，我并不是在寻找连接 int 和 const char * 指向的字符串，以便利用 HASH_ADD_KEYPTR() 和 HASH_FIND_STR() 便捷宏。

我无法弄清楚如何使用第一种方法(即 (int, const char *))。看起来不可能避免复制，正如 uthash 库的设计一样。我这样理解对吗？或者是否有我忽略的非复制方法？

Answer 1

对于这个库的设计来说这是不可能的(并且任何通用的实现都不可能不进行复制)。

对于任何哈希表实现，您需要对某些数据应用一些哈希函数。因此，您当然可以编写您的特定实现，其中哈希函数使用整数字段的字节和其他字段指向的字符串的字节。但是，如果您的哈希表实现是通用的，则哈希函数的唯一选择将类似于以下内容:

unsigned int hash(void *data, size_t size);

原型(prototype)不必看起来完全像这样，但在任何情况下，输入都是指向一些数据(任何类型)和大小的指针该数据。因此，显然，您不能让这样的函数同时从两个不同的位置读取。

根据the uthash documentation ，uthash 通过要求复合键由相邻的结构成员组成来解决复合键的问题。然后从这些成员中的第一个读取数据，其大小包括所有成员和填充。库的文档意识到了这个问题，并要求结构必须初始化为全零，例如使用memset()，因此填充位具有定义的值。如果您想使用它，您必须使您的字符串成为该结构的成员(而不是指向它的指针)。

虽然这在大多数实现中可能工作得很好，但我个人根本不会依赖该功能，因为 C 标准不保证在设置某些成员后定义的填充值，请参阅

C11(草案 N1570)，§6.2.6.1 p6:

When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values. [...]

<小时/>

因此，在该库中使用复合 key 的真正安全且可移植的方法是:获取数据的串联副本。您可以做这样的事情，给定上面的结构并添加一个字段char *hashKey:

#define ENTRY_KEYLEN(str) (sizeof(int) + strlen(str))
#define ENTRY_GETKEY(key, e) (getEntryKey((key), (e)->num, (e)->str))

static void getEntryKey(char *key, int num, const char *str)
{
    memcpy(key, &num, sizeof num);
    memcpy(key + sizeof num, str);
}

然后你可以像这样使用 uthash 宏:

entry *entries = 0;

entry *myent;
// allocate space, fill data in myent

// store in hashtable:
char *key = malloc(ENTRY_KEYLEN(myent->str));
// check key for NULL
ENTRY_GETKEY(key, myent);
myent->hashKey = key;
HASH_ADD_KEYPTR(hh, entries, key, ENTRY_KEYLEN(myent->str), myent);

// [...]

// find in hashtable
const char *str = "foo";
int id = 42;
key = malloc(ENTRY_KEYLEN(str));
// check key for NULL
getEntryKey(key, id, str);
entry *found;
HASH_FIND(hh, entries, key, ENTRY_KEYLEN(str), found);
free(key);

<小时/>

您可能最好使用不同的通用哈希表实现，这使您的用例更容易，例如通过使用一些回调函数来检索哈希 key 数据。