一、uthash介绍
uthash github地址:http://troydhanson.github.io/uthash/userguide.html
Hash操作可以将数据通过Key进行标识,提高查找效率,例如字典操作。
C语言不像其他的高级语言本身并没有实现Hash相关的库,当需要在C语言编程中需要使用hash操作时,可以使用开源的UtHash。
UtHash不是库,只是编写的头文件,可以将uthash.h包含在源码中进行使用。例如:
#include "uthash.h"
这样就可以直接使用uthash提供的相关Hash操作。
uthash支持如下的Hash操作:
1)添加/替换
2)查找
3)删除
4)统计
5)遍历
6)排序
二、开始使用uthash
当包含了uthash.h头文件后,就可以使用uthash的类型和操作了
1、声明一个需要Hash的数据
当一个数据需要进行Hash操作时,需要在该数据中包含hash handle,标识该数据可以hash操作,例如
struct my_struct {
int myKey;
char Info[10];
UT_hash_handle hh;
};
其中这里将myKey作为Hash的key值,
UT_hash_handle hh作为hash的操作句柄,记住这里的变量名是要要求的
1)变量名为hh,是指可以直接使用基于整数、指针、字符串进行Hash的句柄,也就是说整数、指针、字符串对应的hash函数已内部集成,在使用uthash提供的宏操作时,不需要再体现hash函数,对应着简化uthash宏。
2)其它变量名,是指需要使用用户自定义的hash函数,在对应的uthash宏中,需要其它相关的参数来携带更多的用户信息进行hash操作。
这里我们仅以基本的整数为例介绍,使用的都是简化uthash宏。
2、声明一个uthash初始空指针
struct my_struct *users = NULL;
这个指针对于uthash宏操作都需要是可见的,并且指针值会被修改,通常为全局变量。
3、uthash相关的操作
3.1)添加操作
HASH_ADD_INT(users,myKey,s),这里使用简化宏操作
这里的三个参数需要再说明下,第一个参数为2中定义的全局的指针,第二个参数是数据结构中 用作key的变量名,这里记住是变量名字而非数据。
第三个参数为需要添加的hash数据结构的指针。例如:
void add_user(int id,char *info)
{
struct my_struct *s;
s = (struct my_struct *)malloc(sizeof(my_struct));
s->myKey = id;
strcpy(s->info, info);
HASH_ADD_INT(users, myKey, s);
}
由于对于Hash添加操作,当出现相同的key值数据时,会出现Hash碰撞问题,所以在添加可以检查是否已存在key相同的数据。
3.2)查找操作
HASH_FIND_INT(users, &key, s)
这里的第一个参数也是全局的hash指针,第二个参数是本次key的地址,第三个参数是返回的数据地址
如果找到了已存在的hash数据,则s返回非空;否则,s返回为空。
3.3)删除操作
HASH_DEL(users, s)
这里的第一个参数也是全局的hash指针,第二个函数是本次要删除hash数据地址
这里的删除只是从hash表中删除该数据,即该数据不在关联到hash表中,但s实际的数据空间,需要用户管理释放。
3.4)遍历(迭代)操作
HASH_ITER(hh, users, current_user, tmp)
第一个参数为hash句柄hh,第二个参数为全局hash表指针,第三、四为本地hash指针
其中本次迭代操作为current_user,tmp为迭代内部使用的临时hash表指针,用于记录本次迭代的下一个hash表指针
所以即使在本次迭代操作中将current_user释放,也不会影响继续迭代,所以该迭代是删除安全的迭代。
3.5)清除hash操作
HASH_CLEAR(hh, users)
第一个参数为hash句柄hh,第一个参数为全局hash表指针。
这个操作会将hash表整个清除,但不会释放每个hash数据的内存,这里需要用户自行维护处理。
执行后,users变为NULL
3.6)统计操作
HASH_COUNT(users)
第一个参数为全局hash表指针,返回目前hash表中的hash数据个数。
3.7)排序操作
HASH_SORT(users,comparisonFunc)
第一个参数是全局hash表指针,第二个函数是一个比较函数指针。排序将按该函数的值进行排序。
比较函数需要返回小于0,等于0,大于0三种结果。
经过排序后,全局hash表指针可能会被刷新。
4、一个例子
#include <stdio.h> /* gets */
#include <stdlib.h> /* atoi, malloc */
#include <string.h> /* strcpy */
#include "uthash.h"
struct my_struct {
int id; /* key */
char name[10];
UT_hash_handle hh; /* makes this structure hashable */
};
struct my_struct *users = NULL;
void add_user(int user_id, char *name) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */
if (s == NULL) {
s = (struct my_struct *)malloc(sizeof *s);
s->id = user_id;
HASH_ADD_INT(users, id, s); /* id: name of key field */
}
strcpy(s->name, name);
}
struct my_struct *find_user(int user_id) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s); /* s: output pointer */
return s;
}
void delete_user(struct my_struct *user) {
HASH_DEL(users, user); /* user: pointer to deletee */
free(user);
}
void delete_all() {
struct my_struct *current_user, *tmp;
HASH_ITER(hh, users, current_user, tmp) {
HASH_DEL(users, current_user); /* delete it (users advances to next) */
free(current_user); /* free it */
}
}
void print_users() {
struct my_struct *s;
for (s = users; s != NULL; s = (struct my_struct*)(s->hh.next)) {
printf("user id %d: name %s\n", s->id, s->name);
}
}
int name_sort(struct my_struct *a, struct my_struct *b) {
return strcmp(a->name, b->name);
}
int id_sort(struct my_struct *a, struct my_struct *b) {
return (a->id - b->id);
}
void sort_by_name() {
HASH_SORT(users, name_sort);
}
void sort_by_id() {
HASH_SORT(users, id_sort);
}
int main(int argc, char *argv[]) {
char in[10];
int id = 1, running = 1;
struct my_struct *s;
unsigned num_users;
while (running) {
printf(" 1. add user\n");
printf(" 2. add/rename user by id\n");
printf(" 3. find user\n");
printf(" 4. delete user\n");
printf(" 5. delete all users\n");
printf(" 6. sort items by name\n");
printf(" 7. sort items by id\n");
printf(" 8. print users\n");
printf(" 9. count users\n");
printf("10. quit\n");
gets(in);
switch(atoi(in)) {
case 1:
printf("name?\n");
add_user(id++, gets(in));
break;
case 2:
printf("id?\n");
gets(in); id = atoi(in);
printf("name?\n");
add_user(id, gets(in));
break;
case 3:
printf("id?\n");
s = find_user(atoi(gets(in)));
printf("user: %s\n", s ? s->name : "unknown");
break;
case 4:
printf("id?\n");
s = find_user(atoi(gets(in)));
if (s) delete_user(s);
else printf("id unknown\n");
break;
case 5:
delete_all();
break;
case 6:
sort_by_name();
break;
case 7:
sort_by_id();
break;
case 8:
print_users();
break;
case 9:
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);
break;
case 10:
running = 0;
break;
}
}
delete_all(); /* free any structures */
return 0;
}