Using utstring as Key of uthash

uthash 是一个 C 语言的 hash 库; utstring 是前者的一个子项目,即 C 语言的动态字符串。本文将介绍如何将 utstring 作为 uthash 的 key 来使用。

HASH_KEYCMP

自定义该宏可以覆盖 uthash 默认比较 key 的方式。该宏有如下形式:

1
#define HASH_KEYCMP(a, b, n)

表达式的值为 0 则代表 a 和 b 两个 key 相等,任何非零值代表不相等,默认调用的是 memcmp 函数。

为方便编写代码,我们先定义一个辅助函数用来比较两个 utstring 的值:

1
2
3
4
5
static int utstring_cmp(UT_string *a, UT_string *b) {
int n = utstring_len(a);
int result = n - utstring_len(b);
return result ? result : memcmp(utstring_body(a), utstring_body(b), n);
}

接下来定义我们自己的 HASH_KEYCMP :

1
2
#define HASH_KEYCMP(a, b, n) \
utstring_cmp((UT_string *)(a), (UT_string *)(b))

HASH_FUNCTION

自定义该宏可以覆盖默认的哈希函数。该宏有如下形式:

1
#define HASH_FUNCTION(kptr, keylen, hashv) ...

该表达式不需要有值,但是需要设置 hashv 为哈希值,如:

1
#define HASH_FUNCTION(kptr, keylen, hashv) (hashv) = (kptr) + (keylen)

我们可以借助 uthash 中预定义的几个哈希函数来定义我们自己的函数,预设的哈希函数可以见官方文档

我们的 HASH_FUNCTION 定义如下:

1
2
3
#define HASH_FUNCTION(kptr, keylen, hashv) \
HASH_JEN(utstring_body((UT_string *)(kptr)), \
utstring_len((UT_string *)(kptr)), hashv)

此处选用了 JEN 算法来生成哈希值。

Usage

需要在 #include <uthash.h> 之前自定义上述两个宏以及辅助函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define HASH_FUNCTION(kptr, keylen, hashv) \
HASH_JEN(utstring_body((UT_string *)(kptr)), \
utstring_len((UT_string *)(kptr)), hashv)
#define HASH_KEYCMP(a, b, n) \
utstring_cmp((UT_string *)(a), (UT_string *)(b))

#include <uthash.h>
#include <utstring.h>

static int utstring_cmp(UT_string *a, UT_string *b) {
int n = utstring_len(a);
int result = n - utstring_len(b);
return result ? result : memcmp(utstring_body(a), utstring_body(b), n);
}

定义哈希节点如下:

1
2
3
4
5
typedef struct {
UT_hash_handle hh;
UT_string key;
void value;
} __hash_node;

接下来即可添加,删除,查找等操作:

1
2
3
HASH_ADD(hh, head, key, utstring_len(&node->key), node);
HASH_DELETE(hh, head, node);
HASH_FIND(hh, head, &key, utstring_len(&key), node);

需要注意的是若在头文件中使用这种方法时会污染全局 uthash 的行为,因此最好是在 .c 文件中封装自己的 hash 设施,只在 .h 文件中暴露接口即可。