登录后台

页面导航

uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构作为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不同。

使用uthash代码时只需要包含头文件"uthash.h"即可。由于该代码采用宏的方式实现,所有的实现代码都在uthash.h文件中,因此只需要在自己的代码中包含该头文件即可。

支持以下的hash表操作:

  1. add/replace
  2. find
  3. delete
  4. count
  5. iterate
  6. sort

添加、查找和删除的时间复杂度都是常量级别。uthash力求简约高效,它是用宏的形式实现的,所以在调用时会自动内嵌。

uthash不是一个c语言的lib库,而是一个单独的头文件uthash.h。所以仅需将该头文件拷贝到自己的项目中即可使用。

在hash操作中,都是按照“键-值“对的方式进行插、查等操作,在uthash中,其基本数据结构就是一个包含“键-值“对的结构体,另外,该结构体中还包含一个uthash内部使用的hash处理句柄,如下代码所示:

#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};

其中:

  • id是键(key);支持int、string、指针、结构体
  • name是值,即自己要保存的数据域,这里可以根据自己的需要让它变成结构体指针或者其他类型都可以;
  • hh是内部使用的hash处理句柄,在使用过程中,只需要在结构体中定义一个UT_hash_handle类型的变量即可,不需要为该句柄变量赋值,但必须在该结构体中定义该变量
  • Uthash所实现的hash表中可以提供类似于双向链表的操作,可以通过结构体成员hh的 hh.prev和hh.next获取当前节点的上一个节点或者下一个节点。

在 uthash 中,将结构添加到哈希表中时,它永远不会被移动或复制到其他位置。 这意味着,无论在程序运行期间是否从hash表中添加或删除结构体,你都可以保留安全指向结构体的其他数据结构。

hash操作

// 声明hash表
struct my_struct *users = NULL;    /* important! initialize to NULL */

// 在hash表中寻找键值对
HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */

// 添加键值对
void add_user(int ikey, char *value_buf) {  
    struct my_struct *s;  
    HASH_FIND_INT(g_users, &ikey, s);  /* 插入前先查看key值是否已经在hash表g_users里面了 */  
    if (s==NULL) {  
      s = (struct my_struct*)malloc(sizeof(struct my_struct));  
      s->ikey = ikey;  
      HASH_ADD_INT(g_users, ikey, s );  /* 这里必须明确告诉插入函数,自己定义的hash结构体中键变量的名字 */  
    }  
    strcpy(s-> value, value_buf);  
}  

// 删除键值对
void delete_user(int ikey) {  
    struct my_struct *s = NULL;  
    HASH_FIND_INT(g_users, &ikey, s);  
    if (s!=NULL) {  
      HASH_DEL(g_users, s);   
      free(s);              
    }  
}  

// 清空hash表
// HASH_CLEAR(hh, g_users);函数,它不释放各节点的内存,因此尽量不要使用它,
void delete_all() {  
  struct my_struct *current_user, *tmp;  
  HASH_ITER(hh, users, current_user, tmp) {  
    HASH_DEL(g_users,current_user);    
        free(current_user);              
  }  
}  

// 统计hash表中的已存在的元素数量
num_users = HASH_COUNT(g_users);

// 遍历hash表(hash.hh.next , hash.hh.prev)
for (s = users; s != NULL; s = s->hh.next) {
        printf("user id %d: name %s\n", s->id, s->name);
}

// 遍历hash表(HASH_ITER)
struct my_struct *s, *tmp;
HASH_ITER(hh, users, s, tmp) {
    printf("user id %d: name %s\n", s->id, s->name);
    /* ... it is safe to delete and free s here */
}

// 排序
HASH_SORT(users, name_sort);
//第二个参数是指向比较函数的指针。 它必须接受两个指针参数(要比较的项),
//如果第一个项目排序在第二个项目之前、相等或之后,则必须返回一个小于零、零或大于零的 int。 
// (这与标准 C 库中的 strcmp 或 qsort 使用的约定相同)。
int by_name(const struct my_struct *a, const struct my_struct *b) {
    return strcmp(a->name, b->name);
}

int by_id(const struct my_struct *a, const struct my_struct *b) {
    return (a->id - b->id);
}

void sort_by_name() {
    HASH_SORT(users, by_name);
}

void sort_by_id() {
    HASH_SORT(users, by_id);
}
博主已关闭本页面的评论功能