Using utstring as Key of uthash

Posted on Edited on In Views: Disqus:

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 文件中暴露接口即可。