0

我想将utash库用于带有一对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()）。

用户指南展示了如何使用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()

我不知道如何使用第一种方法（即）来使用HASH_ADD(),和其他通用宏。看起来不可能避免复制，就像 uthash 库设计一样。我理解对吗？还是有我忽略的非复制方法？HASH_FIND()(int, const char *)

4

1 回答 1

1

这在这个库的设计中是不可能的（对于任何没有复制的通用实现都是不可能的）。

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

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

原型不必完全像这样，但无论如何，输入是指向某些数据（任何类型）的指针以及该数据的大小。因此，显然，您不能同时从两个不同的位置读取这样的函数。

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

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

C11（N1570 草案），§6.2.6.1 p6：

当一个值存储在结构或联合类型的对象中时，包括在成员对象中，对应于任何填充字节的对象表示的字节采用未指定的值。[...]

因此，在此库中使用复合键的真正安全且可移植的方法是：获取数据的串联副本。你可以做这样的事情，给你上面的结构加上一个字段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);

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

于 2017-08-27T08:24:17.790 回答