在C语言编程时使用uthash

一、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;
}

 

 

 

 

 


版权声明:本文为yuanyeshizhe原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。